1
$\begingroup$

Às the title already indicates, I would like to know: Are MACs vulnerable to birthday attacks?

$\endgroup$
  • $\begingroup$ In a situation where you can get arbitrary messages signed (MACed) you can try to produce two colliding messages with the reduced probability of a birthday attack. So yes they are. But since you normally cannot do that without having the secret key it's most of the time not practically relevant. $\endgroup$ – eckes Jul 12 '17 at 10:28
  • $\begingroup$ In the principle (MAC is a compression function) there's always a probability of collision. The task is make the probability negligible. Wikipedia (Cryptographic_hash_function) claims "It requires a hash value at least twice as long as that required for preimage-resistance; otherwise collisions may be found by a birthday attack ( Introduction to Modern Cryptography)" $\endgroup$ – gusto2 Jul 12 '17 at 11:04
  • $\begingroup$ Please edit your question to describe what research you have done. See, sharing research efforts helps everyone. Tell us what research you did, what you found, and why it didn’t meet your needs. That shows users you took time trying to help yourself, saves us from reiterating obvious answers, and helps you get more relevant, on-point answers. At worst might help you frame “a better question”; at best it might even answer it. $\endgroup$ – e-sushi Jul 12 '17 at 21:26
  • $\begingroup$ Related: Is HMAC prone to birthday attacks? $\endgroup$ – e-sushi Jul 12 '17 at 21:31
5
$\begingroup$

Are Message Authentication Codes (MAC) are vulnerable to birthday attacks...

Like most things in life, it depends.

Certainly, if you have an $n$-bit MAC, then after about $O(2^{n/2})$ MAC'ed messages, there's a decent probability that you see two different messages $M_1, M_2$ for which $\text{MAC}_k( M_1 ) = \text{MAC}_k( M_2 )$

However, that begs the question: is this observation actually an attack? After all, the security property of a MAC is "it's hard to generate the MAC of a message you haven't seen"; in the above attack scenario, you've seen the MAC's for both $M_1$ and $M_2$, and so neither would qualify under the "you haven't seen" part.

The pertinent question is "does having two message evaluating to the same MAC actually allow us to deduce the MAC of a message we haven't seen". For most MACs, it doesn't; there's no obvious way to do this for HMAC, and for nonce-based MACs, the fact that each message was MAC'ed with a different nonce would appear to block any such obvious approach.

However, there is a common MAC where it would appear to be an issue: CMAC. That is, if we can find two messages $M_1, M_2$ (both a multiple of 16 bytes in length; it is easy to extend this observation to non-multiples of 16 bytes) with $\text{CMAC}_k(M_1) = \text{CMAC}_k(M_2)$, then we know that, for any string $N$, we have $\text{CMAC}_k(M_1 | N) = \text{CMAC}_k(M_2 | N)$. Hence, if we find such a collision, we can ask for the MAC of $M_1 | N$, and then we immediately know the MAC for $M_2 | N$; this counts as a valid attack.

However, CMAC is the only MAC I can think of with this potential vulnerability.

$\endgroup$
  • 1
    $\begingroup$ Are you thinking of CBC-MAC, aka ISO/IEC 9797-1 MAC Algorithm 1, when used for variable-length messages despite a cautionary note in the standard? CMAC seems to never have been vulnerable to the attack described. Wikipedia's link to CMAC now redirects to OMAC; I guess the old name created too much confusion. $\endgroup$ – fgrieu Jul 13 '17 at 6:26
  • 1
    $\begingroup$ @fgrieu: no, CMAC. With CMAC, in the case that the message is a multiple of 16 bytes long, the algorithm is: compute the CBC MAC on the entire message except for the last 16 bytes; then xor in the last block and a secret value, and then do a final AES op. If we have two messages blocking (the output of the final AES is the same), then the input to the final AES must have been the same, and hence the CBC MAC of the initial message xor with the final block must be the same. $\endgroup$ – poncho Jul 13 '17 at 12:45
  • $\begingroup$ @poncho: That sounds like a special case of a generic state collision attack, applicable to any finite-state iterated construction $F$ that processes variable-length inputs incrementally. If I can find any $M_1 ≠ M_2$ such that absorbing these as prefixes yields the same intermediate state, then for all $N$, $F(M_1 \| N) = F(M_2 \| N)$. The CMAC-specific bit is that you can infer a state collision from any colliding pair of block-size-multiple messages, and not just e.g. pairs with the same length (because the construction does not use message length). $\endgroup$ – Luis Casillas Jul 14 '17 at 2:04
  • 1
    $\begingroup$ @LuisCasillas: good point, However, CMAC has the additional disadvantage of having a small internal state, hence you need fewer known message, tag pairs before being likely to find a collision; e.g. you need only $2^{49}$ pairs to have a 1-in-a-$2^{32}$ probability... $\endgroup$ – poncho Jul 14 '17 at 13:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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