Fixing the broken hashes

Published: 2007-01-28
Last Updated: 2007-01-28 20:08:12 UTC
by Maarten Van Horenbeeck (Version: 2)
0 comment(s)

One media source reported earlier this week of a ‘breakthrough finding’ in attacks on SHA1. Some readers wrote us quoting the article, asking what was up. The article in fact referred to a well-known finding in early February 2005, when a Chinese research team announced they had found ways to identify collisions in a much faster way than purely through brute force attack.

As SHA1 generates 160 bits of output, there are 2160 potential output values. Due to the birthday paradox, brute force attacks against SHA1 would as such have taken 280 iterations to find a collision – two messages with an identical hash value. Technically this attack would be difficult to achieve on current hardware.

The 2005 findings by Xiaoyun Wang and her research team decreased this to 269 hash operations. As this is purely a collision attack, its use as an attack strategy is limited to certain situations in which system designers require strong collision resistance.

There are already certain hash functions that are not affected by these recent attacks. NESSIE, a European Commission research project identified a number of recommended hash functions. These included Whirlpool, as well as the SHA-based functions SHA-256, SHA-384 and SHA-512. The project reported negatively on SHA1 due to its short output length of 160 bits. In March of 2006, the National Institute for Standards and Technology (NIST) started advising against the use of SHA-1 for implementations that require collision resistance and suggested some of those same alternatives.

This week, NIST released a draft minimum requirements list for candidate hash algorithms to replace SHA-1 as the Secure Hash Standard. They are actively soliciting input in order to allow for the organization of a new public competition, similar to that used to select Rijndael as the AES standard.

The advice fellow handler Dan gave back in 2005 still stands:
- know where the affected hash functions are used in your organization;
- identify the cryptographic services they deliver in each instance;
- identify which types of service are affected by new attacks;
- liaise with your vendors and developers to ensure availability of alternatives where necessary;
- closely track standardization efforts to ensure implemented alternatives are peer-reviewed and widely supported.

Maarten Van Horenbeeck

0 comment(s)


Diary Archives