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