SHA-256, Step by Step

Pad a message, and build the sixty-four-word schedule one word at a time. Then step through one of the sixty-four rounds.

SHA-256demo

Objectives

Predict how many blocks a message of a given length pads to, and explain the 55/56-byte boundary.
Say why the message length is padded into the input rather than tracked beside it.
Compute one schedule word from its four sources and contrast the expansion with MD5's reordering.
Trace one SHA-256 round through T1 and T2, naming Ch, Maj and the two big sigma functions.
Explain why two words are computed each round while the other six only shift along.

33%

Padding, the sixty-four-word schedule, and one of the sixty-four rounds.

SHA-256 works on 64-byte blocks, so a message is first padded to a whole number of them: the byte 0x80, then zeros, then the length of the original message in bits as eight big-endian bytes.

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 of message become 64 bytes in 1 block. The length field takes the last eight bytes and the 0x80 needs one more, so 55 bytes is the longest message that still fits in a single block: at 56 bytes the padding no longer has room and a second block appears. Try it.

Length padding is not tidying. Without it, a message and a longer one that begins the same way could arrive at the compression function with the same final block. Putting the length inside the input is what the collision-resistance argument for a chained hash rests on.

Sixteen words arrive from the block, and sixty-four are needed: one per round. Each new word mixes four earlier ones through two functions that rotate and shift.

W[t] = σ₁(W[t−2]) + W[t−7] + σ₀(W[t−15]) + W[t−16]

The message schedule

word index t

the four sources and the word they build

W[14]  00000000   sigma1 -> 00000000
W[ 9]  00000000
W[ 1]  00000000   sigma0 -> 00000000
W[ 0]  61626380

W[16]  61626380   the four added, low 32 bits kept

σ₀ and σ₁ are each two rotations and one shift, XORed together. The shift is what stops them from being rotations alone, which would keep every bit inside its own position.

This is the difference from MD5 worth naming. MD5 reads its sixteen words four times each in four orders. SHA-256 reads sixteen and builds forty-eight more, so a difference planted in one word does not reappear unchanged later; it is combined with others every time.

Eight working words, sixty-four rounds, one schedule word and one constant per round. Two values are computed each round, and the other six words shift along.

T₁ = h + Σ₁(e) + Ch(e,f,g) + K[t] + W[t] T₂ = Σ₀(a) + Maj(a,b,c)

Round 1 of 64

round

K[0] = 428a2f98

W[0] = 61626380

the working words, before and after

            a        b        c        d        e        f        g        h        
before      6a09e667 bb67ae85 3c6ef372 a54ff53a 510e527f 9b05688c 1f83d9ab 5be0cd19
after       5d6aebcd 6a09e667 bb67ae85 3c6ef372 fa2a4622 510e527f 9b05688c 1f83d9ab

what the round computed

Sigma1(e)   3587272b
Ch(e,f,g)   1f85c98c
T1          54da50e8
Sigma0(a)   ce20b47e
Maj(a,b,c)  3a6fe667
T2          08909ae5

new e = d + T1     fa2a4622
new a = T1 + T2    5d6aebcd

Ch uses each bit of e to select the matching bit of f or of g. Maj takes the bit value that appears at least twice among a, b and c. Both are non-linear, which is what the rotations and additions on their own are not.

Two new words, six copies. That means a value entering at a is still visible four rounds later at d, travelling while it is also being mixed in through T₁.

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.

step 1/3

CPE 645 / CS 685

SHA-256, Step by Step

SHA-1, Step by Step

SHA3-256, Step by Step