Authenticated Encryption: CCM and GCM

AUTHENTICATED ENCRYPTION: CCM AND GCM

Authenticated encryption (AE) is a term used to describe encryption systems that simultaneously protect confidentiality and authenticity (integrity) of communications. Many applications and protocols require both forms of security, but until recently the two services have been designed separately.

[BLAC05] discussed four common approaches to providing both confidential- ity and encryption for a message M.

•                           HtE: Hash-then-encrypt. First compute the cryptographic hash function over

M as h  = H(M). Then encrypt the message plus hash function: E(K, (M||h)).

MtE: MAC-then-encrypt. Use two keys. First authenticate the plaintext by computing the MAC value as T = MAC(K1, M). Then encrypt the message plus tag: E(K2, (M || T). This approach is taken by the SSL/TLS protocols (Chapter 16).

•                           EtM: Encrypt-then-MAC. Use two keys. First encrypt the message to yield the ciphertext C  = E(K2, M).        Then  authenticate          the     ciphertext   with T = MAC(K1, C) to yield the pair (C, T). This approach is used in the IPsec protocol (Chapter 19).

•                           E&M: Encrypt-and-MAC. Use two keys. Encrypt the message to yield the ciphertext C = E(K2, M). Authenticate the plaintext with T = MAC(K1, M)  to yield the pair (C, T). These operations can be performed in either order. This approach is used by the SSH protocol (Chapter 16).

Both decryption and verification are straightforward for each approach. For HtE, MtE, and E&M, decrypt first, then verify. For EtM, verify first, then decrypt. There are security vulnerabilities with all of these approaches. The HtE approach is used in the Wired Equivalent Privacy (WEP) protocol to protect WiFi networks. This approach had fundamental weaknesses and led to the replacement of the WEP proto- col. [BLAC05] and [BELL00] point out that there security concerns in each of the three encryption/MAC approaches listed above. Nevertheless, with proper design, any of these approaches can provide a high level of security. This is the goal of the two approaches discussed in this section, both of which have been standardized by NIST.

Counter with Cipher Block Chaining-Message Authentication Code

The CCM mode of operation was standardized by NIST specifically to support the security requirements of IEEE 802.11 WiFi wireless local area networks (Chapter 17), but can be used in any networking application requiring authenticated encryption. CCM is a variation of the encrypt-and-MAC approach to authenticated encryption. It is defined in NIST SP 800-38C.

The key algorithmic ingredients of CCM are the AES encryption algorithm (Chapter 5), the CTR mode of operation (Chapter 6), and the CMAC authentica- tion algorithm (Section 12.6). A single key K is used for both encryption and MAC algorithms. The input to the CCM encryption process consists of three elements.

1.                                       Data that will be both authenticated and encrypted. This is the plaintext message P of data block.

2.                                       Associated data A that will be authenticated but not encrypted. An example is a protocol header that must be transmitted in the clear for proper protocol operation but which needs to be authenticated.

3.                                       A nonce N that is assigned to the payload and the associated data. This is a unique value that is different for every instance during the lifetime of a proto- col association and is intended to prevent replay attacks and certain other types of attacks.

Figure 12.9 illustrates the operation of CCM. For authentication, the input includes the nonce, the associated data, and the plaintext. This input is formatted as a sequence of blocks B0 through Br. The first block contains the nonce plus some formatting bits that indicate the lengths of the N, A, and P elements. This is fol- lowed by zero or more blocks that contain A, followed by zero of more blocks that contain P. The resulting sequence of blocks serves as input to the CMAC algorithm, which produces a MAC value with length Tlen, which is less than or equal to the block length (Figure 12.9a).

For encryption, a sequence of counters is generated that must be independent of the nonce. The authentication tag is encrypted in CTR mode using the single counter Ctr0. The Tlen most significant bits of the output are XORed with the tag to produce an encrypted tag. The remaining counters are used for the CTR mode encryption of the plaintext (Figure 6.7). The encrypted plaintext is concatenated with the encrypted tag to form the ciphertext output (Figure 12.9b).

SP 800-38C defines the authentication/encryption process as follows.

For decryption and verification, the recipient requires the following input: the ciphertext C, the nonce N, the associated data A, the key K, and the initial counter Ctr0. The steps are as follows.

1.                                       If Clen £ Tlen, then return INVALID.

2.                                       Apply  the  counter  generation  function  to  generate  the  counter     blocks

Ctr0, Ctr1,  Á, Ctrm, where m = < Clen/128 >.

3.                                       For j  = 0 to m, do Sj  = E(K,  Ctrj).

4.  Set S = S1 || S2 || Á || Sm.

5.                                       Set P = MSBClen - Tlen(C) { MSBClen - Tlen(S).

6.                                       Set T = LSBTlen(C)  NOR  MSBTlen(S0).

7.                                       Apply   the   formatting   function to (N, A, P) to   produce   the  blocks B0, B1, Á , Br.

8.                                       Set Y0  = E(K, B0).

9.                                       For i = 1 to r, do Yi = E(K, (Bi  NOR  Yi - 1)).

10.                                   If T  |=MSBTlen (Yr), then return INVALID, else return P

CCM is a relatively complex algorithm. Note that it requires two complete passes through the plaintext, once to generate the MAC value, and once for encryp- tion. Further, the details of the specification require a tradeoff between the length of the nonce and the length of the tag, which is an unnecessary restriction. Also note that the encryption key is used twice with the CTR encryption mode: once to generate the tag and once to encrypt the plaintext plus tag. Whether these complexities add to the security of the algorithm is not clear. In any case, two analyses of the algorithm ([JONS02] and [ROGA03]) conclude that CCM provides a high level of security.

Galois/Counter Mode

The GCM mode of operation, standardized by NIST in NIST SP 800-38D, is designed to be parallelizable so that it can provide high throughput with low cost and low latency. In essence, the message is encrypted in variant of CTR mode. The resulting ciphertext is multiplied with key material and message length information over GF(2128) to generate the authenticator tag. The standard also specifies a mode of operation that supplies the MAC only, known as GMAC.

The GCM mode makes use of two functions: GHASH, which is a keyed hash function, and GCTR, which is essentially the CTR mode with the counters deter- mined by a simple increment by one   operation.

GHASHH(X) takes a input the hash key H and a bit string X such that len(X) = 128m bits for some positive integer m and produces a 128-bit MAC value. The function may be specified as follows (Figure 12.10a).

This formulation has desirable performance implications. If the same hash key is to be used to authenticate multiple messages, then the values H2, H3, Á can be precalculated one time for use with each message to be authenticated. Then, the blocks of the data to be authenticated (X₁, X₂, Á , Xm) can be processed in parallel, because the computations are independent of one another.

GCTRK(ICB, X) takes a input a secret key K and a bit string X arbitrary length and returns a ciphertext Y of bit length len(X). The function may be specified as follows (Figure 12.10b).

1.                        If X is the empty string, then return the empty string as   Y.

2.                        Let n  =  <(len(X)/128)>. That is, n is the smallest integer greater than or equal to len(X)/128.

Note that the counter values can be quickly generated and that the encryption operations can be performed in parallel.

We can now define the overall authenticated encryption function (Figure 12.11). The input consists of a secret key K, an initialization vector IV, a plaintext P, and

additional authenticated data A. The notation [x]s means the s-bit binary representa- tion of the nonnegative integer x. The steps are as follows.

1.  Let H  = E(K, 0128).

2.                                       Define a block, J0, as

If len(IV) = 96, then let J0 = IV || 031 || 1.

If len (IV) |=96, then let s = 128 < len(IV)/128 = - len(IV), and let

J0  =  GHASHH(IV || 0s + 64 || [len(IV)]64).

3.                                       Let C = GCTRK(inc32(J0), P).

4. Let u = 128 <len(C)/128> - len(C) and let v = 128 <len(A)/128> - len(A).

5.                                       Define a block, S, as

S = GHASHH(A || 0v || C || 0u || [len(A)]64 || [len(C)]64)

6.                                       Let T  =  MSBt(GCTRK1J0, S)), where t is the supported tag length.

7.                                       Return (C, T).

In step 1, the hash key is generated by encrypting a block of all zeros with the secret key K. In step 2, the pre-counter block (J0) is generated from the IV. In par- ticular, when the length of the IV is 96 bits, then the padding string 031 || 1 is appended to the IV to form the pre-counter block. Otherwise, the IV is padded with the minimum number of 0 bits, possibly none, so that the length of the result- ing string is a multiple of 128 bits (the block size); this string in turn is appended with 64 additional 0 bits, followed by the 64-bit representation of the length of the IV, and the GHASH function is applied to the resulting string to form the pre- counter block.

Thus, GCM is based on the CTR mode of operation and adds a MAC that authenticates both the message and additional data that requires only authentica- tion. The function that computes the hash uses only multiplication in a Galois field. This choice was made because the operation of multiplication is easy to perform within a Galois field and is easily implemented in hardware [MCGR05].

[MCGR04] examines the available block cipher modes of operation and shows that a CTR-based authenticated encryption approach is the most efficient mode of operation for high-speed packet networks. The paper further demonstrates that GCM meets a high level of security requirements.