Paper 2022/734

Tight Preimage Resistance of the Sponge Construction

Charlotte Lefevre, Radboud University Nijmegen
Bart Mennink, Radboud University Nijmegen
Abstract

The cryptographic sponge is a popular method for hash function design. The construction is in the ideal permutation model proven to be indifferentiable from a random oracle up to the birthday bound in the capacity of the sponge. This result in particular implies that, as long as the attack complexity does not exceed this bound, the sponge construction achieves a comparable level of collision, preimage, and second preimage resistance as a random oracle. We investigate these state-of-the-art bounds in detail, and observe that while the collision and second preimage security bounds are tight, the preimage bound is not tight. We derive an improved and tight preimage security bound for the cryptographic sponge construction. The result has direct implications for various lightweight cryptographic hash functions. For example, the NIST Lightweight Cryptography finalist Ascon-Hash does not generically achieve $2^{128}$ preimage security as claimed, but even $2^{192}$ preimage security. Comparable improvements are obtained for the modes of Spongent, PHOTON, ACE, Subterranean 2.0, and QUARK, among others.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published by the IACR in CRYPTO 2022
Keywords
sponge hash function preimage security tightness
Contact author(s)
charlotte lefevre @ ru nl
b mennink @ cs ru nl
History
2022-06-23: revised
2022-06-08: received
See all versions
Short URL
https://ia.cr/2022/734
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/734,
      author = {Charlotte Lefevre and Bart Mennink},
      title = {Tight Preimage Resistance of the Sponge Construction},
      howpublished = {Cryptology ePrint Archive, Paper 2022/734},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/734}},
      url = {https://eprint.iacr.org/2022/734}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.