4
$\begingroup$

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?

$\endgroup$
11
  • $\begingroup$ Your scheme does not have semantic security - same messages have the same MAC. $\endgroup$
    – orlp
    Oct 17, 2013 at 15:41
  • $\begingroup$ @nightcracker: Which messages produce the same MAC (with non-negligible probability)? The provided example only finds intermediate values for doing so. $\endgroup$
    – B-Con
    Oct 18, 2013 at 19:39
  • $\begingroup$ @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. $\endgroup$
    – B-Con
    Oct 18, 2013 at 19:43
  • $\begingroup$ @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. $\endgroup$
    – orlp
    Oct 18, 2013 at 19:52
  • $\begingroup$ @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.) $\endgroup$
    – B-Con
    Oct 18, 2013 at 20:37

2 Answers 2

8
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ the relevant paragraph from the hmac paper: "In this work we have initiated the first rigorous treatment of the subject and, in particular, present the first constructions whose security can be formally analyzed, without resorting to unrealistic assumptions such as the “ideality” of the underlying hash functions." $\endgroup$ Sep 26, 2016 at 22:17
  • $\begingroup$ @David天宇Wong What if the mac-construction used an additional outer hash? Such as, $H(E(H(m))$ with the same ECB-mode encryption and SHA256 hash function... $\endgroup$
    – ManRow
    Sep 21, 2021 at 18:04
  • $\begingroup$ Or, alternatively, what if the mac-construction simply reversed the order, becoming $H(E(m))$ instead? (with likewise same ECB mode and SHA-256...) $\endgroup$
    – ManRow
    Sep 21, 2021 at 18:11
  • $\begingroup$ @ManRow, the comments here probably aren't the place to ask that question. Instead, please use the 'Ask Question' button in the upper-right, and provide full context, motivation, and show what you've done to try to answer the question on your own. $\endgroup$
    – D.W.
    Sep 21, 2021 at 20:03
  • $\begingroup$ @D.W. Sure, I've created crypto.stackexchange.com/questions/95193/… for the question in my second comment . Looking over fgrieu's approach in that question, however, it doesn't initially look like there would be a weakness for the $H(E(H(m)))$ mac-construction for a strong-enough hash function (although, there could still be an attack I have not considered!) $\endgroup$
    – ManRow
    Sep 24, 2021 at 11:14
1
$\begingroup$

In the CBC-MAC scheme, your attack is included as well. However, it also states, that CBC-MAC unlike encryption in CBC mode, does not use an IV (due to that attack), but is initialized with 0 (although any predefined constant would work).

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.