Authenticated Encryption

A New Cryptographic Primitive?

By far the oldest and perhaps also the best-known goal of cryptographic methods is the protection of secrecy, or confidentiality, of data. This goal is achieved by employing encryption techniques. Decryption can only be performed by someone possessing the right decryption key.

Of far greater relevance in most commercial applications is the protection of the correctness, or authenticity, of data. This goal is achieved by means of digital signatures, or message authentication codes (MACs). Both digital signatures and MACs compute a tag, which can be seen as a kind of checksum computed over the message and using a secret key. Without the secret key, it is not possible to compute a valid tag - hence all modifications applied to the data after the computation of the tag can be detected easily.

Separation of the concepts confidentiality and authenticity is relatively new. Historically, cryptographers believed that by using a strong encryption algorithm, they could ensure the authenticity of data as well. And indeed, when we are talking about human-readable messages, this assumption is justified. However, in the case of digital input data, both theory and practice have shown that the two goals are quite different.

Hence, next to encryption algorithms, cryptographers developed authentication algorithms. For example, the CBC-MAC algorithm operates by 'encrypting' the message with a block cipher in the Cipher Block Chaining (CBC) mode of operation, and then outputs the last block of ciphertext (possibly truncated) as tag. There are many variants on this scheme, most of them attempting to solve the problems that arise when a legacy block cipher like the DES is used as the underlying block cipher. When using the AES, even the simplest CBC-MAC construction is secure. 

When the length of the message to be protected is relatively large compared to the block length of the block cipher, the performance of the authentication step can be improved by using alternative constructions. Most widely used is HMAC, which produces a tag by hashing a message and a key together, operating at the speed of the underlying hash algorithm (e.g. SHA-256).

For applications that need to protect both confidentiality and authentication, the most straightforward approach is to process the input twice: once to encrypt the data and once to compute the authentication tag. This is called making two passes over the data. Recently, this approach has lost its appeal, for several reasons. The first observation that can be made is that there seems to be room for performance optimizations. Implementations may use the CBC mode of operation both for encryption and authentication, and it may appear a bit odd to run essentially the same process twice, each time with a different key. Secondly, and more importantly, there is the issue of ordering. Should we first encrypt the message and subsequently authenticate the ciphertext, or should we authenticate the message and subsequently encrypt both message and tag, or should we apply both in parallel on the message? Thirdly, can we use any encryption algorithm together with any authentication algorithm, or should we worry about mutual side-effects?

In order to solve these matters, cryptographers have been looking with increased interest at a different approach: the use of authenticated encryption modes. Here, a block cipher is used in a special mode of operation, which simultaneously provides confidentiality and authentication. The most efficient authenticated encryption modes provide authentication at a negligible additional cost compared to encryption only. These modes all appear to be patented or patent-pending. The second class of authenticated encryption modes offers no performance advantages compared to separate encryption and authentication passes, but still solves the ordering issue and avoids worrying about side-effects.

An example of the first class is the Integrity Aware Cipher Block Chaining Mode (IACBC). This mode is very similar to the ordinary CBC mode. A message consisting of m blocks P_i is encrypted (and authenticated) as shown below:

Integrity Aware Cipher Block Chaining Mode (IACBC)

C₀ = X₀ = Enc_K (r)

X_i = Enc_K (P_i + X_i-1)

C_i = X_i + S_i

C_m+1 = Enc_K (P₁ + P₂ + ... + P_m + X_m) + S₀

Here r is a random nonce, as with CBC. The whitening values S_i are new. They are derived from r by means of a scheme using log₂(m + 1) encryptions under a different key K'. The final ciphertext block is also new. It is an encryption of a checksum of all the plaintext blocks. Compared to ordinary CBC, authentication is provided at the cost of log₂(m + 1) + 1 additional encryptions and management of one additional key.

In the second class, the CCM mode of operation uses two separate passes to provide confidentiality and authenticity. It consists of an input formatting step, a CBC-MAC operation (with IV set to zero), and finally an encryption in counter (CTR) mode. The underlying block cipher is assumed to be AES. The same key is used for both the CBC-MAC operation and the CTR encryption. The EAX mode of operation is similar, but different. It uses OMAC instead of CBC-MAC, and it performs the authentication step after the encryption step, which is still done with CTR mode. 

All the proposed modes come with a proof of security, provided that the underlying block ciphers satisfies some requirements. CCM has the advantage of having been adopted by NIST but, despite (or perhaps because!) of this, it has been the subject of criticisms by members of the cryptographic community. 

None of the proposed modes offers a functionality that can't be provided using a combination of the classical techniques at the same or marginally slower performance. Their main advantages are their simpler proofs of security, reduced key management and the fewer opportunities they leave for mistakes. 

References

NIST Special Publication 800-38C: Recommendation for block cipher modes of operation: the CCM mode for authentication and confidentiality.

Image: "1040", courtesy of x6e38, Flickr (CC BY 2.0)

Previously published in Cryptomathic NewsOnInk, 2005