# Number of rounds for constant header size in common hashes and XOFs

We compute hash $$H(M_0\mathbin\|M_1)$$ of size $$d\ge1$$ for some constant header $$M_0$$ of size $$m_0$$, and $$\nu\ge1$$ messages $$M_1$$ of random content and size $$m_1$$.

For Merkle-Damgård hashes, a simple optimization pre-computes the first $$\left\lfloor m_0/r\right\rfloor$$ rounds (where $$r$$ is the block size), and for some minimum extra size $$\mu$$, the total number of rounds computed is $$\text{rounds}=\left\lfloor\frac{m_0}r\right\rfloor+\nu\left\lceil\frac{\left(m_0\bmod r\right)+m_1+\mu}r\right\rceil$$ with, for some hashes: $$\begin{array}{l|rrrl|rrrl} \text{hash} & d&r&\mu&\text{(bits)}&\tilde d&\tilde r&\tilde \mu&\text{(bytes)}\\ \hline \operatorname{SHA-256} & 256 & 512 & 65 && 32 & 64 & 9 \\ \operatorname{SHA-512} & 512 & 1024 & 129 && 64 & 128 & 17 \\ \end{array}$$

Note: The right side of the table assumes quantities are expressed in byte rather than bit. The only change to the formula is that variables get a tilde, except $$\nu$$.

For more common hashes and XOFs¹, what are the corresponding formulas and parameters?

I'm especially interested in common variants of SHA-3 (or KECCAK if it differs from SHA-3 other than by value of padding); SHAKE; various BLAKE; and perhaps some parallelizable hashes.

Update: I have changed notation several times to align with that in KECCAK/SHAKE for $$r$$ and output size $$d$$, and used greek letters in an attempt to avoid confusion with existing hash specifications.

¹ eXtendable Output Functions essentially are hashes where the output size $$d$$ is a parameter rather than fixed. An example is SHAKE256 of the SHA-3 family.

$$\begin{array}{l|rrrl|rrrl} \text{hash} & d&r&\mu&\text{(bits)}&\tilde d&\tilde r&\tilde \mu&\text{(bytes)}\\ \hline \operatorname{MD5} & 128 & 512 & 65 && 16 & 64 & 9 \\ \operatorname{SHA-1} & 160 & 512 & 65 && 20 & 64 & 9 \\ \operatorname{RIPEMD-160} & 160 & 512 & 65 && 20 & 64 & 9 \\ \operatorname{SHA-224} & 224 & 512 & 65 && 28 & 64 & 9 \\ \operatorname{SHA-256} & 256 & 512 & 65 && 32 & 64 & 9 \\ \hline \operatorname{SHA-512/224}& 224 & 1024 & 129 && 28 & 128 & 17 \\ \operatorname{SHA-512/256}& 256 & 1024 & 129 && 32 & 128 & 17 \\ \operatorname{SHA-384} & 384 & 1024 & 129 && 48 & 128 & 17 \\ \operatorname{SHA-512} & 512 & 1024 & 129 && 64 & 128 & 17 \\ \hline \operatorname{SHA3-224} & 224 & 1152 & 4 && 28 & 144 & 1 \\ \operatorname{SHA3-256} & 256 & 1088 & 4 && 32 & 136 & 1 \\ \operatorname{SHA3-384} & 384 & 832 & 4 && 48 & 104 & 1 \\ \operatorname{SHA3-512} & 512 & 576 & 4 && 54 & 72 & 1 \\ \hline \operatorname{SHAKE-128} & d & 1344 & 6 && \lceil d/8 \rceil & 168 & 1 \\ \operatorname{SHAKE-256} & d & 1088 & 6 && \lceil d/8 \rceil & 136 & 1 \\ \hline \operatorname{BLAKE2s-256} & 256 & 512 & 0 && 32 & 64 & 0 \\ \operatorname{BLAKE2b-512} & 512 & 1024 & 0 && 64 & 128 & 0 \\ \end{array}$$

## SHA3-x

1. $$\operatorname{SHA3-224}(M) = \operatorname{KECCAK}[448] (M \mathbin\| 01, 224)$$
2. $$\operatorname{SHA3-256}(M) = \operatorname{KECCAK}[512] (M \mathbin\| 01, 256)$$
3. $$\operatorname{SHA3-384}(M) = \operatorname{KECCAK}[768] (M \mathbin\| 01, 384)$$
4. $$\operatorname{SHA3-512}(M) = \operatorname{KECCAK}[1024](M \mathbin\| 01, 512)$$

KECCAK

and KECCAK defined as

• $$\operatorname{KECCAK}[c] (N, d) = \operatorname{SPONGE}[\operatorname{KECCAK-p}[1600, 24], \operatorname{pad10*1}, 1600–c] (N, d)$$

and note that $$N = M\mathbin\|01$$ and $$d$$ is the required output size, Now we have

1. $$\operatorname{SHA3-224}(M) = \operatorname{SPONGE}[\operatorname{KECCAK-p}[1600, 24], \operatorname{pad10*1}, 1600–448] (N, 224)$$
2. $$\operatorname{SHA3-256}(M) = \operatorname{SPONGE}[\operatorname{KECCAK-p}[1600, 24], \operatorname{pad10*1}, 1600–512] (N, 256)$$
3. $$\operatorname{SHA3-384}(M) = \operatorname{SPONGE}[\operatorname{KECCAK-p}[1600, 24], \operatorname{pad10*1}, 1600–768] (N, 384)$$
4. $$\operatorname{SHA3-512}(M) = \operatorname{SPONGE}[\operatorname{KECCAK-p}[1600, 24], \operatorname{pad10*1}, 1600–1024] (N, 512)$$

• $$\operatorname{pad10*1}(x, m)$$ is not important since the message is not formed yet.

SPONGE

• $$\operatorname{SPONGE}[f, \operatorname{pad}, r](N, d)$$

1. Let $$P=N \mathbin\| \operatorname{pad}(r, \operatorname{len}(N))$$.

2. Let $$n=\lfloor\operatorname{len}(P)/r\rfloor$$.

3. Let $$c=\lfloor b/r\rfloor$$.

4. Let $$P_0, \ldots, P_{n-1}$$ be the unique sequence of strings of length $$r$$ such that $$P = P_0 \mathbin\| \ldots\mathbin\| P{n-1}$$.

5. Let $$S=0^b$$

6. $$\textbf{For } i \textbf{ from }0 \textbf{ to } n-1$$

$$\textbf{let } S=f (S \oplus (P_i\mathbin\| 0c))$$.

7. ...

As we can see, we can precompute a message $$M$$ up to the maximum multiple of $$r$$ that is smaller than $$\operatorname{len}(M)$$. More mathematically $$\operatorname{precomputableLen} = \lfloor(\operatorname{len}(M)/r)\rfloor \cdot r.$$ And the $$r$$ for

1. $$\operatorname{SHA3-224}(M)$$ is $$r = 1152$$
2. $$\operatorname{SHA3-256}(M)$$ is $$r = 1088$$
3. $$\operatorname{SHA3-384}(M)$$ is $$r = 832$$
4. $$\operatorname{SHA3-512}(M)$$ is $$r = 576$$

and the formula

$$\text{rounds}=\left\lfloor\frac{m_0}r\right\rfloor+\nu\left\lceil\frac{\left(m_0\bmod r\right)+m_1+\mu }r\right\rceil$$

## SHAKE128 and SHAKE256

• $$\operatorname{SHAKE128}(M, d) = \operatorname{KECCAK}[256] (M \mathbin\| 1111, d)$$
• $$\operatorname{SHAKE256}(M, d) = \operatorname{KECCAK}[512] (M \mathbin\| 1111, d)$$

As we can see the main difference is the capacity and extra two bits appended to have the domain separation.

1. $$\operatorname{SHAKE128}(M, d)$$ is $$r =1344$$
2. $$\operatorname{SHAKE256}(M, d)$$ is $$r =1088$$

and the formula

$$\text{rounds}= \underbrace{\left\lfloor\frac{m_0}{r}\right\rfloor + \nu\left\lceil\frac{\left(m_0\bmod r\right)+m_1+\mu}r\right\rceil}_{\text{Absorbing part}} + \underbrace{\nu \left\lceil \frac{d}{r} -1 \right\rceil }_{\text{Squeezing part}}$$

## BLAKE2b and BLAKE2s

BLAKE2 uses modified ChaCha as compression function with 16 words. BLAKE2s is the 32-bit version so $$r=512$$ here, and for BLAKE2b $$r = 1024$$ ( $$s$$ for small, $$b$$ for big).

and the formula

$$\text{rounds}=\left\lfloor\frac{m_0}r\right\rfloor+\nu\left\lceil\frac{\left(m_0\bmod r\right)+m_1+\mu } r\right\rceil$$

since BLAKE2 uses all-zero padding, they called it minimal padding.

• The padding of KECCAK evolved during the competition. Apr 29, 2021 at 14:09
• Ah, so the difference in the Ethereum variant of SHA-3 would be "only" in the padding, and not other parameters. I imagined (baselessly) that the issue was with modified $c$ in the interest of speed, which existed at some point (see this).
– fgrieu
Apr 29, 2021 at 15:02
• BLAKE2 pads the last data block if and only if necessary, with null bytes. If the data length is a multiple of the block length, no padding byte is added. Apr 29, 2021 at 22:50
• Thanks a lot for the nice and hard work, I really like that table! Possible areas of polishing: "can precompute a message M".. That's $M_0$ in the question, and it has length $m_0$. Perhaps some indication in the first table that the "squeazing" of SHAKE is not accounted for [or adding that to the table, which might require putting the (bits) and (bytes) indication at more appropriate place, which I failed to do; if so, add reference to SHAKE formula]. For Blake2, perhaps replace formula with indication that $\mu=0$, or leave formula without $\mu$.
– fgrieu
Apr 30, 2021 at 7:38