A Modular Framework for Building Variable-Input-Length Tweakable Ciphers

For this weeks study group I presented a paper by Shrimpton and Terashima from AsiaCrypt 2013[1]: A Modular Framework for Building Variable-Input-Length Tweakable Ciphers. Starting from the bottom, the authors take a modular approach to build an Authenticated Encryption (AE) scheme, starting with some relatively simple primitives and extending their functionality until full AE is supported. So, the paper can be broken up into 4 sections:

1. Introduce our primitives: Tweakable Block Ciphers (both Beyond Birthday fixed-input-length and Variable-input-length)
2. Combine these with their new Protected IV (PIV) to form an Arbitrary Input Length Tweakable Block cipher (AIL TBC)
3. Provide two explicit examples of such constructions
4. Build a secure AE scheme out of a VIL TBC

From a practical point of view, Part 3 is arguably the most interesting, because it provides explicit examples of secure constructions and (when combined with 4) yields an AE scheme that may be secure beyond the birthday bound (which is the point at which most symmetric security proofs break down).
This blog will mainly focus on Part 2, and readers are encouraged to read the full paper for more details on .

Background

Very briefly, let us sketch a few key notions:

• A TBC (Tweakable Blockcipher) acts like a family of block ciphers, one for each tweak. If it is secure, then any change in the tweak should make the TBC act completely differently, which we call an STPRP (for strong tweakable pseudo-random permutation).
• A primitive is VIL (Variable Input Length) secure if it is secure when queried on messages of different lengths
• A primitive is AIL (Arbitrary Input Length) secure if it is secure when queried with message of any (single) length
• Authenticated Encryption was discussed in a blog post last year[2] and (roughly) corresponds to secure communication between two people sharing a key.
• The Birthday Bound on n bits is roughly $q^2/2^n$, and is the point many symmetric security results break down. A scheme that is still secure for $q>2^{n/2}$ is known as Beyond Birthday Bound (BBB) secure.

The Protected IV (PIV) construction

The key aim of the paper was to build a secure VIL TBC (ie an STPRP) from a fixed-width TBC with variable length tweak (F) and a VIL TBC (V). To do so, the authors describe the PIV (for Protected-IV) scheme. A diagram of the construction is given to the right, and we thank the authors for permission to reproduce their graphic. It can be seen as an extension of the SIV scheme[3], except that by re-encrypting the keeping the IV secret ("protecting" it) and letting it carry some information about the plaintext, the authors have managed to remove the ciphertext expansion required for SIV security.
The most interesting thing about the scheme is that V does not have to be secure as a VIL TBC: V only has to be secure if the tweak is never repeated (similar to the idea of a nonce-based authenticated encryption scheme). This makes V much easier to construct with (for example) a slight variant of counter mode sufficing.
The idea behind the proof is relatively intuitive, built around the fact that (because F is secure) the IV is random and doesn't repeat (up to a birthday bound term on |IV|). So, V is always called with a unique tweak, securely encrypting the X_r (or decrypting the Y_r) content, and so the output is nicely random, making the whole scheme a secure STPRP. Thus security of the scheme reduces to the security of F, V and of a birthday attack on the IV.

Instantiations and Building Authenticated Encryption

To close, the paper provided some instantiations, and explains how to extend the Encode-then-Encipher[4] concept and proof to achieve strong Authenticated Encryption from a STPRP. We didn't have time to discuss these elements in detail, but observed that to achieve Beyond Birthday security, the IV had to be twice as wide as the birthday bound we seek to pass.

References

1. A Modular Framework for Building Variable-Input-Length Tweakable Ciphers, Shrimpton & Terashima
2. 52 Things #27: What is AEAD?, from this blog
3. Deterministic Authenticated-Encryption: A Provable-Security Treatment of the Key-Wrap Problem Rogaway & Shrimpton
4. Encode-then-encipher encryption: How to exploit nonces or redundancy in plaintexts for efficient cryptography BEllare & Rogaway