[SHA, Right] The Algorithm
SHA-0 (or something more clever here)
SHA-0 was specified in the first Secure Hash Standard (SHS) (current draft) issued in 1993. Two years later, NIST issued a small change to the SHA-0 expansion function; the new function is known as SHA-1. There was no justification for the updated function, but it is assumed the NSA found a collision attack.
Structure of the Hash Function
The SHA hash function works on blocks of 512 bits and outputs a hash value of 160 bits. The function proceeds as follows:
- Pad the message by adding a single 1 bit and then a string of 0 bits suffixed with the length (in bits) of the message without padding (represented as a 64-bit big endian integer). The number of zero bits is chosen as the minimum number to evenly pad the message to the next 512 bit boundary.
- The five state variables are initialized to fixed constants:
A = 0x67452301 B = 0xefcdab89 C = 0x98badcfe D = 0x10325476 E = 0xc3d2e1f0
- For each message block, call the compression function using the current state, A through E, and the current block. The compression function will return the new state. Pseudocode:
state[i + 1] = compress(current_block, state[i])
- The output of the function is the concatentation of the state variables. Pseudocode:
return A ++ B ++ C ++ D ++ E
The Compression Function
The compression function is where all the “good stuff” happens.
is computed as:
- Divide the 512-bit message block, M, into 16 32-bit words .
- Expand the 16 words into 80 words using the expansion function defined by the recurrence relation:
- Initialize the state variables, , using
- For each word in W, , compute the new state as:
The function is defined below.
- The output is given as:
The function "f_i(X,Y,Z)" and "K_i" are defined as: If i is in the range: [ 0, 20) "IF" f_i = (X & Y) | (X & Z) K_i = 0x5A827999 [20, 39) "XOR" f_i = X ^ Y ^ Z K_i = 0x6ED9EBA1 [40, 59) "MAJ" f_i = (X & Y) | (X & Z) | (Y & Z) K_i = 0x8F1BBCDC [60, 79) "XOR" f_i = X ^ Y ^ Z K_i = 0xCA62C1D6 NOTE: Add a link to the python implementation.