Dissecting an Example Standard One-Way Hash Function

How does one "encrypt" messages of different length to the hash, which is always x bits long, without even using a key? To answer the first part of the question, you XOR the data with a fixed initial value x bits long. To answer the second part of the question, the hashed data itself becomes a key; subkeys for every round are derived from the data input to the hash. We illustrate how such an algorithm can work using an example of the Secure Hashing Algorithm (SHA) designed by the NSA. A full description of the SHA standard is available at the NIST Web page at http://www.itl.nist.gov/fipspubs/fip180-1.htm. In fact, there are four SHA standards: SHA-1 (160-bit hash), SHA-256, SHA-384, and SHA-512, with hashes of name-corresponding length. In Chapter 14 we extensively use SHA when setting up a VPN to protect your wireless traffic. In this chapter, we try to make SHA iterations more understandable for the nonmathematical audience.

Essentially, SHA-1 is a block cipher that encrypts a 160-bit block (the initial constant) with a "key" (data hashed) of variable length (less than 2⁶⁴ bits) using 80 32-bit subkeys in 80 rounds.

Both SHA-1 and SHA-2 begin by converting the input to their unique representation as a multiple of 512 bits in length, keeping track of the input's original length in bits. To do it, append one to the input message. Then add as many zeros as necessary to reach the needed length, which would be the next possible length that is 64 bits less than a whole multiple of 512 bits. Finally, use these preserved 64 bits to append the original length of the message in bits.

Expand each block of 512 bits into a source of 80 32-bit subkeys using the block itself as the first 16 subkeys. All remaining subkeys are generated as follows: subkey N is the XOR of subkeys N-3, N-8, N-14, and N-16, subjected to a circular left shift of one position.

The initial 160-bit block constant value happened to be 67452301 EFCDAB89 98BADCFE 10325476 C3D2E1F0 (perhaps in ASCII it would make the name of the SHA author's cat). Use it as an input for processing 512-bit blocks of the modified hashed data.

For every message block, encipher this starting value using 80 subkeys for the current message block. Add each of the 32-bit pieces of the ciphertext result to the starting value modulo 2³² and use that result as the starting value for handling the next message block. The starting value created at the end of handling the last block is the actual hash value, which is 160 bits long.

Because we feed a 160-bit input value into SHA rounds, each block of data is divided into five pieces, instead of two halves, as in DES. An F function is run on four of the five pieces, although it is actually the XOR of a function of three of the input pieces and a circular left shift of a fourth, which is XORed with another piece. That piece is modified by being XORed with the current round's subkey and a constant. The very same constant is used over each group of 20 rounds. One of the other blocks is also altered by undergoing a circular left shift, and then the (160-bit) blocks are rotated.

The F function, as well as the constant, is changed every 20 rounds. Calling the five pieces of input a, b, c, d, and e, the rounds of the SHA block cipher component proceed as follows:

• Change a by adding the current constant to it.

• These constants are:

  
  

  
  For rounds 1 to 20: 5A827999
  
  
  
  For rounds 21 to 40: 6ED9EBA1
  
  
  
  For rounds 41 to 60: 8F1BBCDC
  
  
  
  For rounds 61 to 80: CA62C1D6
  
  

  
  

• Change a by adding the appropriate subkey for this round to it.

• Change a by adding e, circular left-shifted 5 places, to it.

• Change a by adding the main F function of b, c, and d to it. The F function is calculated as follows:

  
  

  
  For rounds 1 to 20, it is (b && c) || ((!= b) && d).
  
  
  
  For rounds 21 to 40, it is b ^= c ^= d.
  
  
  
  For rounds 41 to 60, it is (b && c) || (b && d) || (c && d).
  
  
  
  For rounds 61 to 80, it is again b ^= c ^= d.
  
  

  
  

• Change d by giving it a circular shift of 2 positions.

• Swap the pieces,by moving each piece to the next earlier one, except that the old a value ends up being moved to e.

A picture is still worth a thousand words, so Figure 12-1 shows an SHA round operation scheme.

Figure 12.1. SHA round operation scheme.

[View full size image]

Operation of SHA-256, SHA-384, and SHA-512 is similar to the SHA-1 workings. Of course, the size of the hashes is different, and SHA-384 and SHA-512 operate with 64-bit, not 32-bit, words. The input values and round constants in all types of SHA are also completely different.