Network Working Group J. Etienne Internet-Draft May 14, 2001 Expires: November 12, 2001 The counter-mode and its use with ESP draft-etienne-ipsec-esp-ctr-mode-00.txt Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working 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 inappropriate 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. This Internet-Draft will expire on November 12, 2001. Copyright Notice Copyright (C) The Internet Society (2001). All Rights Reserved. Abstract This memo presents the use of the counter mode in the context of ESP and specifies its application to DES, 3DES and AES. The counter mode significantly reduces the ESP space overhead compared to the standard CBC with explicit IV (Section 5.2.1). Moreover, the counter mode allows parallelisation and precomputation of most of the processing (Section 5.1). Etienne Expires November 12, 2001 [Page 1] Internet-Draft counter mode with ESP May 2001 Table of Contents 1. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1 Description of the counter mode . . . . . . . . . . . . . . 3 1.2 Terminology . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Counter . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.1 Counter construction . . . . . . . . . . . . . . . . . . . . 4 2.2 Counter Uniqueness . . . . . . . . . . . . . . . . . . . . . 5 3. Encryption and decryption . . . . . . . . . . . . . . . . . 5 3.1 Counter initialization . . . . . . . . . . . . . . . . . . . 6 3.2 Pad's length computation . . . . . . . . . . . . . . . . . . 6 3.3 Generate N_BLK blocks of pad . . . . . . . . . . . . . . . . 6 3.4 Apply the pad . . . . . . . . . . . . . . . . . . . . . . . 6 4. Assumptions and limitations . . . . . . . . . . . . . . . . 6 4.1 relation to anti-replay . . . . . . . . . . . . . . . . . . 6 4.2 relation to authentication algorithms . . . . . . . . . . . 7 4.3 relation to encryption algorithms . . . . . . . . . . . . . 7 5. Performance Evaluation . . . . . . . . . . . . . . . . . . . 7 5.1 Speed evaluation . . . . . . . . . . . . . . . . . . . . . . 7 5.2 Space evaluation . . . . . . . . . . . . . . . . . . . . . . 8 5.2.1 Comparison with CBC and explicit IV . . . . . . . . . . . . 8 6. Application to cipher algorithms . . . . . . . . . . . . . . 8 6.1 Mode of operations . . . . . . . . . . . . . . . . . . . . . 8 6.2 Key size . . . . . . . . . . . . . . . . . . . . . . . . . . 9 6.3 Weak keys . . . . . . . . . . . . . . . . . . . . . . . . . 9 6.4 block size and padding . . . . . . . . . . . . . . . . . . . 10 6.5 rounds . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 7. Security considerations . . . . . . . . . . . . . . . . . . 10 8. Acknowledgement . . . . . . . . . . . . . . . . . . . . . . 11 References . . . . . . . . . . . . . . . . . . . . . . . . . 11 Author's Address . . . . . . . . . . . . . . . . . . . . . . 12 A. block size smaller than 64bit . . . . . . . . . . . . . . . 12 Full Copyright Statement . . . . . . . . . . . . . . . . . . 13 Etienne Expires November 12, 2001 [Page 2] Internet-Draft counter mode with ESP May 2001 1. Overview We present the counter mode in ESP independently of any specific block cipher algorithms. Examples are given using DES, 3DES, and AES (Section 6). This memo does not explain the cryptographic principals behind the security of the counter mode, see [13] for details. Briefly, the counter mode uses an unique counter that is shared by both peers. This counter is used to generate a pad, which is X-ORed with plaintext to obtain ciphertext. The pad appears as a pseudo- random bitfield. It is a concatenation of blocks, each of them being the encryption of an incremented counter (see Section 1.1 for more details). The counter mode is intended to add little overhead, be efficiently processed, and be easily implemented: It doesn't add any space overhead to ESP (Section 5.2). CBC with explicit IV (RFC2405 [5] or AES-CBC [11]) has an overhead 28% to 109% larger depending on the SA parameters (Section 5.2.1). It allows precomputation and parallelisation (Section 5.1). Both encryption and decryption of the payloads in counter mode use the encryption function of the chosen cipher (Section 3). This reduces the software required, which aids in optimization of both hardware and software implementations. 1.1 Description of the counter mode Counter mode adds the need to share a counter in addition to sharing the usual secret key. Note that the counter (Section 2) doesn't need to be secret. The processing of the i-th block of a packet is: o Ci = Pi xor E( counter + i ) for the encryption o Pi = Trunc(n,Ci xor E( counter + i )) for the decryption With the following notation: o E() is the encryption function of a block cipher (e.g DES). o Ci is the i-th block of the encrypted packet. o Pi is the n first bytes of the i-th block of the plain packet. The value of n is between 1 and the block size. This assumes the data length is exchanged out of band, in our case it is computed from the ip total length (RFC0791.3.1 [1]). o The Trunc(x,y) function truncates the x first bytes of the y value. Etienne Expires November 12, 2001 [Page 3] Internet-Draft counter mode with ESP May 2001 o counter is a counter incremented at each block (Section 2). 1.2 Terminology The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in rfc2119 [2]. In this memo, the term pad is unrelated to the padding length field present in the ESP header (RFC2406.2 [6]). 2. Counter The counter is the core of this mode of operation (Section 2.1). The security relies on its uniqueness (Section 2.2) for any block encrypted with a given ESP key. We assume the block size is at least 64 bits long. We believe it is reasonable as most block ciphers match this requirement. In Appendix A, we suggest possible modifications for block ciphers with a block size smaller than 64-bit. 2.1 Counter construction The counter is composed of the counter block which includes the effective counter: 1. The counter block is as large as the cipher block size and is stored in network order. It is the input of the block cipher during the pad computation. The 64 least significant bits are called the effective counter. The bits of the counter block outside the effective counter are zeroed. 2. The effective counter is then separated into the ESP sequence number which resides in 32 most significant bits, and the block index which resides in the 32 least significant bits. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ESP Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Block Index | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure: The effective counter Etienne Expires November 12, 2001 [Page 4] Internet-Draft counter mode with ESP May 2001 ESP sequence number: 32-bit strictly increasing number stored in network order. It is a field of the ESP header (RFC2406.2.2 [6]) used to prevent an attacker from replaying packets. Each ESP datagram contains a unique sequence number. Block index: 32-bit unsigned integer coded in network order. It is the block index inside a single packet. The first block of a packet has the index 0, the next has 1 and so on. 2.2 Counter Uniqueness The counter MUST be unique (Section 2.2) for any block encrypted by a given ESP key or an attacker could XOR 2 cipher blocks and obtain a XOR of the 2 corresponding blocks of plaintext. We believe our counter matches this requirement because: o The ESP sequence number is strictly increasing and so, is unique per packet (RFC2406.3.3.3 [6]). o The block index MUST be never cycle during the processing of a packet. It MUST be equal to and greater than the largest possible packet divided by the block size of the cipher. ESP is applicable to IPv4 and IPv6 (RFC2406.3.1 [6]). The size of the biggest IPv4 packet is 64 Kbyte (RFC0791.3.1 [1]). For IPv6, it is 64 Kbyte (RFC2460.3 [9]) without option, and can go up to 4 Mbyte with the jumbo option (RFC2675 [10]). In the worst case of a maximally sized 4MByte packet and the smallest block size of 64 bits, the block index must be at least 29-bit. A 32-bit value is guaranteed not to cycle, the unused three bits are considered a reasonable overhead allowing for simplicity of implementation. The block index does not overflow in a packet, and each packet contains an ESP sequence number that is unique per key. So the sequence number and block index tuple is unique per key. 3. Encryption and decryption This section explains the encryption and decryption using the counter mode. The two operations use the exact same code which simplifies the implementation and reduces the memory footprint. In this section, the term source text describe the plaintext for a encryption and ciphertext for an encryption. The steps for encrypting or decrypting are initializing the counter, computing the pad's length, generating N_BLK blocks of pad and, then, applying the pad to the source text. Note that the pad generation and its application may be interleaved Etienne Expires November 12, 2001 [Page 5] Internet-Draft counter mode with ESP May 2001 to save resources. 3.1 Counter initialization The counter block is initialized in 3 step: First, any bit more significant than the 64th is zeroed (applicable only if the block is larger than 64-bit). Second, the ESP sequence number is copied from the ESP header to the 32 most significant bit of the effective counter. Last, the block index is zeroed. 3.2 Pad's length computation Before operating on a packet of PKT_LEN bytes, a pad of N_BLK blocks must be generated with: N_BLK = Floor( (PKT_LEN + BLK_SIZE -1) / BLK_SIZE ) BLK_SIZE is the cipher block size and Floor(X) returns the largest integer not greater than X. The pad may be longer than the source text up to BLK_SIZE-1 byte. 3.3 Generate N_BLK blocks of pad For each block of pad, the corresponding counter is encrypted with the cipher algorithm to become a block of pad. After generating any block, except the last, the block index MUST be incremented. As the block index is large enough for any packet length and block size, it won't overflow the ESP sequence number and there is no need to handle a multi-precision addition on 32-bit CPU. 3.4 Apply the pad Each byte of the source text is XORed with the byte of the pad with the same offset. Thus, the source text doesn't need to be block aligned. 4. Assumptions and limitations Using the counter mode assumes to enable the anti-replay for this SA (Section 4.1), not to expect authentication from it (Section 4.2) and not to use a differentially weak encryption algorithm (Section 4.3). 4.1 relation to anti-replay The anti-replay (RFC2406.3.3.3 [6]) MUST be enabled. The ESP sequence number is the base of the counter and if the sequence number rolls over, the counter would be reused. This would be a flaw because the counter must be unique under the lifetime of a key Etienne Expires November 12, 2001 [Page 6] Internet-Draft counter mode with ESP May 2001 (Section 2.2). We believe that required anti-replay support is reasonable because it adds negligible processing overhead and prevents attackers from replaying packets. 4.2 relation to authentication algorithms Like CBC and other common modes [12], the counter mode doesn't insure integrity or authentication. It isn't a goal of the mode of operation. In ESP, the authentication is optional (RFC2406.3.2.2 [6]). If integrity or authentication are desired, the authentication algorithm MUST NOT be NULL. There are no known issues regarding interactions between DES, 3DES or AES in counter mode with any authentication algorithms. 4.3 relation to encryption algorithms The encryption algorithm MUST NOT be differentially weak. As the counter mode is based on the encryption of a counter, an attacker may obtain many pairs of plaintext/ciphertext with low hamming distance between the plaintext and performs a differential cryptanalysis attack [17]. We believe it is a reasonable requirement as it isn't a goal of the mode of operation to fix the cipher's flaw. WORK: status of DES, 3DES, AES 5. Performance Evaluation The counter mode is very efficient in speed thanks to parallelisation and precomputation (Section 5.1) and in space because it doesn't need explicit IV or padding (Section 5.2). 5.1 Speed evaluation The computation is parallelisable i.e. two blocks can be computed independently. An implementation may take advantages of this to increase it speed. In software, it is possible to use pipelining, large number of registers or SIMD instructions. Moreover, the hardware can be more fully used thanks to the fine grain parallelisation. The computation may be preprocessed. Most of the processing time is due to the encryption algorithm in the pad calculation. The ESP sequence number is predictable and the pad values don't depend on the source text. So, the pad can be precomputed even before receiving the packet. Etienne Expires November 12, 2001 [Page 7] Internet-Draft counter mode with ESP May 2001 5.2 Space evaluation The counter mode is very efficient from a space viewpoint: It doesn't need explicit IV or padding. So it can be done in place. 5.2.1 Comparison with CBC and explicit IV CBC with explicit IV (RFC2405 [5]) is the current MUST for the ESP encryption (RFC2406.5 [6]). But it requires including an explicit IV in the output which adds an additional block of bytes to the output. It also requires aligning the plaintext to the cipher block size, which adds half the block size, on average, to the output. This implies that the counter mode will see a savings of one and a half times the block size in comparison. The following table presents the overhead size in bytes according to the SA parameters (i.e. cryptography and ESP mode). The unit is the byte and the percentages are compared to same cipher using the counter mode. The IPv4 header typically uses 20-byte (RFC0791.3.1 [1]). The ESP header and footer uses 10-byte (RFC2406.2 [6]) and the default authentication is a 96-bit MAC, so 12 bytes long (RFC2403 [3] or RFC2404 [4]). +================================================================+ | SA \ Avg Overhead | cipher | ESP tunnel | ESP transport | +===================+=============+==============+===============+ |(DES-CTR | AES-CTR)| | 20+10+12= | 10 + 12 = | | +HMAC-MD5-96 | 0 | 42 | 22 | +----------------------------------------------------------------+ | DES-CBC-EXP-IV | | | | | + HMAC-MD5-96 | 12 | 54 (+28%) | 34 (+54%) | +----------------------------------------------------------------+ | AES-CBC-EXP-IV | | | | | + HMAC-MD5-96 | 24 | 66 (+57%) | 46 (+109%) | +================================================================+ Figure: Overhead comparison in bytes for IPv4 6. Application to cipher algorithms This section describes the use of DES, 3DES (FIPS-46-3 [14]) and AES (FIPS-AES [15]) with the counter mode. Mode, key size, weak keys, block size, and rounds are documented for each cipher. 6.1 Mode of operations In this memo, all the encryption algorithms are used in counter mode. An overview can be found in Section 1. Etienne Expires November 12, 2001 [Page 8] Internet-Draft counter mode with ESP May 2001 A chaining mode must conceal the patterns in the plaintext inside a single packet and between several packets without compromising the security of the underlying cipher. We believe the CTR-mode matches these requirements as the counter is unique for any block encrypted by a given key (Section 2.2). 6.2 Key size The key size may hint at the security of an encryption algorithm, assuming it is the weakest link. Some algorithms offer variable key size (e.g AES) while others offer only a fixed size (e.g. DES, 3DES). +============+======================+===========+ | Algorithm | Key Sizes (bits) | Default | +============+======================+===========+ | AES | 128, 192, 256 | 128 | +------------+----------------------+-----------+ | DES | 64 | 64 | +------------+----------------------+-----------+ | 3DES | 192 | 192 | +------------+----------------------+-----------+ Figure: key size for various ciphers 6.3 Weak keys The cryptographic community is still debating whether or not to check for weak keys. Critics of key checking argue that it increases the complexity of the system, leading to an increases probability of flaws. Moreover, if the weak keys of a cipher algorithm consume a non negligible part of its key space, it may be considered flawed and should not be used. Proponents make the practical argument that any additional safety that can be checked at a reasonable price should be done. To follow the current trend in ESP standards (RFC2405.4 [5]), weak key checks SHOULD be performed. If such a key is found, the key SHOULD be rejected and a new SA requested. The weak keys for DES, 3DES and AES are: o DES has 4 weak keys and 12 semi-weak keys (RFC2409.A [7] or FIPS- 74 sec.3.6 [16]) , which amount to 2^-52 of the key space. o 3DES WORK: found an authoritative source o AES has no known weak keys, at the time of writing this memo. Etienne Expires November 12, 2001 [Page 9] Internet-Draft counter mode with ESP May 2001 6.4 block size and padding The counter mode doesn't require the plaintext to be block aligned (Section 3). The block size may be different depending on the algorithm. Older ciphers (e.g. DES, 3DES) tend to have 64-bit block while recent ones (e.g. AES) have 128-bit block. +============+===============+ | Algorithm | Block size | +============+===============+ | AES | 128 | +------------+---------------+ | DES | 64 | +------------+---------------+ | 3DES | 64 | +------------+---------------+ Figure: block size per algorithm 6.5 rounds Most block cipher algorithms are based on an atomic function, like that found in a feistel network, applied several times. A single application is called a round and the number of rounds may be correlated with the security of the system. This number may be negotiable (e.g AES) or fixed (e.g. DES, 3DES) and it may be dependent on the key size (e.g. AES). +============+===============+=======================+ | Algorithm | Negotiable? | Default # of Rounds | +============+===============+=======================+ | | | 10 for 128-bit key | | AES | Yes | 12 for 192-bit key | | | | 14 for 256-bit key | +------------+---------------+-----------------------+ | DES | No | 16 | +------------+---------------+-----------------------+ | 3DES | No | 48 | +------------+---------------+-----------------------+ Figure: number of rounds per algorithm 7. Security considerations WORK: to write Etienne Expires November 12, 2001 [Page 10] Internet-Draft counter mode with ESP May 2001 8. Acknowledgement We would like to acknowledge Zach Brown for his contribution to the edition of this document. References [1] Postel, J., "Internet Protocol", STD 5, RFC 791, Sep 1981. [2] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [3] Madson, C. and R. Glenn, "The Use of HMAC-MD5-96 within ESP and AH", RFC 2403, November 1998. [4] Madson, C. and R. Glenn, "The Use of HMAC-SHA-1-96 within ESP and AH", RFC 2404, November 1998. [5] Madson, C. and N. Doraswamy, "The ESP DES-CBC Cipher Algorithm With Explicit IV", RFC 2405, November 1998. [6] Kent, S. and R. Atkinson, "IP Encapsulating Security Payload (ESP)", RFC 2406, November 1998. [7] Harkins, D. and D. Carrel, "The Internet Key Exchange (IKE)", RFC 2409, November 1998. [8] Pereira, R. and R. Adams, "The ESP CBC-Mode Cipher Algorithms", RFC 2451, November 1998. [9] Deering, S. and R. Hinden, "Internet Protocol, Version 6 (IPv6) Specification", RFC 2460, December 1998. [10] Borman, D., Deering, S. and R. Hinden, "IPv6 Jumbograms", RFC 2675, August 1999. [11] Frankel, S., Glenn, R. and S. Kelly, "The AES Cipher Algorithm and Its Use With IPsec", draft-ietf-ipsec-ciph-aes-cbc-01.txt Work In Progress, Nov 2000. [12] Bellovin, S., "Problem Areas for the IP Security Protocol", Usenix Unix Security Symposium 6th, Jul 1996. [13] Lipmaa, H., Rogaway, P. and D. Wagner, "CTR-MODE encryption", Comment on mode of operations NIST, Jan 2001. [14] NIST, , "Data encryption standard (DES)", FIPS 46-3, Oct 1999. Etienne Expires November 12, 2001 [Page 11] Internet-Draft counter mode with ESP May 2001 [15] NIST, , "Advanced Encryption Standard (AES)", FIPS not yet published, summer 2001. [16] NIST, , "Guidelines for implementing and using the nbs data encryption standard", FIPS 74, Apr 1981. [17] Biham, E. and A. Shamir, "Differential Cryptanalysis of DES- like cryptosystems", Journal of Cryptology Vol 4, Jan 1991. Author's Address Jerome Etienne EMail: jme@off.net URI: http://www.off.net/~jme Appendix A. block size smaller than 64bit o WORK: to write Etienne Expires November 12, 2001 [Page 12] Internet-Draft counter mode with ESP May 2001 Full Copyright Statement Copyright (C) The Internet Society (2001). All Rights Reserved. This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English. The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns. This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Acknowledgement Funding for the RFC Editor function is currently provided by the Internet Society. Etienne Expires November 12, 2001 [Page 13]