39
$\begingroup$

This Q & A https://security.stackexchange.com/questions/33123/hotp-with-as-hmac-hashing-algoritme-a-hash-from-the-sha-2-family

says that the security of HMAC-SHA1 does not depend on resistance to collisions? Are they are saying specifically with respect to HOTP or for HMAC-SHA1 for any use?

If HMAC-SHA1 is used for verifying the integrity of a document and you can find a collision, you can make changes in the document, right?

https://www.rfc-editor.org/rfc/rfc2104#section-6

Even the RFC says that resistance to collisions is relevant

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

What am I missing here?

$\endgroup$
4
  • $\begingroup$ There seems to be a confusion in the question: HMAC-SHA1 is not used for signing a document (at least, not usually; and assuming it was, the standard assumption for HMAC that its key input is secret can't hold since the signature verification procedure is public). I find that answer quite fine. $\endgroup$
    – fgrieu
    Commented Jun 25, 2015 at 9:52
  • $\begingroup$ @fgrieu - I think I made a mistake in terminology - when I wrote signing, I should have actually written generating a message authentication digest to protect integrity. In case of collisions, you can change the message and preserve the same MAC, so it is a problem, right? $\endgroup$
    – user93353
    Commented Jun 25, 2015 at 9:59
  • $\begingroup$ Should we close this as a duplicate of Is HMAC-MD5 considered secure for authenticating encrypted data?? While this question is about SHA1, not MD5, the answer is nearly the same. $\endgroup$ Commented Jun 25, 2015 at 10:32
  • $\begingroup$ I'm pretty sure if I have a pre-image attack against SHA-1 this explodes. $\endgroup$
    – Joshua
    Commented Mar 10, 2017 at 21:19

2 Answers 2

39
$\begingroup$

In the first section of this answer I'll assume that through better hardware or/and algorithmic improvements, it has become routinely feasible to exhibit a collision for SHA-1 by a method similar to that of Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu's attack, or Marc Stevens's attack. This has been achieved publicly in early 2017, and had been clearly feasible (the effort represents mere hours of the hashing effort spent on bitcoin mining; but the hardware used for that can't be re-purposed for the attack on SHA-1).

Contrary to what is considered in the question, that would not allow an attacker not kowing the HMAC-SHA-1 key to make an undetected change in a document; that's including if the attacker is able to prepare the document s/he's willing to later alter.

One explanation is that the collision attacks on SHA-1 we are considering require knowledge of the state of the SHA-1 chaining variable, and the attacker of HMAC not knowing the key is deprived from that knowledge by the key entering on both extremities of the iteration of rounds in which the message stands in HMAC. A much deeper break of SHA-1's round function would be needed to break HMAC. Not coincidentally, M. Bellare's New Proofs for NMAC and HMAC: Security without Collision-Resistance shows that security of HMAC holds assuming only weaker properties on its round function than needed for collision resistance of the corresponding hash.

What would be possible is for an attacker knowing the HMAC key to prepare a document that s/he willing to later alter, that can be altered without changing the MAC. But since the attacker is holding the HMAC key, that's not considered a break of HMAC.


A comment asks when should SHA-1 not be used?

Original advise, 2015: It is advisable to quickly phase out SHA-1 in applications requiring collision-resistance (as an image: quickly walk away, as you exit a building which fire alarm rings when there's no smoke). That includes hashing for integrity check or digital signature of documents prepared by others even in part (which is, most documents). If continuing to use SHA-1 has strong operational benefits, it can safely be made an exception by inserting something unpredictable by adversaries before any portion of the message that an adversary can influence. For example, by enforcing an unpredictable certificate serial number at time of request of a certificate, a certification authority could still safely issue certificates using SHA-1 for their internal signature.

As explained in the first section of this answer, as long as the key of HMAC-SHA-1 is assumed secret, there is no indication that HMAC-SHA-1 is insecure because it uses SHA-1. If the key is assumed public, or its leak is considered an operational possibility where it is still wanted collision-resistance for HMAC including for message prepared after disclosure of the key, then the precautions discussed in the previous paragraph apply.


Update, 2022: As the saying attributed to the NSA by Bruce Schneier goes: Attacks only get better; they never get worse. The current state of the art finds a new collision in SHA-1 at cost comparable to $2^{61.2}$ hashes (comparing to $2^{69}$ for the first theoretical attack and $2^{63}$ for the first practical attack). More importantly in practice, a chosen-prefix collision (one with colliding files starting differently and arbitrarily) has become possible, with cost comparable to $2^{63.4}$ hashes, which is entirely practical. Such chosen-prefix collision attack (resp. variations) make it difficult (resp. essentially impossible) for even an expert to detect a planned-in-advance substitution of a document signed with SHA-1, or integrity-protected by HMAC-SHA-1 using a key known to the perpetrator. Still, every piece of advise given in this answer remains valid as far as we know.

$\endgroup$
4
  • $\begingroup$ So when should SHA1 not be used? i.e. discovery of the issue in SHA1 precludes it from use where? $\endgroup$
    – user93353
    Commented Jun 25, 2015 at 10:42
  • 2
    $\begingroup$ It's generally advised to move away ("walk", not "run") from SHA-1. That said, the specific construct of HMAC-SHA1 is still considered safe to use (assuming a secret key) due to the security proof for HMAC which does not rely on collision resistance of the underlying PRF. When in doubt, move to SHA-2. $\endgroup$ Commented Jun 25, 2015 at 16:37
  • $\begingroup$ @StephenTouset - yeah I got that. However, is there any usage of SHA-1 from which you should run away rather than move away or walk away. $\endgroup$
    – user93353
    Commented Jun 25, 2015 at 19:23
  • $\begingroup$ No, otherwise that would be the advice. SHA-1's collision resistance is only broken in a theoretical sense right now. No known collisions have yet been found, although the current best attack is just on the edge of feasibility. $\endgroup$ Commented Jun 25, 2015 at 19:50
19
$\begingroup$

When people say HMAC-MD5 or HMAC-SHA1 are still secure, they mean that they're still secure as PRF and MAC.

The key assumption here is that the key is unknown to the attacker.

$$\mathrm{HMAC} = \mathrm{hash}(k_2 | \mathrm{hash}(k_1 | m)) $$

  • Potential attack 1: Find a universal collision, that's valid for many keys:

    Using HMAC the message doesn't get hashed directly, but it has $k_1$ as prefix. This means that the attacker doesn't know the internal state of the hash when the message starts. Finding a message that collides for most choices is $k_1$ is extremely hard1.

  • Potential attack 2: Recover the key

    For this to succeed the hash function needs much bigger breaks than merely collisions. It's similar to a first pre-image attack, a property that's still going strong for both MD5 and SHA1.

On the other hand, if you used a key known to the attacker and the attacker has the ability to find collisions in the underlying hash (for arbitrary IVs), these turn into collisions of HMAC. So if you need security in an unkeyed scenario, use a collision resistant hash, like SHA2 and consider not using HMAC at all.


1 I suspects it's not possible (for realistic message sizes) even for computationally unbounded attackers, but proving that is difficult.

$\endgroup$
8
  • $\begingroup$ So when should SHA1 not be used? i.e. discovery of the issue in SHA1 precludes it from use where? $\endgroup$
    – user93353
    Commented Jun 25, 2015 at 10:41
  • $\begingroup$ @user93353 Like I said, the security of HMAC-SHA1 depends on the unknown key. If there is no key or it is known to the attacker, the collisions in SHA1 become a threat. But SHA1 should rarely, if ever, be used in new designs, since there are better alternatives available. $\endgroup$ Commented Jun 25, 2015 at 10:47
  • $\begingroup$ If the key is known to the attacker, then even SHA2 will be a problem, right? $\endgroup$
    – user93353
    Commented Jun 25, 2015 at 10:53
  • $\begingroup$ @user93353 Depends on what you want to achieve. Of course no unkeyed hash is a MAC. $\endgroup$ Commented Jun 25, 2015 at 11:03
  • $\begingroup$ @CodesInChaos - you say that HMAC-SHA1 is a problem only if the key is known. But if the key is known, that will be a problem for any HMAC-hash operation, right? $\endgroup$
    – user93353
    Commented Jun 25, 2015 at 11:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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