15.3 Security of generic composition

In their seminal publication Authenticated Encryption: Relations among Notions and Analysis of the Generic Composition Paradigm [18], Bellare and Namprempre analyze the generic compositions encrypt-and-MAC, MAC-then-encrypt, and encrypt-then-MAC, and prove whether these compositions are secure for the notions IND-CPA, IND-CCA, NM-CPA, INT-PTX, and INT-CTX.

The proofs given by Bellare and Namprempre are valid under the assumption that the block cipher used is secure against a chosen-plaintext attack and the MAC algorithm is strongly unforgeable under a chosen-message attack.

Popular cryptographic algorithms we have covered so far – for example, the block cipher AES and the keyed hash function HMAC used for message authentication – are believed to offer such security guarantees. As a result, Bellare and Namprempre emphasize that analyzing the compositions under these assumptions yields a realistic and practically useful result.

Table 15.1 summarizes the security analysis results for the three composite authenticated encryption schemes. Entries marked with ✓ mean that the composition was proven to meet the corresponding security requirement assuming that the block cipher is IND-CPA secure and the message authentication code is strongly unforgeable under a chosen-message attack.

Entries marked with × mean that there exists some IND-CPA secure block cipher and some strongly unforgeable MAC where the composition based on them does not meet the security requirement.

 Table 15.1: Security results from [18] for composite authenticated encryption schemes

The results in Table 15.1 are quite counter-intuitive as they clearly show that the different generic composition variants are not equivalent in terms of their security. If we use a block cipher that is IND-CPA-secure and a message authentication code that is strongly unforgeable under a chosen-message attack – a reasonable assumption for standardized cryptographic algorithms – encrypt-then-MAC composition is the most secure.

15.4 Authenticated ciphers

Authenticated ciphers are an alternative to the block cipher and MAC combinations. An authenticated cipher algorithm is functionally equivalent to a cipher and MAC combination, but it is simpler, faster, and oftentimes more secure [11].

In addition to the ciphertext, an authenticated cipher also produces a so-called authentication tag. Formally, Authenticated Encryption (AE) is defined as:

where K is the secret key, P is the plaintext, C is the ciphertext, and T is the authentication tag.

The inverse operation, Authenticated Decryption (AD), is defined as:

Analogous to verifying a MAC, if the authentication tag T is invalid, ADK will return an error to prevent the receiving party from processing the decrypted plaintext since the ciphertext C was manipulated.

Authenticated encryption, among other things, prevents chosen-ciphertext attacks where an adversary creates ciphertexts and asks the legitimate party (an oracle in cryptographic parlance) for the corresponding plaintexts.