International Association
for Cryptologic Research

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.