SHA1 Collisions can be Found in 2^63 Operations
August 19, 2005
Overview: This note summarizes a recent breakthrough in the cryptanalysis of the SHA-1 hash algorithm. On Tuesday Evening(8/16/2005), it was announced that it is possible to find a collision in SHA-1 in 2^63 operations. This research result is due to Professor Xiaoyun Wang of Tsinghua University in Beijing, together with Professors Andrew Yao and Frances Yao. It extends the work of Wang, Yin, and Yu [WYY], which demonstrated that a collision could be found in 2^69 operations. The new result was announced by Adi Shamir at the Crypto 2005 conference in Santa Barbara, on behalf of Professor Wang, who was unable to secure a visa for the conference.
Technical Overview: Such attacks first pinpoint a favorable message differential D, such that two messages m and m XOR D have a higher than expected probability of having the same hash value. Depending on the differential, some number of probabilistic conditions must be met. The work of [WYY] employed a technique called "message modification" to eliminate some of these conditions which appeared in the early stages of the hash compression function. This reduction allowed them to achieve an overall complexity of 2^69 for the collision attack.
The recent work announced this week is an enhancement of the same approach. A modified differential was employed so that more of the conditions were located at the beginning of the hash computation. This way, Wang could apply an improvement to the message modification techniques to eliminate more of the conditions, reducing the overall complexity to an estimated 2^63 operations.
Status of the Attack: Although it is clear that the approach is viable, the improved message modification calculations have not been confirmed by experts. As with the work of [WYY], this work estimates the difficulty of an attack, rather than producing an actual collision. No actual collision for SHA-1 has been exhibited to date. However 2^63 is within reach of a distributed computing effort. It will not be surprising if further improvements to SHA-1 collision attacks appear in the coming months.
Practical Ramifications: This research has ramifications for applications which require collision resistant hash functions: for example digital signatures (see [R] and [K] for a discussion of the ramifications of earlier collision attacks on SHA-1). Practically, this cryptanalytic result suggests the acceleration of upgrading software which uses hash functions. Three viable approaches for improving the security of applications are:
- Replace the hash function with a stronger one. The most commonly suggested approach is to simply employ SHA-256, possibly truncating the output to 160 bits.
- Alter the protocol so that it no longer requires that the hash function be collision resistant. A recent proposal suggests adding randomness to hash functions [HK]. To implement this, the application must have a good source of randomness and must alter the protocol.
- Implement simple message pre-processing to convert plaintext messages into a form which renders all existing collision attacks inapplicable. This approach can be accomplished with minimal code change, and is described in [SY]. This practical alternative is appealing for applications which want to extend the secure life of SHA-1. Slides describing this approach are available at [SY2]
[HK] S. Halevi, and H. Krawczyk, Strengthening Digital Signatures via Randomized Hashing, Internet Draft, 2005.
[K] B. Kaliski, RSA Security - How These Discoveries Affect RSA Security's Products: Frequently Asked Questions, RSA Laboratories Technical Report, March 17, 2005.
[R] J. Randall, Hash Function Update Due to Potential Weakness Found in SHA-1, RSA Laboratories Technical Report, March 11, 2005.
[SY] Szydlo M. and Yin Y., Collision-Resistant usage of MD5 and SHA-1 via Message Preprocessing. IACR Eprint archive 2005 #248.
[SY2] Szydlo M. and Yin Y. Collision Resistant Usage of SHA-1 via Message Pre-processing, Powerpoint Slides.
[W] X. Wang, A. Yao, and F. Yao, New Collision search for SHA-1, Rump Session Crypto'05.
[WYY] X. Wang, Y.L. Yin, and H. Yu. Finding Collisions in the Full SHA-1, Advances in Cryptology -- Crypto'05.