Internet Draft P. Rogaway draft-rogaway-cbc-encrypt-00.txt UC Davis Expires in six months April 27, 1995 CBC Encryption STATUS OF THIS MEMO This document is an Internet Draft. Internet Drafts are working documents of the Internet Engineering Task Force (IETF), its Areas, and its working groups. Internet Drafts are draft documents valid for a maximum of 6 months. Internet Drafts may be updated, replaced, or obsoleted by other documents at any time. It is not appropriate to use Internet Drafts as reference material or to cite them other than as a "working draft" or "work in progress". To learn the current status of any Internet- Draft, 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), or munnari.oz.au (Pacific Rim). This particular Internet Draft is a submission to the IP Security Working Group of the IETF. It is intended that a future version of this draft be submitted for consideration as a standards-track document. Comments on this draft should be submitted to the ipsec@ans.net mailing list. Distribution of this document is unlimited. 0. ABSTRACT A privacy transform is a pair of algorithms intended to support message privacy. This document defines the F-CBC transform for an arbitrary block cipher F. Three particular transforms are then singled out, including the DES-CBC transform. 1. INTRODUCTION This document defines the DES-CBC privacy transform. More generally, this document defines the privacy transform obtained by cipher block chaining an arbitrary block cipher. Rogaway [Page 1] Internet Draft CBC Encryption April 27, 1995 We begin by describing the most important design choices underlying this document. 1.1. The Application / Transform Abstraction Boundary In this document, transforms are specified in a manner independent of their intended use. Thus a CBC privacy transform (as described herein) can be employed to form the Encapsulated Security Payload (ESP) of an IPv4/IPv6 datagram [At-ESP]. But a CBC transform can also be used for many other purposes. Describing transforms in an application-independent way not only makes them more generally useful, but (at least as important) it is essential to tractable protocol analysis. One consequence of a rigid application / transform abstraction boundary is that there is a narrow and well-defined interface between this document and any document which uses it. The using document must specify all and only the following: (a) a transform identifier (see Section 1.3); (b) when the application wants to encrypt a string-- three strings: the one to encrypt, a key, and a ``nonce''; (c) when the applications wants to decrypt a string-- two strings: the one to decrypt, and a key. The using document should use CBC- encrypted data (obtained from (b)) only as an opaque data type. 1.2. Genericness The selection of an encryption algorithm can be a difficult and even political issue. For this reason, among others, this document aims to be algorithm-neutral. Thus we give not just a specific transform, but a ``template'' which can be instantiated to yield multiple transforms. This is the same approach followed by the International Standards Organization [ISO-10116]. Being TOO algorithm-neutral would make this document, by itself, not so useful. It would have to be accompanied by a companion document enumerating specific instantiations. Instead of this, we specify a specific transform. In fact, we specify three of them. Specifying a transform within the framework of this document means instantiating the generic F-CBC transform with a particular block cipher F. The three block ciphers we single out are all based on the NBS Data Encryption Standard (DES), as described in [FIPS-46]. The three block ciphers are DES itself (after disregarding parity conventions), plus two different versions of ``triple DES.'' Additional CBC privacy transforms are easily specified: follow the model of Sections 5/6/7. Rogaway [Page 2] Internet Draft CBC Encryption April 27, 1995 1.3. Transform Identifiers A ``transform identifier'' is a 32-bit number which uniquely names a transform. A transform identifier for a privacy mechanism completely specifies the maps for encrypting and decrypting strings. A transform identifier for a message authenticity mechanism completely specifies the maps for generating and verifying authentication tags. Transform identifiers are very useful. They serve as a short and unambiguous name in protocol negotiations, key separation, and other purposes. Transform identifiers must be unique in the space of all registered transforms. For example, a privacy transform and a message authenticity transform may NOT be given the same transform identifier. Each document which defines a transform must specify its transform identifier. 2. NOTATION The following notation will be used in the remainder of this document. If s and t are strings, st denotes their concatenation. The bits of an m-bit string s are numbered as s = s[1] ... s[m]. That is, bit 1 is the most significant bit of the first byte; bit 8 is the least significant bit of the first byte; and so forth. By |s| we denote the length of string s. Thus |s| = m in the example above. By s[i..j] we denote the substring of s which runs from bit location i until bit location j, inclusive: s[i..j] = s[i] s[i+1] ... s[j]. If s and t are strings of equal length, y = s XOR t is the string whose i-th bit y[i] is the exclusive-OR (XOR) of s[i] and t[i]. By 2**n we denote 2 raised to the power n. We shall often write a symbol (like ``F''), followed by an underscore (``_''), followed by a second symbol (like ``k''). Read the second symbol as a subscript of the first. If what follows the underscore is in curly brackets (``{ ... }'') then read everything inside the curly brackets as the subscript. Rogaway [Page 3] Internet Draft CBC Encryption April 27, 1995 3. SYNTAX We begin by describing what, syntactically, is a block cipher. Then we describe what, syntactically, is a CBC privacy transform. 3.1. Block Cipher Syntax A block cipher F specifies - a ``block length,'' BLEN, which is a number; - a ``key length,'' KLEN, which is a number; - the set of ``valid keys'' (each of KLEN bits); and - for each valid key k, a permutation on the set of strings of BLEN bits. We let F_k(P) denote the value of this permutation on string P. 3.2. F-CBC Transform Syntax This document will describe how a block cipher F induces an ``F-CBC transform.'' What is an F-CBC transform? Formally, this is a pair of functions (F-CBC-Encrypt, F-CBC-Decrypt). Function F-CBC-Encrypt maps - a ``key,'' k, of KLEN bits; - a ``plaintext,'' x, of an arbitrary number of bits, |x|; and - a ``nonce,'' m, of BLEN bits TO: - a ``ciphertext,'' F-CBC-Encrypt_{k,m}(x), having |x| + BLEN bits; or else the distinguished value BADKEY. Function F-CBC-Decrypt maps - a key, k, of KLEN bits; and - a ``ciphertext,'' y, of at least BLEN bits TO: - a string F-CBC-Decrypt_k(y) having |y| - BLEN bits; or else the distinguished value BADKEY. 4. DEFINITION OF THE F-CBC TRANSFORM Our definition of the F-CBC transform is a straightforward extension of [FIPS-81]. The only ``unusual'' thing is the nonce m. This plays the role usually played by the ``Initialization Vector,'' IV. Our reasons for defining the encryption function in terms of (x,k,m) --and not (x,k,IV)-- is that IV is rather easily misused. See Appendix B, part B.3. Rogaway [Page 4] Internet Draft CBC Encryption April 27, 1995 4.1. F-CBC-Encrypt Let F be a block cipher with block length BLEN and key length KLEN. Let x be a string of arbitrary length, let k be a string of KLEN bits, and let m be a string of BLEN bits. Define F-CBC- Encrypt_{k,m}(x) as the value returned by the following algorithm: [E.0] If k is an invalid key for block cipher F, return BADKEY. /* comment: the block ciphers of Sections 5,6,7 have no invalid keys. */ [E.1] Partition x into x = x_1 x_2 ... x_n x', where |x_i| = BLEN (for each 1 <= i <= n) and 0 <= |x'| < BLEN. /* comment: each x_i is a ``full block,'' while x' is a ``short block.'' (x' is the empty string if |x| is divisible by BLEN.) */ [E.2] Let IV = y_0 = F_k(m). [E.3] If |x|=0, return IV. [E.4] For 1 <= i <= n, let y_i = F_k(x_i XOR y_{i-1}). [E.5] Let y' = x' XOR (F_k(y_n)[1..|x'|]). /* comment: the short piece of ciphertext corresponding to x'. */ [E.6] Return y = IV y_1 ... y_n y'. The above method essentially coincides with CBC encrypting the string m x using Initialization Vector IV=0. 4.2. F-CBC-Decrypt For valid key k and a string C of BLEN bits, denote by F-INV_k(C) the (unique) string P such that F_k(P)=C. Let y be a string of length at least BLEN bits, and let k be a string of KLEN bits. Define F-CBC-Decrypt_k(y) as the value returned by the following algorithm: [D.0] If k is an invalid key for block cipher F, return BADKEY. [D.1] Partition y into y = y_0 y_1 y_2 ... y_n y', where |y_i| = BLEN for each 0 <= i <= n, and 0 <= |y'| < BLEN. Rogaway [Page 5] Internet Draft CBC Encryption April 27, 1995 [D.2] For each 1 <= i <= n, let x_i = y_{i-1} XOR F-INV_k(y_i). [D.3] Let x' = y' XOR (F_k(x_n))[1..|y'|]. [D.4] Return x = x_1 ... x_n x'. 5. THE DES-CBC TRANSFORM This section specifies the F-CBC transform for F = DES. 5.1. Definition Let DES-STANDARD(k,P) be the function defined by [FIPS-46], where k is the 64-bit key and P is the 64-bit plaintext block. According to [FIPS-46], each byte of k should have odd parity, and every eighth key bit is unused. So for any 64-bit string k, let fix-parity(k) be the 64-bit string k' which is identical to k except that bits k'[8], k'[16], k'[24], k'[32], k'[40], k'[48], k'[56], and k'[64] are modi- fied, if necessary, so that each byte of k' will have odd parity. Block cipher F = DES is defined as follows. It has BLEN = 64 and KLEN = 64. Every 64-bit key is valid. We define DES_k(P) as the 64-bit string DES-STANDARD(fix-parity(k), P). 5.2. Transform Identifier When F is the block cipher DES (as described above) the F-CBC trans- form is called the ``DES-CBC transform.'' It is the ordered pair (DES-CBC-Encrypt, DES-CBC-Decrypt). The DES-CBC transform is given transform identifier is XXX. 6. THE EDE2-CBC TRANSFORM This section specifies the F-CBC transform for F a two-key version of ``triple DES.'' 6.1. Definition For 64-bit strings k and P, let E_k(P) = DES_k(P). For 64-bit strings k and C, let D_k(C) be the (unique) string P such that E_k(P)=C. Rogaway [Page 6] Internet Draft CBC Encryption April 27, 1995 Block cipher F = EDE2 is defined as follows. It has BLEN = 64 and KLEN = 128. Every 128-bit key is valid. Set EDE2_k(P) = E_k[1..64] (D_k[65..128] (E_k[1..64] (P) )). That is, we encrypt/decrypt/encrypt using DES, the first and last operations using the first half of key k, and the middle operation using the second half of key k. 6.2. Transform Identifier When F is the block cipher EDE2 (as described above) the F-CBC trans- form is called the ``EDE2-CBC transform.'' It is the ordered pair (EDE2-CBC-Encrypt, EDE2-CBC-Decrypt). The EDE2-CBC transform is given transform identifier is YYY. 7. THE EDE3-CBC TRANSFORM This section specifies the F-CBC transform for F the three-key ver- sion of ``triple DES.'' 7.1. Definition Block cipher F = EDE3 is defined as follows. It has BLEN = 64 and KLEN = 192. Every 192-bit key is valid. Set EDE3_k(P) = E_k[129..192] (D_k[65..128] (E_k[1..64] (P) )). That is, we encrypt/decrypt/encrypt using DES, the first operation using the first 64 bits of k; the second operation using the second 64 bits of key; and the last operations using the last 64 bits of key. 7.2. Transform Identifier When F is the block cipher EDE3 (as described above) the F-CBC trans- form is called the ``EDE3-CBC transform.'' It is the ordered pair (EDE3-CBC-Encrypt, EDE3-CBC-Decrypt). The EDE3-CBC transform is given transform identifier is ZZZ. [NOTE: HOW DO I GET OFFICIAL NUMBERS XXX, YYY, ZZZ ?] 8. SECURITY CONSIDERATIONS Rogaway [Page 7] Internet Draft CBC Encryption April 27, 1995 This entire document is about security. But the following considera- tions should be singled out. 8.1 The F-CBC transform does NOT provide data integrity (regardless of F). When cryptographic integrity/authenticity is desired, F- CBC encrypted ciphertext should be supplemented by a message authentication code (MAC) computed over said ciphertext using a key which has been properly separated from that used for (F-CBC- Encrypt, F-CBC-Decrypt). 8.2 The value of nonce m must NOT be reused within a given security context. See Appendix A. 8.3 When making multiple F-CBC-Encrypt calls under a common key, that key should be changed before 2**(BLEN/2) blocks (including short blocks) have been encrypted. This is true regardless of the strength of the cipher. In particular, users of the (BLEN = 64) transforms of Sections 6,7,8 should change keys before 2**32 blocks (including short blocks) have been encrypted. 8.4 At the time of this writing no practical cryptanalytic attack on DES is known. Current state of the art is [BiSh] and [Matsui]. The advances represented by these works make timely key change (as in (8.3)) particularly important for the DES-CBC transform. 8.5 The DES-CBC transform is susceptible to key-exhaustion attack by an adversary with large (but not unreasonable) computing resources. [Weiner] gives a careful cost estimate for a DES- cracking machine. To overcome key-exhaustion attacks use the EDE2-CBC transform or the EDE3-CBC transform (with an adequately unpredictable key). ACKNOWLEDGMENTS The comments of Hugo Krawczyk substantially improved this document. REFERENCES [At-ESP] R. Atkinson, ``IP Encapsulating Security Payload (ESP).'' Work in progress. [Biham] E. Biham, ``On Modes of Operation.'' In ``Fast Software Encryption, Cambridge Security Workshop'' (Ross Anderson, Rogaway [Page 8] Internet Draft CBC Encryption April 27, 1995 ed.). Lecture Notes in Computer Science 809, Springer- Verlag, 116-120 (1994). [BiSh] E. Biham and A. Shamir, Differential Cryptanalysis of the Data Encryption Standard. Springer-Verlag (1993). [FIPS-46] National Bureau of Standards, ``Data Encryption Standard.'' FIPS PUB 46 (January 1977). [FIPS-81] National Bureau of Standards, ``DES Modes of Operation.'' FIPS PUB 81 (December 1980). [ISO-10116] International Standards Organization, ``Information technol- ogy -- Security techniques -- Modes of operation of an n-bit block cipher.'' ISO/IEC 10116 (1991). [Matsui] M. Matsui, ``The First Experimental Cryptanalysis of the Data Encryption Standard.'' Advances in Cryptology -- CRYPTO '94 Proceedings. Springer-Verlag, 1-11 (1994). [Wiener] M. Wiener, ``Efficient DES Key Search.'' Carleton Univer- sity TR-244, Department of Computer Science (1994). APPENDIX A: USE OF NONCE ``m'' This appendix is not a part of the definition of the F-CBC transform. Nonetheless, the material of this Appendix must be understood to cor- rectly use an F-CBC transform. The map F-CBC-Encrypt requires a ``nonce,'' m, of BLEN bits. The following paragraph gives one acceptable choice of a nonce: a simple counter. The user of F-CBC-Encrypt is usually encrypting strings within some particular ``security context.'' Each encryption of a string within this context uses the same key, k. Within a particular security con- text the first application of F-CBC-Encrypt may select m = 0 (encoded as a string of BLEN bits). Each subsequent use of F-CBC-Encrypt (within the same security context) would select a value of m one greater than that previously used in this security context. The relevant feature of a nonce is that no value should be reused within a single security context. As a consequence, the security context must be torn down once the 2**BLEN possible values of nonce m have been used. But Section 8, part 8.3, already provided a stricter restriction: the session should be terminated before 2**(BLEN/2) Rogaway [Page 9] Internet Draft CBC Encryption April 27, 1995 blocks (including short blocks) have been encrypted. Assuming that this is done, a random string of BLEN bits also makes an acceptable choice for nonce m. APPENDIX B: DESIGN RATIONALE This appendix documents design rationale not described elsewhere. This appendix is strictly informational. B.1 Several mechanisms have been proposed which encrypt a string using a key of KLEN bits by making use of an underlying block cipher having key length klen < KLEN bits. The method of this document is sometimes called ``outer chaining.'' An alternative is ``inner chaining'' where, for example, multiple DES-CBC passes are made over the message being encrypted. Experts believe outer chaining to be safer. See [Biham]. B.2 One reason the EDE2/EDE3 block ciphers are attractive is that they are upwardly compatible extensions to DES, in the following sense: for a 64-bit key k, DES_k(P) = EDE2_{kk}(P) = EDE3_{kkk}(P). In particular, a hardware implementation of EDE2/EDE3 also can be used to compute DES. B.3 Usually one defines CBC encryption in terms of (k, x, and) an ``Initialization Vector,'' IV. Here, instead, we used (k, x, and) a ``nonce,'' m. At issue is the fact that the IV must be adversarially unpredictable: a general nonce (e.g., a counter) does NOT work as a correct IV. This fact does not seem to be well-known. Expecting the application using an F-CBC transform to understand this --and then provide an adversarially- unpredictable IV-- is asking too much. By computing the IV our- selves, from a variable which needs only be nonce, we lessen the chance that the user will incorrectly use the F-CBC transform. APPENDIX C: LIMITATIONS ON THE {DES, EDE2, EDE3}-CBC TRANSFORMS This appendix documents some security requirements unfulfilled by any of the transforms specified in Sections 6,7, and 8. This appendix is strictly informational. C.1 Block ciphers EDE2 and EDE3 are almost three times as slow to compute as block cipher DES. The transforms EDE2 and EDE3 induce offer no solution for applications which want the speed Rogaway [Page 10] Internet Draft CBC Encryption April 27, 1995 of DES, the assurance associated to being a DES-variant, and better-than-DES resistance to key exhaustion. C.2 The DES block cipher was designed to be hardware-efficient. Efficient software encryption is better accomplished using a cipher designed to be software-efficient. Such a solution would not be built around DES. The three transforms specified in this document offer no solution for applications which require a very software-efficient privacy transform. Author's Address Phillip Rogaway Department of Computer Science Engineering II Building University of California Davis, California 95616 (916) 752-7583 rogaway@cs.ucdavis.edu Rogaway [Page 11]