How does a preimage attack on MD5 break the security of HMAC-MD5?

Question

It was mentioned in an answer to a different question that

it's possible that, any day now, someone might figure out a way to turn those into a preimage attack, which would compromise the security of HMAC-MD5.

Reminder: $\text{HMAC-MD5}_K(x) = \text{MD5}(K \oplus opad \mathbin\| \text{MD5}(K \oplus ipad \mathbin\| x))$

Given that the input to the MD5 calls in HMAC includes the keys I don't immediately see how this turns into an attack. Could somebody clarify?

Answer 1

I fail to see how an hypothetical black box doing a (first) preimage attack on MD5 could be turned into an attack on HMAC-MD5, even if that box was able to effortlessly find the admissible combinations of prescribed unknown bits in an otherwise known message, given the hash; for example, if that box returned the (likely: very few, like less than 3) possible first 128 bits of message, given rest of message and hash.

And I'm at least convinced that a key-recovery attack on HMAC-MD5 requires more than a few preimage attacks on either MD5 or its round function.

Updated rationale: a successful attack on HMAC-MD5 can't be made by guessing a key $K$ of $k$ bits using a preimage attack on either of the two MD5 composing HMAC, taken in isolation.

• The output of the outer MD5 (the one with opad) is known, but one not knowing $K$ is facing the situation where the first $k$ bits of the hashed message are unknown, as well as the 128 bits produced by the other MD5 (that involves the unknown $K$ thru at least two rounds, thus is essentially random). A preimage attack on the outer MD5 is thus expected to return about $2^k$ solutions (each yielding a combination of $K$ on $k$ bits, and the result of the inner hash on 128 bits). We have to weed out which is the right $K$, which requires about $2^{k-1}$ tests involving the inner MD5 and the $K$ tested, to check if that matches the last 128 bits of the preimage. We have hardly reduced the effort compared to a brute force attack. The alternate strategy of computing the full HMAC-MD5 for each $K$ suggested by the preimage black box is no better, under the reasonable assumption that these $K$ are random-like, thus have moderate overlap.
• The output of the inner MD5 is not known, thus a defining hypothesis of a preimage attack is not met.

If we break HMAC-MD5 into individual rounds, we similarly conclude that a preimage attack on any round taken in isolation can't break HMAC, because the attack is no better than brute force, or/and because the round's output is unknown.

---

However, if a preimage attack on MD5 (or/and its round function) was possible, the security argument we have on HMAC-MD5 would vanish, and the prudent thing would be to act as if HMAC-MD5 was broken.