4
$\begingroup$

I'm reading Ferguson, Schneier, and Kouno's Cryptography Engineering, and it has a section on MACs. It discusses different types of MACs, but it seems to claim that to acheive 128-bit level security, you need a 256-bit MAC due to the birthday attack.

Why is this the case? Why are collision attacks a concern in MACs? I think that to break a MAC, you need a preimage attack to guess the plaintext, or a second-preimage attack to forge messages. In these cases, the birthday attack is irrelevant since it only finds some random collision, which may not be relevant to the data stream being attacked.

What am I missing? It seems that in general 128-bit MACs are much more popular (GCM and CCM and all those fancy AEAD modes have 128-bit authentication tags); surely they can't have only 64 bits of security? Is Cryptography Engineering simply paranoid?

Improve this question
$\endgroup$
5
  • $\begingroup$ Because security for MACs is defined in a way that for an adversary it should not be possible to forge a MAC for an arbitrary message (for which he has not already obtained a tag) without having access to the secret key efficiently. The birthday attack will allow to produce such a forgery. If you want 128 bit security, by taking 256 bit MAC you rule that one out. $\endgroup$
    – DrLecter
    Commented Apr 12, 2014 at 15:20
  • $\begingroup$ @DrLecter : $\:$ How will the birthday attack "allow to produce such a forgery"? $\hspace{1.76 in}$ $\endgroup$
    – user991
    Commented Apr 12, 2014 at 15:31
  • $\begingroup$ @RickyDemer By a collision in the block cipher or compression function in any iterated-MAC construction. If this happens then you have two different prefixes which happen to collide somewhere. Then request another tag for a message with the same prefix but different suffix and exchange the prefix and you have a tag for a message not queried. $\endgroup$
    – DrLecter
    Commented Apr 12, 2014 at 15:44
  • $\begingroup$ I thought that would be about the chaining variable's length, rather than the MAC's length. $\hspace{.95 in}$ $\endgroup$
    – user991
    Commented Apr 12, 2014 at 15:56
  • $\begingroup$ @RickyDemer I was having constructions in mind that do not use truncation. Otherwise a MAC collision does not mean that there must not necessarily be an internal collision. $\endgroup$
    – DrLecter
    Commented Apr 12, 2014 at 16:03

1 Answer 1

Reset to default
7
$\begingroup$

The attack outlined by Drlecter is valid for any deterministic MACs (that is: with the MAC a function of message and key) with an iterated structure and an $n$-bit state. It relies on internal state collisions, expected to occur after about $2^{n/2}$ messages (the birthday bound), that can allow forgery once discovered. I'll illustrate this in the case of CBC-MAC with a 64-bit block cipher (e.g. 3DES) operating on fixed-size 3-block messages (24-byte) with 8-byte MAC (the full block cipher width).

The adversary asks for the MAC of $2^{33}$ messages with random first two blocks and the last block fixed. It is expected that a collision occurs, and the adversary then has $(M_0||M_1||M_2)$ and $(M'_0||M'_1||M_2)$ having the same MAC, with $M_0\ne M'_0$. So far, this is not a break. But notice that, with certainty, the collision has occurred after the second block, and continued after the third.

Now, for any last block $M'_2$, $(M_0||M_1||M'_2)$ and $(M'_0||M'_1||M'_2)$ collide with certainty. That allows the adversary to predict the MAC of one of these messages by querying for the MAC of the other, which is a break.

Thus a deterministic MAC with $n$ bit internal state (and output, but in itself truncating the output does not help much), after $q$ queries with the same key, has become unsafe with odds about $q^2/2^{n+1}$, for $1\ll q\ll2^{n/2}$. E.g. after $2^{60}$ queries, HMAC-SHA1 has odds $2^{-41}$ to be vulnerable.

Note: This attack (or any generic attack with similar result that I am aware of) does NOT in general apply to iterated MACs with an $n$-bit output. E.g. HMAC-MD5 or CBC-MAC-AES truncated to $64$-bit are not awfully vulnerable to this attack; after $2^{40}$ queries odds that the attack works are $2^{-49}$.

Improve this answer
$\endgroup$
9
  • 1
    $\begingroup$ you may want to add some short statement about iterated-MAC constructions at the beginning to fully answer the OP's question and to underpin why the birthday happens to be of interest. $\endgroup$
    – DrLecter
    Commented Apr 12, 2014 at 17:14
  • 3
    $\begingroup$ I would like to point out that this arguments doesn't work when you start talking about MACs with nonces; in that case, if you model the nonce as a part of the state, then the probability of an internal collision between two different messages may be 0, because the two messages will always have different nonces. $\endgroup$
    – poncho
    Commented Apr 12, 2014 at 18:25
  • 1
    $\begingroup$ Does this attack work for HMAC? I seem to recall that HMAC is secure even when the underlying hashing function is vulnerable to collision attacks much faster than birthday (i.e. MD5). $\endgroup$
    – ithisa
    Commented Apr 12, 2014 at 21:01
  • 2
    $\begingroup$ @user54609: Yes, this attack works against HMAC with a hash using a 128-bit state, and e.g. allows a forgery of HMAC-MD5 in about $2^{64}$ queries. It does not contradict the fact that HMAC-MD5 remains practically unbroken as far as we know, when MD5 is not secure against collision, as supported by that security argument. $\endgroup$
    – fgrieu ♦
    Commented Apr 12, 2014 at 21:17
  • 3
    $\begingroup$ @user54609: 64-bit security against brute force key search is kinda ridiculous nowadays, but a 64-bit MAC is still very strong when the only way to check if it is right or wrong is try on the actual target and that takes 1 microsecond (that figure is unrealistically low even for a direct 10 Gbps Ethernet link): odds of success are worse than 1/500000 per year of continuous attack. Also, it is easy to detect such attacks. $\endgroup$
    – fgrieu ♦
    Commented Apr 12, 2014 at 21:57

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.