The Sponge Construction

The second half of this chapter is about where every random byte in both standards comes from.

Chapter 5 listed the roles: expanding a seed into the matrix $A$, sampling the centred binomial noise, hashing the public key, hashing the message, deriving the final shared key. ML-DSA adds sampling the commitment randomness and the challenge.

Every one of those is served by the same primitive, parameterised differently. That primitive is a sponge, and it is built on the Keccak permutation.

01.What a sponge is

Two ingredients.

A fixed-width permutation $f$ on $b$ bits, designed to be indistinguishable from a random permutation. Keccak-$f$[1600] gives $b = 1600$.

A split of the state into a rate $r$ and a capacity $c$, with $r + c = b$.

The construction has two phases.

Absorbing. Pad the input to a multiple of $r$ bits. For each block: XOR it into the top $r$ bits of the state, then apply $f$. After every block is absorbed, the state has been mixed with the whole input.

Squeezing. Read the top $r$ bits of the state as output. Need more? Apply $f$ again and read another $r$ bits. Repeat until the caller has enough.

The bottom $c$ bits are never read and never written directly. They are a hidden buffer separating what an attacker can supply from what an attacker can observe.

02.Why this is such a useful shape

A sponge is not a hash function with extra features. It is a more general object that a hash function is a special case of, and the generality is what makes one primitive serve every role.

Absorb an input, squeeze 32 bytes, and it is a hash function.

Absorb a seed, squeeze indefinitely, and it is a stream cipher or an extendable output function. This is what expanding $\rho$ into the matrix $A$ needs, since the matrix requires hundreds of bytes and the amount is not known in advance because of rejection sampling.

Absorb a key and a nonce, squeeze, and it is a pseudorandom function. This is what noise sampling uses.

Absorb two things concatenated, squeeze, and it is a key derivation function.

Every one of those is the same code with different parameters and a different amount squeezed. In hardware it is one block. In software it is one routine. That is why Chapter 5's list of five different-looking primitives collapses to a single engine.

03.Why the capacity is what matters

The capacity is the part an attacker never touches, and it is what makes the sponge hard to invert.

Any attempt to force a collision, meaning two different inputs producing identical output, has to arrange for the hidden $c$ bits to coincide. The best known generic attack needs about $2^{c/2}$ permutation calls, by the birthday bound.

So the capacity sets the security level, and the rate sets the speed. They trade directly against each other since they sum to 1600.

Every row sums to 1600.

SHAKE128 has capacity 256, so collision work is about $2^{128}$, matching NIST level 1. SHAKE256 has capacity 512, giving about $2^{256}$ and matching level 5.

The names are worth a warning, because they read backwards. SHAKE128 is the faster one, with more rate, producing more bytes per permutation call. SHAKE256 is the stronger one, with less rate. The number in the name is the security level, not the output size, and both produce output of any length.

That explains the choices in the standards. Expanding the matrix needs many bytes and only needs the output to be unpredictable, so SHAKE128 is used for its throughput. Sampling secrets and deriving keys use SHAKE256 for the stronger guarantee, where the volume is small.

04.Padding and domain separation

The sponge pads with a rule called pad10*1: append a domain-separation byte, then zero bits, then a final $1$ bit landing exactly on the rate boundary.

The trailing $1$ guarantees no two distinct inputs pad to the same block sequence, which would otherwise be a trivial collision.

The domain byte is the interesting part. It is 0x06 for the SHA3 family and 0x1F for the SHAKE family, and that single byte is the only difference between them. SHA3-256 and SHAKE256 have the same rate, the same capacity and the same permutation. They differ in one byte of padding.

That byte is doing real work. Without it, a SHA3-256 digest and the first 32 bytes of a SHAKE256 stream on the same input would be identical, and a protocol using both would have two roles collapse into one. Domain separation of this kind is a recurring theme in the standards, and it is cheap precisely because the sponge makes it cheap.

The next note opens the permutation itself.