## What is a hash function?

Hash functions are one of the most important cryptographic building blocks. They accept input of arbitrarly 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?

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.

Illustration of SHA-1 Compression Function.

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'.