How secure is SHA1? What are the chances of a real exploit?

Question

I read that, in February 2017, a SHA1 collision was calculated for the first time. This, and earlier theoretical proof, means that SHA1 is officially cryptographicaly insecure. But, when using SHA1 in a protocol (SAML assertions in my case), both the protocol dictates a certain message format and the information in the message has to be meaningful to create a real collision exploit. Under these circumstances, how feasible is a real exploit?

Not being hindered by any real knowledge in the field I suspect this will 'never' happen. Or am I missing something?

Answer 1

Actually SHA-1 has been "officially insecure" for a longer time, since an attack method was published in 2011. The 2017 collisions was just the first known case of actually running the attack. But everybody was already quite convinced that the attack worked, and, indeed, the 2017 collision was produced with the expected computational cost.

The important point is that we are talking here about collisions. A collision is when you find two distinct messages that are hashed to the same value.

In many protocols, collisions don't matter; what is important is the resistance to second preimages. A second preimage is like a collision, except that the attacker does not get to choose one of the messages; the attacker is challenged to find a colliding pair of messages, the first one being fixed. Finding second preimages is a lot harder than finding collisions. For a "perfect" hash function with a 160-bit output (like SHA-1), a collision can be found with effort 2⁸⁰, while finding a second preimage requires effort 2¹⁶⁰ (i.e. a million billion billion times more). Moreover, while a structural weakness is known in SHA-1, that allows lowering the cost of the collision attack from 2⁸⁰ to 2⁶³, making it merely "very expensive", no such weakness is known that would help for second preimages.

So right now, SHA-1 seems still very very robust for second preimages, and any protocol that uses SHA-1 and relies on second preimage resistance can keep on doing so safely for the time being.

The tricky issue is to determine if a given protocol relies on second preimages, or if collisions can impact it. SAML is a complicated beast. It seems that it uses SHA-1 in conjunction with digital signatures, and this relies on second preimages, except in situations where attackers can get to choose part of the data that is being signed, in which case they might want to exercise a collision between "innocent-looking data" and malicious data. In the case of the published SHA-1 collision, this is done with PDF files because the PDF format is flexible enough to turn an difference in only a few bits into an arbitrary visual effect.

The cautious course of action would be to migrate to SHA-256. There is no absolute urgency to do so; but if ten years from now you still use SHA-1, then this means that your software management is terrible (and this is much more likely to be an issue than SHA-1 weaknesses).

Answer 2

With hash functions there is a wide gulf between "perfectly ok" and "totally broken".

When this answer was first written the sha1 collision attack went like.

1. The attacker picks a common chosen prefix.
2. The attacker generates the actual collision blocks.
3. The attacker picks a common chosen suffix.

The attacker now has two files with the same sha1 hash. These files only differ in the collision blocks.

This is concerning but it's difficult to work up into a practical exploit. Both files must contain both the "good" and the "evil" data and some form of logic must be employed to chose which is used based on the content of the collision blocks.

---

The next step up in attacks is a "distinct chosen prefix" collision attack. With a distinct chosen prefix collision attack the attacker can.

1. Choose two seperate prefixes, a "good" one and an "evil" one.
2. Generate the collision blocks.
3. Choose a common suffix

This is far more dangerous. The attacker needs to be able to control only a small section of the "good" data and predict some of the rest. The ammount of "collision garbage" can be small and may be able to be hidden inside something like a comment field or a RSA key or similar.

A distinct chosen prefix collision attack was found for md5 about 3 years after the first collision attack on md5 was found. It was later exploited against a certification authority to produce a rouge CA certificate. In addition to the distinct chosen prefix collision attack this exploit also relied on a certification authority that did not randomise serial numbers.

To the best of my knowledge no distinct chosen prefix attack on sha1 has been publicly announced but it is at least plausible that one will be found soon and/or that one has already been found but it's discovery is being kept secret.

A sha1 distinct chosen prefix collision attack was announced in 2020 https://eprint.iacr.org/2020/014.pdf

---

The ultimate attack on a hash function is a second preimage attack. Such attack would likely break virtually every cryptosystem based on the hash but preimage attacks are computationally much harder than collision attacks. To the best of my knowlage even MD5 has no known computationally feasible preimage attack (there is a theoretical attack which is marginally easier than brute force).