United BOINC

  • Increase font size
  • Default font size
  • Decrease font size
Home BOINC Projects SHA-1 Collision Search Graz

SHA-1 Collision Search Graz

E-mail Print PDF
User Rating: / 5
AddThis Social Bookmark Button

SHA-1 Collision Search Graz

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?

SHA-1 Collision
Search Graz
Getting started
Download BOINC
Download BOINC
Create account
Create account
Get help
Your account
Participant profiles
Top participants
Server status

Hash functionsHash 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

1) one-wayness:

Given a hash value, is should be infeasible to find an input that maps to a given digest.


2) collision-resistance:

It should be infeasible to find two inputs that hash to the same digest 


What is SHA-1?

Illustration of SHA-1 Compression FunctionThe 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.

Illustration of a single SHA-1 step transformation

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

Sequence Of DifferencesSo 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.

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:

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


Check out these cool BOINC videos!

World Community Grid and IBM Tackle Rice CrisisWorld Community Grid & IBM Tackle Rice Crisis


Einstein@home - LIGO Gravitational Wave ObservatoryEinstein@home - LIGO Gravitational Wave Observatory


climateprediction.net - Results Programme Documentaryclimateprediction.net - Results Programme Documentary


Check out this science project!


Yoyo@home is a project bringing existing project to the world of BOINC using the wrapper technology. The project is currently running 3 different projects and they're always looking for new projects to integrate intoYoyo@home. The project is run by the German BOINC team Rechenkraft.net

Yoyo@home project URL; http://www.rechenkraft.net/yoyo/


Poll Poll 1

Is BOINC manager "User friendly"?

Poll Poll 2

How many BOINC projects are you running?

Poll Poll 3

Have you ever used an Account Manager?