Network Working Group IPsec Working Group INTERNET DRAFT C.S. Jutla, IBM November 2000 Expiration Date: May 2001 A Parallelizable Authenticated Encryption Algorithm for IPsec Status of this Memo This document is an Internet-Draft and is in full con- formance with all provisions of Section 10 of RFC2026. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its work- ing groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inap- propriate to use Internet- Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Abstract This document describes a new authenticated encryption mode of operation of block ciphers called "Integrity Aware Parallelizable Mode (IAPM)" which is simple, efficient, highly parallelizable, and provably secure. One of the main features distinguishing the new mode (IAPM) from existing modes is that along with providing confidentiality of the payload, the new mode also pro- vides authenticity of the payload. This is particularly relevant to the ESP security protocol of IPsec. The mode IAPM has the same provable security as CBC (for confidentiality) and CBC-MAC (for authentication). IAPM has a critical path of only two block cipher invo- cations, leading to highly parallel implementations. Moreover, for serial implementations the new mode of operation offers twice the throughput of CBC plus CBC- MAC, as it achieves the additional property of authen- tication with little extra expense. Jutla 1 Table of Contents 1. Introduction ....................................... 3 2. Integrity Aware Parallelizable Mode (IAPM) ......... 4 2.1. Generating the Pairwise Independent Set ..... 5 2.2. Generating the random vector r .............. 6 2.3. Keys ........................................ 6 2.4. Security Considerations ..................... 6 3. ESP Header Authentication .......................... 7 4. Further Variants .................................. 8 4.1. Generating the Pairwise Differentially Uniform Set ...................................... 9 5. Intellectual Property Issues ....................... 10 6. Acknowledgments .................................... 10 7. References ......................................... 10 8. Author's Address ................................... 11 Jutla 2 Internet Draft Nov 2000 1. Introduction In this document we propose a new mode of operation for symmetric key block cipher algorithms. Modes of opera- tion are relevant to IPSEC (RFC 2401) as they are used to implement the security protocols in IPSEC. One of the main features distinguishing the new mode of opera- tion from existing modes is that along with providing confidentiality of the payload, it also provides authenticity of the payload. In other words, the new mode is not just a mode of operation for encryption, but a mode of operation for authenticated encryption. The new mode achieves the additional property with lit- tle extra overhead. The new mode which we refer to as "Integrity Aware Parallelizable Mode (IAPM)" is highly parallelizable, as the name suggests. In fact, IAPM has critical path of only two block cipher invocations. By one estimate, a hardware implementation of the IAPM mode on a single board (housing 1000 block cipher units) achieves terabits/sec of authenticated encryption. Moreover, there is no penalty for doing a serial implementation of this mode. In fact, a serial implementation is expected to be almost twice as fast as doing encryp- tion with Cipher Block Chaining (CBC) ([ANSI],[NBS]) mode and a separate authentication with CBC-MAC. The new mode is highly relevant to IPsec, as one of the most prevalent security protocols in IPsec (the Encap- sulating Security Payload) recommends both encryption and integrity protection (see [Bel],[CGHK]). The default IPsec algorithms are DES in CBC mode of opera- tion, and HMAC-MD5 ([BCH]). However, as the standard currently stands, the goal of authenticated encryption is achieved by employing DES in CBC mode and then authenticating using HMAC-MD5 in a separate pass. The new mode achieves both goals in a single pass, and more importantly offers highly parallel implementations. Although, parallelizable modes of operation for encryp- tion were well known, e.g. the counter mode, there was no mode known for authentication which could achieve this level of parallelism. The authentication code Jutla 3 Internet Draft Nov 2000 UMAC [BHKKR] does have an inherent parallelism, but it suffers from requiring too much key material (or a pseudorandom number generator to expand the key). The new mode IAPM also comes with proofs of security [Jut], assuming that the underlying block cipher is secure. For confidentiality, the mode has the same provable security as CBC. For authentication, the mode has the same provable security as CBC-MAC. 2. Integrity Aware Parallelizable Mode (IAPM) Let n be the block size of the underlying block cipher. For example, DES ([FIPS]) has block size 64 bits, and AES has block size 128 bits. If the block cipher requires keys of length k, then this mode requires two keys of length k. Let these keys be called K0 and K1. We will use Encrypt(K,B) to denote the n bit result produced by the underlying block cipher when a block B of size n bits is encrypted using key K. Similarly, we will use Decrypt(K,B) to denote the n bit result pro- duced by the underlying block cipher (in decrypt mode) when a block B of size n bits is decrypted using key K. The payload to be encrypted P, is divided into blocks of length n each. Let these blocks be P[1],P[2],...,P[m-1]. We will assume that the payload is sufficiently padded as is provisioned in IPSEC. An n bit random initial vector r is chosen (see section 2.2 for more details). Using the key K0, this random vector is used to prepare (m+1) new pair-wise independent n- bit random vectors S[0],S[1],...,S[m]. Assume for now the following declaration of a procedure to generate such a set S: procedure pairwise_independent_set(in r, m, K0; out S); A proposed standard definition of the above pro- cedure is given in section 2.1. Given the plaintext payload P of (m-1) blocks, random vector r, the keys K0, and K1, the cipher text C= is generated as follows: invoke pairwise_independent_set(r,m,K0,S) M[0]= r N[0]= Encrypt(K1,M[0]) C[0]= N[0] Jutla 4 Internet Draft Nov 2000 for i= 1 to m-1 do M[i]= P[i] xor S[i] N[i]= Encrypt(K1,M[i]) C[i]= N[i] xor S[i] end for checksum = P[1] xor P[2] xor ... xor P[m-1] M[m]= checksum xor S[m] N[m]= Encrypt(K1,M[m]) C[m]= N[m] xor S[0] Note that S[0] is used in the last block. Also note that the ciphertext has two more blocks than the plain- text; one corresponding to the random vector r, and one corresponding to the checksum. The operation xor above is the bit-wise exclusive or operation. Given the ciphertext payload C of (m+1) blocks, C= , and the keys K0, and K1, the plaintext P= is generated as follows (along with an authentication test): N[0]= C[0] M[0]= Decrypt(K1,N[0]) r= M[0] invoke pairwise_independent_set(r,m,K0,S) for i= 1 to m-1 do N[i]= C[i] xor S[i] M[i]= Decrypt(K1,N[i]) P[i]= M[i] xor S[i] end for checksum = P[1] xor P[2] xor ... xor P[m-1] N[m]= C[m] xor S[0] M[m]= Decrypt(K1,N[m]) P[m]= M[m] xor S[m] Integrity = (P[m] == checksum) 2.1. Generating the Pairwise Independent Set The pairwise independent set can be generated by a sim- ple algebraic method involving arithmetic modulo a prime p. For this purpose, a standard prime p should be chosen for each block size. The proposed standard prime for block size 64 bits is p = 2^64-257. The proposed standard prime for block size 128 bits is p= 2^128-159. Here is the proposed definition of the procedure pairwise_indepedent_set for 128 bit block size ciphers: Jutla 5 Internet Draft Nov 2000 procedure pairwise_independent_set(in r, m, K0; out S) { a= Encrypt(K0,r+1) b= Encrypt(K0,r+2) if (b > (2^128 - 159)) then b = (b + 159) mod 2^128 S[0]= a for i= 1 to m do S[i]= (S[i-1] + b ) mod 2^128 if (b > S[i]) S[i] = (S[i] + 159) mod 2^128 end for } The condition (b > S[i]) is equivalent to checking if a carry was produced off the most significant bit in the previous addition. 2.2. Generating the random vector r The algorithm as described in section 2 calls for a random vector r. Sometimes, this random vector is called initial vector (IV). The algorithm doesn't require the random vector to be random (in the sense of uniformly distributed etc.), but different for each payload. This can be easily achieved in ESP (Encapsu- lating Security Payload) as the ESP Header requires a sequence number (which is a unique number for each packet, till the key is refreshed). In ESP the standard sequence number is a 32 bit quantity. If the key is not going to be used for more than 2^32 different payloads, then clearly, the sequence number can serve the purpose of r. However, we recommend that the other 32 bits be assigned a random number how so ever chosen (for 64 bit block ciphers). 2.3. Keys The mode as described in section 2 requires two dif- ferent keys K0, K1 of k bits each, where k is the length of the key required by the underlying block cipher. The mode of operation remains secure even if the keys K0 and K1 are same. However, we recommend that different independent keys be chosen. 2.4. Security Considerations The mode IAPM proposed in section 2, like CBC, employs a block cipher. A mode of operation allows a longer payload to be encrypted/authenticated, using an Jutla 6 Internet Draft Nov 2000 underlying block cipher like DES. There are no proofs of security of block ciphers; a block cipher is regarded secure if it has been tested against all known attacks and cryptanalytic tools. However, once one assumes that a block cipher is secure, the security of modes of operation like CBC, CBC-MAC and IAPM can be proven. In simple terms, if a block cipher of block size n bits is considered secure for usage of upto 2^n blocks, then it is useful to prove that the block cipher used in a mode to encrypt longer messages (i.e. longer than one block, and now security refers to secrecy of the whole message), is still secure for usage of upto 2^(n/2) total blocks. Here, the total blocks refers to sum of the number of blocks over all messages. The mode of operation CBC (Cipher Chain Blocking) was proven secure in [BDJR] in this sense. Similarly, the authentication scheme CBC-MAC was proven secure in [BKR]. Both these proofs assume that the underlying block cipher is secure. Similarly, assuming that the underlying block cipher is secure, the mode IAPM has the same security bound for confidentiality as CBC, and the same security bound for authentication as CBC-MAC (see [Jut] for proofs of security). 3. ESP Header Authentication The ESP protocol requires that even the ESP header be authenticated. In paritcular, the ESP header contains the sequence number of the packet which needs to be authenticated, otherwise the ESP protocol is prone to replay attacks. However, the ESP header is transmitted unencrypted. It is sent unencrypted, partly because it has other information as to which encryption algorithm to use, but also because most implementations keep a window of sequence numbers, and can discard a packet with a repeated sequence number even before decryption/authentication. The mode as proposed in section 2, authenticates only the ciphertext, and thus the sequence number was sent encrypted. However, the mode in section 2 can be modified so that the block C[0] instead of being an encryption of r, can be r itself. This was observed in [Rog]. In other words, C[0]=r Jutla 7 Internet Draft Nov 2000 This variant of the mode still authenticates the whole ciphertext i.e. C=. In other words, any change in the ciphertext will be detected on decryption as integrity failure. Thus, r is transmitted unencrypted, but still authenticated. The proofs of security in [Jut] continue to hold for this variant. Since, r contains the sequence number, the crucial por- tion of the ESP header which needed to be authenticated is indeed authenticated. The block C[0] can then be made part of the ESP header itself. The last block C[m] can be placed in the "MAC" field of the ESP packet. 4. Further Variants For smaller payloads, the generation of two random numbers a, b in the procedure pairwise_independent_set maybe expensive. This concern was expressed in [GD], where they had a solution which generated only one ran- dom number a. Here we propose another variant of the IPAM mode of section 2 which only requires generating one random number a. This variant instead of using a pairwise independent set S, uses a pairwise differen- tially uniform set. The security bounds as mentioned in section 2.4, and the proofs in [Jut] continue to hold for this variant. More precisely, this variant has the same security bounds as CBC (for confidentiality) and CBC-MAC (for authentication). The solution in [GD] pro- vides a slightly weaker security bound than CBC and CBC-MAC. Assume for now the following declaration of a procedure to generate a pairwise differentially uniform set S: procedure pairwise_diff_uniform_set(in r, m, K0; out S); A proposed standard definition of the above procedure is given in section 4.1. Given the plaintext payload P of (m-1) blocks, random vector r, the keys K0, and K1, the cipher text C= is generated as follows: Jutla 8 Internet Draft Nov 2000 invoke pairwise_diff_uniform_set(r,m,K0,S) C[0]= r for i= 1 to m-1 do M[i]= P[i] + S[i] N[i]= Encrypt(K1,M[i]) C[i]= N[i] + S[i] end for checksum = P[1] + P[2] + ... + P[m-1] M[m]= checksum + S[m] N[m]= Encrypt(K1,M[m]) C[m]= N[m] + S[0] The operation "+" above is the n-bit integer addition operation. Given the ciphertext payload C of (m+1) blocks, C= , and the keys K0, and K1, the plaintext P= is generated as follows (along with an authentication test): r= C[0] invoke pairwise_diff_uniform_set(r,m,K0,S) for i= 1 to m-1 do N[i]= C[i] - S[i] M[i]= Decrypt(K1,N[i]) P[i]= M[i] - S[i] end for checksum = P[1] + P[2] + ... + P[m-1] N[m]= C[m] - S[0] M[m]= Decrypt(K1,N[m]) P[m]= M[m] - S[m] Integrity = (P[m] == checksum) The operation "-" above is the n-bit integer subtract- ion operation. 4.1. Generating the Pairwise Differentially Uniform Set Again, a standard prime p should be chosen for each block size. The proposed standard prime for block size 64 bits is p = 2^64-257. The proposed standard prime for block size 128 bits is p= 2^128-159. Here is the proposed definition of the procedure pairwise_diff_uniform_set for 128 bit block size ciphers: Jutla 9 Internet Draft Nov 2000 procedure pairwise_diff_uniform_set(in r, m, K0; out S) { a= Encrypt(K0,r+1) if (a > (2^128 - 159)) then a = (a + 159) mod 2^128 S[0]= a for i= 1 to m do S[i]= (S[i-1] + a ) mod 2^128 if (a > S[i]) S[i] = (S[i] + 159) mod 2^128 end for } 5. Intellectual Property Issues IBM has filed U.S. patents on this mode and its vari- ants in April, 2000. 6. Acknowledgments The author would like to thank Pau-Chen Cheng, J.R. Rao, and Pankaj Rohatgi for helpful comments. The author would also like to thank Don Coppersmith, Ron Rivest and Pankaj Rohatgi for going through the secu- rity proofs. 7. References [ANSI] ANSI X3.106, ``American National Standard for Information Systems - Data Encryption Algorithm - Modes of Operation'', American National Standards Institute, 1983. [NBS] National Bureau of Standards, NBS FIPS PUB 81, ``DES modes of operation'', U.S. Department of Commerce, 1980. [FIPS] National Bureau of Standards, Data Encryption Stan- dard, U.S. Department of Commerce, FIPS 46 (1977) [Bel] S. M. Bellovin, "Problem Areas for the IP Security Protocols", Proc. of the 6th USENIX UNIX Security Symp., Jul 1996 [BCH] M. Bellare, R. Canetti, H. Krawczyk, " Keyed Hash Functions and Message Authentication", Advances in Cryptology, Crypto 96, LNCS 1109, 1996. Jutla 10 Internet Draft Nov 2000 Expiration Date: May 2001 [BKR] M. Bellare, J. Kilian, P. Rogaway, ``The Security of Cipher Block Chaining'', CRYPTO 94, LNCS 839, 1994 [BDJR] M. Bellare, A. Desai, E. Jokiph, P. Rogaway, ``A Con- crete Security Treatment of Symmetric Encryption: Analysis of the DES Modes of OPeration'', 38th IEEE FOCS, 1997 [CGHK] P,-C. Cheng, J.A. Garay, A. Herzberg, H. Krawczyk, "A security architecture for the internet protocol", IBM Systems Journal, Vol 37, No. 1, 1998. [GD] V. D. Gligor and P. Donescu, "Fast Encryption and Authentication: XCBC Encryption and XECB Authentication Modes", Symmetric Key Block Cipher Modes of Operation Workshop, http://csrc.nist.gov/encryption/aes/modes/ [IPSEC] Security Architecture for the Internet Protocol, RFC 2401, http://www.ietf.org/rfc/rfc2401.txt [Jut] C.S. Jutla, "Encryption Modes with Almost Free Message Integrity", http://eprint.iacr.org/2000/039, August 1, 2000. Also, Symmetric Key Block Cipher Modes of Opera- tion Wksp., http://csrc.nist.gov/encryption/aes/modes/ [Rog] P. Rogaway, "OCB Mode: Parallelizable Authenticated Encryption", Symmetric Key Block Cipher Modes of Opera- tion Wksp., http://csrc.nist.gov/encryption/aes/modes/ 8. Author's Address Charanjit S. Jutla IBM T.J. Watson Research Center, Yorktown Heights, NY 10598-704. Phone: 914-784-7890 Email: csjutla@watson.ibm.com Comments should be sent to the above e-mail address. Jutla 11