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
PoorBest 
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
Homepage
Getting started
Download BOINC
Download BOINC
Create account
Create account
Get help
Participants
Your account
Community
Participant profiles
Statistics
Top participants
Information
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.

one-wayness

2) collision-resistance:

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

collision-resistance

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!

LHC@home - CERN & the Large Hadron Collider (LHC)

LHC@home - CERN & the Large Hadron Collider (LHC) 

 

QMC@home - Quantum Chemistry in actionQMC@home - Quantum Chemistry in action

 

SETI@home: Listening to the Universe

SETI@home - Listening to the Universe

 

Check out this science project!

NanoHive@home

NanoHive@Home is a distributed computing system used for large-scale nanotech systems simulation and analysis. The goal of NanoHive@Home is to perform large-scale nanosystems simulation and analysis that is otherwise too intensive to be calculated via normal means, and thereby enable further scientific study in the field of nanotechnology.

NanoHive@home project URL; http://www.nanohive-1.org/atHome/

Read more...

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?