# What is the definition of “security beyond the birthday paradox”?

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?

-
More fishy search terms might be beyond birthday bound –  fgrieu Oct 13 '13 at 9:16
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. –  DrLecter Oct 13 '13 at 16:31
@DrLecter you should write that up as an answer. –  mikeazo Oct 29 '13 at 14:01
Ok, added, but not much longer due to lack of time. Feel free to add more content :) –  DrLecter Oct 29 '13 at 17:10

"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)$

-

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.

-
+1, short, sweet and to the point –  mikeazo Oct 29 '13 at 17:36
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. –  Dmitry Khovratovich Oct 29 '13 at 19:35