You are here: Start » Research » Krypto »

« SHA-1 collsion basics

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 2^n/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 useable 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.