The SHA (Secure Hash Algorithm) family is a set of related cryptographic hash functions designed by the National Security Agency (NSA) and published by the National Institute of Standards and Technology (NIST). The first member of the family, published in 1993, is officially called SHA. However, today, it is often unofficially called SHA-0 to avoid confusion with its successors. Two years later, SHA-1, the first successor to SHA, was published. Four more variants, have since been published with increased output ranges and a slightly different design: SHA-224, SHA-256, SHA-384, and SHA-512 (all are sometimes referred to as SHA-2).

SHA-0 and SHA-1

One iteration within the SHA-1 compression function. A, B, C, D and E are 32-bit words of the state; F is a nonlinear function that varies; <<< denotes left circular shift. K_t is a constant.

The original specification of the algorithm was published in 1993 as the Secure Hash Standard, FIPS PUB 180. This version is now often referred to as "SHA-0". It was withdrawn by NSA shortly after publication and was superseded by the revised version, published in 1995 in FIPS PUB 180-1 and commonly referred to as "SHA-1". This was done, according to NSA, to correct a flaw in the original algorithm which reduced its cryptographic security. However, NSA did not provide any further explanation or identify what flaw was corrected. In 1998, an attack on SHA-0 was found which did not apply to SHA-1 — it is unknown whether this is the flaw discovered by NSA, but it does give some indication that the change improved the security. SHA-1 has been very closely examined by the public cryptographic community, and no attacks have been found. In 2004, however, a number of attacks were reported on cryptographic hash functions with a similar structure to SHA-1; this has raised questions about the long-term security of SHA-1.

SHA-0 and SHA-1 produce a 160-bit digest from a message with a maximum size of 2⁶⁴ bits, and is based on principles similar to those used by Professor Ronald L. Rivest of MIT in the design of the MD4 and MD5 message digest algorithms.

Cryptanalysis of SHA-0

At CRYPTO 98, two French researchers presented an attack on SHA-0 (Chabaud and Joux, 1998 (http://springerlink.metapress.com/link.asp?id=p795v6nj1vj525kp)): collisions can be found with complexity 2⁶¹; less than the 2⁸⁰ for an ideal hash function of the same size.

In 2004, Biham and Chen found near-collisions for SHA-0 — two messages that hash to nearly the same value; in this case, 142 out of the 160 bits are equal. They also found full collisions of SHA-0 reduced to 62 out of its 80 rounds.

Subsequently, on 12 August 2004, a collision for the full SHA-0 algorithm was announced by Joux, Carribault, Lemuet and Jalby. This was done by using a generalization of the Chabaud and Joux attack. Finding the collison had complexity 2⁵¹ and took about 80,000 CPU hours on a supercomputer with 256 Itanium 2 processors.

On 17 August 2004, at the Rump Session of CRYPTO 2004, preliminary results were announced by Wang, Feng, Lai, and Yu, about an attack on MD5, SHA-0 and other hash functions. The complexity of their attack on SHA-0 is 2⁴⁰, significantly better than the attack by Joux et al [1] (http://www.freedom-to-tinker.com/archives/000664.html), [2] (http://groups.google.com/groups?selm=fgrieu-05A994.05060218082004%40individual.net).

One of these attacks on SHA-0 may be the problem NSA noted, and which caused withdrawal of SHA-0 and release of SHA-1.

Cryptanalysis of SHA-1

In the light of the results on SHA-0, some experts suggested that plans for the use of SHA-1 in new cryptosystems should be reconsidered. After the results were published, NIST announced that they planned to phase out the use of SHA-1 by 2010 in favour of the SHA-2 variants [3] (http://csrc.nist.gov/hash_standards_comments.pdf).

In 2005, Rijmen and Oswald published an attack on a reduced version of SHA-1 — 53 out of 80 rounds — which finds collisions with a complexity of less than 2⁸⁰ operations [4] (http://eprint.iacr.org/2005/010).

Longer variants

NIST has published three additional variants of SHA, each with longer digests. These are named after their digest lengths (in bits): "SHA-256", "SHA-384", and "SHA-512". They were first published in 2001 in the draft FIPS PUB 180-2, at which time review and comment were accepted. FIPS PUB 180-2, which also includes SHA-1, was released as an official standard in 2002. These new hash functions have not received as much scrutiny by the public cryptographic community as SHA-1 has, and so their cryptographic security is not yet as well-established. In February 2004, a change notice was published for FIPS PUB 180-2, specifying an additional variant, "SHA-224", defined to match the key length of two-key Triple DES.

Gilbert and Handschuh (2003) have studied the newer variants and found no weaknesses. The consequences of the Wang, Feng, et al paper in August of 2004 for these SHA variants is not entirely clear as of September 2004.

Applications

SHA-1, SHA-224, SHA-256, SHA-384, and SHA-512 are the required secure hash algorithms for use in U.S. Federal applications, including use by other cryptographic algorithms and protocols, for the protection of sensitive unclassified information. FIPS PUB 180-1 also encouraged adoption and use of SHA-1 by private and commercial organizations.

A prime motivation for the publication of the Secure Hash Algorithm was the Digital Signature Standard, in which it is incorporated.

The SHA hash functions have been used as the basis for the SHACAL block ciphers.

The copy prevention system of Microsoft's Xbox game console relies on the security of SHA-1.

SHA1 hashes

The following are some examples of SHA1 digests:

SHA1("The quick brown fox jumps over the lazy dog") = 2fd4e1c67a2d28fced849ee1bb76e7391b93eb12

Even a small change in the message will (with overwhelming probability) result in a completely different hash, e.g. changing d to c:

SHA1("The quick brown fox jumps over the lazy cog") = de9f2c7fd25e1b3afad3e85a0bd17d9b100db4b3

The hash of a zero-length string is:

SHA1("") = da39a3ee5e6b4b0d3255bfef95601890afd80709

A description of SHA-1

Pseudocode for the SHA-1 algorithm follows:

 Note: All variables are unsigned 32 bits and wrap modulo 2^32 when calculating Initialize variables: h0 := 0x67452301 h1 := 0xEFCDAB89 h2 := 0x98BADCFE h3 := 0x10325476 h4 := 0xC3D2E1F0 Pre-processing: append "1" bit to message append "0" bits until message length ≡ 448 (mod 512) append length of message as 64-bit big-endian integer to message Process the message in successive 512-bit chunks: break message into 512-bit chunks for each chunk break chunk into sixteen 32-bit big-endian words w(i), 0 ≤ i ≤ 15 Extend the sixteen 32-bit words into eighty 32-bit words: for i from 16 to 79 w(i) := (w(i-3) xor w(i-8) xor w(i-14) xor w(i-16)) leftrotate 1 Initialize hash value for this chunk: a := h0 b := h1 c := h2 d := h3 e := h4 Main loop: for i from 0 to 79 if 0 ≤ i ≤ 19 then f := (b and c) or ((not b) and d) k := 0x5A827999 else if 20 ≤ i ≤ 39 f := b xor c xor d k := 0x6ED9EBA1 else if 40 ≤ i ≤ 59 f := (b and c) or (b and d) or (c and d) k := 0x8F1BBCDC else if 60 ≤ i ≤ 79 f := b xor c xor d k := 0xCA62C1D6 temp := (a leftrotate 5) + f + e + k + w(i) e := d d := c c := b leftrotate 30 b := a a := temp Add this chunk's hash to result so far: h0 := h0 + a h1 := h1 + b h2 := h2 + c h3 := h3 + d h4 := h4 + e digest = hash = h0 append h1 append h2 append h3 append h4 (expressed as big-endian) 

Note: Instead of the formulation from the original FIPS PUB 180-1 shown, the following may be used for improved efficiency:

 (0 ≤ i ≤ 19): f := d xor (b and (c xor d)) (40 ≤ i ≤ 59): f := (b and c) or (d and (b or c)) 

See also

• RIPEMD-160
• MD5
• Topics in cryptography
• Hashcash
• Digital timestamping

References

• Eli Biham, Rafi Chen, Near-Collisions of SHA-0, Cryptology ePrint Archive, Report 2004/146, 2004 (to appear CRYPTO 2004) [5] (http://eprint.iacr.org/2004/146/)
• Florent Chabaud, Antoine Joux: Differential Collisions in SHA-0. CRYPTO 1998. pp56–71
• Henri Gilbert, Helena Handschuh: Security Analysis of SHA-256 and Sisters. Selected Areas in Cryptography 2003: pp175–193

External links

• FIPS PUB 180-2 (http://csrc.nist.gov/encryption/tkhash.html), Secure Hash Standard
• RFC 3174 (http://www.ietf.org/rfc/rfc3174.txt), US Secure Hash Algorithm 1 (SHA1)
• Online SHA1 and MD5 calculator (http://www.xml-dev.com/blog/sha1.php)
• A Javascript SHA-1 calculator showing intermediate values in the calculation (http://www.cs.eku.edu/faculty/styer/460/Encrypt/JS-SHA1.html) (note that this does not work in Safari due to a bug in the JavaScript interpreter)
• Collision Found in SHA-0 (http://www.md5crk.com/sha0col/)
• Jacksum (http://www.jonelo.de/java/jacksum/index.html) (a program with various message verification functions, supporting SHA-1 and three variants of SHA-2)
• Optimized SHA-1 source code in C (GPL license) (http://www.cr0.net:8040/code/crypto/sha1/)
• Optimized SHA-256 source code in C (GPL license) (http://www.cr0.net:8040/code/crypto/sha256/)