Keccak provides a sort of very useful XOFs.
Can other sponge construction hash function like Spongent work as XOF?
Is there any lightweight XOF for hardware or software implementation?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ KangarooTwelve is based on the Keccak derived XOF SHAKE128 / 256. It's designed to be much faster. $\endgroup$– NatanaelFeb 27, 2019 at 14:25
-
$\begingroup$ Might consider gimli.cr.yp.to too. $\endgroup$– Squeamish OssifrageFeb 27, 2019 at 17:07
-
$\begingroup$ XOF is simply what happens when you keep squeezing from a sponge function, so any secure sponge will work as an XOF within its security bound. See the NORX core permutation for an interesting lighter weight permutation $\endgroup$– Richie FrameFeb 28, 2019 at 2:28
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
Can any hash function based on the sponge construction work as extendable output function?
Yes.
Pick any permutation $\pi\colon \{0,1\}^n \to \{0,1\}^n$, and capacity $c < n$. For example, you could pick Keccak-p[1600, 24] like SHA-3 uses, with state size $n = 1600$ and capacity $c = 2\lambda$ for a $\lambda$-bit security level—that is, SHAKE128 uses $c = 256$ for 128-bit collision resistance (provided, of course, the output is at least 256 bits). Let $r = n - c$ be the rate.
Start with the initial state $x_0 = 0^n$, i.e. a string of $n$ zero bits. Break the padded input message $m$ into $r$-bit blocks $m_1 \mathbin\| m_2 \mathbin\| \cdots \mathbin\| m_\ell$.
Absorb. For each block $m_i$, update the state $x_i = \pi(x_{i-1} \oplus (m_i \mathbin\| 0^c))$; that is, pad the $r$-bit block $m_i$ with $c = n - r$ zeros, xor it into the state, and permute the state.
Squeeze. Reveal the first $r$ bits of $x_\ell$, the first $r$ bits of $\pi(x_\ell)$, the first $r$ bits of $\pi^2(x_\ell)$, the first $r$ bits of $\pi^3(x_\ell)$, and so on, until you've produced the number of output bits you want.
Is there any lightweight XOF for hardware or software implementation?
There are many permutation-based designs these days.
Keccak comes in many sizes: SHA-3 uses Keccak-p[1600, 24] with parameters that were overdesigned partly out of paranoia and partly for political reasons, but KangarooTwelve uses Keccak-p[1600, 12], i.e. half the number of rounds of SHA-3, and higher rates $r$, and still has a good security margin against the best collision attacks. You could possibly even tune the Keccak parameters to be even smaller if collision resistance isn't important for your application, and there are other options for smaller word sizes.
NORX, a 512- or 1024-bit permutation, was designed like an ARX network but with the approximation $a + b \approx a \oplus b \oplus ((a \wedge b) \mathbin\ll 1)$ to make hardware designs a little cheaper, since integer addition has a high cost for carry propagation; Gimli is a newer design with a 384-bit permutation that improves on NORX. The CAESAR winner Ascon uses another 320-bit permutation.
answered Mar 7, 2019 at 18:29
-
$\begingroup$ That is to say, any permutation based hash function (including but not only sponge construction) can work as XOF? Additionally, The capacity c = 2λ for Keccak-p[1600, 24]. $\endgroup$– ZacharyMar 9, 2019 at 10:19
-
$\begingroup$ Any permutation: Well, sure, even if you didn't use it as a sponge before you could use it as a sponge for an XOF. What I described is just the sponge construction. In fact, the only difference between SHA3-256 and SHAKE128-256 is how you pad messages. Capacity: Yes, you're right about the capcity parameter for SHAKE—fixed. The formula I had given is for SHA3-d with security level d/2, not for SHAKEn with security level at most n. $\endgroup$ Mar 9, 2019 at 15:21