Paper 2017/302

Quantum preimage, 2nd-preimage, and collision resistance of SHA3

Jan Czajkowski, Leon Groot Bruinderink, Andreas Hülsing, and Christian Schaffner

Abstract

SHA3 and its extendable output variant SHAKE belong to the family of sponge functions. In this work, we present formal security arguments for the quantum preimage, $2^{\text{nd}}$-preimage, and collision resistance of any sponge function. We just assume that the internally used transformation behaves like a random transformation. These are the first formal arguments that sponge functions (incl. SHA3 and SHAKE) are secure in the post-quantum setting. We even go one step further and prove that sponges are collapsing (Unruh, EUROCRYPT'16). Thereby, we can also derive the applicability of sponge functions for collapse-binding commitments. In addition to the security arguments, we also present a quantum collision attack against sponges. The complexity of our attack asymptotically matches the proven lower bound up to a square root.

Note: This paper is superseded by eprint report 2017/771 which merges this work with eprint report 2017/282, a concurrent work by Dominique Unruh. In addition eprint report 2017/771 fixes a misinterpretation of our results. This paper claims to provide security statements for SHA3 which it does not. While our formal security arguments are sound, they are limited to settings where the internal block function used in the Sponge is either a random function or a random one-way permutation (which is stated in our theorems). The limitation to (random) one-way permutations is necessary as the proof breaks down as soon as the adversary is given access to an oracle that allows to invert the permutation. As the Keccak permutation is efficiently invertible, it is not covered by these results. Therefore, the results do not apply to SHA3. For a more detailed discussion of the issue see eprint report 2017/771.