1 2 3 next »

Reinhard Wobst, Jürgen Schmidt

Hash cracked

The consequences of the successful attacks on SHA-1

Almost all security applications currently use the hash function SHA-1. It is used, for instance, in digital signatures and integrity checks for software. Modern operating systems do not save passwords directly, but only their hash value. The secure hash algorithm SHA-1 is used in OpenPGP, S/MIME, IPSec, SSH, and the emerging TCPA. In addition to RSA and AES, SHA-1 constitutes the foundation of our current cryptographic security infrastructure. Are the successful Chinese attacks going to make the whole building collapse?

A bit of background knowledge is required if we are realistically to assess the significance of the attacks by the Chinese research group. A hash function creates a comparatively short string of numbers – called the hash value – from a longer set of data. This hash value is then used as a kind of fingerprint. If the stored hash value of the original corresponds to the copy being used, one assumes that the data are the same and have not been changed.

The quality of a cryptographic hash function is mainly judged in terms of how well it resists two types of attacks:

• Pre-image attacks: How hard is it to create a message that has the same hash value as the one stored?
• Collision attack: How hard is it to find two messages with the same checksum?

Theoretically, both attacks are possible with 'brute force'. For instance, SHA-1 creates hash values of 160 bits. There are therefore 2¹⁶⁰ different hash values, and although some data records may have the same hash value, it is only a remote possibility. If we obtain a hash value and somehow manage to try out 2¹⁶⁰ random messages, we are very likely to get one with the same hash value. However, this process would take far more than 100 million years with the hardware currently in use.

If we only want to find a collision – in other words, two messages with the same hash value not determined beforehand – we only have to try out 2⁸⁰ randomly selected messages. Pre-image attacks on SHA-1 thus do not take twice as many attempts, but rather 2⁸⁰ times as many hash operations as a collision attack. Nonetheless, even a simple search for SHA-1 collisions is far beyond what is currently technically possible.

Birthday

The birthday paradox illustrates the tremendous difference between the effort required for a pre-image attack and a collision attack. If you are trying to find someone who has the same birthday as you, you'll have to ask 253 people to have a 50 per cent chance that at least one of them shares that birthday. But if you only want to have two people with the same birthday regardless of what day that is, you can make do with far fewer people. Within a group of only 23 people, there is a 50 percent chance that two of them will share a birthday.

If an attack is successful with far fewer attempts than in the brute force method, the procedure is considered cracked. According to Schneier, this is exactly what the Chinese research group has accomplished: they are said to have developed a method of finding a collision with 2⁶⁹ operations instead of 2⁸⁰. The number of operations now necessary would then be lower by a factor of 2,048 (2¹¹).

1 2 3 next »