Secure Hash Algorithm

The term secure hash algorithm ( SHA, English for secure hash algorithm) refers to a group of standardized cryptologic hash functions. These are used to calculate a unique check value for any digital data (news) and are the basis for creating a digital signature.

The check value is used to ensure the integrity of a message. If two messages give the same test value, is the equality of the messages normally expect to be guaranteed, without prejudice targeted Attempts to manipulate the news. That is why we demand from a cryptologic hash function the property of collision safety: it should be virtually impossible to generate two different messages with the same test value.

• 7.1 The weaknesses of SHA

History - SHA/SHA-0

The National Institute of Standards and Technology ( NIST) developed in collaboration with the National Security Agency (NSA ), a hash function as part of the Digital Signature Algorithms (DSA ) for the Digital Signature Standard ( DSS). The function was published in 1994. This as the Secure Hash Standard (SHS ) designated standard specifies the Secure Hash Algorithm (SHA ) with a hash value of 160 bits in length for any digital data from up to 264-1 bits ( ≈ 2 Exbibyte ) length. Internal blocks of size 512 bits (64 bytes ) is used. The algorithm is similar in design, developed by Ronald L. Rivest MD4. The SHA has been corrected due to a " design flaw " in 1995 and never played because of a role. This new variant is now known as SHA -1, the original as SHA -0.

SHA-1

However, the corrected version of the SHA differs from SHA -0 only in a little more detail (left shift), not in the number of traversed rounds or other measures that can immediately expect a much higher level of security. Cryptanalysis confirmed, however, that the left shift obviously considerably complicates the calculation of a collision.

In principle, it was assumed that the same design goals as in MD4. With its longer hash value of 160 bits SHA but is more resistant to brute- force attacks to find collisions.

Weaken

On 15 February 2005, the cryptography expert Bruce Schneier reported in his blog that the scientists Xiaoyun Wang, Yiqun Lisa Yin and Hongbo Yu of Shandong University in China have successfully SHA -1 broken. They had managed to reduce the effort for collision calculation from 280 to 269. 269 ​​calculations possibly could be carried out with high-performance computers. Collisions were not published until today.

A short time later, on 17 August 2005, was presented another, more efficient collision attack on SHA- 1 of Xiaoyun Wang, Andrew Yao and Frances Yao at the CRYPTO 2005 conference, which reduces the amount of calculation to 263.

In August 2006, another, much more serious attack against SHA -1 was presented at the CRYPTO 2006, which may possibly also show in practice effects. During this attack, a part of the fake message are in the content freely chosen ( up to 25% currently). In the previous collision attack, the so-called hash twins were formed only with meaningless combinations of letters of the plaintext and were easy to spot.

A critical attack scenario assumes, however, that the attacker can create a second, at least meaningful in parts version of a document that gives the same SHA- 1 value and thus also the same signature. Whereas the new attack method currently remaining 75 % meaningless combinations of letters (ie garbage ) can be possibly technically easily hidden from the eyes of an untrained observer. The attacker can therefore say that the fake variant has been signed instead of the original version.

From 8 August 2007 to May 12, 2009 attempted a research group at the Technical University of Graz means of a distributed computing project collisions in SHA -1 algorithm to find (SHA -1 Collision Search Graz). The project was terminated due to insufficient progress.

Recommendations

In response to the become known attacks against SHA- 1, the National Institute of Standards and Technology held ( NIST) in October 2005, a workshop, in which the current state of cryptographic hash functions was discussed. NIST recommends the transition from SHA -1 to hash functions SHA -2 family (SHA -224, SHA -256, SHA -384, SHA- 512). In the long term this will be replaced by a new standard SHA -3. For this purpose, called the NIST modeled on the Advanced Encryption Standard (AES) on a tender. The final selection and appointment then fell in October 2012 on Keccak.

Example hashes

SHA1 ( " quick brown fox completely dilapidated taxi across Bavaria " )   = 68ac906495480a3404beee4874ed853a037a7a8f A small change in the message generates a completely different hash. This property is referred to in cryptography as avalanche effect.

( Changed only one letter ) with Frank instead Franz gives:

SHA1 ( " Frank chases in the completely dilapidated taxi across Bavaria " )   = d8e8ece39c437e515aa8997c1a1e94f1ed2a0e62 The hash of a string of zero length is:

SHA1 ("")   = da39a3ee5e6b4b0d3255bfef95601890afd80709 pseudocode

The following is the pseudo code for the SHA-1.

/ / Note: All variables are unsigned 32 -bit values ​​and / / Behave in calculations congruent ( ≡ ) modulo 2 ^ 32 / / Initialize the variables: var int h0: = 0x67452301 var int h1: = 0xEFCDAB89 var int h2: = 0x98BADCFE var int h3: = 0x10325476 var h4 int: = 0xC3D2E1F0 / / Preparation of the 'message' is: var int message_laenge: = BIT_LENGTH (message) Extended message to bit "1" Extended message to bits " 0" to length of message in bits ≡ 448 (mod 512) Extended message to message_laenge as a 64- bit big-endian integer / / Process the message to consecutive 512 -bit blocks: for all 512 -bit block of message     Bottoms 16 32 -bit block in big-endian words W (i), 0 ≤ i ≤ 15     / / Upgrade the 16 32 -bit words to 80 32 -bit words:     for all i 16-79         w (i ) = (W (i -3) XOR W ( i -8) XOR W ( i -14) XOR W ( i -16) ) 1 leftrotate     / / Initialize the hash value for this block:     var int a: = h0     var int b: = h1     var int c: = h2     var int d: = h3     var int e: = h4     / / Main loop:     for all i between 0 and 79         if 0 ≤ i ≤ 19 then             f: = (b and c ) or ( (not b ) and d)             k: = 0x5A827999         else if 20 ≤ i ≤ 39 then             f: = b xor c xor d             k: = 0x6ED9EBA1         else if 40 ≤ i ≤ 59 then             f: = (b and c ) or ( b and d) or ( c and d)             k: = 0x8F1BBCDC         else if 60 ≤ i ≤ 79 then             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     / / Add the hash value of the block to the sum of previous 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 / / (represented as a big-endian) Note: instead of the original formulation of the FIPS PUB 180-1 may alternatively be used as the following formulations:

(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

NIST has four additional variants of the algorithm published, generate the larger hash values ​​. It involves the SHA -224, SHA -256, SHA -384 and SHA -512 where the appended number indicates in each case the length of the hash value (in bits). These developments are often collectively referred to as SHA -2. The SHA -1 and SHA -256 are also the basis for the block cipher SHACAL.

SHA -3

Specifications

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