Network Working Group W A Simpson Internet Draft [DayDreamer] expires in six months July 1997 ESP with Cipher Block CheckSums (CBCS) draft-simpson-ipsec-cbcs-00.txt Status of this Memo This document is an Internet-Draft. Internet Drafts are working doc- uments of the Internet Engineering Task Force (IETF), its Areas, and its Working Groups. Note that other groups may also distribute work- ing 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 not appropriate to use Internet Drafts as refer- ence material, or to cite them other than as a ``working draft'' or ``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) ds.internic.net (US East Coast) ftp.isi.edu (US West Coast) munnari.oz.au (Pacific Rim) Distribution of this memo is unlimited. Abstract This document describes the Cipher Block Chaining mode with addi- tional single or double parallel CheckSums for integrity, used with a number of Internet Encapsulating Security Payload (ESP) transforms. This version is described in terms of 64-bit block ciphers, but can be expanded to other block sizes. Simpson expires in six months [Page i] DRAFT CBCS July 1997 1. Introduction The Encapsulating Security Payload (ESP) [RFC-1827x] provides confi- dentiality for IP datagrams by encrypting the payload data to be pro- tected. This specification describes the ESP use of the Cipher Block Chaining (CBC) mode, with an added checksum for integrity. CBC is used to mask patterns of identical blocks within the same datagram. Together with an Initialization Variable (IV) that is dif- ferent for every datagram, identical plaintext payloads will each encrypt to different ciphertext payloads. As an added benefit, when the cipher output is effectively random in appearance (a characteris- tic of a good cipher), masking the plaintext with previous ciphertext will easily strengthen the entropy of the next input to the cipher. A pair of checksums are added to detect changes to the ciphertext, providing a modest degree of integrity in a single pass over the data, rather than using a separate pass with a stronger algorithm. This combination is intended to be reasonably simple to implement, either serially in software or in parallel hardware for performance. Although a simple checksum over multiple blocks would not normally be considered cryptographically secure, the use of a cipher in the mid- dle provides a background of highly random internal chaining. These random blocks are used as a masking function to inhibit determination of the internal state of the checksums. CBC was first defined for DES in [FIPS-81], and generalized by [ISO-8732] and [ISO/IEC-10116]. For a technical exposition on CBC, see [MOV97]. For more explanation and implementation information for CBC, and a useful comparison with other modes of operation, see [Schneier95]. Although this algorithm is described in terms of 64-bit (8 byte) blocks with 128-bit (16 byte) internal chaining values, this could be expanded to other block sizes. 1.1. Design Goals Unlike the CBC stream orientation, CBCS is intended from its incep- tion to be used with the Internet Protocol (IP) datagram network. This environment provides specific limitations on the scope of vul- nerability. Each IP datagram has a length limitation of 576 bytes, unless a larger size is explicitly indicated by the transport layer. Future IP versions extend this length to 1500 bytes. The CBCS integrity is designed to reliably detect any multiple bit change within the Simpson expires in six months [Page 1] DRAFT CBCS July 1997 11,680-bit payload, with an order of at least 1/2**16 probability of failure. This is considerably stronger than the 1/2**7 probability provided by the IP, TCP and UDP checksums. Given that ESP provides a Sequence Number range of 2**32-1, and the window of acceptable values is in the range 2**5 to 2**8, CBCS is intended to be computationally infeasible to predictably and unde- tectably modify a datagram in transit during the time provided by the communication bandwidth-delay product. Software processing cost should be less than half as much as crypto- graphic hashing algorithms (such as MD5 or SHA1) on a little-endian machine, much better on a 32-bit big-endian machine, and nearly neg- ligible on a 64-bit big-endian machine. Hardware performance will benefit from the removal of multiple algo- rithm passes over the same data. The hardware resources required are considerably less than required for MD5 or SHA1. 1.2. Primary CheckSum The primary checksum involves feed-forward through the encryption function, in the same fashion as CBC, through XOR with the plaintext. Any single or multiple bit change in a cipher block (or the datagram IV) will result in a large unpredicatable change to all following cipher blocks. The primary checksum may be used alone. Its strength is based on an integrity secret-key, the related blocksize of the cipher, and is dependent on the strength of the cipher itself. 1.3. Secondary CheckSum The secondary checksum involves only the checksum of successive ciphertext blocks. Any single bit change in a cipher block (or the datagram IV) will result in a small unpredicatable change to all fol- lowing cipher blocks. Multiple bit changes in carefully chosen pairs can be used to reduce the unpredictability. The secondary checksum is likely too weak to be used alone. Its strength is based on an integrity secret-key, the related blocksize of the cipher, and the unpredictability of the cipher output. However, it can be combined with the primary checksum to double the amount of internal chaining for the integrity function. Simpson expires in six months [Page 2] DRAFT CBCS July 1997 2. Description IVa P1 P2 Pi | | | | +-----+ v +-----+ v +-----+ v Sa->| S |->(X)->| S |->->(X)->| S |->->(X)-> +-----+ | +-----+ | +-----+ | v ^ v ^ v +-----+ ^ +-----+ ^ +-----+ k->| E | ^ k->| E | ^ k->| E | +-----+ ^ +-----+ ^ +-----+ | ^ | ^ | IVb +->->->+ +->->->+ +->->-> | | | | +-----+ v +-----+ v +-----+ v Sb->| S |->(X)->| S |->->(X)->| S |->->(X)-> +-----+ | +-----+ | +-----+ | v ^ v ^ v +->->->+ +->->->+ +->->-> | | | C1 C2 Ci The Cipher Block CheckSums (CBCS) mode is a simple variant of the CBC mode [RFC-wwww]. For each datagram, the checksums are initialized with separate con- stant seeds (Sa, Sb). An Initialization Variable (IV) is split into two parts (IVa, IVb) which are separately added to the primary and secondary checksums respectively. The primary checksum output is XOR'd with the first plaintext block (P1). The keyed encryption function (Ek) is followed by another XOR with the secondary checksum output, which generates the ciphertext (C1) for the block. For successive blocks, the previous output of the encryption function (before masking) is added to the primary checksum, and the previous ciphertext block (after masking) is added to the secondary checksum. The primary checksum output is XOR'd with the current plaintext (Pi). The keyed encryption function (Ek) is followed by another XOR with the secondary checksum output, which generates the ciphertext (Ci) for that block. Simpson expires in six months [Page 3] DRAFT CBCS July 1997 C1 C2 Ci | | | IVb +->->->+ +->->->+ +->->-> | | v | v | +-----+ v +-----+ v +-----+ v Sb->| S |->(X)->| S |->->(X)->| S |->->(X)-> +-----+ | +-----+ | +-----+ | v v v +->->->+ +->->->+ +->->-> v v v v v +-----+ v +-----+ v +-----+ k->| D | v k->| D | v k->| D | +-----+ v +-----+ v +-----+ IVa v v v v v | | v | v | +-----+ v +-----+ v +-----+ v Sa->| S |->(X)->| S |->->(X)->| S |->->(X)-> +-----+ | +-----+ | +-----+ | P1 P2 Pi To decrypt, the order of the manipulations is reversed (as shown). Design Notes: The (X) is a crude symbol indicating XOR of the two blocks, but the horizontal block is passed unaltered to the next checksum stage. The checksums could be seeded with the encryption key. However, additional keying material is relatively easy to generate, and should provide an increase in the security of the integrity check. Commonly, only one IV of the block size is available. The check- sums could both use the same IV, but separate IVs should provide an increase in the security. Using the plaintext was considered as the addend to the secondary checksum, but this was rejected in fear of revealing some bits of the plaintext, or a cipher relationship between the plaintext and the ciphertext. 3. Initialization Variable CBCS requires an Initialization Variable (IV). The IV conceals ini- tial blocks that repeat in multiple datagrams. For ESP, each datagram generates its IV from material carried in the Simpson expires in six months [Page 4] DRAFT CBCS July 1997 datagram. This ensures that decryption of each received datagram can be performed, even when some datagrams are lost, duplicated, or re- ordered in transit. For 64-bit block ciphers, the primary 64-bit IVa is generated from the 32-bit Security Parameters Index (SPI) field followed by (con- catenated with) the 32-bit Sequence Number (SN) field. Then, the bit-wise complement of the 32-bit Sequence Number (SN) value is XOR'd with the first 32-bits (SPI): (SPI ^ -SN) || SN The secondary 64-bit IVb is the complement of IVa: (-SPI ^ SN) || -SN Security Notes: Each IV is intended to be unique over the lifetime of the ESP cipher session-key(s). A counter is most commonly used to gener- ate the IV, providing an easy method to prevent repetition. Incorporating the ESP Security Parameters Index (SPI) and the anti-replay ESP Sequence Number (SN) together can provide greater uniqueness and mutual protection between the first block and the ESP header. Modification of the SPI to alter the decryption key(s) will prevent correct decryption of the first block. Modi- fication of the SN to avoid anti-replay measures will also prevent correct decryption of the first block, which is most likely to contain datagram headers required for delivery. Attempts to mod- ify the IV to deliberately redirect transport headers will also likely be detected by the transport checksums. Inclusion of the bit-wise complement of SN ensures that bit changes are reflected twice in the IV. The checksum step with an unknown constant seed is intended to generate unpredictable ini- tial values, avoiding the rare serendipitous occurrence when the SN repeatedly changes in exactly the same fashion as corresponding bit positions in the first block. The resulting IV values are protected from disclosure. This completely protects the first block from undetectable modification. Simpson expires in six months [Page 5] DRAFT CBCS July 1997 4. Integrity CheckSums Unlike CBC alone, CBCS provides integrity for the datagram. A single ciphertext bit change will affect the current block, and every fol- lowing block. The final checksum will give a highly probable indica- tion of the alteration. For 64-bit block ciphers, the checksum functions are calculated in three steps: 1) addition modulo 2**64-1; 2) count the number of 1-bits in the 64-bit sum; 3) left circular rotation of the sum by the bit count. 4.1. Single CheckSum (CBCS1-64) For ESP with a single checksum, the optional Authenticator (when pro- vided) is calculated in six final steps: a) split the checksum into two 32-bit halves; b) multiply the two 32-bit halves, yielding a 64-bit product; c) count the number of 1-bits in the 64-bit product; d) left circular rotation of the product by the bit count; e) split the product again into two 32-bit halves; f) XOR the 32-bit halves, yielding a final 32-bit Authenticator value. 4.2. Double CheckSum (CBCS2-64) For ESP with a double checksum, the optional Authenticator (when pro- vided) is calculated in nine final steps: a) multiply the primary and secondary 64-bit checksums, yielding a 128-bit product; b) split the product into two 64-bit halves; Simpson expires in six months [Page 6] DRAFT CBCS July 1997 c) count the number of 1-bits in each 64-bit half of the product; d) left circular rotation of each half by their bit count; e) addition modulo 2**64-1 of the halves, yielding a 64-bit sum; f) count the number of 1-bits in the 64-bit sum; g) left circular rotation of the sum by the bit count; h) split the sum into two 32-bit halves; i) XOR the 32-bit halves, yielding a final 32-bit Authenticator value. 5. Collisions The "birthday paradox" probability of identical ciphertexts is squareroot(pi/2) * 2**(blocksize/2). Additional 2**(blocksize/2+n) ciphertexts yield 2**(2**n) collisions. Each such collision reveals a linear relation between two (random) unknown plaintexts and two (random) known ciphertexts. So, an observer learns that Pi = Pj + K for some i, j, and a known constant [Maurer91, Knudsen94]. A datagram generally consists of several ciphertext blocks. The num- ber of datagrams that can be safely exchanged under a single session- key is a function of the total size of the datagrams. Ciphers using CBC need to refresh keys more frequently than might otherwise be expected. Security Notes: For a 64-bit block cipher, the basic collision rate is on the order of 48 GigaBytes. While at first glance that might seem like a lot of data, a telephone conversation generates about 7,200 bytes per second, or 26 MegaBytes per hour, not including neces- sary transport headers. Simpson expires in six months [Page 7] DRAFT CBCS July 1997 Security Considerations Specific security limitations are described as notes in the relevant sections. Acknowledgements Most of the text of this specification was derived from earlier work by Perry Metzger and William Allen Simpson in multiple Request for Comments. The mathematical explanation of the collision rate was provided by Bart Preneel, based on "folklore" from the late 1980s and analysis in the early 1990s. The telephone analogy was provided by Bob Baldwin. References [ISO-8732] "Banking -- Key management (wholesale)", International Orga- nization for Standardization, 1988. [ISO/IEC-10116] "Information Processing -- Modes of Operation for an n-bit block cipher algorithm", International Organization for Standardization, 1991. [FIPS-81] US National Bureau of Standards, "DES Modes of Operation", Federal Information Processing Standard Publication 81, December 1980. [Knudsen94] Knudsen, L., PhD thesis, 1994. [Maurer91] Maurer, U., "Self-Synchronizing Stream Ciphers", Euro- Crypt'91. [MOV97] Menezes, A.J., van Oorschot, P., and Vanstone, S., "Handbook of Applied Cryptography", CRC Press, 1997. [RFC-1827x] Simpson, W., "IP Encapsulating Security Protocol (ESP) for implementors", work in progress. Simpson expires in six months [Page 8] DRAFT CBCS July 1997 [Schneier95] Schneier, B., "Applied Cryptography Second Edition", John Wiley & Sons, New York, NY, 1995. ISBN 0-471-12845-7. Contacts Comments about this document should be discussed on the ipsec@tis.com mailing list. Questions about this document can also be directed to: William Allen Simpson DayDreamer Computer Systems Consulting Services 1384 Fontaine Madison Heights, Michigan 48071 wsimpson@UMich.edu wsimpson@GreenDragon.com (preferred) bsimpson@MorningStar.com Simpson expires in six months [Page 9]