[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
IPSEC (comments on Internet Drafts)
Some comments (about 10 pages) on the Internet Drafts:
1. draft-ietf-ipsec-auth-00.txt
2. draft-ietf-ipsec-esp-00.txt
3. draft-ietf-ipsec-arch-00.txt
4. draft-ietf-ipsec-esp-des-cbc-03.txt
5. draft-ietf-ipsec-ah-md5-02.txt
I hope this input is reflected in the discussion
in Danvers; I am unable to attend.
Regards,
Phil
Comments P. Rogaway
rogaway-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
correctness 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
assumption 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
collision-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
appropriately 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 mechan-
ism, 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 propo-
sals 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]