Distributed effort to crack SHA-1 launched

August 13, 2007

The first big distributed computing effort aimed at definitively cracking SHA-1, one of the most widely used forms of encryption, was opened to public participation in Europe this week.

The Graz group's project is based on the Boinc distributed computing tool, which lets users dedicate unused time on their own computers to outside projects, linking the individual PCs into the something like the equivalent of a supercomputer.

The Graz group, like other similar efforts before it, will devote massive amounts of effort and computing time to finding a single collision, and replicating that for nefarious ends would hardly be immediately practical.1

However these efforts do not mean that SHA-1 has never been "cracked". In fact, ever since collisions were first detected in SHA-1 by Chinese researchers in 2005, the National Institute of Standards and Technology has encouraged organizations to rapidly adopt SHA-2 hash functions for digital signatures, and that Federal agencies stop relying on digital signatures that are generated with SHA-1 by the end of 2010.2

What the Chinese researchers had proven was that it was possible to find collisions in SHA-1 in 2^69 calculations, which was about 2,000 times faster than 2^80 calculations that would be required to find a collision by brute force.

The NSA has a saying: "Attacks always get better; they never get worse."3 The attack against SHA-1 will continue to improve, as others read about it and develop faster tricks, optimizations, etc. Coupled with Moore's Law, the attacks will only get faster and more affordable.4

If you wish to switch to a stronger hashing algorithm, some of the more commonly used ones are SHA-512 or Whirlpool.

And for those who enjoy comparing the hash values of different hash functions, there is an online tool that will convert text, hexadecimal data, or a file into 14 different hashes.

1. "Distributed SHA-1 code-cracking effort launched", Wired, August 14, 2007

2. "NIST Comments on Cryptanalytic Attacks on SHA-1", NIST, Retrieved: August 14, 2007

3. "Cryptanalytic Progress: Lessons for AES", NIST, pp.6, Retrieved: August 14, 2007

4. "Cryptanalysis of SHA-1", Schneier, Bruce, February 18, 2005