Researchers can crack sha-1 algorithm with chosen-prefix collision attack

Security researchers have shown an easy-to-execute way to break the sha-1 hash algorithm. It is possible with the attack to produce identical hashes from different input types.

The vulnerability was found by two security researchers from the French scientific research institute Inria and the Technical University of Singapore. They describe the attack on a website. It will be called ‘Sha-1 is a Shambles’. The researchers compare the weakness in the algorithm with that of md5, which has not been safe for years. “All the attacks that were practically possible on md5 are now practically possible on sha-1,” they write. The researchers have also written a white paper with more technical background.

The vulnerability can be exploited with a so-called chosen-prefix collision attack. A lot of computing power is used to look for two equal hashes of different inputs with brute forcing. In a standard collision attack, an attacker has to search until he finds two identical hashes, which was first shown a few years ago. In a chosen-prefix attack, an attacker can actually find a hash of a specific input. In this way it is possible to forge a hash because it contains a different message than the original. For example, an attacker can impersonate an SSL certificate or pgp private key.

Chosen prefix collision attacks have been difficult and expensive to perform for many years because many more calculations are required to find an identical hash. The researchers have now found a way to reduce those costs. They said it would cost about $45,000 to carry out the attack. Those costs would only be ten thousand euros in five years, they say. Limitations in the research design meant that cracking a hash took longer than expected. The researchers showed a proof of concept in which they made two identical hashes from different pgp keys.

Sha-1 as a hash algorithm has been slowly being phased out for years because of its limitations, and because there are now much better alternatives. Nevertheless, a number of important applications still use the algorithm. GnuPG and OpenSSL, among others, still use it. The researchers have informed ‘a large number’ of developers, but by no means everyone. Some of them, like GnuPG, are now considering phasing out sha-1 altogether. That hasn’t happened everywhere yet.