Friday, April 10, 2015

52 Things: Number 27: What is the AEAD security definition for symmetric key encryption?

This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know' to do Cryptography: a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. This post will kick off the 'Security Definitions and Proofs' section with a brief overview of Authenticated Encryption.

In a recent post Luke described a number of well-used modes of operation (ECB, CBC and CTR) for blockciphers, modes that provide privacy (confidentiality) only. We may also want integrity from our encryption mechanism, meaning that the recipient is assured that the message it receives is the one sent without accidental changes or intentional tampering, and authenticity meaning that the receiver is convinced of the origin of the message. To get these additional goals we often use a message authentication code (MAC), and the most widely used are those based on blockciphers and those based on hash functions (HMAC). Putting these two primitives together is non-trivial: to get an IND-CCA secure scheme we need to follow the 'Encrypt-then-MAC' paradigm with a secure encryption scheme and a strongly unforgeable MAC, meaning computing the MAC on the ciphertext (see here and here for more info on Encrypt-and-MAC and MAC-then-Encrypt, with a focus on why one should avoid them). The 'AD' refers to variable-length associated data such as packet headers, and we normally expect authenticity and integrity but not confidentiality from this optional component. For further reading and examples, see Adam Langley's blog on the topic.

Next week's blog post will see an in-depth overview of IND-CCA2 security in the context of public-key encryption. The 'real-or-random' definition of IND-CCA2 (and IND-CCA1) gives the adversary access to an encryption oracle, which has an encryption key hardwired and on input message $m$ returns either a 'real' encryption $\mathsf{E}_k (m)$ or 'fake' $\mathsf{E}_k (\$^{|m|})$, and a decryption oracle that given a ciphertext $c$ will return $\mathsf{D}_k (c)$ - the adversary is then asked to distinguish which world he is in. In 2004 Shrimpton showed that a new notion dubbed IND-CCA3, where the decryption oracle in the 'fake' world is replaced by an oracle that always returns the invalid symbol $\perp$, is equivalent to the previously considered notion of AE, where the notions of privacy and authenticity/integrity are looked at separately. This observation was incorporated into Rogaway and Shrimpton's paper on the keywrap problem and Deterministic Authenticated Encryption. For more information on the impact of associated data, see here and here.

In practice, a large proportion of traffic uses CCM mode, which is a combination of a blockcipher in counter mode with CBC-MAC with the MAC-then-Encrypt approach, and GCM which uses Encrypt-then-MAC with a blockcipher in counter mode and a polynomial-based hash function called GHASH. CCM is comparatively inefficient as it requires two blockcipher calls per message block and is not online (message length needs to be known before processing can occur), and as this paper by Saarinen shows, GCM has some weak keys.

The CAESAR competition is currently in progress, with the aim of selecting a portfolio of authenticated ciphers for recommendation based on thorough academic public scrutiny. One of the main aims is to get more researchers thinking about such a vital topic, and the large number (and varied nature) of first round submissions indicates this goal has already been achieved. The second round candidates are expected to be announced next week, and an overview of the submissions can be found at the AE Zoo which is run by a number of researchers from DTU.

No comments:

Post a Comment