2
$\begingroup$

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.

$\endgroup$
0
2
+100
$\begingroup$

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.


$\endgroup$
4
  • 1
    $\begingroup$ The padding of KECCAK evolved during the competition. $\endgroup$
    – kelalaka
    Apr 29 at 14:09
  • 1
    $\begingroup$ 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). $\endgroup$
    – fgrieu
    Apr 29 at 15:02
  • 1
    $\begingroup$ 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. $\endgroup$
    – kelalaka
    Apr 29 at 22:50
  • 1
    $\begingroup$ 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$. $\endgroup$
    – fgrieu
    Apr 30 at 7:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.