Stupid Compiler

Notes on things about stuff

[SHA, Right] The Algorithm

leave a comment »

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:

  1. 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.
  2. The five state variables are initialized to fixed constants:
    A = 0x67452301
    B = 0xefcdab89
    C = 0x98badcfe
    D = 0x10325476
    E = 0xc3d2e1f0
    
  3. 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])
    
  4. 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:

  1. Divide the 512-bit message block, M, into 16 32-bit words W_0, W_1, \ldots, W_15.
  2. 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}
  3. Initialize the state variables, A, B, C, D, E, using h
  4. 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.
  5. 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.
Advertisements

Written by dionthegod

April 29, 2008 at 5:42 am

Posted in Uncategorized

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: