SHA family

   

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. Kt is a constant.
Enlarge
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. Kt 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 264 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 261; less than the 280 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 251 and took about 80,000 CPU hours on a supercomputer with 256 Itanium2 processors [1] (http://www.md5crk.com/sha0col/). 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 240, 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 [2] (http://www.freedom-to-tinker.com/archives/000664.html) and in discussions on sci.crypt, e.g. [3] (http://groups.google.com/groups?selm=fgrieu-05A994.05060218082004%40individual.net). 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. After the results were published, NIST announced that planned to phase out the use of SHA-1 by 2010 in favour of the SHA-2 variants [4] (http://csrc.nist.gov/hash_standards_comments.pdf).

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 entire copy prevention system of Microsoft's Xbox game console relies on the security of SHA-1. If a preimage attack of either type is found against SHA-1, it will become possible for illegally copied games to run on the system without the aid of a modchip. This is just one example of ways in which companies place their livelihood in the hands of SHA-1's security.

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

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


de:Secure Hash Algorithmus zh:SHA 家族

Retrieved from "http://www.mywiseowl.com/articles/SHA_family"

This page has been accessed 1302 times. This page was last modified 00:45, 15 Nov 2004. All text is available under the terms of the GNU Free Documentation License (see Copyrights for details).