5
$\begingroup$

In most uses of Sponge mode of operations such as SHA3 and many of the round-2 candidates in the NIST lightweight cryptography project, the underlaying primitive is a cryptographic permutation - that is, it's bijective.

For reasons of curiosity, I noticed that a proposed Sponge-based PRNG implement forward secrecy (back-tracing resistance) by truncating part of the permutation state to all-bits-zero (Section 4.3 of the linked paper).

This got me wonder, what if the permutation is one-way (e.g. $p(x) \oplus x$):

Q1: What are the security implications if SHA3 hash and XOF functions were built on top of Sponge-PRF?

Q2: If the proposed PRNG used PRF, how would the security proof break apart?

Q3: If sponge-based duplex AEADs used PRF, how would their security proof break apart?

$\endgroup$
  • 3
    $\begingroup$ One minor note: Sponges usually do not use keyed permutations (PRPs) but public random permutations, so technically PRF is not the correct model here. $\endgroup$ – SEJPM Dec 6 '19 at 12:02
1
$\begingroup$

I sent a mail to the Keccak team asking about this, and I got a response from one of the authors (Joan Daemen to be specific).

According to him, we actually can instantiate Sponge functions and Duplex objects with a "transformation" in addition to a permutation, the latter of which is what we commonly do. As long as the underlaying (fixed-width) function is indistinguishable (computationally) from a random one.

So the real reason we don't usualy use a "transformation", is that - It's not usually efficient.

Quote from the mail response.

The reason that the sponge construction is mostly instantiated with permutations (Keccak, Xoodyak, Spongent, etc.) is that we - as a cryptographic community - have a method to build efficient permutations that seem to give rise to secure sponge functions but not to build efficient transformations that do the same and the invertibility of the permutation does not hurt as far as the indifferentiability and indinguishability bounds are concerned. ...

This is true, the round functions in Feistel-network block ciphers such as DES and SM4 aren't optimal efficiency-wise, especially when compared to constructs such as ARX (add-rotate-xor such as that in ChaCha20), and bitwise-and-shift operations (such as those in Gimli, Keccak, NORX).

To conclude:

... We actually build a permutation by iterating a simple round function that does mixing, nonlinearity and shuffling. Sponges have been built with a transformation that is not a permutation, like Gluon, but that was no great success in my opinion.

|improve this answer|||||
$\endgroup$

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.