Chapter 6Hash FunctionsA hash function usually means a function that compresses, meaning the output is shorter than theinput. Often, such a function takes an input of arbitrary or almost arbitrary length to one whoselength is a fixed number, like 160 bits. Hash functions are used in many parts of cryptography,and there are many different types of hash functions, with differing security properties. We willconsider them in this chapter.6.1 The hash function SHA1The hash function known as SHA1 is a simple but strange function from strings of almost arbitrarylength to strings of 160 bits. The f unction was finalized in 1995, w hen a FIPS (Federal Inf ormationProcessing Standard) came out from the US National Institute of Standards that specified SHA1.Let {0, 1}<ℓdenote the set of all strings of length strictly less than ℓ. The function SHA1:{0, 1}<264→ {0, 1}160is shown in Fig. 6.1. (Sin ce 264is a very large length, we think of SHA1as taking inputs of almost arbitrary length.) It begins by padding the message via the functionshapad, and then iterates the compression function sha1 to get its output. The operations used inthe algorithms of Fig. 6.1 are described in Fig. 6.2. (The first input in the call to SHF1 in co de forSHA1 is a 128 bit string written as a sequence of four 32-bit words, each word being consisting of8 hexadecimal characters. Th e same convention holds for the initialization of the variable V in theco de of SHF1.)SHA1 is derived from a function called MD4 that was proposed by Ron Rivest in 1990, and thekey ideas behind SHA1 are already in MD4. Besides SHA1, another well-known “child” of MD4 isMD5, wh ich was likewise proposed by Rivest. The MD4, MD5, and SHA11 algorithms are all quitesimilar in structure. The first two produce a 128-bit output, and work by “chaining” a compr essionfunction that goes from 512+128 b its to 128 bits, while SHA1 produces a 160 bit output and worksby chaining a compression function from 512 + 160 bits to 160 bits.So what is SHA1 supposed to do? First and foremost, it is supposed to be the case that nobodycan find distinct strings M and M′such that SHA1(M) = SHA1(M′). This property is calledcollision resistance.Stop for a moment and think about the collision-resistance requirement, for it is really q uiteamazing to think that such a thing could be possible. The function SHA1 maps strings of (almost)any length to strings of 160 bits. So even if you restricted the domain of SHA1 ju st to “short”strings—let us say strin gs of length 256 bits—then there must be an enormous number of pairs of2 HASH FUNCTIONSalgorithm SHA1(M) // |M | < 264V ← SHF1( 5A827999 k6ED9EBA1 k 8F1BBCDC k CA62C1D6 , M )return Valgorithm SHF1(K, M) // |K| = 1 28 and |M | < 264y ← shapad(M)Parse y as M1k M2k ··· k Mnwhere |Mi| = 512 (1 ≤ i ≤ n)V ← 67452301 k EFCDAB89 k 98BADCFE k 10325476 k C3D2E1F0for i = 1, . . . , n doV ← shf1(K, Mik V )return Valgorithm shapad(M) // |M| < 264d ← (447 − |M|) mod 512Let ℓ be the 64-bit binary representation of |M|y ← M k 1 k 0dk ℓ // |y| is a multiple of 512return yalgorithm shf1(K, B k V ) // |K| = 128, |B| = 512 and |V | = 160Parse B as W0k W1k ··· k W15where |Wi| = 32 (0 ≤ i ≤ 15)Parse V as V0k V1k ··· k V4where |Vi| = 32 (0 ≤ i ≤ 4)Parse K as K0k K1k K2k K3where |Ki| = 32 (0 ≤ i ≤ 3)for t = 16 to 79 doWt← ROTL1(Wt−3⊕ Wt−8⊕ Wt−14⊕ Wt−16)A ← V0; B ← V1; C ← V2; D ← V3; E ← V4for t = 0 to 19 doLt← K0; Lt+20← K1; Lt+40← K2; Lt+60← K3for t = 0 to 79 doif (0 ≤ t ≤ 19) then f ← (B ∧ C) ∨ ((¬B) ∧ D)if (20 ≤ t ≤ 39 OR 60 ≤ t ≤ 79) then f ← B ⊕ C ⊕ Dif (40 ≤ t ≤ 59) then f ← (B ∧ C) ∨ (B ∧ D) ∨ (C ∧ D)temp ← ROTL5(A) + f + E + Wt+ LtE ← D ; D ← C ; C ← ROTL30(B) ; B ← A ; A ← tempV0← V0+ A ; V1← V1+ B ; V2← V2+ C ; V3← V3+ D ; V4← V4+ EV ← V0k V1k V2k V3k V4return VFigure 6.1: The SHA1 hash f unction and the underlying SHF1 family.strings M and M′that hash to th e same value. This is just by the pigeonhole principle: if 2256pigeons (the 256-bit messages) roost in 2160holes (the 160-bit hash values) then some two pigeons(two distinct strings) roost in the same hole (have the same hash). Indeed countless pigeons mustshare the same hole. The difficult is only that nobody has as yet identified (meaning, explicitlyprovided) even two such pigeons (strings).Bellare and Rogaway 3X ∧ Y bitw ise AND of X and YX ∨ Y bitw ise OR of X and YX ⊕ Y bitw ise XOR of X and Y¬X bitw ise complement of XX + Y integer s um modulo 232of X and YROTLl(X) circular left shift of bits of X by l positions (0 ≤ l ≤ 31)Figure 6.2: Operations on 32-bit words used in sha1.In trying to define this collision-resistance property of SHA1 we immediately run into “foun-dational” problems. We would like to say th at it is computationally infeasible to outp ut a pairof distinct strings M and M′that collide under SHA1. But in what sense could it be infeasible?There is a program—indeed a very short an simple one, having just two “print” statements—whoseoutput specifies a collision. It’s not computationally hard to output a collision; it can’t be. Theonly difficulty is our human problem of not knowing what this p rogram is.It seems very hard to make a mathematical definition that captures the id ea that human beingscan’t find collisions in SHA1. In order to reach a mathematically precise definition we are going tohave to change the very nature of what we conceive to be a hash function. Namely, rather than itbeing a single function, it will be a family of functions. This is unfortunate in some ways, becauseit distances us from concrete hash functions like SHA1. But no alternative is known.6.2 Collision-resistant hash functionsA hash function for us is a family of functions H: K × D → R. Here D is the domain of H andR is the range of H. As usual, if K ∈ K is a particular key then HK: D → R is defined for allM ∈ D by HK(M) = H(K, M). This is the instance of H defined by key K.An example is SHF1: {0, 1}128× {0, 1}<264→ {0, 1}160, as described in Fig. 6.1. This hashfunction takes a 128-bit key and an input M of at most 264bits and returns a 160-bit outpu t. Thefunction SHA1 is an instance of this family, namely the one whose associated key is5A827999 k 6ED9EBA1 k 8F1BBCDC kCA62C1D6 .Let H: K × D → R be a hash function. Here …