[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.

$compress(M, h)$ is computed as:

Divide the 512-bit message block, M, into 16 32-bit words $W_0, W_1, \ldots, W_15$ .
Expand the 16 words into 80 words using the expansion function defined by the recurrence relation:
$W_i = W_{i-3} \oplus W_{i-8} \oplus W_{i-14} \oplus W_{i-16}$
Initialize the state variables, $A, B, C, D, E$ , using $h$
For each word in W, $W_i$ , compute the new state as:
$\begin{align*}A_{i+1} &= (W_i + A_i \lll 5 + f_i(B_i, C_i, D_i) + E_i + K_i) \mod 2^{32}\\B_{i+1} &= A_i\\C_{i+1} &= B_i \lll 30\\D_{i+1} &= C_i\\E_{i+1} &= D_i\end{align*}$
The function $f_i(B,C,D)$ is defined below.
The output is given as:
$(A_0 + A_80, B_0 + B_80, C_0 + C_80, D_0 + D_80, E_0 + E_80)$

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.

Written by dionthegod

April 29, 2008 at 5:42 am

Posted in Uncategorized

Stupid Compiler