Cryptographic Hashes and Credentials Management

Five Essays on Cryptography (4/5)

Cryptography is one of the core disciplines that we use to protect digital information today. It is part of the larger area of Information Security which has become recently one of the most discussed topics across industries. This series of five articles is aimed at those who would like to have an overview of the domain of cryptography, a bit of its history, and a grasp on important concepts and recent developments.

All articles in this series

• 1 Cryptography is Interwoven in our Daily Life
• 2 A Tool for Information Warfare Becomes a Field of Science
• 3 Asymmetric and Symmetric Encryption
• 4 Cryptographic Hashes and Credentials Management
• 5 The Use of Cryptography in our Economy (to appear)

Special thanks to my friend Philipp Jovanovic (Twitter @Daeinar) for sharing his expert opinion on this series of articles.

Comments, Feedback: Laurent Balmelli (Twitter Laurent Balmelli)

What is a Hash Function?

Hash functions are one of the key building blocks of cryptography. There is a need for such functions in many settings, such as digital signatures, message authentication, blockchain, password storage and, as I have explained in the previous article, public key encryption. Therefore, hash functions are also used in the Hypertext Transfer Protocol Secure (HTTPS) used to secure web communications.

The functioning of a hash function is really simple in nature: it takes an input of any length (e.g., number of bits) and outputs a fixed-length value whose size depends on the function used, but typically 256 or 512 bits.

For example consider the following text: “Hello Medium”. Apply a hash function such as SHA-256 to this string (you can run this command in any Linux command line interface)

echo -n “Hello Medium” | sha256sum

and you’ll obtain the following value as output:

c231072511f96fd7ba9aa38b74cd380b82620e826dec6ee1eb994ef7836633d0

I have explained previously that encryption algorithms are aiming at guaranteeing confidentiality, i.e. that an unauthorized party cannot recover the information in plain text. In security a hash function is often used to guarantee the integrity of the data, i.e., that the data has not been modified. This is because, if the data such as the string that I used above has changed in any way, the computed hash value will be different and the hash function allows us to verify that unequivocally, provided that the hash function is free of collisions, as explained below.

For a hash function to be free of collision, no two different input should yield the same output. This is clearly a desirable property for guaranteeing integrity of the input value. The truth is that, since hash functions are producing a fixed-length output based on an input of any size, there will always be collisions (this is referred to as the Pigeonhole Principle). However the trick is that, it should be impossibly hard to find them due to the exponential number of possible outputs (2 to the power of 256 in the case of SHA-256, hence approximately 1 followed by 77 ‘0’ in base 10). This property is called collision resistance.

Another key aspect is that it is a one-way function, i.e. a hash function cannot be reversed, even with unlimited computing power. In other words, there is no way to recover the above input string, i.e., “Hello Medium”, from its computed hash value. The only way to check that this string indeed results in the above value when using the SHA-256 function is to compute it again and compare results. If the input string is unknown, this is equivalent to a brute-force search across all possible existing strings (of any length).

Furthermore, in the special case of a cryptographic hash function even a small variation in the input should lead to a large difference in the output. This is an additional security property. Without it, the result of the hash cannot be used as an oracle when attempting to recover the input using brute-force search. All the hash functions discussed in this article are considered to be cryptographic hashes (read more about all their properties here).

Following the example above, let’s try now to compute the value of the function SHA-256 on the string “Hello Mediul” instead of “Hello Medium”, then the result is

echo -n “Hello Mediul” | sha256sum

bebe3996ad6a6ff3ef64aecbfaebbfef57ae3758e7d9201b197f178db45d077a

The output clearly looks completely different than the one obtained with the first string, even though the difference between the two strings is actually exactly one bit of information. This is because both strings differ only in the last letter (‘l’ instead of ‘m’) and that the letter “m” in a computer is represented with the binary code 01101101, and the letter “l” is 01101100, when using the standard ASCII character set.

Note finally, hash functions are not only used in cryptography. They are also common in data structure management where hash tables are used for search or to prevent errors in data storage, for example using cyclic redundancy checks (CRCs). Theses hash functions are non-cryptographic hashes with desirable properties for their own fields of application.

As I mentioned at the beginning of this article, hash functions are used in many applications related to cryptography and I am exploring the most common ones below and in the next and last article in this series.

Using Hashes for Authentication

I have explained in the previous article in this series that digital signing can be implemented using an asymmetric encryption scheme such as RSA. In fact, such a protocol cannot be efficiently implemented without the use of a hash function. In turn, digital signatures are considered as the most common application of hash functions.

An application that computes a digital signature on the message of arbitrary length does so on a hash of the message rather than the message itself. Hence the hash function acts as a proxy to the message to be signed and computes what is often referred to as a digest of the message.

As I explained above, the value of the digest is sufficient to guarantee that not even a bit of the message can be modified without the computation resulting in a completely different hash value. Hence the digest guarantees the integrity of the message. Then the digest itself is signed on behalf of the message. In practice when using a asymmetric scheme, this is implemented by encrypting the digest with the private key of the person who signs the message.

The main reason for using a proxy of fixed-length (for example 256 bits) to a message of arbitrary length is efficiency. I discussed in the previous article of this series that asymmetric encryption suffers from computational ineffectiveness. In fact, most signature algorithms can only work on short inputs. Fortunately, it has been shown in theoretical cryptography that signing a digest is as secure signing the message itself.

The Failed Case of the MD5 Hash Function

Note that I mentioned before that, for hash functions to be secure, it should be computationally infeasible to find two inputs that produce the same output (i.e. free of collision). This statement implies that there are hash functions that might not be secure by producing collisions. An example of such a hash function is MD5. It belongs to a series of functions that were designed by Ronald Rivest at MIT, i.e. the “R” is RSA. Unfortunately, MD5 function collisions can be found easily with a computer.

This vulnerability in MD5 was unknown until 2012 and one of the first (acknowledged) cyber weapon deployed by a nation-state (by the US, with the cooperation of Israel) on the country of Iran exploited this flaw. In brief, a malware known as Flame, which was used for the cyber weapon Stuxnet, leveraged that flaw to perform a sophisticated attack against part of the Microsoft Windows Update system (read this Microsoft blog for more details). At the time Microsoft was using MD5 to sign (i.e., authenticate) files to update/patch user systems. As explained in the blog, the attackers were able to reproduce a valid signature for a malicious patch that was used to deliver a malware through a seemingly genuine update.

Read more about the story of Stuxnet in the excellent book “Countdown to Zero Day: Stuxnet and the Launch of the World’s First Digital Weapon” by Kim Zetter.

The study of vulnerabilities of hash functions is an ongoing research topic in mathematics and computer science. Vulnerabilities in these key building blocks of cryptography is particularly concerning, because it can expectedly have large repercussions. For example, websites use digital signing to authenticate with users (through the use of certificates) and these certificates are themselves authenticated by higher authorities. This framework is referred to as Public Key Infrastructure (PKI) and I discuss it in detail in the next article of this series. But let me give now a bit more information about certificates and PKI to finish our discussion about hash functions.

How Certificates are Used in PKI and the Relation to MD5

Let me first explain briefly how certificates are used and how they play a central role for the internet. Public key certificates (in the X.509 format, supporting the Secure Socket Layer/Transport Layer Security, SSL/TLS protocol) are used by websites to attest to their identity. For example, the Medium website has a SSL certificate to attest that it is indeed the website linked to the Medium Corporation. You can see this in the URL field of your browser, for example in Google Chrome, it will display that an HTTPS connection was made to the Medium site once the certificate’s signature was validated by the browser (see image below).

This certificate was issued, in this case by DigiCert Inc., after proper vetting of the Medium Corporation as a legitimate business entity.

The easiest way to understand the role of a website certificate is to equate it to a passport. For a passport to be valid, it has to be delivered by an official country. In the internet, the higher authority mentioned above (i.e. DigiCert Inc.) plays the role of the country. Hence if the signature of a valid authority can be faked, then there is no way to safely authenticate websites on the internet anymore. Hence the choice of the hash function for digital signatures is a critical one.

Up to recently (around 2008), MD5 was used to sign digital certificates (i.e., authenticate the “passports of the web”), then the following happened (from wikipedia): “On 30 December 2008, a group of researchers announced at the 25th Chaos Communication Congress how they had used MD5 collisions to create an intermediate certificate authority certificate that appeared to be legitimate when checked by its MD5 hash. The researchers used a cluster of Sony PlayStation 3 units (located at the EPFL in Lausanne, Switzerland) to change a normal SSL certificate issued by RapidSSL into a working CA certificate for that issuer, which could then be used to create other certificates that would appear to be legitimate and issued by RapidSSL.”

In other words, it became possible to create fake certificates… Today, the consensus across the industry is to use SHA-256 as the standard signature hash algorithm for SSL certificates. See the announce from Digicert here.

How to Store Passwords Securely (and Not)

To conclude this discussion, let’s look at how passwords can be safely stored.

Because hash functions cannot be reverted, they are often used to create a secure mechanism to store passwords in computer systems. The guarantee of security here is based on the same property discussed at the beginning of this article that, given a hash stored in place of a password, the only way to recover the password from a hash will be by trying all combinations of characters to identify the unique string resulting to that particular hash value.

However, computers have become so fast that brute-force search (i.e., trying all possible combinations) of a simple password is not a difficult task today. It is well known that to guarantee a minimal security, it is better to choose complex and long passwords. This, in turn, has made password managers an attractive alternative when you need many passwords and do not want to repeat them across systems. Note that I am discussing these aspects from a societal perspective in this other Medium article.

Since I mentioned that hashes are stored in place of passwords (in well implemented systems), let’s discuss how passwords are attacked and how to protect them.

First, when news break that user passwords have leaked from a website, then such a leak is likely in the form of a list of hashes corresponding to user passwords. However, If the leak resulted in a list of passwords in plain-text, then all bets are off. Instead, with user passwords stored as hashes, there is likely still a lot of work for attackers to do before being able to figure out any of the plain-text passwords. To do so, attackers will have to brute-force all the hashes that they obtained maliciously. If a password was long and complex enough, then it is likely that no amount of computer power (or time) will be sufficient to find it. If you want to try yourself at password-cracking, look at this great series of articles and tutorial on the on-line magazine Null-Byte.

Even then, well-implemented systems also take further security measures to protect passwords. Remember that a property of a hash function is that two applications of the same input will compute to the exact same output. Hence two users using the same password will have the same hash as a result. This can give valuable information to an attacker, hence all passwords are “salted” before hashing.

Salting a password is to add a small string of random characters such that two same passwords will hash to different values. This prevents attackers to use pre-computed hash values for more efficiency when brute-forcing (these pre-computed values are referred to rainbow tables). In addition, a hash function will likely be applied multiple times to the password rather than only once. This will increase the time necessary to brute-force password. This is because each attempt at brute-forcing the password needs multiple passes of the hash function, which slows down the attack and make it less and less practical.

Despite all these best-practices, there are still companies that store their passwords in plain text! For example, until recently when using a MasterCard online from Barclay Capital, a verification dialog asks for three of the letters in your password randomly. This type of verification is only possible if the password is stored in plain text! It was also reported on Twitter that customer service at SwissQuote, a Swiss banking group specializing in online financial and trading service, asks customers to authenticate by giving a few of the letters of their password. A customer complaining about this practice obtained the following answer from the SwissQuote representative (see Tweet below):

Note that FINMA is Switzerland’s independent financial-markets regulator.

This is all for this article! In the next and last article of this series, I will introduce a few applications of techniques in cryptography that are used to support and develop our economy. Your feedback on Twitter @laurentbalmelli is welcome.

Thanks again for following this series. Check my other articles about security, technology and societal aspects.