SHA-1 Collision Search Graz is a research project researching cryptanalysis. Cryptanalysis is the study of methods for obtaining the meaning of encrypted information, without access to the secret information which is normally required to do so.
SHA-1 Collision Search Graz project URL; http://boinc.iaik.tugraz.at/sha1_coll_search/
About SHA-1 Collision Search Graz
What is a hash function?
Hash functions are one of the most important cryptographic building blocks. They accept input of arbitrary length and output a hash value (also called a digest or a fingerprint), of fixed length.
Basically a cryptographic hash function is expected to have two properties
Given a hash value, is should be infeasible to find an input that maps to a given digest.
It should be infeasible to find two inputs that hash to the same digest
What is SHA-1?
The hash function SHA-1 (see e.g. wikipedia) is one of the most important cryptographic building blocks used today. It was designed by NSA and put forward as a standard by NIST in 1995. Browsing the Web, administering severs via ssh, or storing and comparing passwords are just a few examples where SHA-1 is used and trusted by many of us on a daily basis.
What happened in the past?
Most predecessors of SHA-1 were broken, i.e. collisions have been found:
The German cryptographer Hans Dobbertin found a pair of colliding messages for MD4 in 1996.
In 2004, a group of Chinese researchers around Prof. Wang found the first collisions for MD5 and RIPEMD.
Independently and shortly afterwards a French group around Antoine Joux reported a collision for SHA-0 (or alternatively called SHA), the direct predecessor of SHA-1.
So far nobody could show a collision for SHA-1, since SHA-1 is much more resistant against these style of attacks.
However, researchers define variants where they reduce the number of steps. The variant which comes closest to the real SHA-1 for which a colliding message pair was found is SHA-1 reduced to 70 out of 80 steps. Note however that the workload grows exponentially with the number of steps. This implies that a hash function for which there is an attack on a variant with only half the number of steps is by no means 'half broken'.
Types of collision search attacks
As soon as the input to a hash function can get longer than the output, collisions between inputs are unavoidable. For a hash function with n bit output size, a birthday attack (see e.g. wikipedia) requires about 2n/2 hash operations to find a colliding message pair. A dedicated attack, on the other hand, tries to exploit the inner working of the hash function. The SHA-1-Collison Search Graz Project is of that type.
Dedicated method for SHA-1
So far nobody could show a collision for SHA-1. Newly developed dedicated collision search methods are in development. Here we briefly illustrate how this method works.
1. A suitable message difference is selected.
2. A sequence of differences (also called path, trail, characteristic or differential characteristic) through the compression function is determined (red dots in next picture).
3. The probability that such a sequence of differences actually happens is very very low in the first place. The next step is to use cryptanalytic methods to fix parts of the input message (16 words = 512 bits) to particular values that improve this probability.
4. The best known method involves dividing this task into two parts and hence double the usable degrees of freedom. The next figure illustrates this 2-block approach.
5. The computationally expensive task is to 'intelligently and efficiently' loop through the remaining search space. This part is distributed via the SHA-1-Collison Search Graz Project.
6. We developed new cryptanalytic methods that are already advanced enough to prevent single bottlenecks in the collision search. As a result, optimizing the running time of the search is a multidimensional optimization problem:
More details will appear in a scientific paper. During the course of the project we expect to gain more data that allows further optimization.
Video showing a brute force hacker at work
|< Prev||Next >|