Paper 2019/573

Security of the Suffix Keyed Sponge

Christoph Dobraunig and Bart Mennink

Abstract

We formalize and analyze the general suffix keyed sponge construction, a pseudorandom function built on top of a cryptographic permutation. The construction hashes its data using the (keyless) sponge construction, transforms part of the state using the secret key, and generates the tag from the output of a final permutation call. In its simplest form, if the key and tag size are at most the rate of the sponge, one can see the suffix keyed sponge as a simple sponge function evaluation whose input is the plaintext appended with the key. The suffix keyed sponge is, however, much more general: the key and tag size may exceed the rate without any need to make extra permutation calls. We prove that the suffix keyed sponge construction achieves birthday-bound PRF security in the capacity, even if key and tag size exceed the rate. Furthermore, we prove that if the absorption of the key into the state happens in a leakage resilient manner, the suffix keyed sponge itself is leakage resilient as well. Our findings show that the suffix keyed sponge compares favorably with the hash-then-MAC construction. For instance, to reach a security level of $k$ bits, the side-channel protected component in the suffix keyed sponge just needs to process $k$ bits of input besides the key, whereas schemes following the hash-then-MAC construction need a side-channel protected MAC function that processes $2k$ bits of input besides the key. Moreover, even if we just consider black-box attacks, the MAC function in a hash-then-MAC scheme needs to be cryptographically strong whereas in the suffix keyed sponge the key may be absorbed by a simple XOR. The security proofs are performed using the H-coefficient technique, and make effective use of the multicollision limit function results of Daemen et al. (ASIACRYPT 2017), both for arguing that state manipulation larger than the rate is tolerated after key processing and for upper bounding the amount of leakage an attacker may gain about the secret key.

Note: 18/6: clarified novelty of this work compared with [12].

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published by the IACR in FSE 2020
Keywords
suffix MACspongeSuKSPRFleakage resilienceproof
Contact author(s)
b mennink @ cs ru nl
History
2019-11-21: last of 2 revisions
2019-05-27: received
See all versions
Short URL
https://ia.cr/2019/573
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/573,
      author = {Christoph Dobraunig and Bart Mennink},
      title = {Security of the Suffix Keyed Sponge},
      howpublished = {Cryptology ePrint Archive, Paper 2019/573},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/573}},
      url = {https://eprint.iacr.org/2019/573}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.