Secure Hash Algorithm

from Wikipedia, the free encyclopedia

The term Secure Hash Algorithm ( SHA for short , English for secure hash algorithm ) describes a group of standardized cryptological hash functions . These are used to calculate a test value for any digital data (messages) and are, among other things, the basis for creating a digital signature .

The check value is used to ensure the integrity of a message. If two messages result in the same check value, the equality of the messages should be guaranteed according to normal discretion, without prejudice to targeted attempts at manipulation of the messages. This is why a cryptological hash function is required to be collision-proof : it should be practically impossible to generate two different messages with the same check value.

History - SHA / SHA-0

The National Institute of Standards and Technology (NIST) together with the National Security Agency (NSA) developed a hash function as part of the Digital Signature Algorithm (DSA) for the Digital Signature Standard (DSS). The feature was released in 1993. This referred to as a Secure Hash Standard (SHS) standard specifies the secure hash algorithm (SHA) with a hash value of 160  bit length for any digital data of a maximum of 2 64  - 1 bit (≈ 2  Exbibyte ) length.

Like the MD4 and MD5 developed by Ronald L. Rivest , SHA is a Merkle-Damgård construction with a Davies-Meyer compression function, and the compression function is also constructed similarly to these. With its longer hash value of 160 bits compared to 128 bits for MD4 and MD5, however, SHA is more resistant to brute force attacks to find collisions.

The message is with an end piece extends encoding the length of the original message. Then it is divided into 512-bit long blocks, which are processed one after the other. For this purpose, an internal data block of 160 bits is encrypted using block encryption, with the message block as the key. The plain text is then added word by word modulo to the ciphertext. The data block calculated in this way is now encrypted with the next message block or output as a hash value after the last message block has been incorporated.

SHA-1

Build a round of SHA-0 and SHA-1

The original SHA was corrected as early as 1995 due to a "design error" and therefore hardly played a role in practice. It is known today as SHA-0 , the corrected variant as SHA-1 .

The correction consists only in a small detail ( rotation of a data word in the key classification), but not in the number of rounds run through or other measures that immediately suggest a significantly higher level of security. However, the cryptanalysis confirms that the rotation makes the calculation of collisions much more difficult.

weaknesses

On February 15, 2005, cryptography expert Bruce Schneier reported on his blog that scientists Xiaoyun Wang, Yiqun Lisa Yin and Hongbo Yu from Shandong University in China had successfully broken SHA-1. They succeeded in reducing the effort involved in calculating the collision from 2 80 to 2 69 . 2 69 calculations could possibly be carried out with high-performance computers.

A short time later, on 17 August 2005, was designed by Xiaoyun Wang, Andrew Yao and Frances Yao at the conference in 2005 CRYPTO presented another, more efficient collision attack on SHA-1, which the computational effort on two 63 reduced.

In August 2006, a far more serious attack against SHA-1 was presented at CRYPTO 2006. Up to 25% of the forged message can be freely selected. In previous collision attacks , the so-called hash twins were only formed with meaningless letter combinations of the plain text. These were easily recognizable.

A critical attack scenario requires that attackers create a second, partially meaningful variant of a document that gives the same SHA-1 value and thus the same signature. The 75% meaningless characters (i.e. garbage) that remain after the attack can be technically hidden from untrained viewers. The attacker can claim that the counterfeit variant was signed instead of the original variant.

In October 2015, Marc Stevens, Pierre Karpman and Thomas Peyrin published a freestart collision for the compression function of SHA1. This meant that previous estimates of when it would be possible to find chosen-prefix collisions for forging TLS certificates for SHA-1 due to increasing computing power and at what cost were no longer applicable. They recommended moving from SHA-1 to SHA-2 or SHA-3 as soon as possible.

In February 2017, Google employees published a first collision of SHA-1. They created two different functioning PDF files with the same SHA-1 check value with enormous effort. A single CPU would have taken around 6500 years to do this.
In 2019, publicly known chosen prefix attacks required 2 66.9 to 2 69.4 SHA-1 calculations to find collisions. In 2017, this corresponded to 100 GPU years of computing capacity.

recommendations

In response to the known attacks against SHA-1, the National Institute of Standards and Technology (NIST) held a workshop in October 2005 in which the current status of cryptological hash functions was discussed. NIST recommends moving from SHA-1 to hash functions of the SHA-2 family (SHA-224, SHA-256, SHA-384, SHA-512). In the long term, these are to be replaced by the new SHA-3 standard . In October 2015, Bruce Schneier recommended moving to SHA-3.

Example hashes

SHA1("Franz jagt im komplett verwahrlosten Taxi quer durch Bayern")
 = 68ac906495480a3404beee4874ed853a037a7a8f

A typing error (G instead of F) changes the text by only one bit (ASCII code 0x47 instead of 0x46): 

SHA1("Granz jagt im komplett verwahrlosten Taxi quer durch Bayern")
 = 89fdde0b28373dc4f361cfb810b35342cc2c3232

A small change in the message creates a completely different hash. This property is also known as the avalanche effect in cryptography .

The hash of a zero-length string is: 

SHA1("")
 = da39a3ee5e6b4b0d3255bfef95601890afd80709

Pseudocode

The pseudocode for the SHA-1 follows . 

// Beachte: Alle Variablen sind vorzeichenlose 32-Bit-Werte und
// verhalten sich bei Berechnungen kongruent (≡) modulo 2^32

// Initialisiere die Variablen:
var int h0 := 0x67452301
var int h1 := 0xEFCDAB89
var int h2 := 0x98BADCFE
var int h3 := 0x10325476
var int h4 := 0xC3D2E1F0

// Vorbereitung der Nachricht 'message':
var int message_laenge := bit_length(message)
erweitere message um bit "1"
erweitere message um bits "0" bis Länge von message in bits ≡ 448 (mod 512)
erweitere message um message_laenge als 64-Bit big-endian Integer

// Verarbeite die Nachricht in aufeinander folgenden 512-Bit-Blöcken:
für alle 512-Bit Block von message
   unterteile Block in 16 32-bit big-endian Worte w(i), 0 ≤ i ≤ 15

   // Erweitere die 16 32-Bit-Worte auf 80 32-Bit-Worte:
   für alle i von 16 bis 79
       w(i) := (w(i-3) xor w(i-8) xor w(i-14) xor w(i-16)) leftrotate 1

   // Initialisiere den Hash-Wert für diesen Block:
   var int a := h0
   var int b := h1
   var int c := h2
   var int d := h3
   var int e := h4

   // Hauptschleife:
   für alle i von 0 bis 79
       wenn 0 ≤ i ≤ 19 dann
           f := (b and c) or ((not b) and d)
           k := 0x5A827999
       sonst wenn 20 ≤ i ≤ 39 dann
           f := b xor c xor d
           k := 0x6ED9EBA1
       sonst wenn 40 ≤ i ≤ 59 dann
           f := (b and c) or (b and d) or (c and d)
           k := 0x8F1BBCDC
       sonst wenn 60 ≤ i ≤ 79 dann
           f := b xor c xor d
           k := 0xCA62C1D6
       wenn_ende

       temp := (a leftrotate 5) + f + e + k + w(i)
       e := d
       d := c
       c := b leftrotate 30
       b := a
       a := temp

   // Addiere den Hash-Wert des Blocks zur Summe der vorherigen Hashes:
   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 //(Darstellung als big-endian)

Note: Instead of the original formulation from the FIPS PUB 180-1, the following formulations can alternatively be used: 

(0 ≤ i ≤ 19): f := d xor (b and (c xor d)) (Alternative)

(40 ≤ i ≤ 59): f := (b and c) or (d and (b or c)) (Alternative 1)
(40 ≤ i ≤ 59): f := (b and c) or (d and (b xor c)) (Alternative 2)
(40 ≤ i ≤ 59): f := (b and c) + (d and (b xor c)) (Alternative 3)
(40 ≤ i ≤ 59): f := (b and c) xor (d and (b xor c)) (Alternative 4)

SHA-2

The NIST has published four other variants of the algorithm, the larger hashes produce. These are the SHA-224, SHA-256, SHA-384 and SHA-512, with the appended number indicating the length of the hash value (in bits). The SHA-512/256 and SHA-512/224 versions were added later. These further developments are often summarized under the name SHA-2. They are based on the same construction principle as SHA-1, only the internal data block has been enlarged to 256 or 512 bits and the block encryption on which the compression function is based has been modified.

The SHACAL block encryption was derived from the SHA-1 and SHA-256 algorithms . This essentially consists of the internal block encryption of SHA-1 or SHA-256, which is used here on its own.

SHA-3

Because fundamental weaknesses in the Merkle-Damgård construction were discovered in 2004, NIST looked for a new hash function that should be much more future-proof than SHA-2. It called for a competition, as it did before for the Advanced Encryption Standard (AES). The choice fell on Keccak in October 2012 , which was then standardized in August 2015 under the designation SHA-3 in various variants. SHA-3 has a fundamentally different structure than SHA-2, namely as a so-called sponge construction .

Specifications

  • RFC 3174 , US Secure Hash Algorithm 1 (SHA1) (September 2001)
  • RFC 4634 , US Secure Hash Algorithms (SHA and HMAC-SHA) (July 2006)
  • RFC 6234 , US Secure Hash Algorithms (SHA and SHA-based HMAC and HKDF) (May 2011)

See also

Web links

The weaknesses of SHA

Individual evidence

  1. ↑ Bruce Schneier : SHA-1 Broken. February 15, 2005, accessed December 10, 2011 .
  2. ↑ Xiaoyun Wang, Yiqun Lisa Yin and Hongbo Yu: Finding Collisions in the Full SHA-1 . In: CRYPTO . 2005, p. 17-36 ( PDF ).
  3. ↑ https://sites.google.com/site/itstheshappening/
  4. ↑ a b https://www.schneier.com/blog/archives/2015/10/sha-1_freestart.html
  5. ↑ Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, Yarik Markov: The first collision for full SHA-1 , shattered.io
  6. ↑ G. Leurent, T. Peyrin: From Collisions to Chosen Prefix Collisions. Application to Full SHA-1 , Inria