European cryptologists attack hash functions

Progress in attacking hash functions was presented by cryptologists at Crypto 2008. They explained their attack on the GOST Russian hash standard – usage of GOST is mandatory in Russian government offices. They also demonstrated the first practical inversion attack against reduced variants of SHA-1 that could be used to back calculate a password from the hash.

The GOST hash function was established as part of the GOST standard at around the same time SHA-1 was established in 1995 and until now has been considered very secure. Russian information security standards, like their aerospace standards, are very conservatively designed.

But now an Austrian/Polish team of cryptologists at the Graz University of Technology and the Military University of Technology in Warsaw have found an unexpected technical vulnerability and exploited it for an attack. The result – PDF – is a collision attack that is 2^23 times faster than expected. A collision attack is one where the attacker finds two arbitrary messages that generate the same hash.

By comparison, the first successful collision attack in 2005 against SHA-1 made the attack faster than expected, by a factor of 2^11 – 2^69 instead of 2^80. No meaningful attacks on the GOST hash function can be expected yet, though. The 256-bit output value means that 2^105 operations are still necessary – considerably more than can currently be realistically performed.

All of the known attacks in recent years against hash functions, such as SHA-1 and now the GOST hash function, have been collision attacks. But these attacks are mainly relevant to signature applications where the attacker has access to the document before the signature is calculated. In that scenario, it is not possible to change the document after signature calculation and preserve the validity of the signature. Many other applications of hash functions, like secure password storage, are not affected, which is why the US standards organisation NIST, for instance, continues to recommend the SHA-1 hash function for those applications.

At Crypto, researchers from the Graz University of Technology and the ENS Paris presented, for the first time, approaches to attacking SHA-1 – PDF – which do affect the wider set of hash function applications. These are attacks that allow a password to be determined when only its SHA-1 hash value is known, or that permit signed documents to be changed after the signature has already been generated. The attacks work for reduced round versions of SHA-1 up to a maximum of 45 of the 80 rounds, which is comparable to collision attacks on SHA-1 four years ago, when theoretical attacks of up to 53 rounds were possible. It does not appear, at this time, that these attacks can be extended to the full 80 rounds. There is another parallel to the earlier attacks though; these new inversion attacks, as was the case with the early collision attacks before 2004, have many unused degrees of freedom. The latest collision attacks – after 2007 – now exploit all of the available degrees of freedom.

Even if many of the current attacks are still theoretical in nature, we have to remember that the analysis of cryptographic hash functions is still far from adequately researched and that new breakthroughs in the future cannot be ruled out. With entries being accepted, till October 2008, for the upcoming competition to select the new SHA-3 hash standard for 2012, it is even more important to favour hash functions with effective security arguments, which is not the case with SHA-1 or the GOST hash function.

(Christian Rechberger)

Christian Rechberger is employed as a scientist at the Institute for Applied Information Processing and Communications (IAIK) at the Graz University of Technology and co-author of the publications on GOST and the inversion attacks against SHA-1.

(djwm)