SHA-1 hash function under pressure

Cryptographic experts at the Crypto 2006 conference have demonstrated a modified method of attack against a reduced variant of the SHA-1 hash algorithm. The new method is an attack which, for the first time, allows at least a part of the message to be freely selected, for example as straight text. Previous approaches, for example the collision attack by Xiaoyun Wang and her team, which attracted considerable attention, were merely able to produce almost completely different hash twins of the same length, both consisting of meaningless gibberish.

Although the demonstration was restricted to the reduced SHA-1 variant in 64 steps, it can, according to the experts, also be generalised to the standard 80 step variant. This means that SHA-1 must also be considered as cracked in principle. Christian Rechberger, who developed the new attack together with his colleague Christophe De Cannière, explained to heise Security that, in their experiments, up to one quarter of the message could be freely selected. The remaining 75 percent is, as before, determined by the attack. Rechberger suspects, however, that the amount that can be freely selected can be further increased by optimising the attack.

The latest violation means that the attacks against the reduced step SHA-1 variant has reached the same level as, for example, the attack against the old MD5 algorithm. The most successful previous attack against SHA-1, by Wang, had until now been inconsequential in practice, because the hash twins produced were always completely unreadable. Using the new method, it is possible, for example, to produce two HTML documents with a long nonsense part after the closing </html> tag, which, despite slight differences in the HTML part, thanks to the adapted appendage have the same hash value.

The SHA-1 algorithm is still the most commonly used hash algorithm, even though rapid progress in SHA-1 attacks has been being made for some time. The new attack method has yet to be successfully implemented for the unreduced SHA-1 standard, but it is now high time that a suitable successor were found. A possible means to do so lies in a public competition, such as that which successfully took place in 1997 for the successor to the DES encryption algorithm, which was at that time showing signs of weakness. Until a new standard has been found, more secure alternatives such as SHA-256 and SHA-512 can at least raise the bar for attackers. The longer hash values mean that the actual collision calculations are incomparably more complex than for their 160 bit predecessor.

See also:

• Hash cracked: The consequences of the successful attacks on SHA-1, know-how article on the attacks by Wang et al. from heise Security.

(ehe)