Beyond Secrecy: Data Integrity, Cryptographic Hashes, and HMAC

Beyond Secrecy: How We Guarantee Data Integrity in Symmetric Ciphers

We move now from confidentiality to the constraint of integrity. This might seem counterintuitive when talking about cryptography, but now we are not interested anymore in hiding the message to transmit, but just in guaranteeing that the content of the message can't be manipulated along the channel.
As we did for confidentiality, we need to model the attack framework that we assume is in place. In this case, we consider a bit-flipping attack (or active attack), in which the attacker can intercept and tamper with the data.
To understand the danger of this kind of attack, try to imagine a bank transaction: by simply changing some bits in the ciphertext, once decrypted, the message can contain a different amount of money with respect to what was originally sent.

Basic Idea: To provide integrity, we can append to the message a tag that the attacker is not able to forge, which can guarantee that the message has not been tampered with. This tag is also called Message Authentication Code (MAC) (and by the way, please note that the name is misleading: the Message Authentication Code provides integrity, not authenticity).
From a high level perspective, we can see this idea as a set of two functions, the first one used by the sender, and the second one by the receiver:

• $compute_{MAC}(string, key)=tag$

• $verify_{MAC}(string, tag, key)=\lbrace true|false\rbrace$

In practice, we can implement this concept using different approaches. CBC-MAC The idea behind a CBC-MAC basically consists in using as tag an encrypted version of the message. But since now, as we will see, the tag will not be decrypted by the receiver, we can use the block ciphers in a different way with respect to the CTR mode, in order to produce a shorter output string.
In particular, the block ciphers are connected in cascade in such a way that the input of each one is the output of the previous block XORed with the corresponding section of the message (the first section can be simply XORed with a 0).
In case the message has a fixed prefix, the tag has to be encrypted one more time for the technique to be secure.

At this point, we can describe the communication flow as follows:

• Alice, given the message $msg$ and the key $k$ , calculates the CBC-MAC tag and sends it to Bob together with $msg$ ;

• Bob, using the message received by Alice and the key $k$ , calculates the CBC-MAC from his side;

• Bob compares his CBC-MAC with the one sent by Alice. If they are the same, the message has not been tampered with.

This method works since any attempt from the attacker to forge the message would cause a change even in the CBC-MAC calculated by Bob. To forge the message, the attacker should also change the CBC-MAC accordingly, but he cannot do it without the key.

The problem with this technique is the efficiency: calculating the CBC-MAC tag every time a message is sent is expensive and slow. This is where things get interesting: enter the next method. Cryptographic Hash Functions

A Cryptographic Hash is a function $H:\Sigma^{\ast}\rightarrow \Sigma^{n}$ for which the following problems are computationally hard:

1. Resistance to first preimage attack: Given $d=H(s)$ , find $s$ (i.e., invert $H$ ).
   In the ideal case, the computation required is $T(n)=O(2^n)$ ;

2. Resistance to second preimage attack: Given $s$ and $d=H(s)$ , find $r\neq s$ such that $H(r)=d$ .
   In the ideal case, the computation required is $T(n)=O(2^n)$ ;

3. Resistance to collision: Find $r,s$ with $r\neq s$ such that $H(s)=H(r)$ .
   In the ideal case, the computation required is $T(n)=O(2^\frac{n}{2})$ .

The output of the function is called hash or digest.

Working with bits, in our case a cryptographic hash function can be more explicitly defined as $H:\lbrace 0,1\rbrace ^{\ast}\rightarrow \lbrace 0,1\rbrace ^{n}$ . So what it does is taking an arbitrary-length-input and convert it into a fixed-length-output. This means that the function is not injective: there will necessarily be multiple input being mapped into the same output. It's however not possible to compress the input indefinitely, as there always exists a minimum number of bits, called entropy, that can be used to represent a certain information. But not every function of this kind is a cryptographic hash function, as they must respect the three requirements. For example, a simple function that just takes the first $n$ bits of the input string is not resistant to both second preimage attack and collision.

The second preimage attack can be reduced to the first preimage attack, and this means that if $H$ does not satisfy the first property, it will necessarily not satisfy the second too. The opposite is, in general, not true. This also explains why, in the ideal case, the time complexity of the two attacks is the same. The ideal complexity required to find a collision is less because the computation can be speeded up by exploiting the math behind the probabilistic birthday paradox.

Worth noting: the first two properties are what, commonly speaking, distinguishes a cryptographic hash function from a simple hash function, which just tries to avoid conflicts.

As discussed talking about block ciphers, we cannot prove in theory that a function is a cryptographic hash function, since we cannot prove the exponential lower bound complexity of an algorithm. So, even in this case, these functions are the result of public contests.
Old cryptographic hash functions as SHA-1 and MD5 has proven to be broken. Nowadays, we can confidently use SHA-2 and SHA-3, that can produce digests of 256, 384 or 512 bits. SHA-3 has been produced because SHA-2 actually shares some mechanism with functions that have been proven to be broken, but both SHA-2 and SHA-3 are currently unbroken and widely standardized. Cryptographic hash functions are highly employed in computer security, for example to avoid storing passwords and other important data in clear text, or in digital forensics to obtain a "fingerprint" of the acquired disk. For our purposes, we need cryptographic hash functions to compute a MAC tag that is easy to build and verify.
Contrary to what we have done for the CBC-MAC, now Alice cannot simply use $h(msg)$ as MAC tag to send with the message $msg$ , since it would be completely useless. In fact, given that the hash is produced without using a key, the attacker can simply forge the message and change the tag accordingly.
So, given the key $k$ that Alice and Bob are using, the problem can be solved by using $h(msg+k)$ as a tag.
We can therefore provide a tag that can guarantee integrity, and that can be computed much more efficiently with respect to the CBC-MAC.

It's worth pointing out that this is just the general idea behind how cryptographic hash functions are used to ensure integrity. In reality, the mechanism is more complex and sophisticated, and goes by the name of HMAC.

The Authenticity Constraint: Why Symmetric Ciphers Are Not Enough

Before moving on to the next part, let's briefly consider the scenario where we want to provide authenticity. This means that the attacker is communicating with the receiver by pretending to be someone else. Differently from confidentiality and integrity, there is actually no ongoing attack to model here: we're just considering standard communication, with the only difference being that the receiver was expecting a message from another sender.

Unfortunately, a symmetric cipher cannot be used to provide authenticity, so we can't discuss this property. To break through, we need a fundamentally different idea, called asymmetric cryptography, that will be discussed in the next article.