SHA-1, Step by Step

Pad a message, and expand its sixteen words into eighty. Step through one of the eighty steps, then finish the block.

SHA-1demo

Objectives

Describe SHA-1 padding and how its length field differs from MD5's.
Compute an expanded word from its four sources and say why the first sixteen are not computed.
Explain what the one-bit rotation in the expansion does to bit positions.
Trace one SHA-1 step, naming the function and constant that change every twenty steps.
Explain the feed-forward at the end of a block and why the steps cannot simply be run backwards.

25%

Padding, the eighty-word expansion, one of the eighty steps, and the feed-forward that closes a block.

SHA-1 pads exactly as MD5 does, with one difference: it writes the bit length with its high byte first. The rest of this page is what happens to a padded block.

The message, padded

message

the padded message, with the length field marked

0000    61  62  63  80  00  00  00  00  00  00  00  00  00  00  00  00 
0010    00  00  00  00  00  00  00  00  00  00  00  00  00  00  00  00 
0020    00  00  00  00  00  00  00  00  00  00  00  00  00  00  00  00 
0030    00  00  00  00  00  00  00  00 [00][00][00][00][00][00][00][18]

3 bytes in, 1 block of 64 bytes out. The last eight bytes hold 24 bits, most significant byte first, so the number reads left to right the way it is written. MD5 puts the same number in the same place backwards.

Sixteen words arrive from the block and eighty are needed, one per step. SHA-1 builds the missing sixty-four, each from four earlier words.

W[t] = ROTL₁(W[t−3] ⊕ W[t−8] ⊕ W[t−14] ⊕ W[t−16]), 16 ≤ t < 80

The expansion, word by word

word index t

the four sources and the word they build

W[13]   00000000
W[ 8]   00000000
W[ 2]   00000000
W[ 0]   61626380
XOR of the four61626380
W[16]   c2c4c700   (the XOR, rotated left by 1)

The first sixteen words are the message itself, so W[16] is the first word this rule produces. Move the slider up and every later word is built from words that were themselves built this way, which is how sixteen words of message reach all eighty steps.

The rotation is not decoration. Without it the rule would be a plain XOR of words at matching bit positions, and bit 7 of every expanded word would depend only on bit 7 of earlier words: thirty-two separate expansions running side by side. Rotating by one carries each dependency into a neighbouring position instead.

Five working words, eighty steps, one expanded word consumed per step. Two things change every twenty steps: the bitwise function and the additive constant.

a ← ROTL₅(a) + f(b, c, d) + e + K + W[t], c ← ROTL₃₀(b)

Step 1 of 80

step

function Ch

K = 5a827999

W[0] = 61626380

the working words, before and after

                a        b        c        d        e
before          67452301 efcdab89 98badcfe 10325476 c3d2e1f0
after           0116fc33 67452301 7bf36ae2 98badcfe 10325476

Only a is computed and only c is rotated; the other three move along unchanged. The rotation by 30 is what stops a difference from sitting in one bit position while it travels down the state.

Ch for steps 1 to 20 uses each bit of b to select the matching bit of c or d. Parity is a three-way XOR. Maj takes the value that appears at least twice. Parity is used for forty of the eighty steps, and it is linear: on its own it hides nothing.

The five words produced by the eighty steps are added back into the state the block started from, and the state after the last block is the digest.

Finishing a block, and the digest

block 0

                a        b        c        d        e
state in        67452301 efcdab89 98badcfe 10325476 c3d2e1f0
after 80 steps  42541b35 5738d5e1 21834873 681e6df6 d8fdf6ad
state out       a9993e36 4706816a ba3e2571 7850c26c 9cd0d89d

Each output word is the sum of the two lines above it, keeping the low 32 bits. That addition is the feed-forward, and it is what stops the eighty steps from being run backwards from their output.

SHA-1 of the message above

a9993e364706816aba3e25717850c26c9cd0d89d

Compare the two pages. MD5 reads sixteen words four times each; SHA-1 builds sixty-four more words from them and reads eighty. More steps, more state, a longer digest, and the same block-by-block shape. That shape is the part SHA-256 keeps as well.

The code behind this page is a teaching implementation. It is written to be read, it is not constant time, and it is not for production use. Use SHA-256 or SHA3-256 in a new design.

step 1/4

CPE 645 / CS 685

SHA-1, Step by Step

MD5, Step by Step

SHA-256, Step by Step