Tweakable
Blockciphers with Beyond Birthday-Bound Security
Will Landecker (
Thomas Shrimpton (
Seth Terashima (
Abstract:
Liskov, Rivest and Wagner
formalized the tweakable blockcipher
(TBC) primitive at CRYPTO'02. The typical recipe for instantiating a TBC is
to start with a blockcipher, and then build up a
construction that admits a tweak. Almost all such constructions enjoy
provable security only to the birthday bound, and the one that does achieve
security beyond the birthday bound (due to Minematsu)
severely restricts the tweak size and requires per-invocation blockcipher rekeying.
This paper gives the first TBC construction that simultaneously allows for
arbitrarily “wide” tweaks, does not rekey, and delivers provable
security beyond the birthday bound. Our construction is built from a blockcipher and an $\eAXU$ hash function.
As an application of the TBC primitive, LRW suggest the TBC-MAC construction
(similar to CBC-MAC but chaining through the tweak), but leave open the
question of its security. We close this question, both for TBC-MAC as a PRF
and a MAC. Along the way, we find a nonce-based variant of TBC-MAC that has a
tight reduction to the security of
the underlying TBC, and also displays graceful security degradation when nonces are misused. This result is interesting on its
own, but it also serves as an application of our new TBC construction,
ultimately giving a variable input-length PRF with beyond birthday-bound
security.