13 August 2007, 09:44

Cracking SHA-1 using distributed computing

Researchers at the Technical University of Graz have launched a distributed computing project to find a new kind of vulnerability in the SHA-1 hash algorithm, which is used in numerous Internet applications such as encrypted connections and e-mails. Hash algorithms like SHA-1 perform a sequence of mathematical operations on a block of data, for example a message, which generates a unique fixed length value or "digest" from the arbitrary length message. Even minor changes to the original message have a great effect on the digest, making changes easy to detect.

However, collisions do occur: the algorithm produces the same digest for two or more different messages. In the presence of a collision, the variant messages involved cannot be distinguished from each other using the digest, although indeed most of the variant messages would often not be very useful, as they would consist of human-meaningless data. But finding collisions is excessively arduous using simplistic methods. However, in 2005, Chinese researchers demonstrated that the search for collisions can in principle be optimized so that the number of attempts falls below the theoretical minimum of 2⁸⁰. Then around a year ago a way to control the content of a possibly quite substantial proportion of the manipulated message was made public.

The cryptologists at the Technical University of Graz are taking a slightly different approach: they are not looking directly for collisions, but for "near misses", where SHA-1 produces very similar digests from two different messages. They believe that two near misses with the same minimal differences might actually compensate for each other, producing the same outcome as a true collision.

To test this theory, the researchers have launched a distributed computing project. The trusty old Boinc client known from other such projects such as Seti@Home is also being used in Graz. Those who wish to help find collisions are advised to read the manual on the project's website.

The successor of SHA-1 is currently being redeveloped from scratch because the algorithms originally intended to be used in the SHA-2 family all are similar to SHA-1 and therefore vulnerable to the same kind of attacks.