Comments P. Rogaway draft-rogaway-ipsec-comments-00.txt UC Davis April 3, 1995 Problems with Proposed IP Cryptography STATUS OF THIS MEMO This document provides criticism on a set of related Internet Drafts. Distribution of this memo is unlimited. ABSTRACT Several recent Internet Drafts make high-level architectural choices and specify low-level cryptographic mechanisms for Internet Protocol (IP) version 4 (IPv4) and IP version 6 (IPv6) security [A-arch, A-ah- arch, A-esp-arch, MS-ah-mech, MKS-esp-mech]. Here I critique cryptographic aspects of this work. 0. INTRODUCTION This memo addresses five recent Internet Drafts: [A-arch, A-ah-arch, A-esp-arch, MS-ah-mech, MKS-esp-mech]. These documents describe the architecture and an initial set of mechanisms in support of message privacy and authenticity in IPv4 and IPv6. The purpose of this note is to help clear up a few cryptographic misunderstandings which seem to be embodied in above documents. It also aims to elucidate some architectural choices which the author deems to be questionable. This memo has some overlap with an e-mail note sent to Ran Atkinson (March 10, 1995) and the IPng mailing list (March 14, 1995). Four authors and two IETF Working Groups have been involved in producing the above referenced Internet Drafts. Nonetheless, I prefer to address this body of work as a unit. In this note I name the above five Internet Drafts the "March-95 IPSEC Drafts." Many of my criticisms go beyond specifics of the March-95 IPSEC Drafts. The reader knowledgable of a broader set of Internet protocols and security matters should draw the the necessary inferences on his own. The organization of this document is simple. Each of the Sections 1-9 address a single technical area in which the March-95 Internet Drafts seems (to me) to get something wrong. I wrap up with some Rogaway [Page 1] rogaway-00.txt IP Cryptography April 3, 1995 conclusions in Section 10. 1. AUTHENTICITY = INTEGRITY The March-95 IPSEC Drafts follow long-standing tradition in implying that there are meaningful and distinct notions of (cryptographic) message authentication and (cryptographic) message integrity. This isn't true -- at least not in the symmetric key trust model and the active-adversary scenario which the design of Internet security assumes. Let me briefly explain why (cryptographic) message authenticity coincides with (cryptographic) message integrity. After all, these two goals sound very different when described in simple English [A- arch, pp. 2-3]. First: what is AUTHENTICITY? Intuitively, you achieve this goal when you send a message to a recipient if the only messages which an adversary can get the recipient to accept as valid are those which did in fact originate with you. To arrive at a realistic and versatile notion of this we usually assume that the adversary can mount a chosen-message attack: she can get authenticated messages of her choice and from these she must produce some NEW message which the recipient will deem authentic. While there are weaker notions of authentication possible, this one is usually regarded as the minimal desirable goal. It was first formalized by Goldwasser, Micali and Rivest [GMR]. Now what, in contrast, is INTEGRITY? It is is often assumed to mean something weaker than what is sketched above. (Integrity is described in [A-arch, p.3] as "the property of ensuring that data is transmitted from source to destination without undetected alternation.") But unless we completely change the adversarial model (e.g., now the adversary just introduces "random noise") the formalization for integrity COINCIDES with that of authenticity. In other words, there is no known (mathematically meaningful) definition for (cryptographic) message integrity except for the same definition used for authenticity. Now all of the above would just be pedantic niggling were it not for the fact that the encryption-provides-integrity belief has concrete implications throughout the March-95 IPSEC Drafts. Two of these are detailed in the next two sections. I thus begin with the following recommendation: RECOMMENDATION 1: Remove all mention of (message) "integrity" and speak only in terms of (message) authenticity. Rogaway [Page 2] rogaway-00.txt IP Cryptography April 3, 1995 In the remainder of this note I'll use the word "authenticity", "integrity", or "authenticity/integrity" interchangeably: these mean the [GMR]-notion sketched above. 2. ENCRYPTION DOES NOT GUARANTEE INTEGRITY Now that we've gone over authenticity/integrity, the next thing to get straight is the orthogonality of this notion to that of privacy. A mechanism which achieves privacy --even perfectly-- need not achieve authenticity/integrity (in any sense at all). Intuitively, you achieve PRIVACY when you send a message if an adversary learns nothing about the plaintext from seeing the ciphertext, except for the length of the plaintext. If the adversary already has prior information about the plaintext, she shouldn't learn anything new about the plaintext by virtue of seeing the ciphertext. This condition must hold regardless of the distribution on messages from which the plaintext is drawn, and regardless of the messages which the adversary may have requested the encryptions of. There are stronger notions of encryption possible, but this one ("semantic security") is usually regarded as the weakest desirable goal. It was first formalized by Goldwasser and Micali [GM]. A (secure) encryption scheme is any mechanism that achieves privacy. A (secure) message authentication scheme is any mechanism that achieves authenticity. In practice, encryption schemes never achieve authenticity. For example, the "ideal" encryption scheme --a one time pad-- does not achieve authenticity. Nor does DES-CBC encryption. For example, it is trivial, given the DES-CBC encryptions of a set of known messages, to assemble the DES-CBC encryptions of an enormous number of known, new messages. As a matter of simplicity, extensibility, and taste, ANY (semantically secure) encryption mechanism should achieve the security goals of the Encapsulated Security Payload (ESP) mechanism. Privacy and authenticity are orthogonal goals and this orthogonality should be reflected in the architecture. RECOMMENDATION 2: Make privacy the sole goal of the ESP. Make the architecture document clearly state that authenticity/integrity is not generally provided by an ESP mechanism. Advise users that most situations which require privacy also require authenticity, and the way to get both privacy and authenticity is to use both the ESP and the AH. Many earlier systems have gotten this all wrong. For example, trying to provide one mechanism for authenticity and one for privacy + Rogaway [Page 3] rogaway-00.txt IP Cryptography April 3, 1995 authenticity (and no mechanism for privacy alone) makes the resulting system less versatile and dramatically decreases the chance that the protocol designers will get the protocols right. 3. IT IS WORTHLESS TO ENCRYPT KNOWN HEADERS As a final consequence of the encryption-provides-integrity error, the March-95 IPSEC Drafts recommend encrypting routing headers "even if the same data is in the unencrypted part of the IP datagram" [A- arch, p. 4]. The drafts maintain that "if this rule is not strictly adhered to, then the system will be vulnerable to various kinds of routing attacks" [A-arch, p. 5]. But in light of what has been said already, it should be clear that encrypting these headers does not (generally) overcome these attacks; to do that one must authenticate the datagram, not (just) encrypt it. As a general principle, since ALL that an ESP mechanism ought guarantee is privacy, it is NEVER useful to encrypt known text. Doing so increases the size of packets and the computational complexity of making them, while it provides no security benefit. RECOMMENDATION 3: Modify the architecture to forbid or deprecate the encryption of known headers. 4. DON'T ENCRYPT MESSAGE AUTHENTICATION CODES In the symmetric setting message authenticity/integrity is best achieved by a "Message Authentication Code" (MAC). A MAC is a short string computed on the message, the key, and possibly random bits or computational state of the signer. The receiver of a message which bears a MAC applies a Boolean-valued verification algorithm on the key, the message, and the MAC. As an example, the [MS-ah-mech] mechanism is a MAC. The most common MAC is the "DES-CBC-MAC," defined in standards ANSI X9.9 and ISO 9797. Though it may sound odd, it is an open question if encrypting a MAC results in a secure MAC. That is, we do not know that encrypting a MAC does not defeat the authenticity which the MAC is supposed to provide. As a consequence of this state of affairs, it is much more transparently correct to MAC an enciphered string than to encipher a MACed one. The March-95 IPSEC Drafts allows both possibilities. This seems unwise. RECOMMENDATION 4: Mandate that, when an ESP and an AH are both used, the scope of the authentication includes the encrypted packet (and not vice versa). Rogaway [Page 4] rogaway-00.txt IP Cryptography April 3, 1995 5. DEFINE TRANSFORMS GENERICALLY The March-95 IPSEC Drafts define their two transforms [MS-ah-mech, MKS-esp-mech] in a manner intertwined with the use of these transforms [A-ah-arch, A-esp-arch]. That is, the transform definitions assume language and context as provided by the higher- level documents. This is unnecessary and problematic. Encryption and authentication mechanisms are used in contexts much wider than the scope of these particular IPSEC Drafts. To make mechanisms generally useful (in particular, useful across IETF work efforts) cryptographic transforms must be defined "generically." A model for how to do this is [Rivest]. In fact, part of the popularity of MD5 derives from a clean statement of a generally- useful algorithm (conveniently packaged up with use-unrestricted code). Thus [MS-ah-mech] should describe a generic message authentication code, useful anywhere one wants message authentication. And [MKS- esp-mech] should describe a generic encryption mechanism, useful anywhere one wants symmetric encryption. RECOMMENDATION 5: Describe cryptographic transforms completely independently of their intended usage. Any "parent" document (the user of a transform) is responsible for specifying how to to use an arbitrary transform (of the proper signature) to carry out its business. It is easy to dismiss the above recommendation as "organizational." But this is an organizational issue with concrete implications. First, the difficulty of obtaining quality review of any proposed cryptographic transform is very different depending on whether or not one draws a clear abstraction boundary at transform. For example, while several colleagues would be willing to review the definitions of a clearly-defined MAC or encryption function, very few skilled colleagues are willing to wade through specialized language and notions which are fundamentally irrelevant. Second, a failure to draw a proper abstraction boundary breeds the "corrupting" of the transform to include dependencies on inappropriate information. For example, the use of the "Data Type" field in [MKS-esp-mech] should not appear at this level, since this has nothing to do with the secure encipherment of a string. Finally, a failure to draw a proper abstraction boundary at the transform makes the resulting mechanism of rather limited use, as described above. Rogaway [Page 5] rogaway-00.txt IP Cryptography April 3, 1995 6. MANDATE HARDWARE-EFFICIENT *AND* SOFTWARE EFFICIENT TRANSFORMS In specifying transforms [MS-ah-mech] and [MKS-esp-mech] the March-95 IPSEC Drafts embody a peculiar asymmetry: one transform [MKS-esp- mech] was designed to be hardware-efficient, while the other mechanism [MS-ah-mech] was intended to be software-efficient. Having a hardware-efficient privacy mechanism and a software-efficient authenticity mechanism is a way to suit no one's needs well. In deciding on mechanisms one must start from the set of requirements. One clear requirement ought to be the ability to obtain message privacy and authenticity services without unnecessary performance impact whether those services are implemented in special- purpose hardware or a general-purpose processor. Let us call this the "cross-platform efficiency goal." Unfortunately, it is impossible to achieve the cross-platform efficiency goal using one privacy mechanism and one authenticity mechanism. The reason is that a cryptographic mechanism which is designed to do well in software will be vastly more efficient in software than a software-implementation of a cryptographic mechanism designed to do well in hardware. Similarly, a cryptographic mechanism which is designed to do well in hardware will be vastly more efficient in hardware than a hardware-implementation of a cryptographic mechanism designed to do well in software. As an example, a software-optimized cipher named "SEAL" (Software Encryption ALgorithm) encrypts in about 20 instructions per (32-bit) word [RC] -- well over an order of magnitude faster than any software implementation of the (hardware-efficient) DES algorithm. On the other hand, appropriate use of DES lets you encrypt at the 1-10 GBit/second speeds of emerging high-speed networks -- not something to try with SEAL. The conclusion is that if we are going to usefully support privacy and authenticity in environments which might or might not have special-purpose hardware, than we should require privacy and authenticity mechanisms which are hardware-efficient as well as privacy and authenticity mechanisms which are software-efficient. RECOMMENDATION 6: There should be (at least) four required cryptographic transforms: a hardware-efficient encryption algorithm; a software-efficient encryption algorithm; a hardware- efficient MAC; and a a software-efficient MAC. Security architecture always involves tradeoffs. Here I am saying that a failure to meet the cross-platform efficiency goal is an unacceptable tradeoff for the slight simplification of having two required mechanisms instead of four. Rogaway [Page 6] rogaway-00.txt IP Cryptography April 3, 1995 Some might argue that two additional encryption transforms should be specified: an exportable software-efficient mechanism and and an exportable hardware-efficient mechanism (thus making 6 specified transforms). I won't voice an opinion on this (political) question, but let me say that it is desirable that, from the start, implementations support multiple encryption transforms. Without this, mechanism-negotiation (which is crucially important) will end up absent or wrong. 7. USE 128-BIT KEYS A second requirement that mechanisms should meet is not to be susceptible to simple key-exhaustion attacks (when the keys are selected from a suitably large space). Key distribution mechanisms should not distribute 64-bit keys. Doing that limits IP security's evolution path. Use of 128-bit keys does not imply incompatibility with algorithms that use 64-bit keys. Where older mechanisms exist with which one wishes to maintain compatibility (DES-CBC encryption) the 128-bit algorithm can be constructed so that particular 128-bit keys induce a transformation which coincides with that of a standard mechanism operating on a 64-bit key. RECOMMENDATION 7: The required encryption and authentication mechanisms should use 128-bit keys. (Of course defining an algorithm in terms of a 128-bit key does not imply that the key resides in its operational form as a 128-bit quantity; it is often convenient to represent the key by a larger structure.) 8. THE MAC MECHANISM The MAC currently specified in [MS-ah-mech] is MAC_a(x) = MD5(MD5(x).a). The MAC specified in the previous version of this document (and still specified in [A-ah-arch] was MAC_a(x) = MD5(a.x.a). While the old suggestion was better than the new one, neither is good. I claim that no similar MD5-mode of operation will make a good choice, either. My reasons: [1] TOO SLOW. The MD5 algorithm takes a few tens of instructions per word, and nothing can be done about that. [2] NO FOUNDATIONS: The correctness of MAC_a(x) = MD5(a.x.a) is unrelated to the assumed collision intractable of MD5. The cor- rectness of MAC_a(x) = MD5(MD5(x).a) requires collision intractability of MD5 but does not appear to imply it. Rogaway [Page 7] rogaway-00.txt IP Cryptography April 3, 1995 Analogous statements seem to hold when one assumes other (unre- lated) cryptographic assumptions about MD5. Thus for neither method do standard or well-understood beliefs about the proper- ties of our cryptographic primitives imply the correctness of the the message authentication code built on top of them. [3] NO MANIFEST PARALLELISM: If you can compute MD5 in x bits per second using one MD5 chip then with two MD5 chips you can com- pute MD5 in ... x bits per second. That is, extra hardware just doesn't help. This concern is not very relevant if one also supports (as suggested) a good, hardware-efficient MAC. But if one is specifying only one authentication mechanism, this would be a problem. What is the alternative to a mechanism like MD5(a.x.a) ? Objection [2] can be answered by switching, for example, to MAC_a(x) = DES-CBC- MAC_a(MD5(x)); this construction is provably-good under the assump- tion that DES is a secure block cipher and MD5 is collision- intractable [BR]. An alternative provably-secure solution (under a different assumption) was recently offered by Bellare, Canetti and Krawczyk [BCK]; it uses MD5 alone as the underlying cryptographic primitive. Unfortunately, both of these alternatives (and ones like them) do nothing to address the efficiency problem [1]; it remains the case that one is spending some 50 or so instructions per (32-bit) word of message [Touch]. An alternative approach for making a fast and high-confidence MAC lies in what is called "Wegman-Carter authentication" [WC]. Using known results, an efficient "almost-universal-2" hash family gives rise to an efficient MAC. Describing such MACs is out of the scope of this note, but recent work of my own [Rogaway] suggests that MACs constructed in this manner will be about 2-4 times faster than MD5. I expect to have a concrete scheme specified in the coming months. RECOMMENDATION 8: Achieve software-efficient message authentica- tion using a Wegman-Carter MAC based on a carefully-designed almost-universal-2 family of hash functions. If for some (political?) reason one insists on basing a MAC on a col- lision-intractable hash function, then there is no reason why the collision-intractable hash function should not be used in a manner which enjoys some provable-security claim. 9. THE ENCRYPTION MECHANISM The DES-CBC transform of [MKS-esp-mech] suffers from a completely different set of problems than the MD5 MAC mechanisms. I take the Rogaway [Page 8] rogaway-00.txt IP Cryptography April 3, 1995 DES-CBC transform to be the proposed method for hardware-efficient encryption, and so it would be inappropriate for me to criticize its software performance. On the other hand, the issue of key size which has plagued DES since its inception only gets worse (e.g., see [Weiner]) -- so much so that, at this point, it may be irresponsible for any NEW proposal to specify DES in a mode of operation which is susceptible to 2**56 complexity key-exhaustion. Fortunately, this problem is easily remedied: one changes the mode of usage of the same cipher. As sketched in Section 7, I recommend that one achieve hardware-efficient encryption using DES in a mode of operation which employs a 128-bit key used in a manner which coin- cides with DES-CBC on a 64-bit key whenever the 128-bit key is appro- priately selected. There are many such possibilities. For example, instead of cipher block chaining DES one could cipher block chain the block cipher F_ab(x)= E_a(D_b(E_a(x)))), where E=DES and D=DES^{-1}. When the key ab is of the form aa, the method coincides with DES- CBC_a. RECOMMENDATION 9: The hardware-efficient encryption mechanism should be a 128-bit upwardly-compatible version of DES-CBC. There are further problems with particulars of the [MKS-esp-mech] proposal. Unlike the MAC proposal [MS-ah-mech], the encryption pro- posal is more a "template" for a mechanism than a particular mecha- nism, since it attempts to avoid pinning down even the length of the Initialization Vector (IV). This is unnecessarily complex and will cause people to mis-implement the choice of IV. RECOMMENDATION 10: Each transform should fully specify one partic- ular function (though this function may be probabilistic or state- ful). For example, if one has a mechanism like DES-CBC, one must specify how the initialization vector is to be selected. The reason for this recommendation is experience that indicates that if a transform is not completely specified, implementors will not know how to finish the "missing pieces" in a way that is cryptograph- ically correct. As an example, it is not true that CBC encryption can use an arbitrary nonce initialization vector: it is essential that the IV be unpredictable by the adversary. (To see this, suppose the IV is a sequence number: 0, 1, 2, ... . Then a (first) encryp- tion of 0x0000000000000000 followed by an encryption of 0x0000000000000001 is recognizably distinct from a (first) encryption of 0x0000000000000000 followed by an encryption of 0x0000000000000000. Clearly this violates violates the notion of a secure encryption sketched in Section 2.) Rogaway [Page 9] rogaway-00.txt IP Cryptography April 3, 1995 10. CONCLUSIONS The March-95 IPSEC Drafts have several significant flaws. Some of these seem to be misunderstandings about the correct use of crypto- graphic primitives; other problems are more architectural in nature. In any case, it seems clear that this body of work needs a lot more thought and maturation. I worry about the process by which cryptographic mechanisms emerge and get standardized. A committee can not do good cryptographic design. Reading [Schneier] does not qualify one to do cryptographic design. A set of requirements should be understood and then propos- als should be sought (from the few relevant people) responsive to those requirements. Let me end by returning (by way of example) to the change we saw dur- ing the last iteration of the MAC mechanism [MS-ah-mech]. Recall that it went from MAC_a(x) = MD5(a.x.a) to MAC_a(x) = MD5(MD5(x).a). It is easy to fall into the trap of arguing in the margins: here one would pick the mechanism he likes more (for me: the old one), and then try to argue why. But this is just silliness. The fact is, the change fixes none of the issues mentioned in Section 8 (in fact, it makes issue [2] worse); neither mechanism is on track. So how did we go from the one old mechanism to the new, and why? The document, at least, provide no clue. It makes one wonder: are we on a path which will lead to meaningful and scientific standards -- or are people just guessing? 11. REFERENCES [A-ah-arch] R. Atkinson, "IP Authentication Header." draft-ietf- ipsec-auth-00.txt, 23 March 1995. [A-esp-arch] R. Atkinson, "IP Encapsulating Security Payload (ESP)." draft-ietf-ipsec-esp-00.txt, 23 March 1995. [A-arch] R. Atkinson, "Security Architecture for the Internet Pro- tocol." draft-ietf-ipsec-arch-00.txt, 23 March 1995. [BCK] M. Bellare, R. Canetti and H. Krawczyk (unpublished). Personal communication through Mihir Bellare (February 1995). [BR] M. Bellare and P. Rogaway, "Entity Authentication and Key Distribution." Proceedings of CRYPTO '93 (1993). Rogaway [Page 10] rogaway-00.txt IP Cryptography April 3, 1995 [GM] S. Goldwasser and S. Micali, "Probabilistic Encryption." J. of Computer and System Sciences, 28, pp 270-299, April 1984. [GMR] S. Goldwasser, S. Micali and R. Rivest, "A digital signa- ture scheme secure against adaptive chosen-message attacks," SIAM Journal of Computing, 17(2), pp. 281-308, April 1988. [MKS-enc-mech] P. Metzger, P. Karn and W. Simpson. "The ESP DES-CBC Transform." draft-ietf-ipsec-esp-des-cbc-03.txt. [MS-auth] P. Metzger and W. Simpson, "IP Authentication using Keyed MD5." draft-ietf-ipsec-ah-md5-02.txt, March 1995. [Rivest] R. Rivest, "The MD5 Message-Digest Algorithm," RFC-1321, DDN Network Information Center, April 1992. [Rogaway] P. Rogaway, "Bucket Hashing and its Application to Fast Message Authentication." Manuscript. February 1995. [RC] P. Rogaway and D. Coppersmith, "A software-optimized encryption algorithm." Fast Software Encryption, Cam- bridge Security Workshop, 1993 Proceedings, R.~Anderson, ed., pp. 56-63. Lecture Notes in Computer Science, vol. 809, Springer-Verlag (1994). [Schneier] B. Schneier, "Applied Cryptography." John Wiley & Sons, 1994. [Touch] J. Touch, "Performance Analysis of MD5." Manuscript (1995). [Weiner] M. Weiner, "Efficient DES Key Search." Manuscript (1993). [WC] M. Wegman and L. Carter, "New Hash Functions and their use in Authentication and Set Equality." J. of Computer and System Sciences, 22, 265-279 (1981). 12. AUTHOR'S ADDRESS Phillip Rogaway Department of Computer Science Engineering II Building University of California Rogaway [Page 11] rogaway-00.txt IP Cryptography April 3, 1995 Davis, California 95616 (916) 752-7583 rogaway@cs.ucdavis.edu Rogaway [Page 12]