Sha

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

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): 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.

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 Itanium2 processors . On 17 August 2004, at the Rump Session of CRYPTO 2004, preliminary results were announced by Wang, Feng, Lai, and Yu, that attack MD5, SHA-0 and other hash functions. The complexity of their attack on SHA-0 is 2⁴⁰, so this is significantly better than the attack by Joux et al. See also MD5 security. A short summary of the Rump Session can be found at and in discussions on sci.crypt, e.g. . One of these may be the problem NSA noted, and which caused withdrawal of SHA-0 and release of SHA-1.

In the light of these results, some experts suggest that plans for the use of SHA-1 in new cryptosystems should be reconsidered.

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. The Fritz-chip will probably use SHA-1 hashes to implement DRM in PCs.

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.

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: Instead of the formulation from FIPS PUB 180-1 shown, the following may be used for improved efficiency:

See also

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

References

• Eli Biham, Rafi Chen, Near-Collisions of SHA-0, Cryptology ePrint Archive, Report 2004/146, 2004 (to appear CRYPTO 2004)
• 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