I'm reading a paper about MACs and I would like to be sure about the meaning of a security beyond the birthday paradox.

Is there a definition?

  • 2
    $\begingroup$ More fishy search terms might be beyond birthday bound $\endgroup$
    – fgrieu
    Oct 13, 2013 at 9:16
  • 3
    $\begingroup$ The birthday bound for a MAC says that when you have $n$ bit tags an adversary will succeed with a forgery after $q=O(2^{n/2})$ tag queries (which is true for many standard MAC constructions). If you can prove that a MAC construction provides security beyond this birthday barrier, say an adversary requires $q=O(2^{2n/3})$ tag queries, then you have security beyond the birthday paradox. $\endgroup$
    – DrLecter
    Oct 13, 2013 at 16:31
  • $\begingroup$ @DrLecter you should write that up as an answer. $\endgroup$
    – mikeazo
    Oct 29, 2013 at 14:01
  • $\begingroup$ Ok, added, but not much longer due to lack of time. Feel free to add more content :) $\endgroup$
    – DrLecter
    Oct 29, 2013 at 17:10

2 Answers 2


For a MAC algorithm considered to be good, the best way to attack a MAC should be by collision (a birthday attack)

This means, that for MACs with $n$ bit tags an adversary will suceed with a forgery after having issued $q=O(2^{n/2})$ tag queries.

In the literature this bound is called the birthday barrier.

Now, if you are able to come up with a MAC construction for which you can prove that an adversary will require more queries, say $q=O(2^{2n/3})$ or $q=O(2^{5n/6})$ as for instance shown here, as given by the birthday bound, your MAC provides security beyond the birthday paradox.

  • 2
    $\begingroup$ To add: the reason for the birthday bound is that many MACs are based on an iterative hash function. After $2^{n/2}$ trials one can find two messages $M_1,M_2$ whose MAC computations collide at some point. Then if we know $MAC(M_1||C)$ for any $C$ we also know $MAC(M_2||C)$ which is the same. This constitutes the forgery. $\endgroup$ Oct 29, 2013 at 19:35

"The birthday paradox" refers to an attack that relies on finding a collision (or possibly the lack of one) internal to the cryptographical primitive in question; "beyond the birthday paradox" refers to something which avoids such attacks.

It is most commonly used in relation to a block cipher mode; in the most common modes, finding a collision (which you can expect to do after $2^{n/2}$ encrypted blocks, assuming a block size of $n$ bits) implies some relation between plaintext blocks (which implies a leak of information). CTR also leaks information after $2^{n/2}$ blocks, but in a different way; here a collision is impossible, and so the information leak is that there are no two CTR output blocks that are exactly the same (and when you go beyond the birthday bound, you would expect one); this is also an information leak (albeit a far more subtle one). "Beyond the birthday paradox" refers to a block cipher mode where this does not happen; they are secure even if you protect significantly more than $2^{n/2}$ blocks.

When you reference a MAC, well, how a collision attack would apply depends on the internals of the MAC function. There is no generic way to use a collision in the output of a MAC to generate a forgery; there may be ways you can use a collision against a specific MAC.

Here are two MACs which are vulnerable to collision attacks:

  • CMAC; if you find two equal length messages $A, B$ with $CMAC(K, A) = CMAC(K, B)$, when we know that $CMAC(K, A | X) = CMAC(K, B | X)$; to violate the MAC properties, we can ask for $CMAC(K, A | X)$, and then claim that we know the value of $CMAC(K, B | X)$, even though we never asked the Oracle for that exact value.

  • HMAC (without truncation); if you find two messages $HMAC(K, M_1) = HMAC(K, M_2)$, then what is likely to happened (at least, with nontrivial probability) is that $Hash(K \oplus IPAD | M_1) = Hash(K \oplus IPAD | M_2)$, if that is the case, then you can construct an message extension $N$ with $HMAC(K, M_1 | N) = HMAC(K, M_2 | N)$.

On the other hand, there are MACs for which collision attacks do not help; one obvious example is $SHA3( K | M)$; it matters little if we find two messages $M_1, M_2$ with $SHA3( K | M_1) = SHA3( K | M_2)$; because SHA3 has such a huge internal state, we are unlikely to have found a collision in all 1500 internal bits, and so we cannot deduce that $SHA3( K | M_1 | X) = SHA3( K | M_2 | X)$


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.