10
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ FWIW, as the author of the cited answer, I agree with what fgrieu wrote below. The implication I made in my answer that any preimage attack on MD5 would automatically break HMAC-MD5 was careless and unsupported, and I have edited my answer to remove it. $\endgroup$ – Ilmari Karonen Mar 20 '17 at 13:22
6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.