SHA-1

SHA-1 (Secure Hash Algorithm) is a message digest algorithm (and cryptographic hash function) designed by the National Security Agency (NSA) and published by the National Institute of Standards and Technology (NIST). It produces a 160-bit digest from a message with a maximum size of 2^64 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.

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 the 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 the NSA, to correct a flaw in the original algorithm which reduced its cryptographic security. However, the NSA did not provide any further explanation. Much later, at the Crypto conference of 1998, two French researchers, F. Chabaud and A. Joux, presented an attack on SHA-0. Their attack did not work on SHA-1. This might, or might not, be the flaw discovered by the NSA. SHA-1 has been very closely examined by the public cryptographic community and no cryptographic insecurities have yet been found. It is therefore considered to be quite secure.

The 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 yet received as much scrutiny by the public cryptographic community as SHA-1 has, and so their cryptographic security is not yet as assured.

SHA-1, 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.

Pseudocode for the SHA-1 algorithm follows:

 (Initialize variables:) 
 a = h0 = 0x67452301
 b = h1 = 0xEFCDAB89
 c = h2 = 0x98BADCFE
 d = h3 = 0x10325476
 e = h4 = 0xC3D2E1F0
 (Pre-processing:)
 paddedmessage = (message) append 1
 while length(paddedmessage) < 512n - 64:
   paddedmessage = paddedmessage append 0
 paddedmessage = paddedmessage append (length(message) in 64-bit format)
 (Process the message in successive 512-bit chunks:) 
 while 512-bit chunk(s) remain(s):
   break the current chunk into sixteen 32-bit words w(i), 0 <= i <= 15
   (Extend the sixteeen 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
   (Main loop:)
   for i from 0 to 79:
     temp = (a leftrotate 5) + f(b,c,d) + e + k + w(i) (note: all addition is mod 2^32)
       where:
       (0 <= i <= 19): f(b,c,d) = (b and c) or ((not b) and d), k = 0x5A827999
       (20 <= i <= 39): f(b,c,d) = (b xor c xor d), k = 0x6ED9EBA1
       (40 <= i <= 59): f(b,c,d) = (b and c) or (b and d) or (c and d), k = 0x8F1BBCDC
       (60 <= i <= 79): f(b,c,d) = (b xor c xor d), k = 0xCA62C1D6
     e = d
     d = c
     c = b leftrotate 30
     b = a
     a = temp
   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

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

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

See also: RIPEMD-160, MD5.

External Links

• FIPS PUB 180-2, Secure Hash Standard, http://csrc.nist.gov/encryption/tkhash.html
• RFC 3174, US Secure Hash Algorithm 1 (SHA1), http://www.ietf.org/rfc/rfc3174.txt