SHA3-256, Step by Step

Mix one block into a state of 1600 bits. Apply the five step mappings one at a time, and measure how fast one changed input bit spreads.

SHA-3demo

Objectives

Split the Keccak state into rate and capacity and say which one input touches.
Explain pad10*1 and the two domain-separation bits that make 0x06 rather than 0x01.
Describe what each of the five step mappings does, and name the only non-linear one.
Measure the diffusion of one flipped input bit round by round, and read half the state as the settled value.
Explain why twenty-four rounds are used for a state that is thoroughly mixed after about six.

25%

A 1600-bit state, five mappings per round, and how far one flipped bit travels in twenty-four of them.

A sponge does not chain a small state from block to block. It keeps one large state, 1600 bits of it, and stirs the message into part of it. That part is the rate: 136 bytes for SHA3-256. The other 64 bytes are the capacity, and no input is ever written there and no output is ever read from there.

rate 136 bytes + capacity 64 bytes = 200 bytes of state

Padding, and the block that gets absorbed

message

the padding this message gets

message      3 bytes
padding      133 bytes: 06 then 131 zeros then 80
blocks       1 of 136 bytes

The rule is called pad10*1: a one bit, as many zeros as needed, and a closing one bit. SHA-3 puts two extra bits in front of it, which is why the first padding byte is 06 rather than 01: those two bits are what separate SHA3-256 from SHAKE, which uses 1f in the same place. A message one byte short of the rate gets a single 86, with both ones in one byte.

the last sixteen bytes of block 0

00000000000000000000000000000080

Compare this with the other three pages. MD5, SHA-1 and SHA-256 all pad the length into the message. SHA-3 does not: the sponge does not need it, because a shorter message and a longer one absorb different numbers of blocks into a state the attacker cannot see all of. The two extra padding bits are for separating functions, not for encoding a length.

The state starts as 1600 zero bits, arranged as twenty-five 64-bit lanes in a 5 × 5 grid. Absorbing a block means XORing its 136 bytes into the first 17 lanes. Nothing else is touched.

The state after the block is XORed in

lanes, before the first permutation

        x=0               x=1               x=2               x=3               x=4
y=0    0000000006636261  0000000000000000  0000000000000000  0000000000000000  0000000000000000 
y=1    0000000000000000  0000000000000000  0000000000000000  0000000000000000  0000000000000000 
y=2    0000000000000000  0000000000000000  0000000000000000  0000000000000000  0000000000000000 
y=3    0000000000000000  8000000000000000 [0000000000000000][0000000000000000][0000000000000000]
y=4   [0000000000000000][0000000000000000][0000000000000000][0000000000000000][0000000000000000]

The eight lanes in brackets are the capacity. They are still zero, because the message never reaches them. They will not stay zero: the permutation mixes the whole state, which is how the message gets in there. What never happens is a byte of message being written to them directly, or a byte of them being read out.

Keccak-f[1600] is twenty-four rounds, and every round is the same five mappings in the same order. Pick a round and a mapping, and the two grids below are the state before and after it, with the lanes it changed in brackets.

Round 1 of 24, step theta

round

before theta

        x=0               x=1               x=2               x=3               x=4
y=0    0000000006636261  0000000000000000  0000000000000000  0000000000000000  0000000000000000 
y=1    0000000000000000  0000000000000000  0000000000000000  0000000000000000  0000000000000000 
y=2    0000000000000000  0000000000000000  0000000000000000  0000000000000000  0000000000000000 
y=3    0000000000000000  8000000000000000  0000000000000000  0000000000000000  0000000000000000 
y=4    0000000000000000  0000000000000000  0000000000000000  0000000000000000  0000000000000000

after theta

        x=0               x=1               x=2               x=3               x=4
y=0   [0000000006636260][0000000006636261][8000000000000000] 0000000000000000 [000000000cc6c4c2]
y=1   [0000000000000001][0000000006636261][8000000000000000] 0000000000000000 [000000000cc6c4c2]
y=2   [0000000000000001][0000000006636261][8000000000000000] 0000000000000000 [000000000cc6c4c2]
y=3   [0000000000000001][8000000006636261][8000000000000000] 0000000000000000 [000000000cc6c4c2]
y=4   [0000000000000001][0000000006636261][8000000000000000] 0000000000000000 [000000000cc6c4c2]

20 of 25 lanes changed

130 of 1600 bits changed

theta adds to every lane the parity of two neighbouring columns, one of them rotated by a bit. It is the only step that moves data between columns, so it is the reason a change anywhere reaches everywhere within a couple of rounds.

the whole round

lanes changed by round 1   24 of 25
bits changed by round 1    251 of 1600

Flip one bit of the message and absorb it into a second state. Both states then go through the same twenty-four rounds. The table counts how many of the 1600 state bits differ after each one.

One flipped input bit, round by round

Bits differing between two states after each round of Keccak-f, starting from messages that differ in one bit.
After	Differing bits	Of 1600
absorbing	1
round 1	22
round 2	378
round 3	820
round 4	842
round 5	798
round 6	824
round 24	830

One bit before the first round; about half the state a few rounds later, and it stays there. Half is the right answer, not all: two unrelated states agree on about half their bits by chance, so a difference that settles at 800 of 1600 is a difference that has stopped telling you anything.

Twenty-four rounds for a state that is thoroughly mixed after about six is not waste. The margin is the design: attacks improve, and a function with no room between "mixed" and "finished" has nowhere to retreat to.

The same permutation with a different rate and a different padding byte gives SHAKE128 and SHAKE256, where the caller chooses how many bytes to squeeze out. Keep squeezing and the permutation runs again between reads. One construction, four fixed-length hashes and two functions of any output length.

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. The mining page runs the same algorithm compiled to WebAssembly, because reading it and racing it are different jobs.

step 1/4

CPE 645 / CS 685

SHA3-256, Step by Step

SHA-256, Step by Step

Mine a SHA3-256 Digest