Cryptography Reference
In-Depth Information
rotates by one bit during expansion, which is a minimal change with
a big effect, as we will see further below. It is called SHA-1 and has
meanwhile become the most frequently used hash function. To distinguish
it, the older version is now called SHA-0. But even in SHA-1, the first
theoretical vulnerabilities have been found (see below).
•
SHA-256
: Hash functions are also used for generating session keys,
among other things. Since AES optionally processes key lengths of 192
and 256 bits, SHA-1 is not suitable for it. This was presumably the main
reason why the NIST published other hash functions, including SHA-512,
in August 2002. As the name suggests, SHA-256 creates hash values of
256-bit length. Though the function is slower, it is easier to program
than SHA-1. And in contrast to SHA-1, no theoretical weaknesses have
become known to date. A description and C program (from GnuPG) in
algor/SHA
is on the Web site.
Minor Earthquake: Collisions Found!
With all due respect for the successes in cryptanalyzing MD4, MD5 collisions
have continued to be wishful thinking for cryptanalysts. Conversely, Chabaud
and Joux introduced a theoretical attack against SHA-0 with complexity 2
61
at
the CRYPTO '98, which means in the worst case that 2
61
SHA-0 values have
to be computed to find a collision (a totally unrealistic number for practical
purposes). The basic idea was derived from differential cryptanalysis: messages
are 'disturbed' in single bits, and one tries to do this in such a way that the
effect of the disturbance is removed in the subsequent compression ('corrective
pattern').
Based on this work and the lecture by Biham and Chen at CRYPTO '04, Joux
succeeded in reducing the cost to 2
51
calculations. A supercomputer with 256
Itanium2 processors was busy for about 13 days (80 000 CPU hours), and the
outcome was the first collision of SHA-0 ever found. You can check it out
using my Python script
algor/SHA/sha0coll.py
from our Web site. This was
a sensation indeed: not even an MD5 collision had been computed up to that
time despite many years' effort. Nobody had even expected something like this
could happen to the SHA-0 algorithm. In contrast to MD4 and MD5, SHA-0
uses each message bit more than 20 times. But the authors exploited the fact
that the bit positions don't 'blur' during expansion of the message ('stretching'
it from 16 words to 80 words) — in contrast to SHA-1! When left rotated,
this single bit in SHA-1, the only difference between the two SHA versions,
has an astonishingly strong effect. How much did the NSA know back then,
considering that they submitted this correction in 1994?
