Infosec policy

DSD Information Security Policy Advice 1/2005

Hash Function Vulnerability

Purpose

DSD provides the following advice in relation to the widespread publicity about the recent results by academic cryptographic researchers regarding hash functions, specifically SHA-1 and MD5.

The Issue

Cryptographic hash functions that compute a fixed size message fingerprint from arbitrary sized messages are widely used for many purposes in cryptography, including digital signatures. Recent academic results describe attacks on a number of hashing algorithms including the DSD approved hashing algorithms SHA-1 and MD5. These results find collisions and near-collisions in a weakened version of SHA-1 and collisions in MD5 more efficiently than random searching.

Wang, Feng, Lai and Yu [2] found a collision within MD5 and a number of other hash functions.

At the time of these results the full round SHA-1 was not broken and no collisions were found in SHA-1.

In February 2005, Bruce Schneier [5] announced that the Chinese team of Wang, Yin and Yu have circulated a paper describing an attack on SHA-1. Their results include the claim that it would be possible to find collisions in SHA-1 by executing approximately 2⁶⁹ hash operations. This is a significant advance over the 2⁸⁰ hash operations which was the previous best attack.

Assessment

DSD does not believe the recent results represent a practical threat to users of SHA-1 or MD5 for most purposes. While these hash functions are "broken" in the sense that it is possible to find collisions more efficiently than by searching randomly, the computational requirements for an attack on SHA-1 are formidable.

More importantly, these attacks find two differing vectors with the same hash, and hence, are not useful for forgery or pre-image attacks which attempt to find a data set with a given hash.

No action by users is necessary in the immediate future. DSD will continue to update users on significant academic results relating to hash functions and will provide further advice as to appropriate timeframes for the use of currently approved algorithms.

References:

[1] Eli Biham, Rafi Chen, "Near collisions of SHA-0", www.cs.technion.ac.il/~biham
[2] Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu, "Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD", http://eprint.iacr.org/2004/199.pdf
[3] Florent Chabaud and Antoine Joux, "Differential Collisions in SHA-0", Advances in Cryptology, proceedings of CRYPTO '98, LNCS 1462, pp.56-71, Springer-Verlag, 1999
[4] NIST, "NIST Brief Comments on Recent Cryptanalytic Attacks on Secure Hashing Functions and the Continued Security Provided by SHA-1", http://csrc.nist.gov/hash_standards_comments.pdf
[5] Bruce Schneier, "Schneier on Security", www.schneier.com/blog/archives/2005/02/sha1_broken.html