Using MACs with Encryption

In our analysis of MACs, we have assumed that the message was sent in the clear to the receiver. However, there are many applications where this is not a reasonable assumption.

The majority of cryptographic applications that require confidentiality also tend to require data origin authentication. Indeed, some people argue that true confidentiality can never be provided by using encryption on its own, which is why confidentiality always needs to be accompanied by data origin authentication. We’ll refer to this combination of security services as authenticated encryption.

A practical issue in applications requiring authenticated encryption is that some message data must not be encrypted but should be authenticated. Examples of this might be a packet header containing routing information or a key identifier informing the recipient which key(s) to authenticate and decrypt. In the following discussion, we’ll use the term message to refer to the data requiring confidentiality and data origin authentication, associated data to refer to the additional data requiring only data origin authentication, and full message to refer to the combination of the message and the associated data.

There are two possible approaches to providing authenticated encryption. The first is to provide these using separate cryptographic primitives. The alternative approach uses a cryptographic primitive explicitly designed to provide both security services.

Using separate primitives

We observed that, in general, encryption doesn’t provide data origin authentication. This is why when both security services are required, the most obvious solution is to use two separate cryptographic primitives. In a symmetric setting, the most natural way of realizing this is to use symmetric encryption and a MAC. But in which order should these cryptographic primitives be applied?

MAC-then-Encrypt

Here’s how MAC-then-Encrypt works:

1. The MAC is computed on the full message.

2. Then, the message and the MAC are encrypted (but not the associated data).

3. Finally, the ciphertext and the associated data are sent to the receiver.

The receiver first decrypts the ciphertext to recover the message and the MAC. The receiver then assembles the full message and checks the MAC. This order, which computes the MAC first, is perhaps the most aesthetic solution from a ‘purist’s’ perspective. It’s the message we want data origin authentication for, not its encrypted form. However, this doesn’t necessarily mean that it is the most secure solution. Indeed, there are some security concerns about this approach. A similar approach is called Encrypt-and-MAC, which differs only because the MAC is not encrypted alongside the message and is instead sent in the clear.

Encrypt-then-MAC

Here’s how Encrypt-then-MAC works:

1. The message is encrypted.

2. Then, the MAC is computed on the combination of the ciphertext and the associated data.

3. Finally, the ciphertext, the associated data, and the MAC are sent to the receiver.

This might not seem like the intuitive order to conduct the two cryptographic operations, but it has a distinct advantage. The receiver will first have to check the MAC on the ciphertext. If this check fails, the receiver will reject the received data without decryption, therefore saving some computation. In contrast, in the case of MAC-then-Encrypt, the receiver must first decrypt and then check the MAC. Encrypt-then-MAC also benefits from the existence of a theoretical security proof, which suggests that it is a good way of combining the two operations.

Note that the encryption and MAC operations should be computed using different cryptographic keys regardless of which order is used. This is because they are different cryptographic operations providing different security services. Using different keys follows the best-practice principle of key separation.

Authenticated encryption primitives

There are several potential issues with using two separate primitives to provide authenticated encryption.