10
$\begingroup$

MD5 collisions have been out for some time. In spite of this, HMAC-MD5 is still secure for authenticating data1. This illustrates a strength of the HMAC construction, it does not require that the hash function be (weakly) collision resistant.

Recently, Dan Kaminsky posted a simple method for finding HMAC-MD5 collisions. The steps of the attack are:

Given a hash function with a collision and a key either known or controlled by an attacker, it’s trivially possible to generate a HMAC collision. The slightly less quick and dirty steps are:

  1. Start with a file at least 64 bytes long
  2. Generate a collision that can append to that file.
  3. XOR the first 64 bytes of your file with 0x36’s. Make that your HMAC key.
  4. Concatenate the rest of your file with your colliding blocks. Make those your HMAC messages.
  5. HMAC(key, msg1+anything) will equal HMAC(key, msg2+anything)

HMAC has been suggested2 as a way to do cryptographic commitments.

Is HMAC-MD5 (or more in general, HMAC with a non-collision-resistant hash function) still a secure way to do commitments?

This is important because, for example, Python's HMAC library uses MD5 by default.

Bonus Question: Are there any other common uses of HMAC and are they still secure for HMAC-MD5?

1. Though not recommended for new applications.
2. If anyone knows of a more authoritative reference for using HMAC for commitment, please edit it in.

$\endgroup$
  • $\begingroup$ HMAC might be secure even in case of collisions of the underlying hash. But OTOH a collision resistant hash function is no guarantee that using it with HMAC will be secure. I don't know if the security requirements HMAC has for the underlying hash are well understood, but it clearly is very different requirements from collision resistance. $\endgroup$ – kasperd May 12 '15 at 22:59
11
$\begingroup$

No, message commitment by disclosing its HMAC-MD5 with a key later revealed is no longer any secure, because of the ease with which MD5 collisions can now be found. There's however no compelling evidence that's insecure for messages constrained to belong in a small arbitrary set that no adversary can choose or influence. Still, whatever the constraints on the messages, the narrow 128-bit output width of HMAC-MD5 allows an attack with a relatively modest (and clearly feasible) $2^{65}$ evaluations of HMAC-MD5.


HMAC builds a PRF from a hash function $H$ with Merkle-Damgård structure, message block width $w$ and output width $h$, with $w\ge h$, as $$\operatorname{HMAC}_H(K,m)=\begin{cases} H\Big((K\oplus\text{opad})\mathbin\|H\big((K\oplus\text{ipad})\mathbin\|m\big)\Big) &\text{if $|K|\le w$}\\ \operatorname{HMAC}_H\big(H(K),m\big) &\text{if $|K|>w$} \end{cases}$$ where $\text{opad}$ (resp. $\text{ipad}$) is the 0x5c5c5c… (resp. 0x363636…) pattern with width $w$, and $\oplus$ is bitwise exclusive-OR with the shortest operand right-padded using zero bits.

If the compression function used to build $H$ has suitable properties, then for random unknown $K$ with $|K|\ge h$, the function $m\mapsto \operatorname{HMAC}_H(K,m)$ is indistinguishable from random with effort less than about $2^h$ evaluations of $H$. We have no compelling evidence that this does not hold for $H=\operatorname{MD5}$ (for which $h=128$, $w=512$). For more details see Mihir Bellare, New Proofs for NMAC and HMAC: Security without Collision Resistance, in Journal of Cryptology, 2015 (originally in proceedings of Crypto 2006).

When $H$ is MD5, or any $H$ that is not collision-resistant, the attack in the question renders insecure a commitment protocol where Alice

  • secretly chooses $m$ and $K$
  • computes and publishes $\operatorname{HMAC}_H(K,m)$ as a commitment of $m$
  • performs some action dependent on $m$ (like: offer a bet about the first bit of $m$)
  • later reveals $m$
  • reveals $K$, allowing a verifier to compute $\operatorname{HMAC}_H(K,m)$ on the $m$ Alice alleges, and compare against Alice's commitment.

Notice however that even with an ideal $H$, there's an attack with effort about $2^{h/2}$ evaluations of $H$, where Alice finds $m$ and $m'$ with $H\big((K\oplus\text{ipad})\mathbin\|m\big)=H\big((K\oplus\text{ipad})\mathbin\|m'\big)$; thus the mere output size of HMAC-MD5 limits its security level to a modest $2^{64}$ evaluations of MD5, in this protocol where $m$ is unconstrained.

On the other hand, I see no attack (much better than brute force on $K$) on the use of HMAC-MD5 (or HMAC with a non-collision-resistant $H$) in the variant of this protocol where Alice is constrained to choose $m$ in a small arbitrary set that no adversary can choose or influence, like $\{\text{“stone”},\text{“paper”},\text{“scissors”}\}$, as considered in the suggestion referenced in the question. Alice has so little choice on the messages that she must be clever in her choice of $K$, rather than $m$, in order to cause a collision. My intuition is that because $K$ enters twice in the computation of $\operatorname{HMAC}_H(K,m)$, with at least one execution of the compression function in-between (for heavily constrained $m$), finding a theoretical shortcut would be extremely hard, well beyond what the current cryptanalysis status of MD5 allows.

$\endgroup$
  • 1
    $\begingroup$ I updated the answer I referenced that had $hmac(m,k)$ to be $hmac(k,m)$ $\endgroup$ – mikeazo May 12 '15 at 17:14
  • 1
    $\begingroup$ I also see no attack on the use of HMACMD5 for Naor's commitment scheme, via G(k) = HMAC(k,100) || HMAC(k,010) || HMAC(k,001), as long as $k$ is significantly less than 192 bits long. $\;$ $\endgroup$ – user991 May 26 '15 at 4:13
  • $\begingroup$ @Ricky Demer: agreed, though I fail to see exactly where 192 comes from (unless that's the the 256-bit security level with some safety margin), or why there would be an actual weakness before 513 bits (where the scheme fails abruptly due to the second case of HMAC and our ability to find 1-block collisions on the hash of the K input) $\endgroup$ – fgrieu May 26 '15 at 5:41
  • 1
    $\begingroup$ If $\: 1 < L \:$ and there are at most $2^{\hspace{.02 in}L}$ permitted keys (in particular, if the key [must have length less than L] or [must have length exactly L]), then the probability of a random setup string being non-binding is less then $1\hspace{-0.02 in}\big/\hspace{-0.05 in}\left(\hspace{-0.02 in}2^{\hspace{.02 in}385-(2\cdot L)}\hspace{-0.05 in}\right)$. $\;\;\;$ That guarantee becomes meaningless slightly above $\: L = 192 \;$. $\;\;\;\;\;\;\;\;$ $\endgroup$ – user991 May 26 '15 at 5:57
1
$\begingroup$

There is absolutely no reason to use HMAC-MD5 in a new product. Don't.

HMAC-MD5 security can still work in many roles, but should not be regarded as "secure" unless you can do extensive analysis as to EXACTLY how it's used. In particular, it is "secure" for document signing only if you are sure that the signer is NOT motivated to break security.

What Kaminsky showed was that an attacker with knowledge of the key can extend the ability to generate collisions in MD5 to generate collisions in HMAC-MD5.

But the "attacker with knowledge of the key" model is a difficult security proposition anyway, and every effort is made in all protocols to prevent it in most cases.

Unfortunately it is exactly the security model involved in code signing in an open-source environment. If the attacker is one of the people signing code, they can take the innocuous code that someone's going to review and some attack code that's going to give them root access whenever the typeahead buffer is full, and twiddle the comments in both files to generate a collision. Then they can check in the innocuous code, and later substitute the attack code without changing the checksum.

$\endgroup$
  • 2
    $\begingroup$ Code signing isn't a very common application of a MAC. MACs are used for message integrity in a symmetric environment (i.e. whoever is verifying the code also has the secret key). Code signing is done with digital signatures, which are unrelated to MACs. $\endgroup$ – cpast May 26 '15 at 6:36
  • $\begingroup$ The more I think about this, the more I'm convinced that it's not at all a vulnerability in this context. Remember, collisions involve knowing the key. If the attacker knows the key, they can produce their own HMACs for whatever the heck they want. In that context, an attacker who produces a collision is just wasting their time trying to crawl through an air duct when the front door was left wide open -- they could simply produce their own HMAC of the malicious code and distribute that. $\endgroup$ – cpast May 26 '15 at 7:38
  • $\begingroup$ The reason you don't worry if the signer is motivated to break security isn't that you trust the signer so much, it's that the signer has a much easier way to pull off the attack (and, again, MACs aren't signatures and are totally unsuited for verifying integrity to the general public; anyone who can verify a MAC can forge said MAC, so they're useless for code signing unless every user of your code should also be able to produce their own code). $\endgroup$ – cpast May 26 '15 at 7:41
  • 2
    $\begingroup$ In addition, most MACs (e.g. CMAC, Carter-Wegman MACs) make it easy to create collisions (and even second preimages) if you know the key. HMAC (based on a collsion-resistant hash) is one of the few that doesn't make it easy. Kaminsky just showed that HMAC-MD5 doesn't have a property that most MACs also don't have. $\endgroup$ – poncho May 26 '15 at 13:33

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.