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

Question

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.

Answer 1

Heading

\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

SHA3-x is defined with KECCAK as;

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)$

Padding

• $\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.

---