sha-1
The IAIK Krypto research group focuses on the security analysis of symmetric cryptographic primitives. For this purpose, we apply and adapt existing mathematical frameworks to practical designs and design methods. We conduct basic and applied research and offer consulting services.
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:
- One-wayness: Given a has value, it should be infeasible to find an input that maps to a given digest.
- 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 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'