Yevgeniy Dodis

Message Authentication Codes from Unpredictable Block Ciphers

Yevgeniy Dodis and John Steinberger

We design an efficient mode of operation on block ciphers. Our mode
has the following properties, when instantiated with a block cipher f
to yield a variable-length, keyed hash function H:

(1) MAC Preservation. H is a secure message authentication code (MAC)
with birthday security, as long as f is unpredictable.
(2) PRF Preservation. H$ is a secure pseudorandom function (PRF) with
birthday security, as long as f is pseudorandom.
(3) Security against Side-Channels. As long as the block cipher f does
not leak side-channel information about its internals to the attacker,
properties (1) and (2) hold even if the remaining implementation of H
is completely leaky. In particular, if the attacker can learn the
transcript of all block cipher calls and other auxiliary information
needed to implement our mode of operation.

Our mode is the first to satisfy the MAC preservation property (1)
with birthday security, solving the main open problem of Dodis et al.
from Eurocrypt 2008. Combined with the PRF preservation (2), our mode
provides a hedge against the case when the block cipher $f$ is more
secure as a MAC than as a PRF: if it is false, as we hope, we get a
secure variable-length PRF; however, even if true, we still "salvage"
a secure MAC, which might be enough for a given application.

We also remark that no prior mode of operation offered birthday
security against side channel attacks, even if the block cipher was
assumed pseudorandom.

Although very efficient, our mode is three times slower than many of
the prior modes, such as CBC, which do not enjoy properties (1) and
(3). Thus, our work motivates further research to understand the gap
between unpredictability and pseudorandomness of the existing block
ciphers, such as AES.