5

SHA-1 is broken because collisions can be found in substantially fewer hash operations than naive brute-force would suggest. HMAC-SHA1 is fine, however, because for HMAC “collisions aren’t important.”

Why aren’t collisions important for HMACs?

  • 3
    Possible duplicate of What does it mean that Hmac is secure?, Finding hash collision. – Steffen Ullrich Jun 16 '18 at 3:36
  • I'm not sure if the first is a duplicate. It looks like those are discussing the various security properties behind HMAC and how they work, not specifically explaining why collisions are not important for the underlying hash function with the exception of a single link to a paper which discusses it (and more importantly, not explaining the OP's misconception that collisions are not important for HMAC itself). The second may be a duplicate, though. – forest Jun 19 '18 at 5:58
7

From RFC 2104 § 6 describing the security requirements for an HMAC:

The security of the message authentication mechanism presented here depends on cryptographic properties of the hash function H: the resistance to collision finding (limited to the case where the initial value is secret and random, and where the output of the function is not explicitly available to the attacker), and the message authentication property of the compression function of H when applied to single blocks (in HMAC these blocks are partially unknown to an attacker as they contain the result of the inner H computation and, in particular, cannot be fully chosen by the attacker).

So it's not that collisions are not important for an HMAC. It's that a collision attack against a hash function does not affect that hash function when used in an HMAC construction. In particular, an HMAC demands much weaker security guarantees from the hash function than many other applications it may have. It only requires weak collision resistance from the underlying hash.

HMAC is defined as HMACK(m) = H((K ⊕ opad) || H((K ⊕ ipad) || m)) where opad and ipad are constants and H is an at least weakly collision-resistant hash. The key K is not known to an attacker. To trigger a collision with an HMAC, an attacker would need to do one of the following:

  1. Find a collision that is valid for a number of keys.

  2. Perform a successful key recovery attack.

Both of these are extremely unlikely to be possible for even the worst of cryptographic hashes, assuming the authentication tag is sufficiently large (typically at least 128 bits).

  • that's not entirely true. If your MAC output (the authentication tag) is of size <= 64 bits, you can try to find collisions on the authentication tag directly in ~ 2^32 queries. If your authentication tag is even smaller, the attack can become really practical. I think another part of the answer should be that in a lot of scenarios, such collisions wouldn't be exploitable, that is not to say that no such scenarios exist and hence this is probably why we mostly use 128-bit authentication tags nowadays. – David 天宇 Wong Apr 18 '19 at 15:50
  • 1
    @David天宇Wong Thanks. I edited the answer to mention the size of the tag. – forest Apr 19 '19 at 0:23
  • I'm way late to this, but there's a proof that HMAC security is not dependent on collision resistance, see cseweb.ucsd.edu/~mihir/papers/hmac-new.html – Swashbuckler Jan 21 at 19:35

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.