SHA-2

The SHA-2 hash functions were developed by the US National Security Agency and published by the National Institute of Standards and Technology in the Federal Information Processing Standard FIPS PUB 180-2 in August 2002 ^[1] . This standard also includes the SHA-1 hash function, developed in 1995. In February 2004, SHA-224 was added to FIPS PUB 180-2 ^[2] . In October 2008, a new edition of the standard was released - FIPS PUB 180-3 ^[3] . In March 2012, the latest edition of FIPS PUB 180-4 was released , which added SHA-512/256 and SHA-512/224 functions based on SHA-512 (since the 64-bit architectures of the SHA-512 work faster than SHA-256) ^[4] .

In July 2006, the RFC 4634 standard "Secure US Hash Algorithms ( SHA and HMAC-SHA )" appeared, describing SHA-1 and the SHA-2 family.

The National Security Agency on behalf of the state issued a patent for SHA-2 ^[5] under the Royalty-free license ^[6] .

General Description

The SHA-2 family hash functions are based on the Merkle-Damgora structure .

The initial message after the addition is divided into blocks, each block - into 16 words. The algorithm passes each message block through a loop with 64 or 80 iterations (rounds). At each iteration, 2 words are converted; the remaining function sets the conversion function. The results of processing each block are added up; the sum is the value of the hash function. However, the initialization of the internal state is the result of processing the previous block. Therefore, it is impossible to independently process blocks and add results. See pseudocode for more details.

The algorithm uses the following bit operations:

• ǁ - concatenation ,
• + - addition ,
• and - bitwise "and"
• xor - exclusive "OR"
• shr (shift right) - logical right shift ,
• rotr (rotate right) - cyclic shift to the right .

Hash Comparison

The following table shows some of the technical specifications for the various SHA-2 variants. “Internal state” means an intermediate hash sum after processing the next data block:

SHA-256

  Explanations: 
   All variables are unsigned, have a size of 32 bits and are summed modulo 2 32 during calculations. 
   message - the original binary message 
   m - converted message

   Variable initialization 
   (the first 32 bits of the fractional parts of the square roots of the first eight prime numbers [from 2 to 19]):
 h0: = 0x6A09E667
 h1: = 0xBB67AE85
 h2: = 0x3C6EF372
 h3: = 0xA54FF53A
 h4: = 0x510E527F
 h5: = 0x9B05688C
 h6: = 0x1F83D9AB
 h7: = 0x5BE0CD19

 Constant table
 (the first 32 bits of the fractional parts of the cubic roots of the first 64 primes [from 2 to 311]):
 k [0..63]: =
    0x428A2F98, 0x71374491, 0xB5C0FBCF, 0xE9B5DBA5, 0x3956C25B, 0x59F111F1, 0x923F82A4, 0xAB1C5ED5,
    0xD807AA98, 0x12835B01, 0x243185BE, 0x550C7DC3, 0x72BE5D74, 0x80DEB1FE, 0x9BDC06A7, 0xC19BF174,
    0xE49B69C1, 0xEFBE4786, 0x0FC19DC6, 0x240CA1CC, 0x2DE92C6F, 0x4A7484AA, 0x5CB0A9DC, 0x76F988DA,
    0x983E5152, 0xA831C66D, 0xB00327C8, 0xBF597FC7, 0xC6E00BF3, 0xD5A79147, 0x06CA6351, 0x14292967,
    0x27B70A85, 0x2E1B2138, 0x4D2C6DFC, 0x53380D13, 0x650A7354, 0x766A0ABB, 0x81C2C92E, 0x92722C85,
    0xA2BFE8A1, 0xA81A664B, 0xC24B8B70, 0xC76C51A3, 0xD192E819, 0xD6990624, 0xF40E3585, 0x106AA070,
    0x19A4C116, 0x1E376C08, 0x2748774C, 0x34B0BCB5, 0x391C0CB3, 0x4ED8AA4A, 0x5B9CCA4F, 0x682E6FF3,
    0x748F82EE, 0x78A5636F, 0x84C87814, 0x8CC70208, 0x90BEFFFA, 0xA4506CEB, 0xBEF9A3F7, 0xC67178F2

 Preliminary processing:
 m: = message ǁ [ unit bit ]
 m: = m ǁ [k zero bits ], where k is the smallest non-negative number such that  
                   (L + 1 + K) mod 512 = 448, where L is the number of bits in the message ( comparable modulo 512 c 448)
 m: = m ǁ Length (message) - the length of the original message in bits as a 64-bit number 
              with byte order from high to low

 Further, the message is processed in successive chunks of 512 bits:
 break the message into pieces of 512 bits
 for each piece
     break a chunk into 16 words 32 bits long (with the order of bytes from high to low within a word): w [0..15]

     Generate an additional 48 words:
     for i from 16 to 63
         s0: = (w [i-15] rotr 7) xor (w [i-15] rotr 18) xor (w [i-15] shr 3)
         s1: = (w [i-2] rotr 17) xor (w [i-2] rotr 19) xor (w [i-2] shr 10)
         w [i]: = w [i-16] + s0 + w [i-7] + s1

     Initialization of auxiliary variables:
     a: = h0
     b: = h1
     c: = h2
     d: = h3
     e: = h4
     f: = h5
     g: = h6
     h: = h7

     Main loop:
     for i from 0 to 63
         Σ0: = (a rotr 2) xor (a rotr 13) xor (a rotr 22)
         Ma: = (a and b) xor (a and c) xor (b and c)
         t2: = Σ0 + Ma
         Σ1: = (e rotr 6) xor (e rotr 11) xor (e rotr 25)
         Ch: = (e and f) xor (( not e) and g)
         t1: = h + Σ1 + Ch + k [i] + w [i]

         h: = g
         g: = f
         f: = e
         e: = d + t1
         d: = c
         c: = b
         b: = a
         a: = t1 + t2

     Add the obtained values ​​to the previously calculated result:
     h0: = h0 + a
     h1: = h1 + b 
     h2: = h2 + c
     h3: = h3 + d
     h4: = h4 + e
     h5: = h5 + f
     h6: = h6 + g 
     h7: = h7 + h

 Get the final hash value:
 digest = hash = h0 ǁ h1 ǁ h2 ǁ h3 ǁ h4 ǁ h5 h6 ǁ h7

SHA-224 is identical to SHA-256 , except for:

• to initialize the variables h0 - h7 , other initial values ​​are used,
• in the final hash, the value h7 omitted.

  The initial values ​​of the variables h0 - h7 in SHA-224:
 h0: = 0xC1059ED8
 h1: = 0x367CD507
 h2: = 0x3070DD17
 h3: = 0xF70E5939
 h4: = 0xFFC00B31
 h5: = 0x68581511
 h6: = 0x64F98FA7
 h7: = 0xBEFA4FA4

SHA-512 has an identical structure, but:

• words are 64 bits long
• 80 rounds are used instead of 64,
• the message is divided into chunks of 1024 bits,
• initial values ​​of variables and constants are extended to 64 bits,
• the constants for each of the 80 rounds are the 80 first primes,
• the shift in the rotr and shr operations is made to a different number of positions.

  The initial values ​​of the variables h0 - h7 in SHA-512:
 h0: = 0x6a09e667f3bcc908, 
 h1: = 0xbb67ae8584caa73b, 
 h2: = 0x3c6ef372fe94f82b, 
 h3: = 0xa54ff53a5f1d36f1, 
 h4: = 0x510e527fade682d1, 
 h5: = 0x9b05688c2b3e6c1f, 
 h6: = 0x1f83d9abfb41bd6b, 
 h7: = 0x5be0cd19137e2179

SHA-384 is identical to SHA-512, except for:

• the variables h0 - h7 have different initial values,
• in the final hash, the values ​​of h6 and h7 omitted.

  The initial values ​​of the variables h0 - h7 in SHA-384 
  (the first 64 bits of the fractional parts of the square roots of the primes from the 9th to the 16th [from 23 to 53]):
 h0: = CBBB9D5DC1059ED8
 h1: = 629A292A367CD507
 h2: = 9159015A3070DD17
 h3: = 152FECD8F70E5939
 h4: = 67332667FFC00B31
 h5: = 8EB44A8768581511
 h6: = DB0C2E0D64F98FA7
 h7: = 47B5481DBEFA4FA4

SHA-512/256 is identical to SHA-512, except for:

• the variables h0 - h7 have different initial values,
• the resulting hash is trimmed to the left 256 bits.

  The initial values ​​of the variables h0 - h7 in SHA-512/256 :
 h0: = 22312194FC2BF72C
 h1: = 9F555FA3C84C64C2
 h2: = 2393B86B6F53B151
 h3: = 963877195940EABD
 h4: = 96283EE2A88EFFE3
 h5: = BE5E1E2553863992
 h6: = 2B0199FC2C85B8AA
 h7: = 0EB72DDC81C52CA2

SHA-512/224 is identical to SHA-512, except for:

• the variables h0 - h7 have different initial values,
• the resulting hash is trimmed to the left 224 bits.

  The initial values ​​of the variables h0 - h7 in SHA-512/224 :
 h0: = 8C3D37C819544DA2
 h1: = 73E1996689DCD4D6
 h2: = 1DFAB7AE32FF9C82
 h3: = 679DD514582F9FCF
 h4: = 0F6D2B697BD44DA8
 h5: = 77E36F7304C48942
 h6: = 3F9D85A86A1D36C8
 h7: = 1112E6AD91D692A1

The following are examples of SHA-2 hashes. All messages imply the use of ASCII encoding.

  SHA-224 (" The quick brown fox jumps over the lazy dog ") 
  = 730E109B D7A8A32B 1CB9D9A0 9AA2325D 2430587D DBC0C38B AD911525

  SHA-256 ("The quick brown fox jumps over the lazy dog") 
  = D7A8FBB3 07D78094 69CA9ABC B0082E4F 8D5651E4 6D3CDB76 2D02D0BF 37C9E592

  SHA-384 ("The quick brown fox jumps over the lazy dog") 
  = CA737F10 14A48F4C 0B6DD43C B177B0AF D9E51693 67544C49 4011E331 7DBF9A50
    9CB1E5DC 1E85A941 BBEE3D7F 2AFBC9B1

  SHA-512 ("The quick brown fox jumps over the lazy dog") 
  = 07E547D9 586F6A73 F73FBAC0 435ED769 51218FB7 D0C8D788 A309D785 436BBB64
    2E93A252 A954F239 12547D1E 8A3B5ED6 E1BFD709 7821233F A0538F3D B854FEE6

  SHA-512/256 ("The quick brown fox jumps over the lazy dog") 
  = DD9D67B3 71519C33 9ED8DBD2 5AF90E97 6A1EEEFD 4AD3D889 00 subway32F C5BEF04D

  SHA-512/224 ("The quick brown fox jumps over the lazy dog") 
  = 944CD284 7FB54558 D4775DB0 485A5000 3111C8E5 DAA63FE7 22C6AA37

The slightest change in the message in most cases leads to a completely different hash due to the avalanche effect . For example, changing dog to cog will cog :

  SHA-256 ("The quick brown fox jumps over the lazy cog") 
  = E4C4D8F3 BF76B692 DE791A17 3E053211 50F7A345 B46484FE 427F6ACC 7ECC81BE

In 2003, Gilbert and Handshuh conducted a SHA-2 study, but did not find any vulnerabilities. ^[8] However, in March 2008, Indian researchers Somitra Kumar Sanadia and Palash Sarkar published their collisions for 22 iterations of SHA-256 and SHA-512 . ^[9] In September of the same year, they presented a method for constructing collisions for truncated SHA-2 variants (21 iterations). ^{[10] [11]} Later collision design methods were found for 31 iterations of SHA-256 ^[12] and for 27 iterations of SHA-512 ^[13] .

Cryptanalysis of the hash function implies a study of the stability of the algorithm with respect to at least the following types of attacks:

• finding collisions , that is, different messages with the same hash,
• finding a type , that is, an unknown message by its hash.

The security of the electronic digital signature using this hash algorithm depends on the stability of the hash function to find collisions. Security of storing password hashes for authentication purposes depends on resistance to finding a prototype.

Due to the algorithmic similarity of SHA-2 with SHA-1 and the presence of potential vulnerabilities in the latter, it was decided that SHA-3 will be based on a completely different algorithm. ^{[14] [15]} On October 2, 2012, NIST approved Keccak as SHA-3.

See also Hash Application.

SHA-224 , SHA-256 , SHA-384 , SHA-512 , SHA-512/256, and SHA-512/224 are allowed by the US law in some government applications, including the use of other cryptographic algorithms and protocols to protect information without a secrecy bar. The standard also allows the use of SHA-2 by private and commercial organizations. ^[sixteen]

The SHA-2 hash functions are used to verify data integrity and in various cryptographic schemes. For 2008, the SHA-2 family of hash functions is not as widespread as MD5 and SHA-1 ^[17] , despite the flaws found in the latter.

Some examples of using SHA-2 are listed in the table:

Studies ^[25] showed that the SHA-2 algorithms work 2-3 times slower than other popular hash algorithms MD5 , SHA-1 , Tiger and RIPEMD-160 .

Certification

Implementations of SHA-2 , like all Federal Information Processing Standards, can be certified for use in some applications in the United States. Certification takes place in the framework of the , which is conducted by the US National Institute of Standards and Technology in conjunction with the Canadian Communications Security Bureau.

As of November 5, 2008, more than 250 implementations of SHA-2 were certified, four of which could operate on messages with a length in bits not a multiple of eight. ^[26]

Certified by FIPS PUB 180-4, CRYPTREC and NESSIE .

• MD5
• SHA-1
• Hash Collision
• Federal Information Processing Standards
• Hashing

• Laponina O.R. Cryptographic security fundamentals . - M .: Internet University of Information Technologies - INTUIT.ru, 2004. - P. 320. - ISBN 5-9556-00020 -5.
• Nils Ferguson , Bruce Schneier . Practical Cryptography = Practical Cryptography: Designing and Implementing Secure Cryptographic Systems. - M .: Dialectics, 2004. - 432 p. - 3000 copies - ISBN 5-8459-0733-0 , ISBN 0-4712-2357-3 .
• Analysis of the truncated version of SHA-256 (inaccessible link) (English)
• Collisions of the truncated version of SHA-256 (English)
• Nonlinear attacks on truncated SHA-2 hash functions (eng.)
• Deterministic collision construction for a 21-iteration SHA-2 hash family (eng.)

• FIPS 180-3 : Secure Hash Standard (SHS)
• RFC 3874 : A 224-bit One-way Hash Function: SHA-224
• RFC 4634 : US Secure Hash Algorithms (SHA and HMAC-SHA)