Internet Engineering Task Force R. Pereira IP Security Working Group TimeStep Corporation Internet Draft R. Adams Expires in six months cisco Systems Inc. November 20, 1997 The ESP CBC-Mode Cipher Algorithms Status of this Memo This document is a submission to the IETF Internet Protocol Security (IPSEC) Working Group. Comments are solicited and should be addressed to the working group mailing list (ipsec@tis.com) or to the editor. This document is an Internet-Draft. 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 draft documents are valid for a maximum of six months and may be updated, replaced, or obsolete 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." To learn the current status of any Internet-Draft, please check the "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe), munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or ftp.isi.edu (US West Coast). Distribution of this memo is unlimited. Abstract This document describes how to use CBC-mode cipher algorithms with the IPSec ESP (Encapsulating Security Payload) Protocol. It not only clearly states how to use certain cipher algorithms, but also how to use all CBC-mode cipher algorithms. R. Pereira, R. Adams [Page 1] Internet Draft The ESP CBC-Mode Cipher Algorithms Nov-97 Table of Contents 1. Introduction...................................................2 1.1 Specification of Requirements...............................2 2. Cipher Algorithms..............................................3 2.1 Mode........................................................3 2.2 Key Size....................................................3 2.3 Weak Keys...................................................4 2.4 Block Size and Padding......................................5 2.5 Rounds......................................................6 2.6 Backgrounds.................................................6 2.7 Performance.................................................9 3. ESP Payload...................................................10 3.1 ESP Environmental Considerations...........................10 3.2 Keying Material............................................10 4. Security Considerations.......................................10 5. References....................................................11 6. Acknowledgments...............................................12 7. Editors' Addresses............................................12 8. Internet Draft Notes..........................................13 1. Introduction The Encapsulating Security Payload (ESP) [Kent97] provides confidentiality for IP datagrams by encrypting the payload data to be protected. This specification describes the ESP use of CBC-mode cipher algorithms. While this document does not describe the use of the default cipher algorithm DES, the reader should be familiar with that document. [Madson97] It is assumed that the reader is familiar with the terms and concepts described in the "Security Architecture for the Internet Protocol" [Atkinson95], "IP Security Document Roadmap" [Thayer97], and "IP Encapsulating Security Payload (ESP)" [Kent97] documents. Furthermore, this document is a companion to [Kent97] and MUST be read in its context. 1.1 Specification of Requirements The keywords "MUST", "MUST NOT", "REQUIRED", "SHOULD", "SHOULD NOT", and "MAY" that appear in this document are to be interpreted as described in [Bradner97]. R. Pereira, R. Adams [Page 2] Internet Draft The ESP CBC-Mode Cipher Algorithms Nov-97 2. Cipher Algorithms All symmetric block cipher algorithms share common characteristics and variables. These include mode, key size, weak keys, block size, and rounds. All of which will be explained below. While this document illustrates certain cipher algorithms such as Blowfish [Schneier93], CAST-128 [Adams97], 3DES, IDEA [Lai], and RC5 [Baldwin96], any other block cipher algorithm may be used with ESP if all of the variables described within this document are clearly defined. 2.1 Mode All symmetric block cipher algorithms described or insinuated within this document use Cipher Block Chaining (CBC) mode. This mode requires an Initialization Vector (IV) that is the same size as the block size. Use of a randomly generated IV prevents generation of identical ciphertext from packets which have identical data that spans the first block of the cipher algorithm's blocksize. The IV is XOR'd with the first plaintext block, before it is encrypted. Then for successive blocks, the previous ciphertext block is XOR'd with the current plaintext, before it is encrypted. More information on CBC mode can be obtained in [Schneier95]. 2.2 Key Size Some cipher algorithms allow for variable sized keys, while others only allow a specific key size. The length of the key correlates with the strength of that algorithm, thus larger keys are always harder to break than shorter ones. This document stipulates that all key sizes MUST be a multiple of 8 bits. This document does specify the default key size for each cipher algorithm. This size was chosen by consulting experts on the algorithm and by balancing strength of the algorithm with performance. R. Pereira, R. Adams [Page 3] Internet Draft The ESP CBC-Mode Cipher Algorithms Nov-97 +==============+==================+=================+==========+ | Algorithm | Key Sizes (bits) | Popular Sizes | Default | +==============+==================+=================+==========+ | CAST-128 [1] | 40 to 128 | 40, 64, 80, 128 | 128 | +--------------+------------------+-----------------+----------+ | RC5 | 40 to 2040 | 40, 128, 160 | 128 | +--------------+------------------+-----------------+----------+ | IDEA | 128 | 128 | 128 | +--------------+------------------+-----------------+----------+ | Blowfish | 40 to 448 | 128 | 128 | +--------------+------------------+-----------------+----------+ | 3DES [2] | 192 | 192 | 192 | +--------------+------------------+-----------------+----------+ Notes: [1] With CAST-128, keys less than 128 bits MUST be padded with zeros in the rightmost, or least significant, positions out to 128 bits since the CAST-128 key schedule assumes an input key of 128 bits. Thus if you had a key with a size of 80 bits '3B5D831CFE', it would be padded to produce a key with a size of 128 bits '3B5D831CFE000000'. [2] The first 3DES key is taken from the first 64 bits, the second from the next 64 bits, and the third from the last 64 bits. Implementations MUST take into consideration the parity bits when initially accepting a new set of keys. The reader should note that the minimum key size for all of the above cipher algorithms is 40 bits, and that the authors strongly advise that implementations do NOT use key sizes smaller than 40 bits. 2.3 Weak Keys Some cipher algorithms have weak keys or keys that MUST not be used due to their weak nature. [Kent97] describes what to do when such a key is generated. CAST-128: No known weak keys. RC5: No known weak keys when used with 16 rounds. R. Pereira, R. Adams [Page 4] Internet Draft The ESP CBC-Mode Cipher Algorithms Nov-97 IDEA: IDEA has weak keys of the following form [Crypto93]: 0000,0000,0x00,0000,0000,000x,xxxx,x000 where "x" can be any hexadecimal number. Keys of this form guarantee the value of bit-wise XOR of resultant ciphertext pairs from the bit-wise XOR of certain plaintext pairs. Blowfish: Weak keys for Blowfish have been discovered. Weak keys are keys that produce the identical entries in a given S-box. Unfortunately, there is no way to test for weak keys before the S- box values are generated. However, the chances of randomly generating such a key are small. 3DES: DES has 64 known weak keys, including so-called semi-weak keys and possibly-weak keys [Schneier95, pp 280-282]. The likelihood of picking one at random is negligible. For DES-EDE3, there is no known need to reject weak or complementation keys. Any weakness is obviated by the use of multiple keys. However, if the first two or last two independent 64-bit keys are equal (k1 == k2 or k2 == k3), then the 3DES operation is simply the same as DES. Implementers MUST reject keys that exhibit this property. 2.4 Block Size and Padding All of the algorithms described in this document use a block size of eight octets (64 bits). Padding is used to align the payload type and pad length octets as specified in [Kent97]. Padding must be sufficient to align the data to be encrypted to an eight octet (64 bit) boundary. R. Pereira, R. Adams [Page 5] Internet Draft The ESP CBC-Mode Cipher Algorithms Nov-97 2.5 Rounds This variable determines how many times a block is encrypted. While this variable MAY be negotiated, a default value MUST always exist when it is not negotiated. +====================+============+======================+ | Algorithm | Negotiable | Default Rounds | +====================+============+======================+ | CAST-128 | No | key<=80 bits, 12 | | | | key>80 bits, 16 | +--------------------+------------+----------------------+ | RC5 | No | 16 | +--------------------+------------+----------------------+ | IDEA [1] | 4, 8 | 8 | +--------------------+------------+----------------------+ | Blowfish | No | 16 | +--------------------+------------+----------------------+ | 3DES | No | 48 (16x3) | +--------------------+------------+----------------------+ Notes: [1] Although there are no known attacks against four round IDEA, those choosing to use four round IDEA for performance reasons may wish to use a shorter key lifetime (presumably via site specific policy). 2.6 Backgrounds CAST-128: The CAST design procedure was originally developed by Carlisle Adams and Stafford Travares at Queen's University, Kingston, Ontario, Canada. Subsequent enhancements have been made over the years by Carlisle Adams and Michael Wiener of Entrust Technologies. CAST-128 is the result of applying the CAST Design Procedure as outlined in [Adams97]. RC5: The RC5 encryption algorithm was developed by Ron Rivest for RSA Data Security Inc. in order to address the need for a high- performance software and hardware ciphering alternative to DES. R. Pereira, R. Adams [Page 6] Internet Draft The ESP CBC-Mode Cipher Algorithms Nov-97 IDEA: Xuejia Lai and James Massey developed the IDEA (International Data Encryption Algorithm) algorithm. The algorithm is described in detail in [Lai] and [Schneier]. The IDEA algorithm is patented in Europe and in the United States with patent application pending in Japan. Licenses are required for commercial uses of IDEA. For patent and licensing information, contact: Ascom Systec AG, Dept. CMVV Gewerbepark, CH-5506 Magenwil, Switzerland Phone: +41 64 56 59 83 Fax: +41 64 56 59 90 idea@ascom.ch http://www.ascom.ch/Web/systec/policy/normal/exhibit1.html Blowfish: Bruce Schneier of Counterpane Systems developed the Blowfish block cipher algorithm. The algorithm is described in detail in [Schneier93], [Schneier95] and [Schneier]. 3DES: This DES variant, colloquially known as "Triple DES" or as DES- EDE3, processes each block three times, each time with a different key. This technique of using more than one DES operation was proposed in [Tuchman79]. R. Pereira, R. Adams [Page 7] Internet Draft The ESP CBC-Mode Cipher Algorithms Nov-97 P1 P2 Pi | | | IV->->(X) +>->->->(X) +>->->->(X) v ^ v ^ v +-----+ ^ +-----+ ^ +-----+ k1->| E | ^ k1->| E | ^ k1->| E | +-----+ ^ +-----+ ^ +-----+ | ^ | ^ | v ^ v ^ v +-----+ ^ +-----+ ^ +-----+ k2->| D | ^ k2->| D | ^ k2->| D | +-----+ ^ +-----+ ^ +-----+ | ^ | ^ | v ^ v ^ v +-----+ ^ +-----+ ^ +-----+ k3->| E | ^ k3->| E | ^ k3->| E | +-----+ ^ +-----+ ^ +-----+ | ^ | ^ | +>->->+ +>->->+ +>->-> | | | C1 C2 Ci The DES-EDE3-CBC algorithm is a simple variant of the DES-CBC algorithm [FIPS-46]. The "outer" chaining technique is used. In DES-EDE3-CBC, an Initialization Vector (IV) is XOR'd with the first 64-bit (8 byte) plaintext block (P1). The keyed DES function is iterated three times, an encryption (Ek1) followed by a decryption (Dk2) followed by an encryption (Ek3), and generates the ciphertext (C1) for the block. Each iteration uses an independent key: k1, k2 and k3. For successive blocks, the previous ciphertext block is XOR'd with the current plaintext (Pi). The keyed DES-EDE3 encryption function generates the ciphertext (Ci) for that block. To decrypt, the order of the functions is reversed: decrypt with k3, encrypt with k2, decrypt with k1, and XOR the previous ciphertext block. Note that when all three keys (k1, k2 and k3) are the same, DES- EDE3-CBC is equivalent to DES-CBC. This property allows the DES- EDE3 hardware implementations to operate in DES mode without modification. For more explanation and implementation information for Triple DES, see [Schneier95]. R. Pereira, R. Adams [Page 8] Internet Draft The ESP CBC-Mode Cipher Algorithms Nov-97 2.7 Performance For a comparison table of the speed of any of these and other cipher algorithms, please see [Schneier97]. CAST-128: CAST runs approximately 3 times faster than a highly optimized DES implementation and runs 5-6 times faster than the DES implementations found in typical applications. This is based on a non-optimized C++ implementation of CAST-128. It can therefore be tuned to give even higher performance, if this is required. RC5: Benchmark numbers from RSA Data Security suggest that RC5-CBC runs about twice as fast as Eric Young's DES-CBC implementation from SSLeay on the popular 32-bit CPUs. IDEA: Normal eight round IDEA is approximately twice as fast as DES on 386 and 486 processors. However on a Pentium, both eight round IDEA and 56 bit key, 16 round DES require about the same number of clock cycles per byte encrypted. Four round IDEA is twice as fast as eight round IDEA. Blowfish: Blowfish is designed to encrypt data very efficiently on 32 bit processors. Although setting up the keys for Blowfish is complex and time consuming, actual encryption is efficient. Sixteen round Blowfish uses only 18 clock cycles per byte encrypted on a Pentium versus 45 clock cycles for 16 round DES with a 56 bit key, and 108 for 48 round Triple-DES. 3DES: Triple DES is approximately 2.5 times slower than "single" DES (rather than 3 times), because inner permutations may be removed. Phil Karn has tuned DES-EDE3-CBC software to achieve very fast performance. Other DES speed estimates may be found at [Schneier, page 279]. R. Pereira, R. Adams [Page 9] Internet Draft The ESP CBC-Mode Cipher Algorithms Nov-97 3. ESP Payload The ESP payload is made up of the IV followed by raw cipher-text. Thus the payload field, as defined in [Kent97], is broken down according to the following diagram: +---------------+---------------+---------------+---------------+ | | + Initialization Vector (8 octets) + | | +---------------+---------------+---------------+---------------+ | | ~ Encrypted Payload (variable length) ~ | | +---------------------------------------------------------------+ 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 The IV field MUST be same size as the block size of the cipher algorithm being used. The IV SHOULD be chosen at random. Common practice is to use random data for the first IV and the last block of encrypted data from an encryption process as the IV for the next encryption process. 3.1 ESP Environmental Considerations Currently, there are no known issues regarding interactions between these algorithms and other aspects of ESP, such as use of certain authentication schemes. 3.2 Keying Material The minimum number of bits sent from the key exchange protocol to this ESP algorithm must be greater or equal to the key size. The cipher's encryption and decryption key is taken from the first bits of the keying material, where represents the required key size. 4. Security Considerations Implementations are encouraged to use the largest key sizes they can when taking into account performance considerations for their particular hardware and software configuration. Note that encryption necessarily impacts both sides of a secure channel, so such consideration must take into account not only the client side, but the server as well. R. Pereira, R. Adams [Page 10] Internet Draft The ESP CBC-Mode Cipher Algorithms Nov-97 For further security considerations, the reader is encouraged to read the documents that describe the actual cipher algorithms. 5. References [Adams97] Adams, C., "The CAST-128 Encryption Algorithm", RFC2144, 1997. [Atkinson95] Atkinson, R., "Security Architecture for the Internet Protocol", draft-ietf-ipsec-arch-sec-01 [Baldwin96] Baldwin, R.W., Rivest, R., "The RC5, RC5-CBC, RC5-CBC- Pad, and RC5-CTS Algorithms", RFC2040, October 1996 [Bradner97] Bradner, S., "Key words for use in RFCs to indicate Requirement Levels", RFC2119, March 1997 [Crypto93] Daeman, J., Govaerts, R., Vandewalle, J., "Weak Keys for IDEA", Advances in Cryptology, CRYPTO 93 Proceedings, Springer- Verlag, pp. 224-230. [FIPS-46] US National Bureau of Standards, "Data Encryption Standard", Federal Information Processing Standard (FIPS) Publication 46, January 1977. [Kent97] Kent, S., Atkinson, R., "IP Encapsulating Security Payload (ESP)", draft-ietf-ipsec-esp-v2-00 [Lai] Lai, X. "On the Design and Security of Block Ciphers", ETH Series in Information Processing, v. 1, Konstanz: Hartung-Gorre Verlag, 1992. [Madson97] Madson, C., Dorswamy, N., "The ESP DES-CBC Cipher Algorithm With Explicit IV", draft-ietf-ipsec-ciph-des-expiv-00 [Schneier] Schneier, B., "Applied Cryptography Second Edition", John Wiley & Sons, New York, NY, 1995. ISBN 0-471-12845-7 [Schneier93] Schneier, B., "Description of a New Variable-Length Key, 64-Bit Block Cipher", from "Fast Software Encryption, Cambridge Security Workshop Proceedings", Springer-Verlag, 1994, pp. 191-204. http://www.counterpane.com/bfsverlag.html [Schneier95] Schneier, B., "The Blowfish Encryption Algorithm - One Year Later", Dr. Dobb's Journal, September 1995, http://www.counterpane.com/bfdobsoyl.html R. Pereira, R. Adams [Page 11] Internet Draft The ESP CBC-Mode Cipher Algorithms Nov-97 [Schneier97] Scheier, B. "Speed Comparisons of Block Ciphers on a Pentium." February 1997, http://www.counterpane.com/speed.html [Thayer97] R. Thayer, N. Doraswamy, R. Glenn, "IP Security Document Roadmap", draft-ietf-ipsec-doc-roadmap-00 [Tuchman79] Tuchman, W, "Hellman Presents No Shortcut Solutions to DES", IEEE Spectrum, v. 16 n. 7, July 1979, pp. 40-41. 6. Acknowledgments This document is a merger of most of the ESP cipher algorithm documents. This merger was done to facilitate greater understanding of the commonality of all of the ESP algorithms and to further the development of these algorithm within ESP. The content of this document is based on suggestions originally from Stephen Kent and subsequent discussions from the IPSec mailing list as well as other IPSec drafts. For CAST, special thanks to Carlisle Adams and Paul Van Oorschot both of Entrust Technologies who provided input and review. For 3DES, thanks to all of the editors of the previous ESP 3DES documents; W. Simpson, N. Doraswamy, P. Metzger, and P. Karn. For RC5, thanks to Brett Howard from TimeStep for his original work. 7. Editors' Addresses Roy Pereira TimeStep Corporation +1 (613) 599-3610 x 4808 Rob Adams cisco Systems Inc. +1 (408) 457 5397 Contributors: Robert W. Baldwin or RSA Data Security, Inc. +1 (415) 595-8782 R. Pereira, R. Adams [Page 12] Internet Draft The ESP CBC-Mode Cipher Algorithms Nov-97 Greg Carter Entrust Technologies +1 (613) 763-1358 Rodney Thayer rodney@sabletech.com Sable Technology Corporation +1 (617) 332-7292 The IPSec working group can be contacted via the IPSec working group's mailing list (ipsec@tis.com) or through its chairs: Robert Moskowitz rgm@chrysler.com Chrysler Corporation Theodore Y. Ts’o tytso@MIT.EDU Massachusetts Institute of Technology 8. Internet Draft Notes This document obsoletes the following documents: draft-ietf-ipsec-ciph-cast-128cbc-00.txt, R. Pereira, G. Carter draft-ietf-ipsec-ciph-rc5-cbc-00.txt, R. Pereira, R. Baldwin draft-ietf-ipsec-ciph-3des-expiv-00.txt, R. Pereira, R. Thayer draft-ietf-ipsec-ciph-idea-cbc-00.txt, R. Adams draft-ietf-ipsec-ciph-blowfish-cbc-00.txt, R. Adams The key size for IDEA was restricted for "ease of use" purposes. Furthermore, the use of setting the sub-keys directly was removed, again for ease of use. IDEA’s weak key derivation was removed as it is the responsibility of the ESP document to describe actions when there is a weak key. DES-CBC could be part of this document with very little effort. Should it be? R. Pereira, R. Adams [Page 13]