Probable or Nonce-sense? Reconsidering Generic Composition

One of the most interesting talks at EuroCrypt 2014 was on ways of combining encryption and authentication algorithms to form a secure authenticated encryption scheme. I hope that (with the help of some Douglas Adams quotes) I can interest you too...

In the beginning the Universe was created. This has made a lot of people very angry and been widely regarded as a bad move.

The Guide

 The story behind this paper begins at AsiaCrypt 2000, where Bellare and Namprempre presented their seminal paper on Generic Composition [BN], studying mechanisms for turning secure MAC and encryption functions into a secure Authenticated Encryption (AE) scheme. The well known “result” of this is is that combining a MAC with an encryption scheme through Encrypt-then-MAC (EtM) is secure, but Encrypt-then-MAC (EtM) or MAC-and-Encrypt (MaE) are not. Unfortunately, this is not quite what the paper says, and leads to one of the most prevalent misunderstandings in symmetric cryptography...

That quite definitely is the answer. I think the problem, to be quite honest with you, is that you've never actually known what the question is.

Deep Thought

[BN] was written at a time when most symmetric schemes were formalised within the probabilistic encryption paradigm. This means that encryption schemes have access to their own internal coins, and output a ciphertext such that the message is recoverable from just the key and the ciphertext. A ciphertext is secure if an adversary cannot distinguish the encryption of a message from the (appropriately long) encryption of 0-bits.

Nowadays, it is standard to abstract away the generation of randomness through a third input parameter (an IV or nonce), which is transmitted unencrypted. Then, a message should be recoverable by combining the key, ciphertext and the IV or nonce. Following the paper, we refer to an IV-based encryption scheme as an 'ivE', and a nonce-based encryption scheme as 'nE', and similarly define 'nAE' as a nonce-based authenticated encryption scheme. Moreover, modern schemes are expected to handle Associated Data (AD) - data that should be authenticated but not encrypted. Overall, this provides a very different model in which to prove security, because, for example, an adversary may read or modify the randomness supplied to the encryption or decryption algorithms

It is within the first of these models that the original results were proven, but since most security results are now given in the latter model, they are no longer directly applicable.

Don't Panic!

The Guide

In this work (henceforth [NRS]), co-authored with Chanathip Namprempre and Phil Rogaway, Tom Shrimpton seeks to reevaluate the security of Generic Composition, answering the questions that many people thought [BN] had already answered.  Specifically, the paper aims to answer the questions "How can you combine an ivE with a secure MAC to form nAE?" and "How can you combine nE with a secure MAC to form nAE?".

With two more inputs (IV and AD) to consider than [BN] took, the first observation is that there are significantly more than three reasonable ways to combine a MAC and an ivE or nE scheme.

Firstly, the authors cover 160 reasonable methods for combining 2 MAC calls, one ivE call and a single concatenation involving a MAC output. Whilst many of these are nonsensical or trivially insecure, the paper produces a portfolio of 8 secure MAC+ivE→nAE methods (one of which is the SIV construction [SIV]), as well as four for which optimal security (or insecurity) could not be proven.

Similarly, the authors exhaust across 20 reasonable methods for combining a MAC call with one nE call to form an nAE scheme, and as before several of these can be trivially discounted. This leads to 3 schemes being proven secure, with the security of one left open.

So, which of these should I use? Well, the short answer is: it depends! Some of the schemes allow tag truncation, parallelizable encryption or parallelizable decryption. For the complete list, we refer the reader to the paper [NRS], where diagrams of each construction is provided.

It is a mistake to think you can solve any major problems just with potatoes.

The Guide

The paper proves some generic composition mechanisms are secure under hypothesis which are much more like the real world. Indeed, several of these form schemes that can be readily implemented from the sort of cryptographic primitives that one may already have access to. However, as with all provable security results, if the hypothesis are not met then the result does not hold. This means that, if you want an nAE scheme to inherit provable security from [NRS], not only must the encryption and MAC primitives be combined in one of the verified mechanisms, but the primitives must also have the properties this paper requires of them. For example, the encryption scheme must satisfy all the normal requirements (such as correctness), but also an additional requirement of 'tidyness', which we can think of as the opposite of correctness. Whilst correctness requires that if E_k(N,M)=C then D_K(N,C)=M, tidyness requires that D_k(N,C)=M implies E_k(N,M)=C.

So, how does this relate to potatoes? Well, there are two things one can take away from this paper. The first is that there are significantly more ways of combining schemes securely, other than EtM, and this is a very useful result. However, arguably the most important message to take away from the paper is that there is no such thing as a generic composition. At the end of the day, a generic composition result is only useful if you use primitives satisfying all the required properties. Potatoes are great, but they're no use if you want a cheese omelette.

So long and thanks for all the fish

The Dolphins

 

---

[BN]:
Authenticated Encryption: Relations among notions and analysis of the generic composition paradigm
Mihir Bellare and Chanathip Namprempre
AsiaCrypt 2000
https://eprint.iacr.org/2000/025
 

[NRS]
Reconsidering Generic Composition
Chanathip Namprempre, Phillip Rogaway and Thomas Shrimpton
EuroCrypt 2014
http://eprint.iacr.org/2014/206

[SIV]
Deterministic Authenticated-Encryption: A Provable-Security Treatment of the Key-Wrap Problem
Phillip Rogaway and Thomas Shrimpton
EuroCrypt 2006
https://eprint.iacr.org/2006/221