15.2 Authenticated encryption – generic composition

An authenticated encryption (AE) scheme is a symmetric-key encryption scheme that provides both confidentiality as well as message integrity and authenticity.

Roughly speaking, sender Alice encrypts her plaintext and, in addition, computes a message authentication code (MAC, see Chapter 11, Hash Functions and Message Authentication Codes) over the ciphertext. The MAC serves as a tag to ensure the integrity and authenticity of the ciphertext. Receiver Bob validates the message’s integrity and authenticity by recomputing the MAC and checking that it is equal to the MAC attached to Alice’s message.

If Bob’s verification is successful, he can be sure that the received ciphertext is untampered and was indeed sent by Alice. So, Bob decrypts the ciphertext and processes the obtained plaintext.

The traditional way of implementing AE, called generic composition, is a combination of encryption (to achieve confidentiality) and message authentication code (to achieve message integrity and authenticity) [33]. The standard flavors of generic composition are as follows:

• Encrypt-and-MAC
• MAC-then-encrypt
• Encrypt-then-MAC

Intuitively, all three generic composition flavors seem to offer the same level of security. However, as we will soon learn, cryptographers have proven that the security guarantees of these variants can differ depending on what assumptions we make regarding the underlying cryptographic primitives, that is, assumptions regarding the strength of the block cipher and the MAC algorithm used.

15.2.1 Encrypt-and-MAC

The encrypt-and-MAC composition encrypts the plaintext and appends the MAC of the plaintext. Using the block cipher encryption e and a message authentication code T, the sender computes:

where m is the plaintext message, ke is the shared secret key for encryption, ka is the shared secret key for message authentication, and ∥ is a concatenation operation.

The encrypt-and-MAC composition is illustrated in Figure 15.1. Sender Alice encrypts plaintext m using the encryption key ke and, in parallel, computes a message authentication code for m using a second key ka. Finally, she concatenates the resulting ciphertext eke(m) and the MAC Tka(m) and sends the result to Bob.

Figure 15.1: Encrypt-and-MAC composition

On the receiver side, Bob first decrypts the ciphertext to obtain plaintext m. He then uses the plaintext to compute the MAC value and compares it to the received MAC value. If the values are equal, Bob is assured that the message was not manipulated and originates from Alice.