Consequences of the successful attacks on SHA-1

21.02.2005 13:28 Uhr Dr. Reinhard Wobst, Jürgen Schmidt

Almost all security applications currently use the hash function SHA-1. It is used, for instance, in digital signatures and integrity checks for software. Is all of that now in danger, and what are the alternatives? Almost all security applications

A bit of background knowledge is required if we are to realistically assess the significance of the attacks by the Chinese research group [1]. 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 2¹⁶⁰ different hash values, and many data records therefore have the same hash value. If we obtain a hash value and 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 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 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 [2] 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 2⁶⁹ operations instead of 2⁸⁰. The number of operations now necessary would then be lower by a factor of 2048 (2¹¹).

Keep your cool

Nonetheless, crypto-experts such as Schneier and Kaliski expect that people will continue to be able to use SHA-1 without having to be worried. After all, 2⁶⁹ is still a tremendous number. If special hardware is used, one hash operation can be executed in around 40 cycles [1] [3]. Even if they could be accelerated from 33 MHz to 4 GHz, the process would still take 170,000 years. And even if a giant cluster of such machines were used, no collisions would be found within a realistic timeframe of a few years. However, the surprising breakthrough of Wang et al. makes it clear that we cannot afford to sit back and relax any longer.

The second reason to keep cool is just as important, if not even more: hackers will have to execute a pre-image attack to manipulate, for instance, a contract that has been digitally signed. In other words, hackers will have to find a second, manipulated contract with the same hash value as the real contract. In principle, the number of operations needed is thus far greater (2¹⁶⁰). Indeed, as far as we know all attacks to date have only concerned collisions, and Wang et al. does not change that. There are no known methods to reduce the number of operations needed considerably for pre-image attacks.

Therefore, current digital signatures and signatures for documents that people create themselves are not in danger for the time being. On the other hand, attacks on digital signatures are possible for collisions that can be found in a realistic period of time when hackers can determine the hash value of the original themselves. The following example illustrates this possibility in a somewhat simplified fashion.

Cheating in poker with contracts

An intelligent hacker creates two contracts: one of them with the correct price for a house; the other, a much higher figure. As this hacker knows that he can find a collision in 2^x hash operations, he makes x number of cosmetic modifications, for example by adding spaces at the end of a line. By executing all possible combinations of these modifications, this hacker creates 2^x versions of each contract. The possibility that two of them will have the same hash value is very great. The hacker then has the victim sign a copy of the contract with the correct purchase price. But he can change the text without changing the hash value later and take the victim to court.

The new attack on SHA-1 may reduce the effort that hackers will have to go to in order to find a collision by a factor of 2000. Nonetheless, their chances of success remain, fortunately, unfeasible in practice. For instance, attacks on SHA-1 signatures would take advantage of deleted paragraphs in Word files to add blocks with random variations to the document. In general, it is a good idea to make a cosmetic change to a document before it is digitally signed.

In addition, pre-image attacks cannot be used to crack methods in which digital signatures precede encryption. If you cannot access the plain language text, you can't even circumvent an MD4 sum. This is why SSH and IPSec remain secure. HMAC sums also remain unaffected. This are hashes that can only be calculated if a secret key is known. They are set up in a way that a hacker cannot calculate a collision without the key.

SHA-1 attacks also do not affect the security provided by passwords, which are only saved as hash values in many systems. For the time being, there is no risk of a password being calculated for a given hash value; rather, dictionary attacks remain the greatest threat here.

Successor to the throne

Despite all of the limitations in terms of the realistic possibilities of such attacks, the success of cryptanalysis demonstrates that the search for potential successors to SHA-1 must be stepped up. Burt Kalinski, head of the research department at RSA, expects the first pre-image attacks on SHA-1 to be successful within the next five to 10 years.

The further developments of SHA-1, which have hardly been used, have longer hash values and are some of the main potential successors: SHA-224, SHA-256, SHA-384, and SHA-512. They have the advantage of being the only hash functions besides SHA-1 that the US National Institute of Standards and Technology (NIST [4]) has specified in its Federal Information Processing Standards [5]. According to press reports [6], the NIST also revealed just before the success of the new SHA-1 attacks was announced that it would be replacing SHA-1 with SHA-256 and SHA-512 in the near future.

But some cryptanalysts doubt that these algorithms offer a good solution for the long term. After all, the main benefit they offer is a longer hash value. They may be vulnerable to the same kinds of attacks that may make SHA-1 obsolete. We have to keep in mind that cryptanalysts have not been dealing with these potential successors nearly as much as with SHA-1. When that starts to change, new weaknesses may be discovered.

The same is true for the European algorithm RIPEMD-160, which did not manage to beat out SHA-1. The RIPEMD variant it is based on was already cracked in 2004. The Chinese research group also cracked MD5, which is still commonly used, back in 2004 [7].

Simply making a hash value longer does not automatically provide more security; this is also true for using two different hash values -- such as MD5 and SHA-1 -- for one message. And other alternatives based on block ciphers are generally too slow.

Another algorithm that has been talked about a lot in the past few days is Whirlpool [8]. It creates 512-bit hash values with its own block cipher called W and is at least two times slower than SHA-1. To make things worse, it is not even two years old and has hardly been studied.

It is thus completely unclear who the successor to the throne will be. Perhaps a consensus will be reached in a manner similar to what happened when DES fell out of favor. Here, the NIST crowned the algorithm Rijndael as the Advanced Encryption Standard (AES).

[9]Links

[1] Comparative Analysis of the Hardware Implementations of Hash Functions SHA-1 and SHA-512 [10] (PDF) (ju [11])

URL dieses Artikels:
https://www.heise.de/-270650

Links in diesem Artikel:
[1] https://www.heise.de/news/Kryptoverfahren-SHA-1-geknackt-135372.html
[2] http://en.wikipedia.org/wiki/Birthday_paradox
[3] #lit-u2
[4] http://csrc.nist.gov/
[5] http://csrc.nist.gov/CryptoToolkit/tkhash.html
[6] http://www.fcw.com/fcw/articles/2005/0207/web-hash-02-07-05.asp
[7] https://www.heise.de/news/Verunsicherung-um-Sicherheit-von-Kryptoalgorithmen-100595.html
[8] http://planeta.terra.com.br/informatica/paulobarreto/WhirlpoolPage.html
[9]
[10] http://www.east.isi.edu/~bschott/pubs/grembowski02comparative.pdf
[11] mailto:ju@ct.de