Cryptography Reference
In-Depth Information
11.4.3 Implementation
SHA-1 was designed to be especially amenable to software implementations. Each
round requires only bitwise Boolean operation with 32-bit registers. Somewhat
countering this effect is the large number of rounds. Nevertheless, optimized imple-
mentations on modern 64-bit microprocessors can achieve throughputs of 1 Gbit/sec
or beyond. These are highly optimized assembly code software and typical imple-
mentations are most likely considerably slower. Generally speaking, one drawback
of SHA-1 and other MD4 family algorithms is that they are difficult to parallelize. It
is hard to execute many of the Boolean operations that constitute a round in parallel.
With respect to hardware, SHA-1 is certainly not a truly large algorithm but there
are several factors which cause it to be larger than one might expect. Recent hard-
ware implementations on conventional FPGAs can reach a few Gbit/sec which is
not that groundbreaking compared to PC-based implementations. One reason is that
the function
f
t
depends on the stage number
t
. Another reason is the many registers
that are required to store the 512 bit intermediate results. Hence, block ciphers like
AES are typically smaller and faster in hardware. Also in some applications, hash
functions built from block ciphers as described in Section 11.3.2 are sometimes
desirable for hardware implementations.
11.5 Discussion and Further Reading
MD4 family and General Remarks
It is instructive to have a look at the attack
history of the MD4 family. A predecessor of MD4 was Rivest's MD2 hash func-
tion, which did not appear to become widely used. It is doubtful that the algorithm
would withstand today's attacks. The first attacks against reduced versions of MD4
(the first or the last rounds were missing) were developed by Boer and Bosselaers in
1992 [53]. In 1995, Dobbertin showed how collisions for the full MD4 can be con-
structed in less than a minute on conventional PCs [61]. Later Dobbertin showed that
a variant of MD4 (a round was not executed) does not have the one-wayness prop-
erty. In 1994, Boer and Bosselaer found collisions in MD5 [54]. In 1995, Dobbertin
was able to find collisions for the compression function of MD5 [62]. In order to
construct a collision for the popular SHA-1 algorithm, about 2
63
computations have
to be executed. This is still a formidable task. In 2007, a distributed hash collision
search over the Internet was organized by Rechberger at the Technical University of
Graz in Austria. At the time of writing, about two years into the search, no collisions
have been found.
RIPEMD-160 plays a somewhat special role in the MD4 family of hash func-
tions. Unlike all SHA-1 and SHA-2 algorithms, it is the only one that was not
designed by NIST and NSA, but rather by a team of European researchers. Even
though there is no indication that any of the SHA algorithms are artificially weak-
ened or contain backdoors (introduced by the US government, that is), RIPEMD-
160 might appeal to some people who heavily distrust governments. Currently, no
