Cryptography Reference
In-Depth Information
11.3.1 Dedicated Hash Functions: The MD4 Family
Dedicated hash functions are algorithms that have been custom designed. A large
number of such constructions have been proposed over the last two decades. In prac-
tice, by far the most popular ones have been the hash functions of what is called the
MD4 family. MD5, the SHA family and RIPEMD are all based on the principles of
MD4. MD4 is a message digest algorithm developed by Ronald Rivest. MD4 was
an innovative idea because it was especially designed to allow very efficient soft-
ware implementation. It uses 32-bit variables, and all operations are bitwise Boolean
functions such as logical AND, OR, XOR and negation. All subsequent hash func-
tions in the MD4 family are based on the same software-friendly principles.
A strengthened version of MD4, named MD5, was proposed by Rivest in 1991.
Both hash functions compute a 128-bit output, i.e., they possess a collision resis-
tance of about 2
64
. MD5 became extremely widely used, e.g., in Internet security
protocols, for computing checksums of files or for storing of password hashes. There
were, however, early signs of potential weaknesses. Thus, the US NIST published a
new message digest standard, which was coined the Secure Hash Algorithm (SHA),
in 1993. This is the first member of the SHA family and is officially called SHA,
even though it is nowadays commonly referred to as SHA-0. In 1995, SHA-0 was
modified to SHA-1. The difference between the SHA-0 and SHA-1 algorithms lies
in the schedule of the compression function to improve its cryptographic security.
Both algorithms have an output length of 160 bit. In 1996, a partial attack against
MD5 by Hans Dobbertin led to more and more experts recommending SHA-1 as a
replacement for the widely used MD5. Since then, SHA-1 has gained wide adoption
in numerous products and standards.
In the absence of analytical attacks, the maximum collision resistance of SHA-
0 and SHA-1 is about 2
80
, which is not a good fit if they are used in protocols
together with algorithms such as AES, which has a security level of 128-256 bits.
Similarly, most public-key schemes can offer higher security levels, for instance,
elliptic curves can have security levels of 128 bits if 256 bits curves are used. Thus,
in 2001 NIST introduced three more variants of SHA-1: SHA-256, SHA-384 and
SHA-512, with message digest lengths of 256, 384 and 512 bits, respectively. A
further modification, SHA-224, was introduced in 2004 in order to fit the security
level of 3DES. These four hash functions are often referred to as SHA-2.
In 2004, collision-finding attacks against MD5 and SHA-0 where announced by
Xiaoyun Wang. One year later it was claimed that the attack could be extended to
SHA-1 and it was claimed that a collision search would take 2
63
steps, which is
considerably less than the 2
80
achieved by the birthday attack. Table 11.2 gives an
overview of the main parameters of the MD4 family.
In Section 11.4 we will learn about the internal functioning of SHA-1, which is
to date—despite its potential weakness—the most widely deployed hash function.
At this point we would like to note that finding a collision does not necessarily
mean that the hash function is insecure in every situation. There are many applica-
tions for hash functions, e.g., key derivation or storage of passwords, where only
