Cryptographic Hash Functions

What are cryptographic hash functions?

A cryptographic hash function provides a secure means to "identify" a given message. Security in this context means "Collision resistance", and "Preimage resistance". Both of these concepts will be discussed shortly.

Cryptographic hash functions should not be confused with regular (non-cryptographic) hash functions, which are often deployed for a similar function but are not designed nor intended to be secure. But, for the sake of brevity, I will make reference to "hash functions" in the rest of this article with the expectation that you understand we are talking specifically about cryptographic hash functions in this context.

What does it mean to "identify" a message?

Securely identifying content/files/messages is a very common application of cryptography. Typical applications include:

1. Detecting message modification.
2. Detecting specific messages/files etc in a system (e.g. known malicious content)
3. Identifying files which are identical, or different (e.g. in search systems)

The basic idea is that you take a message, M, and you feed it into a black box called a "hashing function". The output of this function is a fixed length (typically 256 or 512 bits) hash value (or digest), H that identifies that message.

The same message, fed into the same hashing function, will produce the same output - allowing identification. Any different message fed into the hashing function, even if only one single bit of the message is changed, will produce a completely different output - allowing change detection.

Typical hash functions in use today include:

1. MD5
2. SHA family (SHA-1, SHA-2, SHA-3)
3. BLAKE2

Note that MD5 was broken in 2004 and is not recommended for use in any new project.

Let's Play

Let's have a play with some hash functions so that you can see what they do.

Below is a hash generator component. It takes an input and generates the hash for it in real time. You can select from a number of different hashing functions, and you can select text input or hex.

Note that even a very minor change in the input - even if it was only a single bit of the message that changed - produces a completely different output. This is called the "avalanche" effect and is an important component of hash security. Hashes should be unpredictable, and ideally indistiguishable from a random message.

HASH GENERATOR

Hash Function Security

The purpose of hash functions is to protect data integrity. We want to ensure that data received has not been corrupted in transit or deliberately modified by an attacker.

With this in mind, a secure hash function is one which guarantees that two different messages/files/data will produce a different hash. This enables the hash to be used as a true "identifier" of the communicated information.

Preimage Resistance

A preimage is an input that produces a given hash output.

If you have a hash function, F and a hash value, H, then a preimage of H is any message M such that:

For example, if:

then "hello" is a preimage of the hash value aaf4c61ddcc5e8a2dabede0f3b482cd9aea9434d.

Preimage resistance describes how hard it is to go backwards from a hash value to any valid message M that hashes to it. In other words, I give you a hash value H and you try to find messages M that produce it. For a secure hash function it should be (practically) impossible.

For this reason, a secure hash function can be referred to as a "one way function". You can go from M to H but you can't go back from H to M.

Second Preimage Resistance

Second preimage resistance of a secure hash function says that given a message M1, it should be (practically) impossible for anyone to find a second message M2 such that:

In other words, given M1 you compute its hash value and it should not be possible for you to find another (different) message M2 which computes the same hash value.

Collision Resistance

If a hash function is secure it must have collision resistance and this means it should be (practically) impossible for someone to find any two messages M1 and M2 such that they produce the same hash.

This sounds similar to the previous examples but the difference is that in previous examples the attacker was first given either a message or a hash. In this example, the attacker is given neither and in fact is free to choose both messages. Collision resistance of a hash function is therefore weaker than Preimage resistance.

Here is how the effort breaks down (considering an ideal, secure hash function of n-bits):

Collisions, of course, are inevitable for any significant size of message, M.

For example, if you have a message of size 1kB (1024 bits), and you are using a hashing algorithm that produces hashes of fixed 256 bits size, then it follows that you have many more possible messages than available hash values. So hash values (pigeon holes) will naturally hold more than one message (pigeon).

The point is that for a secure hash function it should be computationally infeasible to find collisions in practice.

Keyed Hashes

With regular secure hash functions as just discussed, anyone can create a hash of any message using any agreed algorithm. This can be acceptable for many cases, but sometimes it can create a security concern.

Where a hash of a message is exchanged along with the message itself, there is the possibility of a Man in the Middle attack. In this scenario, a third party inserts himself between the communications of two parties and can modify any messages going back and forth between them. Since he can also calculate valid hashes for any message he modifies, secure hashes alone will not help under these conditions.

This is where "Keyed Hashes" come into play. Here a secret key is combined with the hash function such that only parties who are in posession of that key can create or validate the hash values. If the man in the middle does not know the secret key, he cannot modify any messages during transit because he cannot calculate a valid hash and therefore the modification would be detected at the other end.

This is where the idea of "keyed hashes" comes in. It involves combining a hashing algorithm with a secret key, such that only people with knowledge of the secret key can create a valid hash of a message.

You might think it would be perfectly acceptable to append the secret key to every message before it is hashed, such that the hash involves the secret key and this will be all we need. But in practice it's a little bit more complicated than that, and simply appending the key to create the hash will expose you to some security vulnerabilities.

I won't dwell on all the different iterations of keyed hashes there are and their vulnerabilities here. I will simply skip forwards to talk about the "HMAC", which is one accepted way of created keyed hashes.

The HMAC

The HMAC uses existing hashing algorithms but combines them with a secret key in a careful, structured way before hashing.

The construction is:

Where:

1. F is the hash function
2. K is the secret key
3. M is the message
4. ipad, opad are fixed constants
5. ⊕ is XOR and || is concatenation

The result of this HMAC function is a hash where only those with the secret key could have computed it.

Let's Play

We can see the HMAC operation in action, below. Choose a "secret" key and a hashing algorithm, then enter your message and you will get a keyed hash as an output.

HMAC GENERATOR

MAC using Block Ciphers

The algorithms discussed so far rely on hash algorithms to create Message Authentication Codes. Such as HMAC.

But it is also possible to create MACs using block ciphers. There are a few examples of such algorithms:

1. CBC-MAC
2. CMAC
3. GMAC

Note that CBC-MAC turned out to be quite easy to break, and CMAC was developed as a "fix" for the shortcomings of CBC-MAC. CMAC is what we shall cover next.

CMAC

Cipher-based MAC (CMAC) is an algorithm for creating Message Authentication Codes based on block ciphers.

Most typically, CMAC is used with AES. But it can be used with other block ciphers as well.

Conceptually, CMAC works as follows:

1. Derive two subkeys K1 and K2 from the supplied secret key. These subkeys are subsequently used during the process later on.
2. Split the supplied message into blocks. The blocks will be the same size of the block cipher. For example with AES, the block size will be 128 bits.
3. Run CBC (Cipher Block Chaining) over the blocks. Each block is XORed with the previous chaining value, and encrypted with the block-cipher and passed on to the next stage.
4. For the final stage, K1 or K2 (depending on some internal circumstances in the algorithm) is XORed into the final message block prior to encryption. and the output of this final stage is the computed MAC.

Let's Play

Below is an interactive component that will allow you to create and play with MACs based on block ciphers.

CMAC GENERATOR