Paper 2015/053

Tight Bounds for Keyed Sponges and Truncated CBC

Peter Gaži, Krzysztof Pietrzak, and Stefano Tessaro

Abstract

We prove (nearly) tight bounds on the concrete PRF-security of two constructions of message-authentication codes (MACs): (1) The truncated CBC-MAC construction, which operates as plain CBC-MAC (without prefix-free encoding of messages), but only returns a subset of the output bits. (2) The MAC derived from the sponge hash-function family by pre-pending a key to the message, which is the de-facto standard method for SHA-3-based message authentication. The tight analysis of keyed sponges is our main result and we see this as an important step in validating SHA-3-based authentication before its deployment. Still, our analysis crucially relies on the one for truncated CBC as an intermediate step of independent interest. Indeed, no previous security analysis of truncated CBC was known, whereas only significantly weaker bounds have been proved for keyed sponges following different approaches. Our bounds are tight for the most relevant ranges of parameters, i.e., for messages of length (roughly) $\ell \le \min\{2^{n/4},2^r\}$ blocks, where $n$ is the state size and $r$ is the desired output length; and for $q \ge \ell$ queries. Our proofs rely on a novel application of Patarin's H-coefficient method to iterated MAC constructions.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Message-authenticationPRFsspongesCBC-MACH-coefficient methodconcrete security
Contact author(s)
tessaro @ cs ucsb edu
History
2015-11-13: last of 2 revisions
2015-01-22: received
See all versions
Short URL
https://ia.cr/2015/053
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/053,
      author = {Peter Gaži and Krzysztof Pietrzak and Stefano Tessaro},
      title = {Tight Bounds for Keyed Sponges and Truncated CBC},
      howpublished = {Cryptology ePrint Archive, Paper 2015/053},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/053}},
      url = {https://eprint.iacr.org/2015/053}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.