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

Question

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.

Answer 1

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.