SHA-1 is broken
Summary
On 15 February 2005 Bruce Schneier reported on the blog Schneier on Security that a team around Xiaoyun Wang could find collisions for the full SHA-1 hash function with about 2 to the power of 69 operations, instead of the 2 to the power of 80 its length promised. This meant SHA-1 was no longer secure for digital signatures, even if the computation was still too expensive for a practical attack. Still, twelve years passed until the first actually computed collision.
What Schneier reported
The team of Xiaoyun Wang, Yiqun Lisa Yin and Hongbo Yu, mostly from Shandong University, had circulated a paper: collisions in the full SHA-1 with 2 to the power of 69 operations, in SHA-0 with 2 to the power of 39 and in a SHA-1 variant reduced to 58 rounds with 2 to the power of 33. Schneier called it a major cryptanalytic result that practically finished SHA-1 for signatures.
Schneier’s caveat mattered: applications such as HMAC, where collisions play no role, were not affected. The same team had presented the first practical collisions for MD5 half a year earlier.
Ideas
- A theoretical break is enough to abandon an algorithm for signatures.
- Not every use of a hash function depends on collision resistance.
- Attacks only get better, never worse.
- Retiring a standard takes longer than breaking it.
Insights
- Twelve years passed between Schneier’s warning in 2005 and the first computed collision, SHAttered, in February 2017, during which SHA-1 continued to run in many places, right up to certificates and Git.
- The lesson from MD5 and SHA-1 is the same: whoever only migrates after a practical collision migrates too late.
Facts
- Collisions in the full SHA-1 with about 2 to the power of 69 instead of 2 to the power of 80 operations.
- Collisions in SHA-0 with 2 to the power of 39 operations.
- The first actually computed SHA-1 collision, SHAttered, was published in February 2017.
References
Remarks
- Schneier wrote the post before the paper was public and stressed not yet being able to verify the results.
Recommendations
- Remove SHA-1 from signatures, certificates and new protocols; use SHA-256 or SHA-3.
- With Git, keep an eye on the transition to SHA-256 repositories.
Links to the original source and the Web Archive open in a new tab.