where the nonlinear functions fi are de¬ned by

i of the compression function updates in turn one

fi f (X, Y, Z) =

of the chaining variables according to one mes-

sage word Wi . As there are more steps in the com- (X § Y)|(¬X § Z), 0 ¤ i ¤ 19

pression function than words in a message block,

fxor (X, Y, Z) =

an additional message schedule is applied to ex-

(X • Y • Z), 20 ¤ i ¤ 39, 60 ¤ i ¤ 79

pand the message block. In the last step, the ini-

fma j(X, Y, Z) =

tial value of the chaining variable is added to each

variable to form the current hash value (or the ((X § Y)|(X § Z)|(Y § Z), 40 ¤ i ¤ 59

¬nal one if no more message blocks are avail-

and the constants Ki by

able). The following provides an overview of SHA-

1, SHA-256, and SHA-512. SHA-0 is almost iden- Ki ← 5A827999x , 0 ¤ i ¤ 19

tical to SHA-1, SHA-224 to SHA-256 and SHA-384

Ki ← 6ED9EBA1x , 20 ¤ i ¤ 39

to SHA-512.

Ki ← 8F1BBCDCx , 40 ¤ i ¤ 59

Ki ← CA62C1D6x , 60 ¤ i ¤ 79.

PADDING: The message is appended with a bi-

nary one and right-padded with a variable num- After 80 steps, the output value of each chain-

ber of zeros followed by the length of the original ing variable is added to the previous intermedi-

message coded over two binary words. The total ate hash value according to the Davies“Meyer con-

padded message length must be a multiple of the struction to give the new intermediate hash value.

message block size. When all consecutive message blocks have been

566 SHA family (secure hash algorithm)

SHA-224

hashed, the last intermediate hash value is the

¬nal overall hash value.

The SHA-224 hash computations are exactly the

SHA-0 same as those of SHA-256, up to the following two

differences: the constants H0 to H7 used in SHA-

The only difference between SHA-1 and SHA-0 224 are not the same as those used in SHA-256,

is the fact that there is no left rotation by one bit and the SHA-224 output is obtained by truncating

in the message schedule of SHA-0. In other words, the ¬nal overall hash value to its 224 leftmost bits.

the 64 message schedule words Wi for SHA-0 are

computed as SHA-384

Wi ← Wi’3 • Wi’8 •Wi’14 • Wi’16 , 16 ¤ i ¤ 79.

The SHA-384 hash computations are exactly the

same as those of SHA-512, up to the following two

SHA-256 and SHA-512 Compression differences: the constants H0 to H7 used in SHA-

Functions 384 are not the same as those used in SHA-512,

and the SHA-384 output is obtained by truncating

Eight chaining variables A, B, C, D, E, F, G, H are

the ¬nal overall hash value to its 6 leftmost words.

initialized to ¬xed values H0 to H7 for the ¬rst

message block, and to the current intermediate SECURITY CONSIDERATION: All six SHA func-

hash value for the following blocks. The ¬rst six- tions belong to the MD4 type hash functions and

teen w-bit words (where w = 32 for SHA-256 and were introduced by the American National Insti-

w = 64 for SHA-512) of the message schedule are tute for Standards and Technology (NIST). SHA

initialized to the input message words. The follow- was published as a Federal Information Process-

ing r ’ 16 (where r = 64 for SHA-256 and r = 80 ing Standard (FIPS) in 1993. This early version is

for SHA-512) message schedule words Wi are com- known as SHA-0. In 1994, a minor change to SHA-

puted as 0 was made, and published as SHA-1 [7]. SHA-

Wi = σ1 (Wi’2 ) + Wi’7 + σ0 (Wi’15 ) 1 was subsequently standardized by ISO [5]. The

following generation of SHA functions with much

+ Wi’16 mod 2w , 16 ¤ i ¤ r ’ 1

larger message digest sizes, namely 256, 384, and

where σ0 and σ1 represent linear combinations of 512 bits, was introduced in 2000 and adopted as a

three rotated values of the input variable. Then FIPS standard in 2002 [8] as well as an ISO stan-

the compression function works as follows: dard in 2003 [5]. The latest member of the family,

namely SHA-224, was adopted in a Change No-

tice to FIPS 180-2 in 2004. This latter generation

for i = 0 to r do

of hash functions provides theoretical security lev-

T1 ← H + 1 (E) + fi f (E, F, G) + Ki

els against collision search attacks which are con-

+ Wi mod 2w

sistent with the security levels expected from the

T2 ← 0 (A) + fma j(A, B, C) mod 2w

three standard key sizes of the Advanced Encryp-

H←G

tion Standard (see Rijndael/AES) (128, 192, and

G←F

256 bits). The ¬rst attack known on SHA-0 is by

F←E

Chabaud and Joux [2]. They show that in about

E ← D + T1 mod 2w

261 evaluations of the compression function it is

D←C

possible to ¬nd two messages hashing to the same

C←B

value whereas a brute-force attack exploiting the

B← A

birthday paradox requires about 280 evaluations

A ← T1 + T2 mod 2w

in theory. In 2004, Biham and Chen introduce the

neutral bit technique and ¬nd near-collisions on

where 0 and 1 again represent linear combina- the compression function of SHA-0 [1] as well as

tions of three rotated values of the input variable collisions on reduced-round versions of SHA-1. In

and Ki is a different w-bit constant for each step August 2004, Joux, Carribault, Jalby and Lemuet

i. Finally, the output value of each chaining vari- [6] ¬rst provide a full collision on SHA-0 using two

able is added to the previous intermediate hash four-block messages and requiring a complexity of

251 compression function computations. In Febru-

value according to the Davies“Meyer construction

to give the new intermediate hash value. When ary 2005, Wang, Yin and Yu [10] announce full col-

lisions on SHA-0 in 239 hash operations and report

all consecutive message blocks have been hashed,

the last intermediate hash value is the ¬nal over- that collisions on SHA-1 can be obtained in less

than 269 hash operations. Saarinen [9] addresses

all hash value.

Shamir™s threshold scheme 567

the existence of slid pairs in SHA-1. The ¬rst se- (see threshold cryptography). An (n, k)-threshold

curity analysis on SHA-256, SHA-384 and SHA- scheme is a particular case of secret sharing

512 in 2003 is by Gilbert and Handschuh [3]. They scheme when any set of k or more participants

show that collisions can be found with a reduced can recover the secret exactly while any set of less

work factor for weakened variants of these func- than k particiants gains no additional, i.e. a pos-

tions. Subsequently, Hawkes and Rose show that teriori, information about the secret. Such thresh-

second pre-image attacks are far easier than ex- old schemes are called perfect and they were con-

pected on SHA-256 [4]. However these observa- structed in [2] and [1]. Shamir™s construction is the

tions do not lead to actual attacks in 2004. following.

Assume that the set S0 of secrets is some

Helena Handschuh ¬nite ¬eld GF(q) of q elements (q should be

prime power) and that the number of partici-

pants of SSS n < q. The dealer chooses n differ-

References

ent nonzero elements (points) x1 , . . . , xn ∈ GF(q),

which are publicly known. To distribute a se-

[1] Biham, E. and R. Chen (2004). “Near-collisions of

cret s0 the dealer generates randomly coef¬cients

SHA-0.” Advances in Cryptology”CRYPTO 2004,

g1 , . . . , gk’1 ∈ GF(q), forms the polynomial g(x) =

Lecture Notes in Computer Science, vol. 3152, ed.

s0 + g1 x + · · · + gk’1 x k’1 of degree less than k and

M. Franklin. Springer-Verlag, Berlin, 290“305.

sends to the i-th articipant the share si = g(xi ).

[2] Chabaud, F. and A. Joux (1998). “Differential

Clearly any k participants can recover the whole

collisions in SHA-0.” Advances in Cryptology”

polynomial g(x) and, in particular, its zero coef-

CRYPTO™98, Lecture Notes in Computer Sci-

ence, vol. 1462, ed. H. Krawczyk. Springer-Verlag, ¬cient (or g(0)), since any polynomial of degree

l is uniquely determined by its values in l + 1

Berlin, 56“71.

[3] Gilbert, H. and H. Handschuh (2004). “Security points and Lagrange interpolation formula shows

analysis of SHA-256 and sisters.” Selected Areas in how to determine it. On the other hand, the point

Cryptography”SAC 2003, Lecture Notes in Com-

0 can be considered as an “evaluation point” x0 ,

puter Science, vol. 3006, eds. M. Matsui and R.

corresponding to the dealer, since s0 = g(0). Then

Zuccherato. Springer-Verlag, Berlin, 175“193.

the above consideration shows that for any given