Permutation-Based Hashing with Stronger (Second) Preimage Resistance

The sponge is a popular construction of hash function design. It operates with a $b$-bit permutation on a $b$-bit state, that is split into a $c$-bit inner part and an $r$-bit outer part. However, the security bounds of the sponge are most often dominated by the capacity $c$: if the length of the digest is $n$ bits, the construction tightly achieves $\min\{n/2,c/2\}$-bit collision resistance, $\min\{n,c/2\}$-bit second preimage resistance, and $\min\{n,\max\{n-r,c/2\}\}$-bit preimage resistance. Here, it is noteworthy that the generic attacks matching the preimage and second preimage bounds make use of the inverse of the permutation.

We demonstrate that, by a relatively simple adjustment, significantly improved preimage and second preimage resistance can be achieved. In detail, we first present the SPONGE-DM construction, that differs from the sponge by evaluating the permutation during absorption in a Davies-Meyer mode. This construction generically achieves $\min\{n/2,c/2\}$-bit collision resistance as the sponge does, but $n$-bit preimage resistance and $\min\{n,c-\log_2(\alpha)\}$-bit second preimage resistance, where $\alpha$ is the maximum size of the first preimage in blocks. Next, we investigate how improved security can be achieved with a smaller feed-forward, and we present the SPONGE-EDM$^a$ family of functions, indexed by a parameter $a\in\{0,\ldots,b\}$. These functions replace the permutation during absorption in the sponge by an Encrypted Davies-Meyer mode, but with only $a$ bits of feed-forward. For $a=b$, comparable bounds as for SPONGE-DM are obtained, and these bounds gradually decrease to the original sponge bounds for decreasing values of $a$.

We present various instantiations of SPONGE-DM and SPONGE-EDM$^a$ using the Keccak and Ascon permutations, and concretely demonstrate the immediate security and performance gains of these instances. For example, one can achieve up to $512$-bit preimage and second preimage resistance using the $800$-bit Keccak permutation (rather than 1600-bit in SHA-3), and likewise, one can use the $1600$-bit Keccak permutation to easily achieve up to $1024$-bit preimage and second preimage resistance (therewith properly fitting within the recently announced Chinese call for a new generation of cryptographic algorithms). Finally, we show the benefits of using these instantiations in the context of hash-based signature schemes whose security relies solely on the (second) preimage resistance of the underlying hash functions (such as Ascon-Sign).