Message Authentication - Codes: The Guide to Secrecy from Ancient to Modern Times - page 254

(3) She compares the two sets of hash values until she finds a collision h ( C G )=
h ( C B ) and recovers the corresponding preimages.
(4) Alice has Bob sign C G via the hash of its value.
(5) Later Alice substitutes C B for C G whose hash value is the same as that
signed by Bob, who has now lost all his money.
From the discussion preceding the Yuval attack above,we see that a birthday
attack requires an effort of only the order of 2 32 . Thus, simple hash functions
based on a 64-bit message digest are insecure, so from a cryptographic perspec-
tive, they are not worth discussing. (As a counterpoint to the above contract
signing scam, we saw on page 193, how to make contract signing secure.)
Modern cryptography requires custom-built hash functions to meet current
standards for security. In 1990 (see [228]), Rivest developed a hash scheme,
called MD4, designed for software implementation on a 32-bit processor. How-
ever, very early after its inception, attacks on it proved it to be insecure under
modern cryptanalysis. MD4 was updated to MD5 in 1992 (see [229]), but in
1996 hash collisions of the underlying compression function proved it to be inse-
cure. In fact, the birthday attack can be used on MD5 to find a collision in about
2 64 iterations, which is quite insu:cient for modern cryptosystems. In 1995, the
Secure Hash Algorithm (SHA-1) was developed for the NSA and standardized
by NIST (see [88]). SHA-1 employs a 160-bit hash function. In 2002, NIST
updated SHA-1 (see [89]) in what they called the Secure Hash Standard (SHS)
containing specifications for 256-, 384-, and 512-bit message digests, called (re-
spectively) SHA-256, SHA-384, and SHA-512. Naturally, these upgraded hash
standards are much slower than SHA-1, yet the increased security level makes
them excellent choices for modern cryptosystems. 7.1 In terms of speed com-
bined with modern-day security requirements the SHA-256 is perhaps the best
choice, since the security level is 2 128 , based upon the above-established fact
that the birthday attack on a message digest of size 256 bits produces an effort
of about 2 128 iterations of workload. Similarly, the SHA-1 scheme requires on
2 80 iterations, and some cryptographers feel that this is insu:cient for modern
standards. Yet, from our perspective, it embodies the fundamentals of the SHA
algorithms, and so deserves to be studied in detail, since it provides a simple
method for describing the underlying mechanisms.
SHA-1
Background Assumptions
The algorithm inputs messages of maximum bitlength 2 64 and outputs 160-
bit message digests. The input is divided into blocks of 512 bits.
7.1 At the August 2004 CRYPTO meeting (see page 232), theoretical attacks against MD5
and the original SHA algorithm show that they are not as secure as originally believed. This
may have some consequences for the security of SHA-1 as well, since the attacks had partial
success in finding collisions for the latter. Thus, use of SHA-256 seems even more prudent.