# Does encrypting a hash of the message yield a secure MAC?

Is $mac = enc(hash(x))$ a secure MAC for hash = SHA256 and enc AES in CBC mode or ECB mode. Normally AES-CBC is malleable. But in this case I use a hash function for the one-way property.

For example, an attacker can change the iv vector:

In CBC c[0] = enc(m[0] ^ iv) an attacker chooses m'[0] and computes iv' by m[0] ^ iv = m'[0] ^ iv'. So, in this case I find 2 digests with the same MAC: hash(x) = m[0]||m[1] and hash(x') = m'[0]||m[1]. But I have found 2 digests, I can't find x' than hash(x') = m'[0]||m[1].

Is my MAC a secure MAC?

-
Your scheme does not have semantic security - same messages have the same MAC. –  nightcracker Oct 17 '13 at 15:41
@nightcracker: Which messages produce the same MAC (with non-negligible probability)? The provided example only finds intermediate values for doing so. –  B-Con Oct 18 '13 at 19:39
@pasgabriele: A PRF is a suitable MAC. Your question is probably best posed as: Is $PRP(hash(x))$ a PRF? Considering that a PRP is a PRF for hash-output sized inputs, this seams plausible at the outset. –  B-Con Oct 18 '13 at 19:43
@B-Con If you send a message $x_0$ and later, under the same key $x_1$ with $x_0 = x_1$ then an eavesdropper will know you sent the same message twice. –  nightcracker Oct 18 '13 at 19:52
@nightcracker: I'm not sure that's a necessary property of MACs. Avoiding leaking $x_0 = x_1$ is a requirement of confidentiality, not authentication. And in practice, the randomized ciphertext of both MTE and ETM will randomize the MAC. (And if you aren't encrypting, the point is moot.) –  B-Con Oct 18 '13 at 20:37

Yes, your MAC is secure. It's probably not quite as secure as you're expecting it to be, and it's not a construction I would recommend to anyone, but it should be secure.

Let's start with a simpler variant: $F_K(M) = E_K(H(M))$ where $H(\cdot)$ is a 128-bit collision-resistant hash (say, the first 128 bits of SHA1) and where $E_K(\cdot)$ is a 128-bit block cipher in ECB mode.

This is secure, under the assumption that $H$ is collision-resistant and $E$ is a secure block cipher, as can be shown using standard methods. Since $E$ is a secure block cipher, it is a secure PRP, which implies that it is a secure PRF (by the PRP/PRF switching lemma). Now it is known that applying a PRF to the hash of a message yields a secure MAC.

However, this still isn't a very good construction to use in practice. It offers weaker security than, say, SHA1-HMAC. Indeed, the authors of SHA1-HMAC explicitly considered something like this and rejected it; instead, they decided to design something new that would be better. Read the SHA1-HMAC research paper for details (it is very readable and a classic), but concisely, one problem with your scheme is that it is susceptible to offline attacks. Someone can try to find a collision in the hash function using an offline attack, and if they succeed, they immediately have broken the MAC. SHA1-HMAC does not have this limitation.

Now I know that's not quite what you proposed, but it's still instructive. What you proposed is a more complicated version of that scheme, but the complications don't really make it much better; they just it make it harder to analyze its security.

For instance, let's look at the scheme where encrypt the SHA256 hash using AES in ECB mode. Is this secure? Yes, it's secure, but less secure than you might expect. If an attacker has observed the MAC on $m$ known messages, then the attacker knows a set of $2m$ known plaintext/ciphertext pairs for AES; let $\mathcal{P}$ denote the set of known plaintexts for which the corresponding ciphertext is known to the attacker. Now suppose the attacker picks a new message $M$ (different from any of the $m$ known messages) and checks if he knows enough to predict its MAC. Let $X,Y$ denote the left and right half of SHA256($M$), respectively. If $X \in \mathcal{P}$ and $Y \in \mathcal{P}$, then the attacker can predict the MAC on the message $M$ with certainty, which is a break of the scheme. What's the probability that this happens? The probability is

$$\Pr[X \in \mathcal{P} \wedge Y \in \mathcal{P}] = \Pr[X \in \mathcal{P}] \times \Pr[Y \in \mathcal{P}] = |\mathcal{P}|^2/2^{256} = 4m^2/2^{256}.$$

So, if the attacker picks a message $M$ at random, he has a $m^2/2^{254}$ chance of being able to guess its MAC. If the attacker picks $2^{90}$ messages $M$ at random, there's roughly a $m^2/2^{154}$ chance that one of their MAC's can be predicted, which breaks the scheme. The attacker can do all of those calculations offline. So, if we consider an attacker who observes the MACs on $m$ known messages and who does $2^{90}$ offline calculations, that attacker can break your scheme with probability $m^2/2^{154}$. If $m=2^{77}$, this is a break with probability close to 1.

This attack is not a serious problem in practice. However, it demonstrates that the security level is less than one might expect from a 256-bit MAC. For this reason alone, I don't recommend your scheme. Instead, something like AES-CMAC or SHA256-HMAC is a better choice.

The good news is that I would expect that one can prove that this is the best an attacker can do (modelling SHA256 as a random oracle, and assuming the block cipher is secure). I haven't tried to write out and verify all the details, so take this with a grain of salt, but I fully expect that the proof should work out.

I haven't tried to think about what happens if you encrypt the SHA256 hash using AES in CBC mode. That seems a bit sketchy; I'm not sure why we'd introduce an extra IV and lengthen the MAC for no apparent reason. I don't think the construction is of any practical interest, given that better schemes exist, and that the better schemes are well-vetted and plenty good enough in practice.

-
For the security of your scheme: In a model with random oracle for the hash function would be secure: An attacker who can create a fake message with the same MAC can find preimages for the hash function by supplying $\mathrm{Enc}_{k}(\text{challenge hash})$ with a random $k$ and gets a different preimage of the hash.
However, your MAC will show if c[0] and c[1] are equal, since they encrypt to the same ciphertext in ECB. The probability of this happening is around $1/2^{128}$, so it's quite unlikely and will not help for preimage resistant hash functions, but some more thought about possible attacks is needed.