# What is the run-time on finding collisions with MACs,…?

I've recently read the claim that finding collisions on block cipher may be not a difficult task, if an attacker can control the key and the message.

So, given a pseudo-random function $f:\{0,1\}^m \times \{0,1\}^{l_0} \times ... \times \{0,1\}^{l_k}\rightarrow \{0,1\}^n$, what is the expected run-time for finding a collision?

$f$ may be any MAC or anything similar.

For $m>n$ and without any other input the answer is trivially $\mathcal O(\sqrt{n})$ (standard hash function), but do the additional inputs change anything?

For blockciphers the case usually is trivial, as second pre-image security is easily broken. Given a pair $(M_1,K_1)$ one can compute $(D_{K_2}(E_{K_1}(M_1)),K_2)$ to trivially obtain a collision.

• If you know nothing about $f$ then there isn't much you can do. However, for known block ciphers this can be done. For example, with DES this can be done very easily. – Yehuda Lindell Jul 15 '15 at 22:02
• @YehudaLindell, is "$f$ is a PRF" the information you were looking for? I've also removed the part asking for block ciphers and added the break for them. – SEJPM Jul 16 '15 at 16:45
• For the case of a PRF, if you want to consider it as a black box, then I don't know of anything that you can do that is better than for a random function (I think). In practice there may be better things that can be done (depending on the construction). However, for HMAC as a PRF, I don't think that you can do better, or you could probably use this to find a collision in the hash function in time less than $O(\sqrt{n})$. (Worth proving to be sure, but should be easy.) – Yehuda Lindell Jul 19 '15 at 8:55

What is the run-time on finding collisions with MACs...

Well, the definition of a MAC is of the form "if you don't know the key, then it is infeasible to ...". This definition does not assert anything if you do know the key (or are able to select it); hence it does not provide any nontrivial lower bound.

In particular, with common MACs (e.g. CMAC, Carter-Wegman MACs), it is trivial to generate second preimages. For CMAC, we can actually generate preimages; we just select an arbitrary prefix (of a multiple of the block length), and compute what the last block needs to be to generate the target image. For Carter-Wegman MACs, we can generate second preimages by looking into the almost universal hash function, and trivially generating a second message that produces the same hash for the given key (at least, for every au hash I've heard of).

On the other hand, we come to HMAC. For HMAC, we can generate collisions between two different keys in two ways:

• If HMAC is given a short key (no longer than the hash block size), it xor's it into the IPAD/OPAD patterns. That implies if we append a zero byte to the key, say, $K_2 = K_1 || 00$, then the result of the xor's will be the same, and so $HMAC(K_1, M) = HMAC(K_2, M)$ for any $M$.

• By taking advantage that, if the key is longer than the hash block size, HMAC first hashes the key, and then uses that hash as the key. Hence, we can select two different keys, $K_1$ (which is long), and $K_2 = Hash(K_1)$, then we have $HMAC(K_1, M) = HMAC(K_2, M)$ for any message $M$.

If we disallow those approaches (and perhaps say that the keys must be the same length), then it is easy to see that finding a collision with HMAC is no easier than finding a collision in the underlying hash function (as a collision in the HMAC will imply a collision in either the upper or lower hashes of the HMAC, or in the hash that preprocesses long keys).

So, bottom line: the definition of MAC does not ensure making finding collisions (assuming the attacker knows the key) difficult; we can find MACs (such as HMAC with a fixed length key) where it is believed to be difficult; we can also find MACs where it is easy.