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
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
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
No comments:
Post a Comment