Network Working Group J. Etienne Internet-Draft May 23, 2001 Expires: November 21, 2001 Secret IV and its use with ESP draft-etienne-ipsec-esp-secret-iv-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 21, 2001. Copyright Notice Copyright (C) The Internet Society (2001). All Rights Reserved. Abstract This memo presents a system of secret IV for ESP, based on the encryption of the sequence number. It doesn't add any space overhead in the packet and its generation can be parallelized and precomputed. Compared to the common explicit random IV (current MUST for ESP RFC2405.3 [5], or AES-CBC.3 [7]), it is more secure, saves bandwidth (e.g. 8 bytes with DES/3DES and 16 bytes with AES) but requires slightly more computation. Etienne Expires November 21, 2001 [Page 1] Internet-Draft Secret IV and its use with ESP May 2001 Table of Contents 1. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . 3 3. Requirements . . . . . . . . . . . . . . . . . . . . . . . . 3 4. IV generation . . . . . . . . . . . . . . . . . . . . . . . 4 5. IV security properties . . . . . . . . . . . . . . . . . . . 4 5.1 Uniqueness of the secret IV . . . . . . . . . . . . . . . . 5 5.2 Hamming distance between secret IVs . . . . . . . . . . . . 5 5.3 Secrecy of the IV . . . . . . . . . . . . . . . . . . . . . 5 6. Performance evaluation . . . . . . . . . . . . . . . . . . . 5 6.1 processing performance . . . . . . . . . . . . . . . . . . . 6 6.2 space performance . . . . . . . . . . . . . . . . . . . . . 6 6.2.1 Comparison with explicit IV . . . . . . . . . . . . . . . . 6 7. limitations . . . . . . . . . . . . . . . . . . . . . . . . 7 7.1 relation to the anti-replay protection . . . . . . . . . . . 7 7.2 relation to differentially-weak ciphers . . . . . . . . . . 7 8. Security Considerations . . . . . . . . . . . . . . . . . . 8 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 8 References . . . . . . . . . . . . . . . . . . . . . . . . . 8 Author's Address . . . . . . . . . . . . . . . . . . . . . . 9 A. Non-random explicit IV for RFC2405 . . . . . . . . . . . . . 9 B. Vulnerability of the random IV . . . . . . . . . . . . . . . 9 B.1 Consequences of an IV collision . . . . . . . . . . . . . . 10 C. Birthday attacks . . . . . . . . . . . . . . . . . . . . . . 10 Full Copyright Statement . . . . . . . . . . . . . . . . . . 11 Etienne Expires November 21, 2001 [Page 2] Internet-Draft Secret IV and its use with ESP May 2001 1. Overview The basic principle of the secret IV is to encrypt the ESP sequence number (RFC2406.2.2 [6]) and to use the resulting ciphertext as IV for the mode of operation. This document presents the secret IV independently of block ciphers and mode of operations. Examples of mode of operations are given with the common modes advised by the NIST [14]: OFB, CBC and CFB (ECB isn't included as it doesn't need IV). Examples of block ciphers are given with DES and AES. A special attention is given to DES-CBC with explicit IV (RFC2405 [5]) because it is the current MUST for ESP. Compared to the common explicit random IV (RFC2405.3 [5], or AES- CBC.3 [7]), secret IV offers a tradeoff (Section 6) which may be attractive: better bandwidth usage and better security versus slightly more CPU processing. 1. The secret IV is more secure than a random explicit IV because the secret IV is secret (Section 5.3) and unique (Section 5.1). DES CBC with random explicit IV (RFC2405.3 [5]) is the current MUST for ESP encryption and it has security flaws based on the colliding IVs (Appendix B). 2. The secret IV doesn't use any additional space in the encrypted packet because it is directly derived from the ESP sequence number (Section 4). 3. The secret IV consumes CPU to generate but its processing can be parallelized and precomputed (Section 6.1). This document gives the requirements which need to be meet by an IV (Section 3), specifies its generations (Section 4), evaluates its security (Section 5) and performance (Section 6) and explains its limitations (Section 7). 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]. 3. Requirements The purpose of an IV is provide a nonce to the mode of operation in order to conceal the plaintext patterns inside a single packet and between several packets. We identified the following requirements: 1. The IV MUST be unique during the lifetime of a key. If several Etienne Expires November 21, 2001 [Page 3] Internet-Draft Secret IV and its use with ESP May 2001 packets have the same IV, the attacker is able to learn additional informations about the plaintext (Appendix B.1). 2. The IV MUST be as large as the cipher block because of the construction of the mode of operation. 3. The hamming distance between IVs SHOULD be high. If it isn't, the first block of the cipher's input will likely differ in just a few bit position and an attacker may use it against a differentially-weak cipher. The secret IV meets these requirements: It is guaranteed to be unique (Section 5.1), the hamming distance is high (Section 5.2) and it is as large as the cipher block (Section 4). 4. IV generation The IV is generated by copying the ESP sequence number to the least significant part of the block. Then, any bit more significant than the 32th is zeroed and the block is encrypted with the same key and cipher algorithm used for the data (RFC2406.3.3.2 [6]). The resulting ciphertext is exactly as large as a block and can be directly used as IV. The generation is self contained i.e. it uses only existing component of ESP: the sequence number, the encryption algorithm and key. It requires the block size to be at least 32-bit long but it isn't a significant constraint as we aren't aware of any block cipher which doesn't match this requirement. 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 0 | ~ (variable size equal to cipher block size - 32 bits) ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | ESP Sequence Number | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure: The plaintext of the IV 5. IV security properties The secret IV is secure as it is guaranteed to be unique (Section 5.1), separated from other IVs by high-hamming distance (Section 5.2) Etienne Expires November 21, 2001 [Page 4] Internet-Draft Secret IV and its use with ESP May 2001 and is secret (Section 5.3). 5.1 Uniqueness of the secret IV An IV is supposed to be a nonce and a failure in this assumption would create a security hole (Appendix B). The secret IV is guaranteed to be unique because it is derived from a unique number by a collision-free function. The ESP sequence numbers (RFC2406.2.2 [6]) is ensured to be unique during the lifetime of a key assuming the anti-replay protection is enabled (Section 7.1). Moreover the derivation function is an block cipher which prevents collision by guaranteeing that any plaintext has a unique ciphertext. 5.2 Hamming distance between secret IVs [13], summarized in RFC2405.6 [5], explains that low hamming distance between IVs may ease cryptanalysis attacks (e.g. differential ones [10]). Secret IV avoids this flaw because a block cipher is assumed to be a pseudo-random permutation i.e. the ciphertext appears unrelated to the plaintext to those who ignore the key. Thus the IV looks random for an attacker and the hamming distance between IVs is high, even if the IV is derived from a low-Hamming distance source (Section 4). 5.3 Secrecy of the IV The secrecy of the IV is useful against attacks requiring predictable IV. In our case, it makes a differential cryptanalysis based on the IV significantly harder (Section 7.2). An attacker can try to obtain the IV from its source, i.e. the ESP sequence number, or its destination, i.e. the first block of ciphertext: 1. The IV is the ESP sequence number encrypted with the shared secret key (Section 4). As the attacker ignores the key, he is unable to regenerate the IV without breaking the cipher algorithm. 2. With CBC, OFB and CFB, the IV is encrypted before being included in the ciphertext so the attacker is unable to deduce it. Thus the secret IV is guaranteed to be secret if the attacker is unable to break the cipher algorithm. 6. Performance evaluation This secret IV offers a tradeoff bandwidth/CPU. The bandwidth usage Etienne Expires November 21, 2001 [Page 5] Internet-Draft Secret IV and its use with ESP May 2001 is reduced (Section 6.2) but the CPU usage is slightly increased (Section 6.1) because of the IV generation (Section 4). 6.1 processing performance The IV generation can be precomputed because the ESP sequence numbers are easily predictable by the receiver. Implementors MAY compute the IVs using spare cycle and cache them to reduce the processing latency while processing packets. The IV generation can be parallelized because the computation of each IV is independent from the others. 6.2 space performance The secret IV doesn't add any space overhead because it is derived from the ESP sequence number which is already present in the packet (RFC2406.2 [6]). 6.2.1 Comparison with explicit IV CBC with explicit IV (RFC2405 [5]) is the current MUST for the ESP encryption (RFC2406.5 [6]). To require an explicit IV adds an additional block of bytes to the output. This implies that an secret IV will see a savings of the block size in comparison. The following tables present 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]). We assume the plain text must be block aligned because the current MUST (RFC2405 [5]) uses CBC. This adds an average overhead of half of the block size. +================================================================+ | SA \ Avg Overhead | cipher | ESP tunnel | ESP transport | +===================+=============+==============+===============+ | DES-CBC-IMP-IV | | 20+10+12+4= | 10+12+4 = | | + HMAC-MD5-96 | 4 | 46 | 26 | +----------------------------------------------------------------+ | DES-CBC-EXP-IV | | | | | + HMAC-MD5-96 | 12 | 54 (+17%) | 34 (+30%) | +================================================================+ Figure: Overhead comparison in bytes with IPv4 and DES Etienne Expires November 21, 2001 [Page 6] Internet-Draft Secret IV and its use with ESP May 2001 +================================================================+ | SA \ Avg Overhead | cipher | ESP tunnel | ESP transport | +===================+=============+==============+===============+ | AES-CBC-IMP-IV | | 20+10+12+8= | 10+12+8 = | | + HMAC-MD5-96 | 8 | 50 | 30 | +----------------------------------------------------------------+ | AES-CBC-EXP-IV | | | | | + HMAC-MD5-96 | 24 | 66 (+32%) | 46 (+53%) | +================================================================+ Figure: Overhead comparison in bytes with IPv4 and AES 7. limitations Using the secret IV assumes to enable the anti-replay protection for this SA (Section 7.1) and not to use cipher algorithms which are extremely weak against differential cryptanalysis (Section 7.2). 7.1 relation to the anti-replay protection The anti-replay (RFC2406.3.3.3 [6]) MUST be enabled. The ESP sequence number is the base of the secret IV and if the sequence number rolls over, the IV would be reused (Section 5.1). We believe that this requirement is reasonable because its overhead is negligible and it prevents attackers from replaying packets as additional benefit. 7.2 relation to differentially-weak ciphers If the cipher algorithm is differentially-weak, an attacker may use the secret IV to obtain many ciphertexts with low hamming distance between the plaintext and performs a differential cryptanalysis [10]. It may be argued that differentially-weak ciphers should not be used and that the goal of the IV isn't to try, probably in vain, to fix a cipher's flaw. In any case, this attack is hard to apply to the secret IV because: o It can't succeed if it requires more than 2^32 pairs. The attacker can obtain at most 2^32 pairs because the ESP sequence numbers MUST NOT cycle and is reset before the transmission of the 2^32nd packet (RFC2406.2.2 [6]). o The ESP sequence numbers are separated by low hamming distance but they are encrypted twice (once to generate the IV and once by the mode of operation) before being included in the ciphertext. It effectively doubles the number of rounds of the cipher and the differential cryptanalysis is typically harder as the number of rounds increases. Etienne Expires November 21, 2001 [Page 7] Internet-Draft Secret IV and its use with ESP May 2001 If the cipher is sufficiently differentially-weak to allow a differential cryptanalysis with only 2^32 secret IVs, each one being encrypted twice, it may be easier to attack the message ciphertext blocks which are significantly more and encrypted only once. 8. Security Considerations The secret IV is secure as it is guaranteed to be unique, separated from other IVs by high-hamming distance and is secret (Section 5). Moreover it isn't vulnerable to birthday attacks (Appendix C) like random IVs required in RFC2405.3 [5] (Appendix B). Appendix A describes a backward compatible method to fix this flaw. 9. Acknowledgements The IV system presented in this memo is inspired from the counter mode, introduced by Diffie and Hellman in 1979 [9]. Lipmaa, Rogaway and Wagner present a comprehensive overview in [8]. The counter mode is a mode of operation based on the encryption of a counter and the secret IV may be seen as a single block of the counter mode pad. We would like to acknowledge Adam Back for his help in understanding the mathematic involved in the birthday paradox. 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] 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. [8] Lipmaa, H., Rogaway, P. and D. Wagner, "CTR-MODE encryption", Etienne Expires November 21, 2001 [Page 8] Internet-Draft Secret IV and its use with ESP May 2001 Comment on mode of operations NIST, 2001. [9] Diffie, W. and M. Hellman, "Privacy and Authentication: An Introduction to Cryptography", Proceedings of the IEEE 67 pp. 397-427, 1979. [10] Biham, E. and A. Shamir, "Differential Cryptanalysis of DES- like cryptosystems", Journal of Cryptology Vol 4, Jan 1991. [11] Menezes, A., Vanstone, S. and P. van Oorschot, "Handbook of applied cryptography", CRC press , 1996. [12] Stinson, D., "Cryptography: theory and practice", CRC press , 1995. [13] Bellovin, S., "Probable plaintext cryptanalysis of the IP security protocols", Proceedings of the Symposium on Network and Distributed System Security , Feb 1997. [14] NIST, , "DES MODES OF OPERATION", FIPS 81, Dec 1980. Author's Address Jerome Etienne EMail: jme@off.net URI: http://www.off.net/~jme Appendix A. Non-random explicit IV for RFC2405 This section describes a backward compatible method to fix the security flaw due to the random IV (Appendix B) in RFC2405 [5]. Implementors MAY use it when backward compatibility is required but they would have the additional processing of the secret IV, wouldn't gain the bandwidth and would lose the secrecy property (Section 5.3) which may increase its vulnerability to differentially-weak ciphers (Section 7.2). The principle is to generate an IV as an secret IV (Section 4) and then to include it in each packet as specified in RFC2405.3 [5]. Thus the IV is explicit but no more vulnerable to birthday attacks. Appendix B. Vulnerability of the random IV RFC2405.3 [5], the current MUST for ESP, requires to use random IV but random IVs are vulnerable to birthday attacks (Appendix C) i.e. it is surprisingly likely that among a pool of packets at least two Etienne Expires November 21, 2001 [Page 9] Internet-Draft Secret IV and its use with ESP May 2001 have the same IV. Note that this attack doesn't require to break the underlying cipher algorithm. Assuming the anti-replay protection is enabled (Section 7.1), an attacker is able to gather 2^32 packets. With a 64-bit block cipher (e.g DES, 3DES), he has 40% chances to have at least two packets with the same IV. It is a security weakness but a minor one. Appendix B.1 explains the consequences of an IV collision. B.1 Consequences of an IV collision The consequences of the collision depend on the mode of operation. We classify them in two classes: the modes which solely rely on the IV to hide the patterns inside a message (OFB) and the ones which additionally use the plaintext to distribute its potential variations along the ciphertext (OFB, CBC). An IV collision with OFB is a huge security weakness because the attacker can XOR the colliding ciphertext and obtain an XOR of the two plaintexts of the whole messages (WORK: assuming they have the same size). For CFB, the attacker can obtain a XOR of the two plaintext too but only up to and including the first plaintext block which is different in both messages. For CBC, an IV collision reveals the common patterns of both packets up to and including the first different blocks. Appendix C. Birthday attacks work: todo. general introduction and application to ESP Etienne Expires November 21, 2001 [Page 10] Internet-Draft Secret IV and its use 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 21, 2001 [Page 11]