The consequences of the successful attacks on SHA-1
Reinhard Wobst, Jürgen Schmidt - 21.02.2005
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 these successful attacks going to make the whole building collapse?
A bit of background knowledge is required if we are to realistically 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 at 160 bits. There are thus only 2160 different hash values, and many data records therefore have the same hash value. If we obtain a hash value and try out 2160 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 used.
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 280 randomly selected messages. Pre-image attacks on SHA-1 thus do not take twice as many attempts, but rather 280 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.
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 percent accuracy rate. 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. With only 23 people, you still have a 50 percent chance of finding two with the same 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 269 operations instead of 280. The number of operations now necessary would then be lower by a factor of 2048 (211).