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?
2
-
3Possible duplicate of What does it mean that Hmac is secure?, Finding hash collision.– Steffen UllrichCommented Jun 16, 2018 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.– forestCommented Jun 19, 2018 at 5:58
Add a comment
|
1 Answer
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:
Find a collision that is valid for a number of keys.
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. Commented Apr 18, 2019 at 15:50
-
1@David天宇Wong Thanks. I edited the answer to mention the size of the tag.– forestCommented Apr 19, 2019 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 Commented Jan 21, 2020 at 19:35
-
@Swashbuckler That's not entirely true. It just has weaker requirements from the collision resistance. There's an attack against HMAC-MD4, for example.– forestCommented Mar 21, 2020 at 23:44