From ipsec-request@ans.net Wed Jun 7 18:21:34 1995 Received: from interlock.ans.net by nis.ans.net with SMTP id AA24879 (5.65c/IDA-1.4.4 for ); Wed, 7 Jun 1995 15:47:27 -0400 Received: by interlock.ans.net id AA19362 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Wed, 7 Jun 1995 15:40:59 -0400 Message-Id: <199506071940.AA19362@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Wed, 7 Jun 1995 15:40:59 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Wed, 7 Jun 1995 15:40:59 -0400 Mime-Version: 1.0 Content-Type: Multipart/Mixed; Boundary="NextPart" To: IETF-Announce: ; Cc: ipsec@ans.net From: Internet-Drafts@CNRI.Reston.VA.US Reply-To: Internet-Drafts@CNRI.Reston.VA.US Subject: I-D ACTION:draft-ietf-ipsec-auth-02.txt Date: Wed, 07 Jun 95 14:21:34 -0400 Sender: cclark@CNRI.Reston.VA.US --NextPart A Revised Internet-Draft is available from the on-line Internet-Drafts directories. This draft is a work item of the IP Security Protocol Working Group of the IETF. Title : IP Authentication Header Author(s) : R. Atkinson Filename : draft-ietf-ipsec-auth-02.txt Pages : 12 Date : 06/06/1995 This document describes a mechanism for providing cryptographic authentication for IPv4 and IPv6 datagrams. An Authentication Header (AH) is normally inserted after the main IP header and before the other information being authenticated. Internet-Drafts are available by anonymous FTP. Login with the username "anonymous" and a password of your e-mail address. After logging in, type "cd internet-drafts" and then "get draft-ietf-ipsec-auth-02.txt". A URL for the Internet-Draft is: ftp://ds.internic.net/internet-drafts/draft-ietf-ipsec-auth-02.txt Internet-Drafts directories are located at: o Africa Address: ftp.is.co.za (196.4.160.2) o Europe Address: nic.nordu.net (192.36.148.17) Address: ftp.nis.garr.it (192.12.192.10) o Pacific Rim Address: munnari.oz.au (128.250.1.21) o US East Coast Address: ds.internic.net (198.49.45.10) o US West Coast Address: ftp.isi.edu (128.9.0.32) Internet-Drafts are also available by mail. Send a message to: mailserv@ds.internic.net. In the body type: "FILE /internet-drafts/draft-ietf-ipsec-auth-02.txt". NOTE: The mail server at ds.internic.net can return the document in MIME-encoded form by using the "mpack" utility. To use this feature, insert the command "ENCODING mime" before the "FILE" command. To decode the response(s), you will need "munpack" or a MIME-compliant mail reader. Different MIME-compliant mail readers exhibit different behavior, especially when dealing with "multipart" MIME messages (i.e., documents which have been split up into multiple messages), so check your local documentation on how to manipulate these messages. For questions, please mail to Internet-Drafts@cnri.reston.va.us. Below is the data which will enable a MIME compliant mail reader implementation to automatically retrieve the ASCII version of the Internet-Draft. --NextPart Content-Type: Multipart/Alternative; Boundary="OtherAccess" --OtherAccess Content-Type: Message/External-body; access-type="mail-server"; server="mailserv@ds.internic.net" Content-Type: text/plain Content-ID: <19950606144127.I-D@CNRI.Reston.VA.US> ENCODING mime FILE /internet-drafts/draft-ietf-ipsec-auth-02.txt --OtherAccess Content-Type: Message/External-body; name="draft-ietf-ipsec-auth-02.txt"; site="ds.internic.net"; access-type="anon-ftp"; directory="internet-drafts" Content-Type: text/plain Content-ID: <19950606144127.I-D@CNRI.Reston.VA.US> --OtherAccess-- --NextPart-- From ipsec-request@ans.net Thu Jun 8 10:49:04 1995 Received: from interlock.ans.net by nis.ans.net with SMTP id AA28702 (5.65c/IDA-1.4.4 for ); Thu, 8 Jun 1995 06:55:48 -0400 Received: by interlock.ans.net id AA49675 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Thu, 8 Jun 1995 06:49:17 -0400 Message-Id: <199506081049.AA49675@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-4); Thu, 8 Jun 1995 06:49:17 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-3); Thu, 8 Jun 1995 06:49:17 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Thu, 8 Jun 1995 06:49:17 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Thu, 8 Jun 1995 06:49:17 -0400 X-Sender: t3125rm@clncrdv1.is.chrysler.com X-Mailer: Windows Eudora Version 2.1.1b3 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Date: Thu, 08 Jun 1995 06:49:04 -0400 To: ipsec@ans.net From: Robert Moskowitz Subject: Production IPSP needed in July for pilot... Chrysler has an immediate need for network level security for piloting in July and production in September. Basic configuration is 50 - 100 DOS/Windows PCs run LAN WORKPLACE for DOS for their TCP/IP stack (some small flexablity on that from Proof of Concept). 1 COMPAQ Prolina running Netware 4.1 (NWIP an option). 2 SPARC 1000s running Solaris 2.4. 1 RS/6000 running AIX. Nominal connectivity for the PCs an Novell server is Ethernet, 10baseT. The SPARCs tend to be on FDDI and the RS/6000 on T/R. PPP notebook access perdicted for October. Code must be a shipping product. D&B will be run on all evaluated companies. What else is out there besides the Timestep PERMIT product (granted, pre-IPSP). Encrypting routers need not apply. I need security closer to the devices. Robert Moskowitz Chrysler Corporation (810) 758-8212 From ipsec-request@ans.net Thu Jun 8 11:55:19 1995 Received: from interlock.ans.net by nis.ans.net with SMTP id AA25114 (5.65c/IDA-1.4.4 for ); Thu, 8 Jun 1995 11:55:19 -0400 Received: by interlock.ans.net id AA14668 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Thu, 8 Jun 1995 11:41:36 -0400 Message-Id: <199506081541.AA14668@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-3); Thu, 8 Jun 1995 11:41:36 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Thu, 8 Jun 1995 11:41:36 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Thu, 8 Jun 1995 11:41:36 -0400 Date: Thu, 08 Jun 95 08:19:50 From: "Housley, Russ" Encoding: 1630 Text To: ipsec@ans.net Cc: burt@rsa.com Subject: Keyless Integrity Check Values IPSECers: I have been traveling a great deal, so I let this issue drop. But I want to revisit the discussion. The last e-mail I recall on the topic was from Paul Lambert, and Paul was voicing support for keyless ICVs (a.k.a. keyless checksums). Before that, Hugo posted a message about attacks on keyless ICVs. Hugo described the following chosen message attack: - Construct a message M = M1 | CS1 | M2, where CS1 is the keyless checksum on M1, and M1 and M2 are arbitrary. The length of M1 | CS1 should be an integral number of blocks. - Give M to the party that's encrypting and authenticating, to obtain C = E (M | CS2), where CS2 is the checksum on M, and E is the encryption function. - In typical modes of encryption, it will be the case that that C = C1 | C2, where C1 = E (M1 | CS1) --- so C1 is a valid message as far as authentication is concerned - Replace C1 with C on the transmission line -- the recipient will accept C1 as authentic I discussed Hugo's attack with Burt Kaliski, and Burt came to the following conclusion: This [attack] works for any kind of checksum, and although it can be thwarted by including the total message length at the beginning of the message, it's an attack cryptographers would like to avoid entirely. Given that we are interested in protecting IP datagrams as well as TCP and UDP protocol data units, we should revisit the keyless ICV discussion because these protocol formats all include payload data lengths. Russ From ipsec-request@ans.net Thu Jun 8 22:42:07 1995 Received: from interlock.ans.net by nis.ans.net with SMTP id AA29054 (5.65c/IDA-1.4.4 for ); Thu, 8 Jun 1995 18:48:40 -0400 Received: by interlock.ans.net id AA22184 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Thu, 8 Jun 1995 18:45:18 -0400 Message-Id: <199506082245.AA22184@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-5); Thu, 8 Jun 1995 18:45:18 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-4); Thu, 8 Jun 1995 18:45:18 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-3); Thu, 8 Jun 1995 18:45:18 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Thu, 8 Jun 1995 18:45:18 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Thu, 8 Jun 1995 18:45:18 -0400 Date: Thu, 8 Jun 1995 15:42:07 -0700 (PDT) From: Chris Swanson X-Sender: cds@sanjose To: Robert Moskowitz Cc: ipsec@ans.net Subject: Re: Production IPSP needed in July for pilot... In-Reply-To: <199506081049.AA49675@interlock.ans.net> Mime-Version: 1.0 Content-Type: TEXT Greetings again, How are you doing? I was just in Ann Arbor, but for less than 20 hours. Have you looked at the SunScreen stuff? Regards, -=Chris +-------------------------+------------------------+-------------------------+ | @@@ @@@ @@@@ @@@ | SSDS, Inc. | Chris Swanson | | @ @ @ @ @ | Minneapolis Operations | Engineer | | @@@ @@@ @ @ @@@ | 8841 Nicollet Ave S. | Tel: (612)/888-4045 | | @ @ @ @ @ | Bloomington, MN | FAX: (612)/888-4066 | | @@@@ @@@@ @@@@ @@@@ | 55420 | Email: cds@ssds.com | +-------------------------+------------------------+-------------------------+ | ** The Intelligent Network Computing Company ** | +----------------------------------------------------------------------------+ On Thu, 8 Jun 1995, Robert Moskowitz wrote: > Date: Thu, 08 Jun 1995 06:49:04 -0400 > From: Robert Moskowitz > To: ipsec@ans.net > Subject: Production IPSP needed in July for pilot... > > Chrysler has an immediate need for network level security for piloting in > July and production in September. > > Basic configuration is 50 - 100 DOS/Windows PCs run LAN WORKPLACE for DOS > for their TCP/IP stack (some small flexablity on that from Proof of > Concept). 1 COMPAQ Prolina running Netware 4.1 (NWIP an option). 2 SPARC > 1000s running Solaris 2.4. 1 RS/6000 running AIX. Nominal connectivity for > the PCs an Novell server is Ethernet, 10baseT. The SPARCs tend to be on > FDDI and the RS/6000 on T/R. PPP notebook access perdicted for October. > > Code must be a shipping product. D&B will be run on all evaluated companies. > > What else is out there besides the Timestep PERMIT product (granted, > pre-IPSP). Encrypting routers need not apply. I need security closer to > the devices. > > Robert Moskowitz > Chrysler Corporation > (810) 758-8212 > > From ipsec-request@ans.net Fri Jun 9 16:18:39 1995 Received: from interlock.ans.net by nis.ans.net with SMTP id AA26789 (5.65c/IDA-1.4.4 for ); Fri, 9 Jun 1995 12:23:24 -0400 Received: by interlock.ans.net id AA52388 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Fri, 9 Jun 1995 12:20:33 -0400 Message-Id: <199506091620.AA52388@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-3); Fri, 9 Jun 1995 12:20:33 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Fri, 9 Jun 1995 12:20:33 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Fri, 9 Jun 1995 12:20:33 -0400 X-Sender: Luke_Nelson@pop.valley.net (Unverified) Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Date: Fri, 09 Jun 1995 12:18:39 -0400 To: ipsec@ans.net From: Luke_Nelson@valley.net (Luke Nelson) Subject: subscribe X-Mailer: subscribe ipsec From ipsec-request@ans.net Fri Jun 9 17:40:00 1995 Received: from interlock.ans.net by nis.ans.net with SMTP id AA26765 (5.65c/IDA-1.4.4 for ); Fri, 9 Jun 1995 15:47:25 -0400 Received: by interlock.ans.net id AA58320 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Fri, 9 Jun 1995 15:44:52 -0400 Message-Id: <199506091944.AA58320@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-5); Fri, 9 Jun 1995 15:44:52 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-4); Fri, 9 Jun 1995 15:44:52 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-3); Fri, 9 Jun 1995 15:44:52 -0400 From: Paul_Lambert-P15452@email.mot.com Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Fri, 9 Jun 1995 15:44:52 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Fri, 9 Jun 1995 15:44:52 -0400 Date: 9 Jun 95 12:40:00 -0500 To: housley@spyrus.com Cc: ipsec@ans.net, burt@rsa.com Subject: Re: Keyless Integrity Check Values Russ, Thanks for the note of support on keyless Integrity Check Values (ICVs). As you noted I am a proponent of this class of security techniques. The keyed integrity mechanisms are not yet widely available in hardware, so the software integrity check process becomes the most critical factor in improving the performance of network security. A simple keyless ICV (with message length either in the ip header or explicit) covered by an encryption algorithm is the most efficient way to provide the best security (integrity, authentication, confidentiality). Paul _______________________________________________________________________________ Subject: Keyless Integrity Check Values Author: housley@spyrus.com@INTERNET Date: 6/8/95 11:19 AM Encoding: 1630 Text IPSECers: I have been traveling a great deal, so I let this issue drop. But I want to revisit the discussion. The last e-mail I recall on the topic was from Paul Lambert, and Paul was voicing support for keyless ICVs (a.k.a. keyless checksums). Before that, Hugo posted a message about attacks on keyless ICVs. Hugo described the following chosen message attack: - Construct a message M = M1 | CS1 | M2, where CS1 is the keyless checksum on M1, and M1 and M2 are arbitrary. The length of M1 | CS1 should be an integral number of blocks. - Give M to the party that's encrypting and authenticating, to obtain C = E (M | CS2), where CS2 is the checksum on M, and E is the encryption function. - In typical modes of encryption, it will be the case that that C = C1 | C2, where C1 = E (M1 | CS1) --- so C1 is a valid message as far as authentication is concerned - Replace C1 with C on the transmission line -- the recipient will accept C1 as authentic I discussed Hugo's attack with Burt Kaliski, and Burt came to the following conclusion: This [attack] works for any kind of checksum, and although it can be thwarted by including the total message length at the beginning of the message, it's an attack cryptographers would like to avoid entirely. Given that we are interested in protecting IP datagrams as well as TCP and UDP protocol data units, we should revisit the keyless ICV discussion because these protocol formats all include payload data lengths. Russ From ipsec-request@ans.net Mon Jun 12 15:54:08 1995 Received: from interlock.ans.net by nis.ans.net with SMTP id AA28000 (5.65c/IDA-1.4.4 for ); Mon, 12 Jun 1995 12:04:13 -0400 Received: by interlock.ans.net id AA44544 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Mon, 12 Jun 1995 11:55:47 -0400 Message-Id: <199506121555.AA44544@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-5); Mon, 12 Jun 1995 11:55:47 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-4); Mon, 12 Jun 1995 11:55:47 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-3); Mon, 12 Jun 1995 11:55:47 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Mon, 12 Jun 1995 11:55:47 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Mon, 12 Jun 1995 11:55:47 -0400 X-Mailer: exmh version 1.5.3 12/28/94 To: IPSEC@ans.net, KARN@QUALCOMM.COM Cc: rja@cs.nrl.navy.mil, paul_lambert@email.mot.com, jis@mit.edu, hugo@watson.ibm.com, pau@watson.ibm.com Subject: Use of signatures vs. encryption (to complement DH in Photuris) In-Reply-To: Your message of "Mon, 05 Jun 1995 09:21:20 EDT." <9506051321.AA47109@gimili.watson.ibm.com> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Date: Mon, 12 Jun 1995 11:54:08 -0400 From: Amir Herzberg Phil, Hugo has proposed in many notes, some already from March, as well as in his presentation in the last IETF, that there are advantages in changing the method of authentication the DH flows in Photuris. The most radical suggestion is that instead of using a signed exchange _after_ the DH messages, Photuris would distribute a key before the DH phase based on public key encryption, and use this key to authenticate the DH messages. I feel that we didn't get a proper response to this (and other) suggestions. While I realise that time is precious and rare, I still expect you to reply to such important suggestions in a timely and reasoned manner. Please do so. As a short reminder, the main advantage of using an encrypted key-exchange before the DH step, instead of authenticating the DH exchange after it's done (using signed messages), is the ability to use the same protocol while skipping the DH exchange, for much higher efficiency. This is esp. relevant to the applications where the protocol is used mainly for authentication (not encryption). Hugo provided a much more detailed discussion of advantages in his notes (and presentation). Please be responsive. We don't care so much for the outcome, as we care for an open discussion and a clear resolution. We are moving rapidly on our implementation, which we hope to ship very soon as a product compatible with as much of the IPSEC standards as possible. While our plan is to later adjust the product to the final standards, we do want to make it as close to the standards as possible. We cannot do this if standards are developed in a closed circle, without active discussion and responses. Best, Amir Herzberg From ipsec-request@ans.net Mon Jun 12 16:40:43 1995 Received: from interlock.ans.net by nis.ans.net with SMTP id AA26761 (5.65c/IDA-1.4.4 for ); Mon, 12 Jun 1995 20:46:09 -0400 Received: by interlock.ans.net id AA30858 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Mon, 12 Jun 1995 20:42:29 -0400 Message-Id: <199506130042.AA30858@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Mon, 12 Jun 1995 20:42:29 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Mon, 12 Jun 1995 20:42:29 -0400 Date: Mon, 12 Jun 95 20:40:43 EDT From: hugo@watson.ibm.com To: KARN@QUALCOMM.COM Cc: IPSEC@ans.net Subject: Status of Photuris Phil, Stockholm is approaching and we have not heard about the developments with Photuris since Danvers. I would like to know the status of the following important issues on which I have had objections and/or recommendations. 1) The DH key (or "session key" SK) must not be signed. Signing SK is unnecessary and, even worst, it is insecure. (See my note of April 12) 2) Encryption of the signature messages is needed for privacy (anonymity). However, it is *not* the right solution for proving possession of the DH key. (The latter is needed to avoid some of the attacks described in the Diffie-Van Oorschot-Wiener paper). A right (and necessary!) solution is to have, in addition of the signature, a MAC (message authentication code, e.g., key-ed MD5) keyed with the DH key and applied to the same information that the signature is applied to (or to the signature itself). In particular, the MAC must be mandated even if the signature is encrypted for privacy (notice that this is a change relative to the original STS protocol). (See my note of April 12). 3) A fast re-key mechanism is to be provided for key refreshment based on symmetric key techniques (as opposed to DH and/or PK techniques). This is to be done by refreshing the key by means similar to those implied in the draft (page 20). However, the necessary nonces for freshness guarantee should be provided explicitly (e.g., by replacing the DH-exponent fields of the DH-exchange message with a fresh nonce). SAID's are not to be used for this purpose. Cookies can be used (since cookies must be unpredictable by definition), however, I would still recommend using special purpose nonces, to avoid the double functionality of cookies against denial of service attacks and nonces (in particular, cookies may be unncessary if the parties already share a previous key since then verifying a MAC is very fast, actually as fast as generating a cookie). One simple and secure solution to this fast re-key is presented in the IKMP draft (Usenix conference version also available); this solution is compatible with the basic Photuris format. (See exchange of notes with Phil at end of March). 4) The protocol should support a DH exchange that is authenticated by means of a previously shared key between the parties. This provides for a secure solution in many important scenarios, including the cases of * parties with manually installed long-lived master keys, * parties that get a common key from a key distribution center (a la Kerberos), or * parties that use a previously shared DH key for refresh via a new DH exchange. In these cases, signatures can be replaced MAC w hich is beneficial both for efficiency and privacy. For the purpose of this exchange the basic DH flows of Photuris remain unchanged except that a) signature is omitted b) the MAC field is used to authenticate the information that is otherwise signed, but the MAC is computed using the previously shared key (e.g., the shared Kerberos key, etc). [This is a basic functionality provided by my "Photuris variant" but which is easily adaptable to the basic Photuris. This was described and discussed with Phil in Danvers] 5) The non-interactive key refreshment in page 26 of the draft (re-key message) needs to be eliminated. If there is a good reason to keep it, it needs to be re-designed to avoid replay attacks (e.g., via a shared counter). The way it is designed now it is vulnerable to replay and then insecure. Hugo PS: Hope this time a revised draft will be available well before Stockholm. From ipsec-request@ans.net Fri Jun 16 17:14:01 1995 Received: from interlock.ans.net by nis.ans.net with SMTP id AA33347 (5.65c/IDA-1.4.4 for ); Fri, 16 Jun 1995 13:27:31 -0400 Received: by interlock.ans.net id AA08721 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Fri, 16 Jun 1995 13:18:59 -0400 Message-Id: <199506161718.AA08721@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Fri, 16 Jun 1995 13:18:59 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Fri, 16 Jun 1995 13:18:59 -0400 To: IETF-Announce: ; Cc: ipsec@ans.net From: The IESG Subject: Last Call: Security Architecture for the Internet Protocol to Proposed Standard Date: Fri, 16 Jun 95 13:14:01 -0400 Sender: scoya@CNRI.Reston.VA.US The IESG has received a request from the IP Security Protocol Working Group to consider the followingt documents for the status of Proposed Standard: 1. Security Architecture for the Internet Protocol 2. IP Authentication Header 3. IP Encapsulating Security Payload (ESP) 4. IP Authentication using Keyed MD5 5. The ESP DES-CBC Transform The IESG plans to make a decision in the next few weeks, and solicits final comments on this action. Please send any comments to the iesg@cnri.reston.va.us or ietf@cnri.reston.va.us mailing lists by June 30, 1995. From ipsec-request@ans.net Fri Jun 16 19:56:38 1995 Received: from interlock.ans.net by nis.ans.net with SMTP id AA19193 (5.65c/IDA-1.4.4 for ); Fri, 16 Jun 1995 16:01:59 -0400 Received: by interlock.ans.net id AA39958 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Fri, 16 Jun 1995 15:58:29 -0400 Message-Id: <199506161958.AA39958@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Fri, 16 Jun 1995 15:58:29 -0400 From: Ran Atkinson Date: Fri, 16 Jun 1995 15:56:38 -0400 Reply-To: rja@cs.nrl.navy.mil X-Mailer: Z-Mail (3.0.0 15dec93) To: ipsec@ans.net Subject: editorial bug in IP Auth Hdr spec Content-Type: text/plain; charset=us-ascii Mime-Version: 1.0 Sender: rja@bodhi.cs.nrl.navy.mil Folks, Partly because I'm working on "TCP for IPv6" and partly to sanity check that my specs are readable by folks other than me, Craig Metz is the person working on our Auth Hdr implementation for IPv6. This past week, Craig has been working on IPv6 reassembly code. For those unfamiliar with IPv6, it might be worthwhile to note that there is no intermediate fragmentation in IPv6 because Path MTU Discovery is always used, but end-to-end fragmentation can still occur (e.g. due to naive UDP applications). As part of work on IPv6 reassembly, Craig pointed out that I put a crucial sentence about fragmentation/reassembly in an "IPv4-only" paragraph rather than in an "applies to both IPv4 and IPv6" paragraph where it should have been. I will make this editorial fix prior to going to RFC, but the change is too small to merit bothering the CNRI folks with putting out a revised online I-D. In Section 4 of that I-D, the existing sentence below applies to both IPv4 and IPv6: "Reassembly of fragmented IP packets occurs PRIOR to processing by the local IP Authentication Header implementation." For clarity, Craig suggested (and I agree) that I should also note with a new sentence in the outgoing processing description that: "For outgoing IP datagrams, IP Authentication Header processing always occurs PRIOR to IP packet fragmentation." Ran rja@cs.nrl.navy.mil From ipsec-request@ans.net Sun Jun 18 13:35:08 1995 Received: from interlock.ans.net by nis.ans.net with SMTP id AA30335 (5.65c/IDA-1.4.4 for ); Sun, 18 Jun 1995 09:46:19 -0400 Received: by interlock.ans.net id AA38857 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Sun, 18 Jun 1995 09:35:19 -0400 Message-Id: <199506181335.AA38857@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Sun, 18 Jun 1995 09:35:19 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Sun, 18 Jun 1995 09:35:19 -0400 Date: Sun, 18 Jun 1995 06:35:08 -0700 From: Clifford Neuman To: ids@uow.edu.au, firewalls@greatcircle.com, cat-ietf@mit.edu, ipsec@ans.net, www-security@ns2.rutgers.edu, www-buyinfo@allegra.att.com Subject: CFP: ISOC Symposium on Network and Distributed System Security CALL FOR PAPERS The Internet Society Symposium on Network and Distributed System Security February 22-23, 1996 San Diego Princess Resort, San Diego, California GOAL: The symposium will bring together people who are building hardware and software to provide network and distributed system security services. The symposium is intended for those interested in the practical aspects of network and distributed system security, focusing on actual system design and implementation, rather than theory. We hope to foster the exchange of technical information that will encourage and enable the Internet community to apply, deploy, and advance the state of available security technology. Symposium proceedings will be published by the IEEE Computer Society Press. Topics for the symposium include, but are not limited to, the following: * Design and implementation of communication security services: authentication, integrity, confidentiality, authorization, non-repudiation, and availability. * Design and implementation of security mechanisms, services, and APIs to support communication security services, key management and certification infrastructures, audit, and intrusion detection. * Requirements and designs for securing network information resources and tools -- WorldWide Web (WWW), Gopher, archie, and WAIS. * Requirements and designs for systems supporting electronic commerce -- payment services, fee-for-access, EDI, notary -- endorsement, licensing, bonding, and other forms of assurance. * Design and implementation of measures for controlling network communication -- firewalls, packet filters, application gateways, and user/host authentication schemes. * Requirements and designs for telecommunications security especially for emerging technologies -- very large systems like the Internet, high-speed systems like the gigabit testbeds, wireless systems, and personal communication systems. * Special issues and problems in security architecture, such as interplay between security goals and other goals -- efficiency, reliability, interoperability, resource sharing, and cost. * Integration of security services with system and application security facilities, and application protocols -- including but not limited to message handling, file transport, remote file access, directories, time synchronization, data base management, routing, voice and video multicast, network management, boot services, and mobile computing. GENERAL CHAIR: Jim Ellis, CERT Coordination Center PROGRAM CHAIRS: David Balenson, Trusted Information Systems Clifford Neuman, USC Information Sciences Institute LOCAL ARRANGEMENTS CHAIR: Thomas Hutton, San Diego Supercomputer Center PUBLICATIONS CHAIR: Steve Welke, Institute for Defense Analyses REGISTRATIONS CHAIR: Donna Leggett, Internet Society PROGRAM COMMITTEE: Tom Berson, Anagram Laboratories Matt Bishop, University of California at Davis Doug Engert, Argonne National Laboratory Warwick Ford, Bell Northern Research (Canada) Burt Kaliski, RSA Laboratories Steve Kent, Bolt Beranek and Newman Paul Lambert, Motorola John Linn, OpenVision Technologies Teresa Lunt, Advanced Research Projects Agency Dan Nessett, Sun Microsystems Hilarie Orman, University of Arizona Michael Roe, Cambridge University (UK) Rob Rosenthal, U.S. National Institute of Standards and Technology Avi Rubin, Bellcore Jeff Schiller, Massachusetts Institute of Technology Rob Shirey, Bolt Beranek and Newman Doug Tygar, Carnegie Mellon University Roberto Zamparo, Telia Research (Sweden) SUBMISSIONS: The committee invites technical papers and panel proposals for topics of technical and general interest. Technical papers should be 10-20 pages in length. Panel proposals should be two pages and should describe the topic, identify the panel chair, explain the format of the panel, and list three to four potential panelists. Technical papers will appear in the proceedings. A description of each panel will appear in the proceedings, and may at the discretion of the panel chair, include written position statements from each panelist. Each submission must contain a separate title page with the type of submission (paper or panel), the title or topic, the names of the author(s), organizational affiliation(s), telephone and FAX numbers, postal addresses, Internet electronic mail addresses, and must list a single point of contact if more than one author. The names of authors, affiliations, and other identifying information should appear only on the separate title page. Deadline for paper submission: August 14, 1995 Notification sent to authors by: October 16, 1995 Deadline for camera-ready copy: November 13, 1995 Submissions must be received by 14 August 1995. Submissions should be made via electronic mail. Submissions may be in either of two formats: PostScript or ASCII. If the committee is unable to print a PostScript submission, it will be returned and hardcopy requested. Therefore, PostScript submissions should arrive well before 14 August. If electronic submission is difficult, submissions should be sent via postal mail. All submissions and program related correspondence (only) should be directed to the program chair: Clifford Neuman University of Southern California Information Sciences Institute 4676 Admiralty Way Marina del Rey, California 90292-6695 Phone: +1 (310) 822-1511 FAX: +1 (310) 823-6714 Email: sndss96-submissions@isi.edu Dates, final call for papers, advance program, and registration information will be made available at the URL: http://nii.isi.edu/info/sndss Each submission will be acknowledged by e-mail. If acknowledgment is not received within seven days, please contact the program chair as indicated above. Authors and panelists will be notified of acceptance by 16 October 1995. Instructions for preparing camera-ready copy for the proceedings will be sent at that time. The camera-ready copy must be received by 13 November 1995. From ipsec-request@ans.net Mon Jun 19 03:24:27 1995 Received: from interlock.ans.net by nis.ans.net with SMTP id AA25912 (5.65c/IDA-1.4.4 for ); Sun, 18 Jun 1995 23:29:15 -0400 Received: by interlock.ans.net id AA33915 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Sun, 18 Jun 1995 23:24:31 -0400 Message-Id: <199506190324.AA33915@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Sun, 18 Jun 1995 23:24:31 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Sun, 18 Jun 1995 23:24:31 -0400 Date: Sun, 18 Jun 1995 23:24:27 -0400 (EDT) From: Russell Willis To: ipsec@ans.net Subject: draft-ietf-ipsec-ah-md5-03.txt (complete) ascii (fwd) Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII To the IP Security working group: I've included my comments below regarding : This draft is about as close as you can get to perfect. Unless I missed something, I didn't see any errors in grammar, etc.. Conclusion: Structure and content - check ( fine ). :-) ---Russell--- From ipsec-request@ans.net Mon Jun 19 04:56:23 1995 Received: from interlock.ans.net by nis.ans.net with SMTP id AA19069 (5.65c/IDA-1.4.4 for ); Mon, 19 Jun 1995 00:59:48 -0400 Received: by interlock.ans.net id AA14282 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Mon, 19 Jun 1995 00:56:27 -0400 Message-Id: <199506190456.AA14282@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Mon, 19 Jun 1995 00:56:27 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Mon, 19 Jun 1995 00:56:27 -0400 Date: Mon, 19 Jun 1995 00:56:23 -0400 (EDT) From: Russell Willis To: ipsec@ans.net Subject: draft-ietf-ipsec-esp-01.txt (complete) ascii (fwd) Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII To the IP Security working group: I've included below my comments/suggestions regarding : ------ begin of draft-ietf-ipsec-esp-01.txt -- ascii -- complete ------ Network Working Group Randall Atkinson Internet Draft Naval Research Laboratory draft-ietf-ipsec-esp-01.txt 25 April 1995 IP Encapsulating Security Payload (ESP) STATUS OF THIS MEMO << Should probably add a blank line after the heading. >> 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 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 "work in progress". This particular Internet Draft is a product of the IETF's IPng and IPsec working groups. It is intended that a future version of this draft be submitted to the IPng Area Directors and the IESG for possible publication as a standards-track protocol. 0. ABSTRACT ^ Since when is '0' used as a heading number? This document describes the IP Encapsulating Security Payload (ESP). ESP is a mechanism for providing integrity and confidentiality to IP datagrams. In some circumstances it can also provide authentication to IP datagrams. The mechanism works with both IPv4 and IPv6. This document also describes the mandatory DES CBC encryption transform for use with ESP. 1. INTRODUCTION ESP is a mechanism for providing integrity and confidentiality to IP datagrams. It may also provide authentication, depending on which algorithm and algorithm mode are used. Non-repudiation and protection from traffic analysis are not provided by ESP. The IP Authentication Header (AH) might provide non-repudiation if used with certain authentication algorithms. [Atk95b] The IP Authentication Header may ^^^^^^^^^^ Place the period after the reference to avoid confusion. be used in conjunction with ESP to provide authentication. Users desiring integrity and authentication without confidentiality should use the IP Authentication Header (AH) instead of ESP. This document Atkinson [Page 1] Internet Draft Encapsulating Security Payload 25 April 1995 assumes that the reader is familiar with the related document "IP Security Architecture", which defines the overall Internet-layer security architecture for IPv4 and IPv6 and provides important background for this specification. [Atk95a] ^^^^^^^^^^ Place period after reference. 1.1 Overview The IP Encapsulating Security Payload (ESP) seeks to provide confidentiality and integrity by encrypting data to be protected and placing the encrypted data in the data portion of the IP Encapsulating Security Payload. Depending on the user's security requirements, this mechanism may be used to encrypt either a transport-layer segment (e.g. TCP, UDP, ICMP, IGMP) or an entire IP datagram. Encapsulating the protected data is necessary to provide confidentiality for the entire original datagram. Use of this specification will increase the IP protocol processing costs in participating systems and will also increase the communications latency. The increased latency is primarily due to the encryption and decryption required for each IP datagram containing an Encapsulating Security Payload. In order for ESP to work properly without changing the entire Internet infrastructure (e.g. non-participating systems), the original IP datagram is placed in the encrypted portion of the Encapsulating Security Payload and that entire ESP frame is placed within an ^^ Try 'a' instead. datagram having unencrypted IP headers. The information in the unencrypted IP headers is used to route the secure datagram from origin to destination. An unencrypted IP Routing Header might be included between the IP Header and the Encapsulating Security Payload. In the case of IP, an IP Authentication Header may be present both as an header of the unencrypted IP packet and also as a header within the encrypted IP packet. In such a case, the unencrypted IPv6 Authentication Header is primarily used to provide protection for the contents of the unencrypted IP headers and the encrypted Authentication Header is used to provide authentication for the encrypted IP packet. This is discussed in more detail later in this document. The encapsulating security payload is structured a bit differently ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ For consistency, either capitalize first letters or place quotes around each occurrence of this phrase. than other IP payloads. The first component of the ESP payload consist of the unencrypted field(s) of the payload. The second ^^^^^^^ Should be 'consists'. component consists of encrypted data. The field(s) of the unencrypted ESP header inform the intended receiver how to properly decrypt and process the encrypted data. The encrypted data component includes protected fields for the security protocol and also the encrypted encapsulated IP datagram. Atkinson [Page 2] Internet Draft Encapsulating Security Payload 25 April 1995 The concept of a "Security Association" is fundamental to ESP. It is described in detail in the compaion document "Security Architecture ^^^^^^^^ Should be 'companion'. for the Internet Protocol" which is incorporated here by reference. [Atk95a] Implementers should read that document before ^^^^^^^^^^ Period after reference. reading this one. 1.2 Requirements Terminology In this document, the words that are used to define the significance of each particular requirement are usually capitalised. These words are: - MUST This word or the adjective "REQUIRED" means that the item is an absolute requirement of the specification. - SHOULD This word or the adjective "RECOMMENDED" means that there might exist valid reasons in particular circumstances to ignore this item, but the full implications should be understood and the case carefully weighed before taking a different course. - MAY This word or the adjective "OPTIONAL" means that this item is truly optional. One vendor might choose to include the item because a particular marketplace requires it or because it enhances the product, for example; another vendor may omit the same item. 2. KEY MANAGEMENT Key management is an important part of the IP security architecture. However, a specific key management protocol is not included in this specification because of a long history in the public literature of subtle flaws in key management algorithms and protocols. IP tries to decouple the key management mechanisms from the security protocol mechanisms. The only coupling between the key management protocol and the security protocol is with the Security Association Identifier (SPI), which is described in more detail below. This ^^^^^ ?? decoupling permits several different key management mechanisms to be used. More importantly, it permits the key management protocol to be changed or corrected without unduly impacting the security protocol implementations. Thus, a key management protocol for IP is not specifed within this draft. The IP Security Architecture describes key management in more detail and specifies the key management requirements for IP. Those key management requirements are Atkinson [Page 3] Internet Draft Encapsulating Security Payload 25 April 1995 incorporated here by reference. [Atk95a] ^^^^^^^^^^ Period after reference. The key management mechanism is used to negotiate a number of parameters for each security association, including not only the keys but other information (e.g. the cryptographic algorithms and modes, security classification level if any) used by the communicating ^^^^^^^^ ^ Place 'and' Place ',' here. before this word. parties. The key management protocol implementation usually creates and maintains a logical table containing the several parameters for each current security association. An ESP implementation normally needs to read that security parameter table to determine how to process each datagram containing an ESP (e.g. which algorithm/mode and key to use). 3. ENCAPSULATING SECURITY PAYLOAD SYNTAX The Encapsulating Security Payload (ESP) may appear anywhere after the IP header and before the final transport-layer protocol. The Internet Assigned Numbers Authority has assigned Protocol Number 50 to IP ESP. [STD-2] The header immediately preceding an ESP header will ^^^^^^^^^ Place period after reference. always contain the value 50 in its Next Header field. ESP consists of an unencrypted header followed by encrypted data. The encrypted data includes both the protected ESP header fields and the protected user data, which is either an entire IP datagram or an upper-layer protocol frame (e.g. TCP or UDP). A high-level diagram of a secure IP datagram follows. |<-- Unencrypted -->|<---- Encrypted ------>| +-------------+--------------------+------------+---------------------+ | IP Header | Other IP Headers | ESP Header | encrypted data | +-------------+--------------------+------------+---------------------+ A more detailed diagram of the ESP Header follows below. +-------------+--------------------+------------+---------------------+ | Security Association Identifier (SPI), 32 bits | +=============+====================+============+=====================+ | Opaque Transform Data, variable length | +-------------+--------------------+------------+---------------------+ Encryption and authentication algorithms, and the precise format of the Opaque Transform Data associated with them are known as "transforms". The ESP format is designed to support new transforms in the future to support new or additional cryptographic algorithms. The transforms are specified by themselves rather than in the main body of this specification. The mandatory transform for use with IP is defined in a separate document [MS95]. Other optional transforms exist in other separate specifications and additional transforms might be defined in the future. Atkinson [Page 4] Internet Draft Encapsulating Security Payload 25 April 1995 3.1 Fields of the Encapsulating Security Payload This is a 32-bit pseudo-random value identifying the security association for this datagram. If no security association has been established, the value of this field shall be 0x00000000. An SPI is similar to the SAID used in other security protocols. The name has been changed because the semantics used here are not exactly the same as those used in other security protocols. The set of SPI values in the range 0x00000001 though 0x000000FF are reserved to the Internet Assigned Numbers Authority (IANA) for future use. A reserved SPI value will not normally be assigned by IANA unless the use of that particular assigned SPI value is openly specified in an RFC. The SPI is the only mandatory transform-independent field. Particular transforms may have other fields unique to the transform. Transforms are not specified in this document. 3.2 Security Labeling with ESP The encrypted IP datagram need not and does not normally contain any explicit Security Label because the SPI indicates the sensitivity level. This is an improvement over the current practices with IPv4 where an explicit Sensitivity Label is normally used with Compartmented Mode Workstations and other systems requiring Security Labels. [Ken91] [DIA] In some situations, users MAY choose ^^^^^^^^^^^^^^^ Period after references. to carry explicit labels (for example, IPSO labels as defined by RFC-1108 might be used with IPv4) in addition to using the implicit labels provided by ESP. Explicit label options could be defined for use with IPv6 (e.g. using the IPv6 End-to-End Options Header or the IPv6 Hop-by-Hop Options Header). Implementations MAY support explicit labels in addition to implicit labels, but implementations are not required to support explicit labels. Implementations of ESP in systems claiming to provide multi-level security MUST support implicit labels. 4. ENCAPSULATING SECURITY PROTOCOL PROCESSING << Blank line after heading. >> This section describes the steps taken when ESP is in use between two communicating parties. Multicast is different from unicast only in the area of key management (See the definition of the SPI, above, for more detail on this). There are two modes of use for ESP. The first mode, which is called "Tunnel-mode", encapsulates an entire IP datagram inside ESP. The second mode, which is called "Transport-Mode", encapsulates a transport-layer (e.g. UDP or TCP) frame inside ESP. The term "Transport-mode" must not be misconstrued as restricting its use to TCP and UDP. For example, an ICMP message MAY be sent either using the "Transport-mode" or the Atkinson [Page 5] Internet Draft Encapsulating Security Payload 25 April 1995 "IP-mode" depending upon circumstance. This section describes ^^^^^^^^^^^^ Should be 'circumstances'. protocol processing for each of these two modes. 4.1 ESP in Tunnel-mode The sender takes the original IP datagram, encapsulates it into the ESP, uses at least the sending userid and Destination Address as data to locate the correct Security Association, and then applies the appropriate encryption transform. If host-oriented keying is in use, then all sending userids on a given system will have the same Security Association for a given Destination Address. If no key has been established, then the key management mechanism is used to establish a ^ Should be 'an'. encryption key for this communications session prior to the use of ESP. The (now encrypted) ESP is then encapsulated in a cleartext IP datagram as the last payload. If strict red/black separation is being enforced, then the addressing and other information in the cleartext IP headers and optional payloads MAY be different from the values contained in the (now encrypted and encapsulated) original datagram. The receiver strips off the cleartext IP header and cleartext optional IP payloads (if any) and discards them. It then uses the combination of Destination Address and SPI value to locate the correct decryption key to use for this packet. Then, it decrypts the ESP using the session key that has been established for this traffic. If no valid Security Association exists for this session (for example, the receiver has no key), the receiver MUST discard the encrypted ESP and the failure MUST be recorded in the system log or audit log. This system log or audit log entry SHOULD include the SPI value, date/time, cleartext Sending Address, cleartext Destination Address, and the cleartext Flow ID. The log entry MAY also include other identifying data. The receiver might not wish to react by immediately informing the sender of this failure because of the strong potential for easy-to-exploit denial of service attacks. If decryption succeeds, the original IP datagram is then removed from the (now decrypted) ESP. This original IP datagram is then processed as per the normal IP protocol specification. In the case of system claiming to provide multilevel security (for example, a B1 or Compartmented Mode Workstation) additional appropriate mandatory access controls MUST be applied based on the security level of the receiving process and the security level associated with this Security Association. If those mandatory access controls fail, then the packet SHOULD be discarded and the failure SHOULD be logged using implementation-specific procedures. Atkinson [Page 6] Internet Draft Encapsulating Security Payload 25 April 1995 4.2 ESP in Transport-mode The sender takes the original UDP or TCP or ICMP frame, encapsulates it into the ESP, uses at least the sending userid and Destination Address to locate the appropriate Security Association, and then applies the appropriate encryption transform. If host-oriented keying is in use, then all sending userids on a given system will have the same Security Association for a given Destination Address. If no key has been established, then the key management mechanism is used to establish a encryption key for this communications session prior to the encryption. The (now encrypted) ESP is then encapsulated as the last payload of a cleartext IP datagram. The receiver processes the cleartext IP header and cleartext optional IP headers (if any) and temporarily stores pertinent information (e.g. source and destination addresses, Flow ID, Routing Header). It then decrypts the ESP using the session key that has been established for this traffic, using the combination of the destination address and the packet's Security Association Identifier (SPI) to locate the correct key. If no key exists for this session or the attempt to decrypt fails, the encrypted ESP MUST be discarded and the failure MUST be recorded in the system log or audit log. If such a failure occurs, the recorded log data SHOULD include the SPI value, date/time received, clear-text Sending Address, clear-text Destination Address, and the Flow ID. The log data MAY also include other information about the failed packet. If decryption does not work properly for some reason, then the resulting data will not be parsable by the implementation's protocol engine. Hence, failed decryption is detectable in the case that cryptography is used with ESP. If decryption succeeds, the original UDP or TCP frame is removed from the (now decrypted) ESP. The information from the cleartext IP header and the now decrypted UDP or TCP header is jointly used to determine which application the data should be sent to. The data is then sent along to the appropriate application as normally per IP protocol specification. In the case of a system claiming to provide multilevel security (for example, a B1 or Compartmented Mode Workstation), additional Mandatory Access Controls MUST be applied based on the security level of the receiving process and the security level of the received packet's Security Association. 4.3. Authentication Some transforms provide authentication as well as confidentiality and integrity. When such a transform is not used, then the Authentication Header might be used in conjunction with the Atkinson [Page 7] Internet Draft Encapsulating Security Payload 25 April 1995 Encapsulating Security Payload. There are two different approaches to using the Authentication Header with ESP, depending on which data is to be authenticated. The location of the Authentication Header makes it clear which set of data is being authenticated. In the first usage, the entire received datagram is authenticated, including both the encrypted and unencrypted portions, while only the data sent after the ESP Header is confidential. In this usage, the sender first applies ESP to the data being protected. Then the other plaintext IP headers are prepended to the ESP header and its now encrypted data. Finally, the IP Authentication Header is calculated over the resulting datagram according to the normal method. Upon receipt, the receiver first verifies the authenticity of the entire datagram using the normal IP Authentication Header process. Then if authentication succeeds, decryption using the normal IP ESP process occurs. If decryption is successful, then the resulting data is passed up to the upper layer. If the authentication process were to be applied only to the data protected by IP ESP and ESP were encapsulating an entire IP datagram, then the IP Authentication Header would be placed normally within that protected datagram. However, if the data encapsulated by ESP were less than an entire IP datagram, then the IP Authentication Header would be placed as the first header inside the encrypted ESP payload and would be calculated across the data encrypted by ESP. If the Authentication Header is encapsulated within the ESP header, and both headers have specific security classification levels associated with them, and the two security classification levels are not identical, then an error has occurred. That error SHOULD be recorded in the system log or audit log using the procedures described previously. It is not necessarily an error for an Authentication Header located outside of the ESP header to have a different security classification level than the ESP header's classification level. This might be valid because the cleartext IP headers might have a different classification level when the data has been encrypted using ESP. 5. CONFORMANCE REQUIREMENTS << Blank line after heading. >> Implementations that claim conformance or compliance with this specification MUST fully implement the header described here, MUST support manual key distribution with this header, MUST comply with all requirements of the "Security Architecture for the Internet Protocol" [Atk95a], and MUST support the use of DES CBC as specified in the companion document entitled "The ESP DES-CBC Transform" [MS95]. Implementers MAY also implement other ESP transforms. Implementers should consult the most recent version of the "IAB Official Standards" RFC for further guidance on the status of this document. Atkinson [Page 8] Internet Draft Encapsulating Security Payload 25 April 1995 6. SECURITY CONSIDERATIONS This entire draft discusses a security mechanism for use with IP. This mechanism is not a panacea, but it does provide an important component useful in creating a secure internetwork. Cryptographic transforms for ESP which use a block-chaining algorithm and lack a strong integrity mechanism are vulnerable to a cut-and-paste attack described by Bellovin and should not be used unless the Authentication Header is always present with packets using that ESP transform. [Bel95] ^^^^^^^^^ Period after reference. Users need to understand that the quality of the security provided by this specification depends completely on the strength of whichever encryption algorithm that has been implemented, the correctness of ^^^^ Omit this word. that algorithm's implementation, upon the security of the key management mechanism and its implementation, the strength of the key [CN94][Sch94, p233] and upon the correctness of the ESP and IP ^ Need comma here. implementations in all of the participating systems. If any of these assumptions do not hold, then little or no real security will be provided to the user. Use of high assurance development techniques is recommended for the IP Encapsulating Security Payload. Users seeking protection from traffic analysis might consider the use of appropriate link encryption. Description and specification of link encryption is outside the scope of this note. If user-oriented keying is not in use, then the algorithm in use should not be an algorithm vulnerable to any kind of Chosen Plaintext attack. Chosen Plaintext attacks on DES are described in [BS93] and [Mit94]. Use of user-oriented keying is recommended in order to ^^^^^^^ Should probably be '[MIT94]'. preclude any sort of Chosen Plaintext attack and to generally make cryptanalysis more difficult. Implementations SHOULD support user-oriented keying as is described in the IP Security Architecture. [Atk95a] ACKNOWLEDGEMENTS << Blank line after heading. >> This document benefited greatly from work done by Bill Simpson, Perry Metzger, and Phil Karn to make general the approach originally defined by the author for SIP, SIPP, and finally IPv6. Many of the concepts here are derived from or were influenced by the US Government's SP3 security protocol specification, the ISO/IEC's NLSP specification, or from the proposed swIPe security protocol. [SDNS89, ISO92a, IB93, IBK93, ISO92b] The use of DES for confidentiality is closely modeled on the work done for the Atkinson [Page 9] Internet Draft Encapsulating Security Payload 25 April 1995 SNMPv2. [GM93] Steve Bellovin, Steve Deering, Dave Mihelcic, and ^^^^^^^^ Period after reference. Hilarie Orman provided solid critiques of early versions of this draft. REFERENCES << Blank line after heading. >> [Atk95a] Randall J. Atkinson, IP Security Architecture, Internet Draft, draft-ietf-ipsec-arch-01.txt, 25 April 1995. [Atk95b] Randall J. Atkinson, IP Authentication Header, Internet Draft, draft-ietf-ipsec-auth-01.txt, 25 April 1995. [Bel89] Steven M. Bellovin, "Security Problems in the TCP/IP Protocol Suite", ACM Computer Communications Review, Vol. 19, No. 2, March 1989. [Bel95] Steven M. Bellovin, Presentation at IP Security Working Group Meeting, Proceedings of the 32nd Internet Engineering Task Force, March 1995, Internet Engineering Task Force, Danvers, MA. [BS93] Eli Biham and Adi Shamir, "Differential Cryptanalysis of the Data Encryption Standard", Springer-Verlag, New York, NY, 1993. [CN94] John M. Carroll & Sri Nudiati, "On Weak Keys and Weak Data: Foiling the Two Nemeses", Cryptologia, Vol. 18, No. 23, July 1994. pp. 253-280 [CERT95] Computer Emergency Response Team (CERT), "IP Spoofing Attacks and Hijacked Terminal Connections", CA-95:01, January 1995. Available via anonymous ftp from info.cert.org. [DIA] US Defense Intelligence Agency (DIA), "Compartmented Mode Workstation Specification", Technical Report DDS-2600-6243-87. [GM93] James Galvin & Keith McCloghrie, Security Protocols for Version 2 of the Simple Network Management Protocol (SNMPv2), RFC-1446, DDN Network Information Center, April 1993. [Hin94] Robert Hinden (Editor), IP Specification, Internet Draft, draft-hinden-ipng-IP-spec-00.txt, October 1994. [IB93] John Ioannidis & Matt Blaze, "Architecture and Implementation of Network-layer Security Under Unix", Proceedings of the USENIX Security Symposium, Santa Clara, CA, October 1993. [IBK93] John Ioannidis, Matt Blaze, & Phil Karn, "swIPe: Network-Layer Security for IP", presentation at the Spring 1993 IETF Meeting, Columbus, Ohio. Atkinson [Page 10] Internet Draft Encapsulating Security Payload 25 April 1995 [ISO92a] ISO/IEC JTC1/SC6, Network Layer Security Protocol, ISO-IEC DIS 11577, International Standards Organisation, Geneva, Switzerland, 29 November 1992. [ISO92b] ISO/IEC JTC1/SC6, Network Layer Security Protocol, ISO-IEC DIS 11577, Section 13.4.1, page 33, International Standards Organisation, Geneva, Switzerland, 29 November 1992. [Ken91] Steve Kent, "US DoD Security Options for the Internet Protocol (IPSO)", RFC-1108, DDN Network Information Center, November 1991. [Mit94] Matsui, M., "Linear Cryptanalysis method for DES Cipher", Proceedings of Eurocrypt '93, Berlin, Springer-Verlag, 1994. [MS95] Perry Metzger & W.A. Simpson, "The ESP DES-CBC Transform with MD5", Work in Progress, April 1995. [NIST77] US National Bureau of Standards, "Data Encryption Standard", Federal Information Processing Standard (FIPS) Publication 46, January 1977. [NIST80] US National Bureau of Standards, "DES Modes of Operation" Federal Information Processing Standard (FIPS) Publication 81, December 1980. [NIST81] US National Bureau of Standards, "Guidelines for Implementing and Using the Data Encryption Standard", Federal Information Processing Standard (FIPS) Publication 74, April 1981. [NIST88] US National Bureau of Standards, "Data Encryption Standard", Federal Information Processing Standard (FIPS) Publication 46-1, January 1988. [STD-2] J. Reynolds and J. Postel, "Assigned Numbers", STD-2, DDN Network Information Center, 20 October 1994. [Sch94] Bruce Schneier, Applied Cryptography, John Wiley & Sons, New York, NY, 1994. ISBN 0-471-59756-2 [SDNS89] SDNS Secure Data Network System, Security Protocol 3, SP3, Document SDN.301, Revision 1.5, 15 May 1989, as published in NIST Publication NIST-IR-90-4250, February 1990. DISCLAIMER The views and specification here are those of the author and are not necessarily those of his employer. The Naval Research Laboratory has not passed judgement on the merits, if any, of this work. The author Atkinson [Page 11] Internet Draft Encapsulating Security Payload 25 April 1995 and his employer specifically disclaim responsibility for any problems arising from correct or incorrect implementation or use of this specification. AUTHOR INFORMATION Randall Atkinson Information Technology Division Naval Research Laboratory Washington, DC 20375-5320 USA Telephone: (202) 404-7090 Fax: (202) 404-7942 Atkinson [Page 12] ------ end of draft-ietf-ipsec-esp-01.txt -- ascii -- complete ------ ---Russell--- From ipsec-request@ans.net Mon Jun 19 09:21:29 1995 Received: from interlock.ans.net by nis.ans.net with SMTP id AA16384 (5.65c/IDA-1.4.4 for ); Mon, 19 Jun 1995 06:35:08 -0400 Received: by interlock.ans.net id AA38862 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Mon, 19 Jun 1995 06:31:19 -0400 Message-Id: <199506191031.AA38862@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-3); Mon, 19 Jun 1995 06:31:19 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Mon, 19 Jun 1995 06:31:19 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Mon, 19 Jun 1995 06:31:19 -0400 Date: Mon, 19 Jun 95 12:21:29 +0300 From: kate@digiw.fi (Kate Marika Alhola) To: ipsec@ans.net In-Reply-To: Russell Willis's message of Mon, 19 Jun 1995 00:56:23 -0400 (EDT) <199506190456.AA14282@interlock.ans.net> Subject: Re: draft-ietf-ipsec-esp-01.txt (complete) ascii (fwd) One question about ESP and transport-mode sending encrypted datagrams. The ESP header contains only SPI, that is used to describe, what key is used to encrypt payload, the IP protocol id is ESP ( 50 ). The rest of ESP datatgram is opaque data. The Tunnel mode is clear, all IP datagram is in encrypted payload, including IP protocol ID, that descrips, what protocol (TCP/IP/ICMP) is used, but how this is done in transport mode ? The IP prptocol ID is now ESP, and only TCP/UDP/ICMP datagram is in the payload, where is protocol ID of the payload ? Kate +=============================================================+ ! Kate Marika Alhola Internet Technologies International Oy ! ! kate@digiw.fi Phone +358 49 740701 ! ! kate@nic.funet.fi http://nic.funet.fi/~kate/ ! +=============================================================+ From ipsec-request@ans.net Mon Jun 19 18:45:48 1995 Received: from interlock.ans.net by nis.ans.net with SMTP id AA19191 (5.65c/IDA-1.4.4 for ); Mon, 19 Jun 1995 15:07:38 -0400 Received: by interlock.ans.net id AA22235 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Mon, 19 Jun 1995 15:00:41 -0400 Message-Id: <199506191900.AA22235@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-4); Mon, 19 Jun 1995 15:00:41 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-3); Mon, 19 Jun 1995 15:00:41 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Mon, 19 Jun 1995 15:00:41 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Mon, 19 Jun 1995 15:00:41 -0400 To: kate@digiw.fi (Kate Marika Alhola) Cc: ipsec@ans.net Subject: Re: draft-ietf-ipsec-esp-01.txt (complete) ascii (fwd) In-Reply-To: Your message of "Mon, 19 Jun 1995 12:21:29 +0300." <199506191031.AA38862@interlock.ans.net> Reply-To: perry@imsi.com X-Reposting-Policy: redistribute only with permission Date: Mon, 19 Jun 1995 14:45:48 -0400 From: "Perry E. Metzger" Kate Marika Alhola writes: > One question about ESP and transport-mode sending encrypted datagrams. > The ESP header contains only SPI, that is used to describe, what key is > used to encrypt payload, the IP protocol id is ESP ( 50 ). The rest > of ESP datatgram is opaque data. > > The Tunnel mode is clear, all IP datagram is in encrypted payload, including > IP protocol ID, that descrips, what protocol (TCP/IP/ICMP) is used, > but how this is done in transport mode ? The IP prptocol ID is now ESP, > and only TCP/UDP/ICMP datagram is in the payload, where is protocol > ID of the payload ? The protocol ID of the ultimate payload is contained inside the opaqued region. Its precise location is described in the documents for each security transform. Perry From ipsec-request@ans.net Mon Jun 19 19:24:42 1995 Received: from interlock.ans.net by nis.ans.net with SMTP id AA28954 (5.65c/IDA-1.4.4 for ); Mon, 19 Jun 1995 15:32:51 -0400 Received: by interlock.ans.net id AA22497 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Mon, 19 Jun 1995 15:29:04 -0400 Message-Id: <199506191929.AA22497@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-4); Mon, 19 Jun 1995 15:29:04 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-3); Mon, 19 Jun 1995 15:29:04 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Mon, 19 Jun 1995 15:29:04 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Mon, 19 Jun 1995 15:29:04 -0400 From: Marcus J Ranum Subject: ipsec@ans.net-request seems to be unmonitored?? To: ipsec@ans.net Date: Mon, 19 Jun 1995 15:24:42 -0400 (EDT) Organization: Information Works! Inc, Baltimore, MD Phone: 410-889-8569 Coredump: Infocalypse Now!!! X-Mailer: ELM [version 2.4 PL24] Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Content-Length: 338 I've sent repeated mail to ipsec-request@ans.net asking to take me off this list. No luck. So I must do the gauche thing and LOUDLY beg to the whole list that whoever owns this PLEASE take me off. Or if you know the Email address of someone who has control over the list, please let me know it so I can get off the list. Thanks, mjr. From ipsec-request@ans.net Tue Jun 20 11:06:38 1995 Received: from interlock.ans.net by nis.ans.net with SMTP id AA05086 (5.65c/IDA-1.4.4 for ); Tue, 20 Jun 1995 07:13:52 -0400 Received: by interlock.ans.net id AA48945 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Tue, 20 Jun 1995 07:07:06 -0400 Message-Id: <199506201107.AA48945@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-4); Tue, 20 Jun 1995 07:07:06 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-3); Tue, 20 Jun 1995 07:07:06 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Tue, 20 Jun 1995 07:07:06 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Tue, 20 Jun 1995 07:07:06 -0400 X-Sender: t3125rm@clncrdv1.is.chrysler.com X-Mailer: Windows Eudora Version 2.1.1b4 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Date: Tue, 20 Jun 1995 07:06:38 -0400 To: Marcus J Ranum , ipsec@ans.net From: Robert Moskowitz Subject: Re: ipsec@ans.net-request seems to be unmonitored?? At 03:24 PM 6/19/95 -0400, Marcus J Ranum wrote: > I've sent repeated mail to ipsec-request@ans.net asking to >take me off this list. No luck. So I must do the gauche thing and >LOUDLY beg to the whole list that whoever owns this PLEASE take >me off. Or if you know the Email address of someone who has control >over the list, please let me know it so I can get off the list. Marcus, What is TIS's (or your) position on IPSP. Will this get implemented or does the 'real' world already have an interop alternative. This is VERY important for a trade group that I serve as main technician to. Also, what do you know of Cylink's plans to create their own IP security standard? Robert Moskowitz Chrysler Corporation (810) 758-8212 From ipsec-request@ans.net Tue Jun 20 13:24:39 1995 Received: from interlock.ans.net by nis.ans.net with SMTP id AA16388 (5.65c/IDA-1.4.4 for ); Tue, 20 Jun 1995 09:31:45 -0400 Received: by interlock.ans.net id AA65913 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Tue, 20 Jun 1995 09:25:22 -0400 Message-Id: <199506201325.AA65913@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-4); Tue, 20 Jun 1995 09:25:22 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-3); Tue, 20 Jun 1995 09:25:22 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Tue, 20 Jun 1995 09:25:22 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Tue, 20 Jun 1995 09:25:22 -0400 X-Sender: t3125rm@clncrdv1.is.chrysler.com X-Mailer: Windows Eudora Version 2.1.1b4 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Date: Tue, 20 Jun 1995 09:24:39 -0400 To: Marcus J Ranum , ipsec@ans.net From: Robert Moskowitz Subject: Re: ipsec@ans.net-request seems to be unmonitored?? At 07:06 AM 6/20/95 -0400, Robert Moskowitz wrote: >At 03:24 PM 6/19/95 -0400, Marcus J Ranum wrote: >> I've sent repeated mail to ipsec-request@ans.net asking to Whoops so much for privacy on a security list! Robert Moskowitz Chrysler Corporation (810) 758-8212 From ipsec-request@ans.net Wed Jun 21 02:46:38 1995 Received: from interlock.ans.net by nis.ans.net with SMTP id AA27955 (5.65c/IDA-1.4.4 for ); Tue, 20 Jun 1995 22:55:33 -0400 Received: by interlock.ans.net id AA31498 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Tue, 20 Jun 1995 22:49:59 -0400 Message-Id: <199506210249.AA31498@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-4); Tue, 20 Jun 1995 22:49:59 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-3); Tue, 20 Jun 1995 22:49:59 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Tue, 20 Jun 1995 22:49:59 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Tue, 20 Jun 1995 22:49:59 -0400 From: Marcus J Ranum Subject: Moskowitz' mail To: ipsec@ans.net Date: Tue, 20 Jun 1995 22:46:38 -0400 (EDT) Organization: Information Works! Inc, Baltimore, MD Phone: 410-889-8569 Coredump: Infocalypse Now!!! X-Mailer: ELM [version 2.4 PL24] Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Content-Length: 2025 Robert Moskowitz writes: >Marcus, > >What is TIS's (or your) position on IPSP. Will this get implemented or does >the 'real' world already have an interop alternative. I need to specify that nowaday's Marcus' position and TIS' position may no longer be the same thing. :) We've parted company quite amiably but I can no longer speak for TIS in any way, shape, or form. I believe (my personal opinion), however, that IPSP will be what everyone will likely hew to when the standards bodies finally get something relevant out the door. At an open discussion today with a number of firewall vendors, the question of standardizing encryption was raised and I was interested (and grimly amused/pained) that nobody seemed to feel that IETF's work was going to produce near-term relevant results. I caught myself sticking up for IETF (since the alternatives are worse) by encouraging people to at least look hard at swIPe before rolling their own, and that way there'd be some kind of evolutionary path. I think a lot of firewalls out there are based on something swIPe-like and if IPSP ever happens and IPV6 ever happens then they'll probably cut over if unencumbered and commercially useable/high-quality versions of IPSP are available. >Also, what do you know of Cylink's plans to create their own IP security >standard? All I know is that they have one. :) Since the standards process has proven ineffective, and vendor lobbyists on standards working groups have shown that they can easily drag IETF's efforts into increasing irrelevance, I suspect a number of vendors are seeing an opportunity to try to grab market share with de facto standards. How well it will work remains to be seen, but it is certainly hard to lose against something that's not available, when you have a customer demand that you can meet today. mjr. [Obviously, since I've just loudly said some harsh truths, these are my opinions only. If you don't like them, you can complain to the president of Information Works! directly at mjr@iwi.com] From ipsec-request@ans.net Wed Jun 21 09:43:38 1995 Received: from interlock.ans.net by nis.ans.net with SMTP id AA28999 (5.65c/IDA-1.4.4 for ); Wed, 21 Jun 1995 13:49:25 -0400 Received: by interlock.ans.net id AA41701 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Wed, 21 Jun 1995 13:43:44 -0400 Message-Id: <199506211743.AA41701@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Wed, 21 Jun 1995 13:43:44 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Wed, 21 Jun 1995 13:43:44 -0400 Date: Wed, 21 Jun 95 13:43:38 EDT From: Robert Glenn To: ipsec@ans.net Subject: Implementation question Shouldn't the SPI be sent in network order as well as the other fields that were specifically mentioned (IV, DES Blocks)? Thanks, Rob G. glenn@snad.ncsl.nist.gov From ipsec-request@ans.net Wed Jun 21 18:29:56 1995 Received: from interlock.ans.net by nis.ans.net with SMTP id AA24116 (5.65c/IDA-1.4.4 for ); Wed, 21 Jun 1995 14:35:18 -0400 Received: by interlock.ans.net id AA54193 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Wed, 21 Jun 1995 14:30:28 -0400 Message-Id: <199506211830.AA54193@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-4); Wed, 21 Jun 1995 14:30:28 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-3); Wed, 21 Jun 1995 14:30:28 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Wed, 21 Jun 1995 14:30:28 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Wed, 21 Jun 1995 14:30:28 -0400 To: Robert Glenn Cc: ipsec@ans.net Subject: Re: Implementation question In-Reply-To: Your message of "Wed, 21 Jun 1995 13:43:38 EDT." <199506211743.AA41701@interlock.ans.net> Reply-To: perry@imsi.com X-Reposting-Policy: redistribute only with permission Date: Wed, 21 Jun 1995 14:29:56 -0400 From: "Perry E. Metzger" Robert Glenn writes: > Shouldn't the SPI be sent in network order as well as the other > fields that were specifically mentioned (IV, DES Blocks)? The DES IV is loaded into a DES algorithm which is (hopefully!) highly positionally dependent. Since the SPI is arbitrary, it doesn't really make any difference what order you interpret it in. You can interpret it in either little or big endian order and it won't alter your operation (so long as you are consistant, of course!) Perry From ipsec-request@ans.net Wed Jun 21 10:25:04 1995 Received: from interlock.ans.net by nis.ans.net with SMTP id AA33348 (5.65c/IDA-1.4.4 for ); Wed, 21 Jun 1995 14:37:15 -0400 Received: by interlock.ans.net id AA17021 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Wed, 21 Jun 1995 14:35:40 -0400 Message-Id: <199506211835.AA17021@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Wed, 21 Jun 1995 14:35:40 -0400 From: smb@research.att.com Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Wed, 21 Jun 1995 14:35:40 -0400 To: Robert Glenn Subject: Re: Implementation question Cc: ipsec@ans.net Date: Wed, 21 Jun 95 14:25:04 EDT > Shouldn't the SPI be sent in network order as well as the other > fields that were specifically mentioned (IV, DES Blocks)? No. The SPI is an opaque field to the sender. It was supplied, via the key management protocol, by the receiver; the sender just emits it unchanged. From ipsec-request@ans.net Thu Jun 22 13:53:12 1995 Received: from interlock.ans.net by nis.ans.net with SMTP id AA33521 (5.65c/IDA-1.4.4 for ); Thu, 22 Jun 1995 18:04:05 -0400 Received: by interlock.ans.net id AA48511 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Thu, 22 Jun 1995 17:57:13 -0400 Message-Id: <199506222157.AA48511@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Thu, 22 Jun 1995 17:57:13 -0400 From: smb@research.att.com Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Thu, 22 Jun 1995 17:57:13 -0400 To: ipsec@ans.net Subject: security protocols versus MTU Cc: dawagner@research.att.com (David Wagner) Date: Thu, 22 Jun 95 17:53:12 EDT When an encryption header is added to an MTU-length packet, the encryptor will have to fragment its output intentionally, with all the problems that entails. The obvious answer is to reduce the MTU advertised upstream. But that's problematic for bump-in-the-cord encryptors or for anything below of the IP layer. Furthermore, if a receiving bump-in-the-cord decryptor is to handle such packets, it would need a full IP reassembly mechanism. (In-kernel decryptors could, of course, let the existing mechanisms reassemble the packet, and pass the result *up* to the IPSP protocol module.) So we need some way to make sure that fragmentation does not happen at this point. The right answer is Path MTU. But only a small fraction of hosts have deployed that to date. (The answer may be different for IPv6, of course.) I suggest, therefore, that whenever we agree on a key management protocol, it include an MTU that can be passed upwards. Thus, machines on the end of, say, PPP links with a 256 byte MTU will advertise a small packet size during any key management negotiations. I should note that the context here is quite concrete. David Wagner is implementing the IPv4 security protocols as a packet driver shim for DOS and Windows. This operates at the link layer, below IP, and while it can tell IP its effective MTU, we don't want to have to reimplement IP fragment reassembly for input packets. So we need some way to make sure that folks don't send us large packets. (By contrast, it's relatively easy for this module to fragment a jumbogram and send out complete IPSP packets whose payload is a single fragment. The normal reassembly mechanisms can cope with that quite nicely.) --Steve Bellovin From ipsec-request@ans.net Sat Jun 24 13:05:08 1995 Received: from interlock.ans.net by nis.ans.net with SMTP id AA30164 (5.65c/IDA-1.4.4 for ); Sat, 24 Jun 1995 17:09:10 -0400 Received: by interlock.ans.net id AA19478 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Sat, 24 Jun 1995 17:05:14 -0400 Message-Id: <199506242105.AA19478@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Sat, 24 Jun 1995 17:05:14 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Sat, 24 Jun 1995 17:05:14 -0400 Date: Sat, 24 Jun 95 17:05:08 EDT From: atkinson@itd.nrl.navy.mil (Ran Atkinson) To: ipsec@ans.net Subject: MTU issue Steve, For what its worth, IPv6 land should have Path MTU Discovery universally deployed except for very small systems that will never send any packet bigger than the smallest legal MTU size for IPv6. I agree it would be good to get the MTU data, but I'm not sure whether or not it might belong inside the key mgmt mechanism (especially if the same key mgmt mechanism were also used to distribute security association/keying information for OSPF/RIP/whatever) . I'd be interested to hear of any other ideas on this. I'm still thinking about the SPI question that Rob Glenn raised. I'm not sure its obvious what the right answer is just yet. My own thought had been that all of the network-layer packet fields were in network-order whilst on the net and in host-order whilst being processed by the host. Recall that we only have required manual key distribution for the present. Consider that two systems A and B have opposite host byte ordering and are using manual key distribution (i.e. administrator types in the key on the console of each machine in, say, hexadecimal). Maybe I'm not thinking clearly, but it seems to me that if the SPI isn't in network-order within the transmitted packet while that packet is on the wire, then the human doing the typing will have to (1) know whether their is a byte ordering issue for the remote system and (2) convert to the receiver's order prior to typing it in. If this is so, then I'd say that it ought to be in network-order whilst on the wire. Corrections of my mistakes are solicited. :-) Ran rja@cs.nrl.navy.mil From ipsec-request@ans.net Mon Jun 26 12:25:27 1995 Received: from interlock.ans.net by nis.ans.net with SMTP id AA28624 (5.65c/IDA-1.4.4 for ); Mon, 26 Jun 1995 12:25:27 -0400 Received: by interlock.ans.net id AA43723 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Mon, 26 Jun 1995 12:14:14 -0400 Message-Id: <199506261614.AA43723@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-3); Mon, 26 Jun 1995 12:14:14 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Mon, 26 Jun 1995 12:14:14 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Mon, 26 Jun 1995 12:14:14 -0400 Date: Mon, 26 Jun 95 08:49:09 From: "Housley, Russ" Encoding: 305 Text To: ipsec@ans.net, atkinson@itd.nrl.navy.mil (Ran Atkinson) Subject: Re: MTU issue Ran makes a good point about manual key management. The SPI (I still do not like that name) bit and byte ordering must be specified so that the identifiers can be matched with the IPSP PDU field. This is a simple thing to specify, and it does not impact implementations very much either. Russ From ipsec-request@ans.net Mon Jun 26 20:28:16 1995 Received: from interlock.ans.net by nis.ans.net with SMTP id AA25614 (5.65c/IDA-1.4.4 for ); Mon, 26 Jun 1995 18:24:32 -0400 Received: by interlock.ans.net id AA38619 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Mon, 26 Jun 1995 18:15:40 -0400 Message-Id: <199506262215.AA38619@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Mon, 26 Jun 1995 18:15:40 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Mon, 26 Jun 1995 18:15:40 -0400 Mime-Version: 1.0 Content-Type: Multipart/Mixed; Boundary="NextPart" To: IETF-Announce: ; Cc: ipsec@ans.net, iesg@CNRI.Reston.VA.US From: Internet-Drafts@CNRI.Reston.VA.US Reply-To: Internet-Drafts@CNRI.Reston.VA.US Subject: I-D ACTION:draft-krawczyk-keyed-md5-00.txt Date: Mon, 26 Jun 95 16:28:16 -0400 Sender: cclark@CNRI.Reston.VA.US --NextPart A New Internet-Draft is available from the on-line Internet-Drafts directories. Title : Keyed-MD5 for Message Authentication Author(s) : H. Krawczyk Filename : draft-krawczyk-keyed-md5-00.txt Pages : 3 Date : 06/22/1995 This document describes a keyed-MD5 mechanism for use as a message authentication code (MAC) (or, integrity check value -- ICV). It is mainly intended for integrity verification of information transmitted over open networks (e.g., Internet) between parties that share a common secret key. The proposed mechanism combines the (key-less) MD5 hash function [RFC-1321] with a shared secret key. The description of keyed-MD5 in this document is independent of its use in any particular protocol. An analogous mechanism can be used in combination with other iterative hash functions, e.g., SHA. Internet-Drafts are available by anonymous FTP. Login with the username "anonymous" and a password of your e-mail address. After logging in, type "cd internet-drafts" and then "get draft-krawczyk-keyed-md5-00.txt". A URL for the Internet-Draft is: ftp://ds.internic.net/internet-drafts/draft-krawczyk-keyed-md5-00.txt Internet-Drafts directories are located at: o Africa Address: ftp.is.co.za (196.4.160.2) o Europe Address: nic.nordu.net (192.36.148.17) Address: ftp.nis.garr.it (192.12.192.10) o Pacific Rim Address: munnari.oz.au (128.250.1.21) o US East Coast Address: ds.internic.net (198.49.45.10) o US West Coast Address: ftp.isi.edu (128.9.0.32) Internet-Drafts are also available by mail. Send a message to: mailserv@ds.internic.net. In the body type: "FILE /internet-drafts/draft-krawczyk-keyed-md5-00.txt". NOTE: The mail server at ds.internic.net can return the document in MIME-encoded form by using the "mpack" utility. To use this feature, insert the command "ENCODING mime" before the "FILE" command. To decode the response(s), you will need "munpack" or a MIME-compliant mail reader. Different MIME-compliant mail readers exhibit different behavior, especially when dealing with "multipart" MIME messages (i.e., documents which have been split up into multiple messages), so check your local documentation on how to manipulate these messages. For questions, please mail to Internet-Drafts@cnri.reston.va.us. Below is the data which will enable a MIME compliant mail reader implementation to automatically retrieve the ASCII version of the Internet-Draft. --NextPart Content-Type: Multipart/Alternative; Boundary="OtherAccess" --OtherAccess Content-Type: Message/External-body; access-type="mail-server"; server="mailserv@ds.internic.net" Content-Type: text/plain Content-ID: <19950622161106.I-D@CNRI.Reston.VA.US> ENCODING mime FILE /internet-drafts/draft-krawczyk-keyed-md5-00.txt --OtherAccess Content-Type: Message/External-body; name="draft-krawczyk-keyed-md5-00.txt"; site="ds.internic.net"; access-type="anon-ftp"; directory="internet-drafts" Content-Type: text/plain Content-ID: <19950622161106.I-D@CNRI.Reston.VA.US> --OtherAccess-- --NextPart-- From ipsec-request@ans.net Mon Jun 26 22:26:00 1995 Received: from interlock.ans.net by nis.ans.net with SMTP id AA30111 (5.65c/IDA-1.4.4 for ); Mon, 26 Jun 1995 18:38:41 -0400 Received: by interlock.ans.net id AA45520 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Mon, 26 Jun 1995 18:30:04 -0400 Message-Id: <199506262230.AA45520@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-4); Mon, 26 Jun 1995 18:30:04 -0400 X400-Received: by interlock.ans.net (Protected-side Proxy Mail Agent-3); Mon, 26 Jun 1995 18:30:04 -0400 X400-Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Mon, 26 Jun 1995 18:30:04 -0400 X400-Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Mon, 26 Jun 1995 18:30:04 -0400 Date: Mon, 26 Jun 1995 18:26:00 -0400 X400-Originator: "/dd.id=1631303/g=paul/i=pc/s=van oorschot/"@bnr.ca X400-Mts-Identifier: [/PRMD=BNR/ADMD=TELECOM.CANADA/C=CA/;bcars735.b.667:26.05.95.22.27.02] X400-Content-Type: P2-1984 (2) Content-Identifier: response to L... From: "paul (p.c.) van oorschot" Sender: "paul (p.c.) van oorschot" To: ietf@cnri.reston.va.us Cc: ipsec@ans.net, iesg@cnri.reston.va.us Subject: response to Last Call on: IP Authentication using Keyed MD5 This note is in response to the Last Call on the Keyed MD5 draft: > From: The IESG > Subject: Last Call: Security Architecture for the Internet Protocol to > Proposed Standard > Date: Fri, 16 Jun 95 13:14:01 -0400 > Sender: scoya@CNRI.Reston.VA.US > The IESG has received a request from the IP Security Protocol Working Group > to consider the followingt documents for the status of Proposed Standard: > 4. IP Authentication using Keyed MD5 ======= Summary ======= The following are apparent deficiencies of the current Keyed MD5 draft. 1. Despite the inclusion of a section ``Security Considerations'', the I-D gives no estimate of the security level of the proposed keyed hash function (e.g. work factor 2^{n} to break, etc.). Moreover, from reading the I-D itself, it is not clear what the conjectured level is. 2. The I-D does not seem to be aware of, nor take into consideration, recent work in the areas of hash functions and keyed hash functions. This includes both generic results, and results specific to functions like MD4 and MD5, both of which indicate that the proposed method is almost certainly less secure than hoped (cf. point 1.). 3. The current I-D does not offer the best (w.r.t. security and speed) solution currently available for the proposed application. One alternative is discussed below; others almost certainly exist. 4. Some technical statements in the current I-D regarding security are both inaccurate and misleading. I suggest that it is unacceptable for such an I-D to be progressed without specifying a conjectured level of security; without this, it cannot be decided if it meets the requirements of an application, or compared with alternatives. I further suggest that upon investigation, it will be found that recent attacks, both generic and MD4/MD5-specific (as noted below), will show the proposed method is weaker than has been believed to date. As a consequence, alternative algorithms should be considered (as discussed below). I suggest that serious attention be given to these points before a decision is taken on the progression of this I-D. Some technical discussion follows in support of these statements. Sincerely, Paul C. Van Oorschot 1995 June 26 ------------------------------------------------------------------------------ Paul Van Oorschot Bell-Northern Research | EMAIL: paulv@bnr.ca | MAIL TO: SHIP TO: | VOICE: 613-763-4199 | BNR, Box 3511, Station C, BNR, 2 Constellation Cr. | FAX: 613-765-3520 | Ottawa, Canada K1Y 4H7 Nepean, ON, Canada K2G 5J9 | | ------------------------------------------------------------------------------ =============================================================== Additional Discussion and Technical Details on the above points =============================================================== The technical content of the I-D is as follows. A keyed hash function is built from MD5 using below will be referred to as the ``envelope method'': ``The variable length secret authentication key is ... concatenated with ... the invariant fields of the entire IP datagram ... concatenated with the variable length secret authentication key again (trailing padded is added by the MD5 algorithm). The resulting 128-bit digest is inserted into the Authentication Data field.'' 1. The ID makes no mention of the level of security which the proposed technique offers. Since historically security of this nature cannot be proven, it is customary to state a conjectured level of security, which essentially summarizes how much work would be required using the best currently-known attack. Some relevant information can be found in a recent newletter article [rsabytes] in which three MD5-based MAC proposals are made for the IPSEC working group, by Matt Robshaw and Burt Kaliski (citing help from Hugo Krawczyk and Mihir Bellare). The three methods are: i. The envelope method with K1 = K2 where K1 is a 128-bit key (padded to a complete first block) ii. MAC(x) = h( K1, h(K2,x) ) iii. MAC(x) = h( K1, h(K1,x) ) Scheme (i) here is essentially that of the proposed I-D. The paper suggests (without details) that the best known attack on these schemes requires 2^{64} chosen message texts. Another paper, to be presented at Crypto'95 [crypto95], provides actual details of an attack which applies to (i). When applied to the proposal of the current I-D with a 128-bit key K = K1, the attack requires 2^{64} _known_ message-MAC pairs, and reduces the number further in the case that the known messages contain a common sequence of s trailing blocks (e.g. reduced to 2^{56.5} known text-MAC pairs for s=2^{16}). (As an aside, the same type of attack can be applied to scheme (ii), using a divide and conquer strategy as outlined in [crypto95], effectively reducing its security to the larger of K1 and K2.) The results are general for an n-bit key (n=128 is discussed above); for n=64, the attack requires on the order of 2^{32} known text-MAC pairs or less, which becomes more worrisome in practice. Perhaps more significantly, the attacks continue to apply in cases where messages are of fixed length, or are prepended by length fields. 2. Point 1. above discusses generic attacks. Regarding attacks on specific hash functions, the I-D notes an attack on the compression function of MD5 by den Boer and Bosselaers, and states: ``There is not yet a known method to exploit these collisions to attack MD5 in practice, but this fact is disturbing to some authors [Schneier94].'' Indeed, considerable additional research has been recently carried out. Bert den Boer himself proposed a new hash function, namely RIPEMD, which was analyzed under the European RACE/RIPE consortium in 1992. RIPEMD is a ``very strong'' version of MD4 involving essentially two strengthened versions of MD4 running in parallel. It was designed to counter known two-round attacks on MD4 and MD5. However, more recent cryptanalytic work on MD4 by Vaudenay [md4-attack] and on RIPEMD by Dobbertin [ripemd-attack] suggests that both MD4 and (very likely) MD5 fail to be as resistent as previously believed to manipulations of their internal structures. As a result of this work, some European researchers now believe that collisions for MD4 and MD5 themselves (rather than just for their compression functions) may soon be found by similar techniques. Even if this is not the case, a very reasonable (and prudent) conclusion is that if functions like these are to be used as the basis for constructing a MAC, a more conservative design should be used than the envelope method. Neither the work of Vaudenay nor Dobbertin is discussed or referenced in the I-D. 3. One alternative to the keyed MD5 method of the I-D is the MDx-MAC construction specified in [crypto95]. This is a conservative design (as recommended in Point 2. above), has been fully implemented and verified by two independent implementations (one at BNR-Ottawa and the other at K.U.Leuven, Belgium), and runs only 5% to 20% slower than MD5 (depending on the processor and implementation). Regarding speed, the MDx-MAC construction allows the function to be based on any MD4-like function, e.g. MDx = MD4, MD5, SHA or RIPEMD; MDx = MD5 yields MD5-MAC. If speed is a tremendous concern, then MD4-MAC runs fastest, with a similar speed ration to MD5-MAC as MD4 to MD5. If security is more of a concern, SHA-MAC can be used. In contrast, the envelope method is not a conservative design. While it may be possible to argue that the envelope method is theoretically secure against various attacks, such proofs typically must assume that the underlying hash function is ``secure'' in some black-box sense (i.e. attacks cannot benefit by taking advantage of details of its internal structure, which the attacks of Vaudenay and Dobbertin noted above clearly do). 4. Two important points in the current I-D are misleading, which is particularly alarming given that so little is said about even a conjectured security level for the proposed method. i) The result from the parallel collision search paper of van Oorschot and Wiener in [OW94] is mis-stated. The I-D states that the attack ``could find messages that hash to an arbitrary given MD5 hash''. The correct statement is that two messages can be found which have a common hash, where both messages can be almost-entirely chosen by an attacker; however, the hash value cannot be. While subtle, the difference is enormous from a security viewpoint: the relative work factors for the two statements are 2^128 and 2^64 operations. ii) The I-D suggests, regarding 128-bit hashes: ``Although this is not a substantial weakness, it should be recognized that current technology is catching up to the 128-bit hash length used by MD5. Applications requiring extremely high levels of security may wish to move in the near future to algorithms with longer hash lengths." I believe this statement to be quite misleading, and may dangerously contribute to further confusion between a MAC and an unkeyed hash algorithm. A 128-bit MAC should indeed be sufficient for the forseeable future (although one might conceivably desire a larger internal chaining variable at some point). In fact, for a hash function such as MD5, [crypto95] shows that keeping less than the full 128 bits makes the MAC more resistant to certain attacks. On the other hand, 128 bits soon may well be too short for an unkeyed hash function, for applciations requiring very high levels of security. ================== Concluding remarks ================== Given the recent work in the area of both hash functions and MACs built from hash functions, the method of the proposed I-D appears to have been either insufficiently analyzed, or improperly placed in context with the best currently-known attacks. The method does not appear sufficiently sound to warrant progression of the I-D to RFC. Given the length of time it has taken for IPSEC to resolve this difficult matter, it would be ironic for this I-D to be progressed to RFC concurrently with the publication of [crypto95] which shows that the level of security it and similar constructions offer is considerably less than believed. Both the proposal of [crypto95], and other similar proposals, should be investigated as alternatives to that of the current I-D. That of [crypto95] can be MD5-based, is resistant to all currently known attacks, is essentially the same speed as MD5 itself, and would appear to be stronger than the envelope method in the case that flaws are found in the future in MD5 itself. The authors would be happy to post [crypto95] to the usual ftp sites convenient to IPSEC. It can also be made available from: K.U.Leuven ftp server: ftp.esat.kuleuven.ac.be directory: pub/COSIC/preneel Hopefully this can be discussed further, as appropriate, prior to and/or at the Stockholm IETF. ========== References ========== [rsabytes] B. Kaliski, M. Robshaw, ``Message authentication with MD5,'', pp.5--8 in _CryptoBytes_ (RSA Labs Technical Newsletter), vol.1 no.1 Spring 1995. [crypto95] Bart Preneel, Paul C. van Oorschot, ``MDx-MAC and Building Fast MACs from Hash Functions'', Proc. Crypto'95, Springer-Verlag LNCS (to appear, Aug. 1995). (A preliminary version of this paper excluding the MDx-MAC construction, ``A new generic attack on message authentication codes'', has been available to some members of the IPSEC working group.) [md4-attack] S. Vaudenay, ``On the need for multipermutations: cryptanalysis of MD4 and SAFER'', _Fast Software Encryption_, Springer-Verlag LNCS, 1995 (to appear). (Proc. of Algorithms Workshop, Leuven, Belgium, Dec. 1994). {email: Serge.Vaudenay@ens.fr} [ripemd-attack] H. Dobbertin, ``Collisions for the last two rounds of the RIPEMD compress function'', presented at rump session of Eurocrypt'95, St. Malo, France, May 1995. {email: dobbertin@skom.rhein.de} ---------------------------------------------------------------------- From ipsec-request@ans.net Mon Jun 26 16:22:51 1995 Received: from interlock.ans.net by nis.ans.net with SMTP id AA38472 (5.65c/IDA-1.4.4 for ); Mon, 26 Jun 1995 21:29:27 -0400 Received: by interlock.ans.net id AA40361 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Mon, 26 Jun 1995 21:21:31 -0400 Message-Id: <199506270121.AA40361@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Mon, 26 Jun 1995 21:21:31 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Mon, 26 Jun 1995 21:21:31 -0400 Date: Mon, 26 Jun 95 20:22:51 EDT From: hugo@watson.ibm.com To: ietf@cnri.reston.va.us Cc: ipsec@ans.net, iesg@cnri.reston.va.us, PAULV@BNR.CA Subject: response to Last Call on: IP Authentication using Keyed MD5 The document: draft-ietf-ipsec-ah-md5-03.txt presents what is supposed to become the "must to implement" message authentication function for IPSP and IPv6. The authors of that document have ignored past recommendations I made to this group regarding the choice of this function. This included recommendations worked out together with my colleagues Mihir Bellare and Ran Canetti in IBM Research, and Burt Kaliski and Matt Robshaw from RSA Labs. Out of these recommendations, all based on the idea of keying the (otherwise keyless) MD5 function, I chose one that seems the most acceptable to the WG (based on feedback from people to the list and personal discussions with some of its members). This particular function is presented in an Internet draft that was just posted: draft-krawczyk-keyed-md5-00.txt This draft limits itself to the description of the function in a way which is protocol independent, and can be referenced by other documents specifying its particular use for a given protocol, e.g., the Authentication Header of IPSP and IPv6. (This approach is similar to the way RFC-1321 is referenced for MD5). In particular, the draft does not explain the rationale for this particular transform. Information on that is provided in the articles referenced in the draft. Some of this rationale was also several times sketched in my notes to the IPSEC WG list. The particular choice presented in this new draft is intended to keep the following properties: * no change to the MD5 code required * no degradation of MD5 speed * simple key requirements Departing from these conditions, other constructions with better analytical properties can be suggested . For example, keying the MD5 function via its initial registers as proposed in references BCK and PV of the draft (this requires less assumptions on the compression function of MD5 at the cost of a minimal change in MD5 code). However, the proposed scheme does not suffer of any practical weakness known today. On the other hand, if the above properties are to be relaxed then other designs which may prove more robust to future attacks are possible. A separate note by Paul Van OOrschot to these lists proposes going in this direction. I support his position if the above conditions (no modification of MD5, speed, etc) are relaxed. Otherwise, I propose the adoption of keyed-MD5 as described in the above draft (draft-krawczyk-keyed-md5-00.txt). Hugo (Krawczyk) From ipsec-request@ans.net Tue Jun 27 02:00:48 1995 Received: from interlock.ans.net by nis.ans.net with SMTP id AA05459 (5.65c/IDA-1.4.4 for ); Mon, 26 Jun 1995 22:07:34 -0400 Received: by interlock.ans.net id AA50995 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Mon, 26 Jun 1995 22:00:55 -0400 Message-Id: <199506270200.AA50995@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-4); Mon, 26 Jun 1995 22:00:55 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-3); Mon, 26 Jun 1995 22:00:55 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Mon, 26 Jun 1995 22:00:55 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Mon, 26 Jun 1995 22:00:55 -0400 To: hugo@watson.ibm.com Cc: ipsec@ans.net, iesg@cnri.reston.va.us, PAULV@BNR.CA Subject: Re: response to Last Call on: IP Authentication using Keyed MD5 In-Reply-To: Your message of "Mon, 26 Jun 1995 20:22:51 EDT." <199506270121.AA40361@interlock.ans.net> Reply-To: perry@imsi.com X-Reposting-Policy: redistribute only with permission Date: Mon, 26 Jun 1995 22:00:48 -0400 From: "Perry E. Metzger" To be very clear here, I'm speaking (as usual) for Perry Metzger -- not for my co-authors, just for me. These are *my* views. Take them as such. hugo@watson.ibm.com writes: > The document: draft-ietf-ipsec-ah-md5-03.txt > presents what is supposed to become the "must to implement" message > authentication function for IPSP and IPv6. The authors of that document > have ignored past recommendations I made to this group regarding > the choice of this function. I'd say that "ignored" is too strong a statement. "Felt exhausted by the battles over the authentication transform and were too desultory about making changes to the document because we were utterly and completely burned out" is perhaps a much more accurate statement. We were sort of depending on people to come up with specific language to insert. There being none mentioned, things slouched towards last call. I'm happy to see the suggestions you made adopted in this round, *PROVIDED* that my co-authors don't object (big provisio) and that the incorporation of your suggestions does not substantially delay the adoption of the document (another big provisio). This has been a draft for some time, and has been in last call for some time -- you did have an opportunity to make objections a long time ago. This is not to say that I don't want the technically best solution adopted, but it is to say that I'm more willing to try to make the changes when the documents move the next notch up the standardization process than I am to let these documents, which should have been out literally years ago, get delayed any longer. The architecture we have adopted permits open addition of new security transforms and it will be a simple matter to make your transform a new one in the suite and to mandate its implementation instead of the the existing MD5 transform in the next round of standardization. The IETF process is very forgiving in this regard. I'd like to say that had your results on this topic in cryptography not been informally discussed in Danvers and had I not enormous (that is to say, overwhelming) respect for you, Hugo, I would be of a mind to work to have your objections tossed out right now because of how ill timed they are. You should have been pressing us with specific language to insert into the drafts two months ago. As it is because I am forced to admit that you know far more about the technical merits of one signed hash method over another than almost anyone else around I feel like we have to bend over backwards to try to accomodate your ideas -- but PLEASE DONT EVER DO THIS AGAIN! Next time, please bring this all up earlier, and be mindful of the fact that the earlier set of working group last calls were in place specifically to remind you to jog our memory about such things. Also remember that this is just the first move towards standardization and that there are plenty of more opportunities to make this sort of technical correction as we move forward. > Hugo (Krawczyk) Perry From ipsec-request@ans.net Sun Jun 27 03:14:00 1995 Received: from interlock.ans.net by nis.ans.net with SMTP id AA30076 (5.65c/IDA-1.4.4 for ); Tue, 27 Jun 1995 01:24:29 -0400 Received: by interlock.ans.net id AA17041 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Tue, 27 Jun 1995 01:16:32 -0400 Message-Id: <199506270516.AA17041@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-5); Tue, 27 Jun 1995 01:16:32 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-4); Tue, 27 Jun 1995 01:16:32 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-3); Tue, 27 Jun 1995 01:16:32 -0400 From: Paul_Lambert-P15452@email.mot.com Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Tue, 27 Jun 1995 01:16:32 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Tue, 27 Jun 1995 01:16:32 -0400 Date: 26 Jun 95 22:14:00 -0500 To: hugo@watson.ibm.com, ietf@CNRI.Reston.VA.US Cc: ipsec@ans.net, iesg@CNRI.Reston.VA.US, PAULV@BNR.CA Subject: Re: response to Last Call on: IP Authentication using Keyed Hugo, Excellent specification for a keyed hash! Your text represents improvements and clarifications on a approach that has been a group consensus within the ipsec working group. As you know, keyed MD5 is being implemented several ways in the IETF, so your clear documentation is a significant contribution. Paul PS - now how do we most expediently update the ipsp specifications From ipsec-request@ans.net Tue Jun 27 12:41:43 1995 Received: from interlock.ans.net by nis.ans.net with SMTP id AA33466 (5.65c/IDA-1.4.4 for ); Tue, 27 Jun 1995 08:49:08 -0400 Received: by interlock.ans.net id AA64775 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Tue, 27 Jun 1995 08:42:25 -0400 Message-Id: <199506271242.AA64775@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-5); Tue, 27 Jun 1995 08:42:25 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-4); Tue, 27 Jun 1995 08:42:25 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-3); Tue, 27 Jun 1995 08:42:25 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Tue, 27 Jun 1995 08:42:25 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Tue, 27 Jun 1995 08:42:25 -0400 X-Mailer: exmh version 1.5.3 12/28/94 To: perry@imsi.com, ipsec@ans.net Subject: Re: response to Last Call on: IP Authentication using Keyed MD5 In-Reply-To: Your message of "Mon, 26 Jun 1995 22:00:48 EDT." <199506270200.AA50995@interlock.ans.net> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Date: Tue, 27 Jun 1995 08:41:43 -0400 From: Amir Herzberg Perry, > > ... The authors of that document > > have ignored past recommendations I made to this group regarding > > the choice of this function. > > I'd say that "ignored" is too strong a statement. "Felt exhausted by > the battles over the authentication transform and were too desultory > about making changes to the document because we were utterly and > completely burned out" is perhaps a much more accurate statement. We > were sort of depending on people to come up with specific language to > insert. There being none mentioned, things slouched towards last call. > > I'm happy to see the suggestions you made adopted in this round, > *PROVIDED* that my co-authors don't object (big provisio) and that the > incorporation of your suggestions does not substantially delay the > adoption of the document (another big provisio). This has been a draft > for some time, and has been in last call for some time -- you did have > an opportunity to make objections a long time ago. Hugo _did_ make his objections known long ago, as you recognize in your note. The one thing he didn't do so far is to contribute replacement text, and your text implies that the only reason you know for not adopting Hugo's suggestions is that such text was not provided and you were too, well, tired to write it yourselves. Your complaint here is not justified, as you (all editors) never expressed your agreement with Hugo's suggestions and asked him to contribute text. > This is not to say that I don't want the technically best solution > adopted, but it is to say that I'm more willing to try to make the > changes when the documents move the next notch up the standardization > process than I am to let these documents, which should have been out > literally years ago, get delayed any longer. We certainly don't want any more delay!! But then, it is folly for the WG to produce a standard where we agree that the basic technique should be changed. The process was delayed too long, and we, and hopefully other vendors, are already planning to offer products which comply to the standard as much as possible this year. If the `draft standard' would contain a wrong function, then it would be implemented, and it'll be difficult to get rid of it. It's not much work to change the draft to make use of Hugo's spec and that seems the best solution. > ... > I feel like we have to bend over backwards to try to accomodate your > ideas -- but PLEASE DONT EVER DO THIS AGAIN! Next time, please bring > this all up earlier, and be mindful of the fact that the earlier set > of working group last calls were in place specifically to remind you > to jog our memory about such things. I'm happy to see you plan to fix things. But please understand: you can't complain that Hugo did not provide text as you never asked him to do so; clearly you were aware of his objections and suggestions. best, Amir From ipsec-request@ans.net Tue Jun 27 13:15:40 1995 Received: from interlock.ans.net by nis.ans.net with SMTP id AA28012 (5.65c/IDA-1.4.4 for ); Tue, 27 Jun 1995 09:25:38 -0400 Received: by interlock.ans.net id AA63832 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Tue, 27 Jun 1995 09:16:16 -0400 Message-Id: <199506271316.AA63832@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-4); Tue, 27 Jun 1995 09:16:16 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-3); Tue, 27 Jun 1995 09:16:16 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Tue, 27 Jun 1995 09:16:16 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Tue, 27 Jun 1995 09:16:16 -0400 To: Amir Herzberg Cc: perry@imsi.com, ipsec@ans.net Subject: Re: response to Last Call on: IP Authentication using Keyed MD5 In-Reply-To: Your message of "Tue, 27 Jun 1995 08:41:43 EDT." <9506271241.AA54520@gimili.watson.ibm.com> Reply-To: perry@imsi.com X-Reposting-Policy: redistribute only with permission Date: Tue, 27 Jun 1995 09:15:40 -0400 From: "Perry E. Metzger" Amir Herzberg writes: > Hugo _did_ make his objections known long ago, as you recognize in your > note. Yes, but he said nothing during working group last call. He also didn't have his paper on the topic ready yet as I recall. Never mind the recriminations. I've made my opinion on the topic known, and I've also made my opinion that Hugo's work is sufficiently worthy to bend over backwards to insert in spite of any such opinions on the topic provided that we can handle this expiditiously. Hugo, do you suppose you could propose appropriate text changes quickly? Perhaps Bill or Ran will volunteer to do it instead (assuming they agree with me that the changes are meritorious -- a big if), but I'm not in a position to volunteer them and frankly I have to do way too much other stuff in the next couple of days to volunteer much time myself. I want to emphasize that this is *my* opinion here. The co-chairs and my co-authors haven't spoken. I'm just saying what *I* think the best course of action is. Perry From ipsec-request@ans.net Tue Jun 27 09:21:21 1995 Received: from interlock.ans.net by nis.ans.net with SMTP id AA31305 (5.65c/IDA-1.4.4 for ); Tue, 27 Jun 1995 13:46:40 -0400 Received: by interlock.ans.net id AA44742 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Tue, 27 Jun 1995 13:33:50 -0400 Message-Id: <199506271733.AA44742@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Tue, 27 Jun 1995 13:33:50 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Tue, 27 Jun 1995 13:33:50 -0400 Date: Tue, 27 Jun 95 13:21:21 EDT From: hugo@watson.ibm.com To: perry@imsi.com Cc: ipsec@ans.net Subject: response to Last Call on: IP Authentication using Keyed MD5 Ref: Your note of Tue, 27 Jun 1995 09:15:40 -0400 (attached) Perry, > > Hugo, do you suppose you could propose appropriate text changes > quickly? > A simple and healthy way to proceed is to have a document specifying the keyed-MD5 independently of IPSEC/IPv6 etc. The Authentication Header draft could directly reference that document, or your draft with Bill could do it. Not only I had insisted in the past with modifications to keyed-MD5, I also had suggested (in particular, echoing Phil Rogaway's clear request) to have documents that define the transforms independently of the protocol that use them (the "rfc-1321 model"). The draft draft-krawczyk-keyed-md5-00.txt can be used for this purpose (or any accepted modification of it). Hugo From ipsec-request@ans.net Tue Jun 27 22:21:54 1995 Received: from interlock.ans.net by nis.ans.net with SMTP id AA39418 (5.65c/IDA-1.4.4 for ); Tue, 27 Jun 1995 18:29:24 -0400 Received: by interlock.ans.net id AA44661 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Tue, 27 Jun 1995 18:21:59 -0400 Message-Id: <199506272221.AA44661@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-3); Tue, 27 Jun 1995 18:21:59 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Tue, 27 Jun 1995 18:21:59 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Tue, 27 Jun 1995 18:21:59 -0400 Date: Tue, 27 Jun 1995 15:21:54 -0700 From: Hilarie Orman To: hugo@watson.ibm.com Cc: ipsec@ans.net In-Reply-To: Yourmessage <199506270121.AA40361@interlock.ans.net> Subject: Re: response to Last Call on: IP Authentication using Keyed MD5 The draft repeats a defect that Van Oorschot noted with respect to draft-ietf-ipsec-ah-md5-03.txt, that it does not address the desired security properties of the transform. I realize that "better than brand X and costs no more" is meant to be a compelling argument, but some reference to absolute criteria would be useful. Why is the padding is changed from 128-bits to 512-bits in the initial key setup? Is this to allow pre-computation? If so, this should be noted so that it is not confused with a security consideration. I cannot find any of the references for the security of the method. I was only able to see a copy of the preprint of Crypto '95 paper for a few minutes and have received no replies to requests for a copy, the URL http://www.rsa.com/rsalabs/cryptobytes/ is non-existent, another reference is a "manuscript". It seems unreasonable to ask the group to make a decision if none of the background material is available to it. From ipsec-request@ans.net Wed Jun 28 10:23:14 1995 Received: from interlock.ans.net by nis.ans.net with SMTP id AA38998 (5.65c/IDA-1.4.4 for ); Wed, 28 Jun 1995 06:34:00 -0400 Received: by interlock.ans.net id AA37340 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Wed, 28 Jun 1995 06:23:23 -0400 Message-Id: <199506281023.AA37340@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-3); Wed, 28 Jun 1995 06:23:23 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Wed, 28 Jun 1995 06:23:23 -0400 Organization: ESAT, K.U.Leuven, Belgium Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Wed, 28 Jun 1995 06:23:23 -0400 Date: Wed, 28 Jun 1995 12:23:14 +0200 From: Bart.Preneel@esat.kuleuven.ac.be To: ipsec@ans.net Subject: Response to Last Call on: IP Authentication using Keyed MD5 Cc: preneel@esat.kuleuven.ac.be X-Charset: LATIN1 X-Char-Esc: 29 In his response of June 16, 95 to Last Call on: IP Authentication using Keyed MD5, Paul Van Oorschot has referenced the following paper: [crypto95] Bart Preneel, Paul C. van Oorschot, ``MDx-MAC and Building Fast MACs from Hash Functions'', Proc. Crypto'95, Springer-Verlag LNCS (to appear, Aug. 1995). This paper is now available in postscript via anonymous ftp: K.U.Leuven ftp server: ftp.esat.kuleuven.ac.be directory: pub/COSIC/preneel file: 175285 Jun 28 10:20 mdxmac_crypto95.ps Bart Preneel Katholieke Universiteit Leuven ----------------------------------------------------------------- ESAT-COSIC | phone: +32 16 32 11 48 K. Mercierlaan 94 | fax : +32 16 32 19 86 B-3001 Heverlee | email: bart.preneel@esat.kuleuven.ac.be Belgium | ----------------------------------------------------------------- From ipsec-request@ans.net Thu Jun 29 08:54:48 1995 Received: from interlock.ans.net by nis.ans.net with SMTP id AA42815 (5.65c/IDA-1.4.4 for ); Thu, 29 Jun 1995 08:59:21 -0400 Message-Id: <199506291259.AA42815@nis.ans.net> Received: by interlock.ans.net id (InterLock SMTP Gateway 3.0 for archive-ipsec@nis.ans.net); Thu, 29 Jun 1995 08:59:20 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-3); Thu, 29 Jun 1995 08:59:20 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Thu, 29 Jun 1995 08:59:20 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Thu, 29 Jun 1995 08:59:20 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-0); Thu, 29 Jun 1995 08:59:20 -0400 Date: Thu, 29 Jun 1995 16:54:48 +0800 From: Phil Rogaway To: ipsec@ans.net Subject: response to Last Call on: IP Authentication using Keyed MD5 Now that it may finally be on the table to do something about draft-ietf-ipsec-ah-md5-03.txt I would like to remind this community that not only should the MAC be defined independent of its intended use, so too should the encryption transform. I did this two months ago (Internet Draft draft-rogaway-cbc-encrypt-00.txt -- the suggested replacement to what is now draft-ietf-ipsec-esp-des-cbc-04.txt). I received 0 (zero) comments on this work, and the revised IPSEC document (draft-ietf-ipsec-esp-des-cbc-04.txt) was non-responsive. This despite the fact that not only is the transform in draft-ietf-ipsec-esp-des-cbc-04.txt intertwined with its use, but its description has at least two major technical errors. These were already pointed out in earlier notes: incorrectly asserting that the mechanism provides integrity, and incorrectly stating that a counter provides as an acceptable IV. Phil Rogaway From ipsec-request@ans.net Thu Jun 29 07:39:30 1995 Received: from interlock.ans.net by nis.ans.net with SMTP id AA19540 (5.65c/IDA-1.4.4 for ); Thu, 29 Jun 1995 09:01:53 -0400 Message-Id: <199506291301.AA19540@nis.ans.net> Received: by interlock.ans.net id (InterLock SMTP Gateway 3.0 for archive-ipsec@nis.ans.net); Thu, 29 Jun 1995 09:01:53 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-3); Thu, 29 Jun 1995 09:01:53 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Thu, 29 Jun 1995 09:01:53 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Thu, 29 Jun 1995 09:01:53 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-0); Thu, 29 Jun 1995 09:01:53 -0400 Date: Thu, 29 Jun 1995 15:39:30 +0800 From: Phil Rogaway To: hugo@watson.ibm.com, perry@imsi.com Subject: Re: response to Last Call on: IP Authentication using Keyed MD5 Cc: PAULV@BNR.CA, iesg@cnri.reston.va.us, ipsec@ans.net Dear Perry, I think it is wrong to characterize Hugo as jumping into this at the last minute: Hugo has been trying, unsuccessfully, to get the MAC mechanism straightened out for a very long time. When you say "PLEASE DONT EVER DO THIS AGAIN!" you do Hugo (and the community) an injustice. Your note suggests that the "correct" model is to have the more knowledgeable scientists press less knowledgeable authors to insert bits of language into their documents. This will never work to yield good cryptographic architecture or mechanisms. In this case the entire MD5 MAC document was in need of being redone (e.g. a transform was not even cleanly (use-independently) specified). Your final remark characterizes Hugo's Internet Draft as a "technical correction" (which is unjust) and suggests that there will be ample opportunities to absorb such "corrections" in the future (a prospect I find extremely unlikely). Phil Rogaway From ipsec-request@ans.net Thu Jun 29 12:15:33 1995 Received: from interlock.ans.net by nis.ans.net with SMTP id AA42976 (5.65c/IDA-1.4.4 for ); Thu, 29 Jun 1995 09:59:27 -0400 Message-Id: <199506291359.AA42976@nis.ans.net> Received: by interlock.ans.net id (InterLock SMTP Gateway 3.0 for archive-ipsec@nis.ans.net); Thu, 29 Jun 1995 09:59:21 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-4); Thu, 29 Jun 1995 09:59:21 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-3); Thu, 29 Jun 1995 09:59:21 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Thu, 29 Jun 1995 09:59:21 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Thu, 29 Jun 1995 09:59:21 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-0); Thu, 29 Jun 1995 09:59:21 -0400 To: Phil Rogaway Cc: ipsec@ans.net Subject: Re: response to Last Call on: IP Authentication using Keyed MD5 In-Reply-To: Your message of "Thu, 29 Jun 1995 16:54:48 +0800." <199506290856.AA39312@interlock.ans.net> Reply-To: perry@imsi.com X-Reposting-Policy: redistribute only with permission Date: Thu, 29 Jun 1995 08:15:33 -0400 From: "Perry E. Metzger" Phil Rogaway writes: > Now that it may finally be on the table to do something about > draft-ietf-ipsec-ah-md5-03.txt > I would like to remind this community that not only > should the MAC be defined independent of > its intended use, so too should the encryption transform. More properly, you should state that it is your opinion that the transforms should be independant of use. > I did this two months ago > (Internet Draft draft-rogaway-cbc-encrypt-00.txt -- the suggested > replacement to what is now draft-ietf-ipsec-esp-des-cbc-04.txt). > I received 0 (zero) comments on this work, Many of us are too tired to comment in detail on every idea that comes forward. I'm still to tired, myself. Hugo has a legitimate point that his method provides more security, so I'm reluctantly seeing if I can lobby to do something about them. Your changes were gratuitous and actually less efficient, so I didn't think of them as being a good idea. > This despite the fact that not only is the transform in > draft-ietf-ipsec-esp-des-cbc-04.txt intertwined with its use, but > its description has at least two major technical errors. These were > already pointed out in earlier notes: incorrectly asserting that the > mechanism provides integrity, and incorrectly stating that a counter > provides as an acceptable IV. "Major technical errors?" I was an author of that document. There is already an explicit reference in the document to the fact that under some circumstances integrity can be breeched... The usual (ICMP, TCP, UDP) transport checksum can detect | this attack, but on its own is not considered cyptographically | strong. In this situation, user or connection oriented integrity | checking is needed [A-AH]. | and the only other reference to the word "integrity" is in the introductory sentence which generically describes goals of ESP and not specific properties of the DES transform. However, I'm sure in this or a later version of the document a single sentence could easily be inserted to note that DES alone can't guarantee integrity. This is hardly the mark of a "major technical error" in the proposal. At worst it's something that we could say more redundantly. I don't see that this would justify holding up the documents, but I'll find out if we could insert a single line to that effect. As for counters, assuming that DES does in fact work as advertised, flipping one bit in the IV should flip, on average, 50% of the output bits. Do you have evidence that this is insufficient for purposes of disguising identical initial blocks, which is all an IV does in life? Perry From ipsec-request@ans.net Fri Jun 30 02:16:55 1995 Received: from interlock.ans.net by nis.ans.net with SMTP id AA45584 (5.65c/IDA-1.4.4 for ); Thu, 29 Jun 1995 22:26:55 -0400 Received: by interlock.ans.net id AA40258 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Thu, 29 Jun 1995 22:19:03 -0400 Message-Id: <199506300219.AA40258@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-3); Thu, 29 Jun 1995 22:19:03 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Thu, 29 Jun 1995 22:19:03 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Thu, 29 Jun 1995 22:19:03 -0400 Date: Fri, 30 Jun 1995 10:16:55 +0800 From: Phil Rogaway To: perry@imsi.com, rogaway@cs.ust.hk Subject: Re: response to Last Call on: IP Authentication using Keyed MD5 Cc: ipsec@ans.net > There is already an explicit > reference in the document to the fact that under some circumstances > integrity can be breeched... I'm not sure what you're trying to say, but the introduction of your document, AND the next higher-level document (draft-ietf-ipsec-esp-01.txt), AND the next higher-level document after that (draft-ietf-ipsec-arch-02.txt) ALL maintain that the encryption mechanism provides integrity. Either DES CBC encryption is architecturally non-compliant (and so the mechanism has to be changed), or else all of the above statements about the encryption buying you integrity need to be changed. (I've said this enough times to turn blue....) > As for counters, assuming that DES does in fact work as advertised, > flipping one bit in the IV should flip, on average, 50% of the output > bits. Do you have evidence that this is insufficient for purposes of > disguising identical initial blocks, which is all an IV does in life? Maybe you don't understand the purpose of the IV: properly used in CBC encryption the method achieves semantic security; improperly used, it does not. A one-line proof of this: simply note that if the IV takes on values <0>, <1>, ... then the adversary can distinguish the encryption of message <0> followed by the encryption of message <0> FROM the encryption of message <0> followed by the encryption of message <1>. (Here means the 64-bit encoding of integer i). (Perry - further discussion on these particular issues need not involve the entire mailing list.) Phil From ipsec-request@ans.net Fri Jun 30 10:48:37 1995 Received: from interlock.ans.net by nis.ans.net with SMTP id AA24720 (5.65c/IDA-1.4.4 for ); Fri, 30 Jun 1995 06:57:10 -0400 Received: by interlock.ans.net id AA02239 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Fri, 30 Jun 1995 06:49:15 -0400 Message-Id: <199506301049.AA02239@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Fri, 30 Jun 1995 06:49:15 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Fri, 30 Jun 1995 06:49:15 -0400 To: ipsec@ans.net Cc: Michael.Roe@cl.cam.ac.uk Subject: Comments on the IPSEC documents Date: Fri, 30 Jun 1995 11:48:37 +0100 From: Mike Roe Comments on the IP Security Internet Drafts Michael Roe Roger Needham Mark Lomas Ross Anderson Ian Jackson Cambridge University Computer Laboratory Executive Summary ================= This document identifies some fairly serious problems with the cryptographic protocols which have been proposed for IP-level security. Accordingly, we believe that these draft protocols should not be adopted as Internet Proposed Standards without undergoing further revision. References =========== ``Security Architecture for the Internet Protocol'' draft-ietf-ipsec-arch-02.txt 8 May 1995 ``Encapsulating Security Payload'' draft-ietf-ipsec-esp-01.txt 23 April 1995 ``The ESP DES-CBC Transform'' draft-ietf-ipsec-esp-des-cbc-04.txt April 1995 ``IP Authentication using Keyed MD5'' draft-ietf-ipsec-ah-md5-03.txt ``Keyed-MD5 for Message Authentication'' draft-krawczyk-keyed-md5-00.txt 1. DES-CBC doesn't provide integrity ==================================== In the architecture, clause 1.3, 5th para, the current text says: ``The IP Encapsulating Security Payload (ESP) is designed to provide integrity, authentication, and confidentiality to IP datagrams.'' Clause 4.3 of the ESP document says that ESP doesn't always provide integrity. In ESP DES-CBC, clause 1, the current text says: ``The Encapsulating Security Payload (ES) [A-ESP] provides confidentiality and integrity by encrypting the data to be protected. This specification describes the ESP use of the Cipher Block Chaining (CBC) mode of the US Data Encryption Standard (DES) algorithm (FIPS-46, FIPS-46-1, FIPS-74, FIPS-81).'' In ESP DES-CBC, ``Security Considerations'' clause, the current text says: ``... on its own is not considered cryptographically strong. In this situation, user or connection oriented integrity checking is needed [A-AH].'' The CBC mode of DES does not provide integrity; it only provides confidentiality. This in itself is not a problem, as CBC mode is quite suitable in situations where only confidentiality is needed. However, it does cause a major problem for this series of related documents. The architecture document assumes that the Encapsulating Security Payload provides integrity as well as confidentiality. The ESP document then admits that ESP, when used with some cryptographic transformations, doesn't provide integrity. Finally, the DES-CBC document defines the cryptographic transformation that is to be used, and it doesn't provide integrity. In the two steps from the architecture, to the ESP, to the cryptographic transformation, things have gone badly wrong. The position has changed by degrees from integrity being provided, to being optionally provided, to not being provided. To make matters worse, the DES-CBC document implies (but doesn't say outright) that DES-CBC provides integrity. This isn't true. For example: (a) The attacker can remove an integral number of 8-octet blocks from the beginning of the ciphertext without being detected. (b) The attacker can remove an integral number of 8-octet blocks from the end of the ciphertext without being detected. (c) The attacker can splice together messages (When the spliced message is deciphered, the block at which the splice occurred may look unusual. The attacker may well be able to get away with this) It could be argued that DES-CBC does provide integrity, it just does it poorly. In the same spirit, one can argue that a Caesar cipher or ROT-13 provides confidentiality, but does it poorly. No-one is seriously proposing that a Caesar cipher should be the standard confidentiality transformation for Internet use. Similarly, DES-CBC shouldn't be the standard integrity transformation; integrity-wise, it's just too easy to break. Suggested Improvements: This could potentially be fixed in two possible ways: (a) By replacing the DES-CBC transformation currently used by ESP with a different transformation that does provide integrity. We recommend this alternative. (b) By deciding that ESP sometimes provides confidentiality only, and changing the documents to reflect this: i) The DES-CBC document would have to admit that DES-CBC doesn't provide integrity ii) The architecture document would have to admit that ESP doesn't always provide integrity, and that if you need integrity and confidentiality you may need BOTH an ESP header AND an Authentication header on each datagram. The ESP document explains that two headers may be needed (in clause 4.3). The architecture document doesn't mention this. This is a very important feature of the architecture. If you're intended to use two headers, the architecture document should say so. Conversely, if you're not supposed to use two headers, then the ESP document shouldn't advise you to do so. 2. ``Keyed MD5'' may not be as secure as MD5 ============================================ The MD5 algorithm is designed as a collision-free hash function. That is, it is designed so that it is hard to find x and y such that MD5(x) = MD5(y), and x<>y. The ``keyed MD5'' method of authentication that is proposed in the ``keyed MD5'' document assumes that MD5 has a completely different property. Specifically, it assumes that MD5(k,m,k) for message m and secret key k is good as a message authentication code. MD5 wasn't designed to have this property. Furthermore, it is quite possible that MD5 will turn out not to have this property. It is quite possible that ``keyed MD5'' turns out to be very easy to break, while MD5 (used as a collision-free hash function) remains very strong. For example, suppose there is a statistical correlation between the input bits and the output bits of MD5. An attacker might be able to use this correlation to determine k, the session key. Once the attacker knows the session key, you're lost. Note that this doesn't help the attack break MD5 used as a collision-free hash function. It's purely an attack on MD5 used as a MAC. The assumption that MD5 is good as a MAC occurs elsewhere in these documents: IP Authentication Header, clause 4, para 1: ``Only algorithms believed to be cryptographically strong one-way functions should be used with the IP authentication header.'' Being a good one-way function has nothing to do with being a good MAC. This clause prevents the Authentication Header being used with some perfectly acceptable cryptographic algorithms, because although they're good MACs (which is what is needed) they're not good one-way functions. Conversely, this clause encourages implementors to use unsuitable algorithms: there are good one-way functions which are extremely poor as MACs. IP Authentication Header, clause 4, para 3 says: ``If a block-oriented authentication algorithm (e.g. MD5, MD4) ...'' This is another example of the same error. Suggested improvement ===================== Delete ``one-way functions'' from IP-AH, clause 4, para 1, last sentence (shown above). Use ``DES MAC'' as an example of a data origin authentication algorithm, not MD5 and MD4 (in IP-AH, clause 4, para 2) More significantly, there should be a new document which describes the use of the Authentication Header with a DES MAC. This algorithm could be used by people who fear that keyed-MD5 is weak. DES MAC needn't be made MANDATORY for all implementations. Indeed, export laws and other regulations will probably prevent some vendors supporting DES MAC. However, it should be specified so that people who want it can use it. 3. Separation of DES-CBC from other protocol layers This issue isn't to do with *security*, but has rather to do with the best way of organising the specification into separate documents. As currently written, the DES MAC document describes the cryptographic transformation in way that is dependent on other parts of the protocol (the SPI, and the payload type). It is quite likely that some other Internet protocol will be developed that needs a DES MAC. It would be nice to have a document that just describes DES MAC, and nothing else, that could be cited by other protocols that need a DES MAC. As things stand, the description of the DES MAC is badly entangled with details of how ESP works. If another Internet protocol needs a DES MAC, an entirely new RFC will have to be written (which will be almost exactly like the ESP DES-MAC document, but with the ESP specific bits removed). Suggested change: Separate the description of DES CBC from the rest of the protocol. in particular, take the SPI out of the DES CBC document (there is no real reason why it should be in there). It would make it easier to separate the description of DES MAC from ESP if the payload type field came *before* the padding, rather than after. That way, the DES MAC document could just describe how to pad and encipher a block of data. The ESP document would explain what was in the enciphered block of data (including the payload type). 4. Use of a counter as an IV The DES CBC document suggests using a counter as an IV. This may be vulnerable with some higher layer protocols. If two ciphertexts are the same, an attacker can infer that the plaintext are the same. One of the purposes of the IV is to prevent an attacker doing this. The IV is always different, ensuring that if the same plaintext is sent twice, the ciphertexts will be different. Unfortunately, this can go wrong if changes in the IV are statistically correlated with changes in the plaintext. Suppose that both the IV and the first block of plaintext are counters (e.g. the plaintext is a transport layer sequence number, or something like that). The first block of ciphertext will be DES(IV xor P1) = DES(counter1 XOR counter2) = DES(0) = constant. That is, the effect of the IV has been cancelled out. The same plaintext for the rest of the message will result in the same ciphertext for the rest of the message, leaking valuable information to an attacker. The above example is an extreme case. In less extreme cases, what happens is that collisions just become more likely, rather than happening every time. For example, half the time only the bottom bit of a counter changes. If the first block of plaintext also has the property that sometime only the bottom bit changes, then the two may cancel each other out quite often. From ipsec-request@ans.net Fri Jun 30 14:08:58 1995 Received: from interlock.ans.net by ftp.ans.net with SMTP id AA12919 (5.65c/IDA-1.4.4 for ); Fri, 30 Jun 1995 10:20:17 -0400 Received: by interlock.ans.net id AA23189 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Fri, 30 Jun 1995 10:09:21 -0400 Message-Id: <199506301409.AA23189@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-4); Fri, 30 Jun 1995 10:09:21 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-3); Fri, 30 Jun 1995 10:09:21 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Fri, 30 Jun 1995 10:09:21 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Fri, 30 Jun 1995 10:09:21 -0400 To: Phil Rogaway Cc: ipsec@ans.net Subject: Re: response to Last Call on: IP Authentication using Keyed MD5 In-Reply-To: Your message of "Fri, 30 Jun 1995 10:16:55 +0800." <199506300216.KAA13799@cssu55.cs.ust.hk> Reply-To: perry@imsi.com X-Reposting-Policy: redistribute only with permission Date: Fri, 30 Jun 1995 10:08:58 -0400 From: "Perry E. Metzger" Phil Rogaway writes: > > There is already an explicit > > reference in the document to the fact that under some circumstances > > integrity can be breeched... > I'm not sure what you're trying to say, but the introduction of your > document, AND the next higher-level document (draft-ietf-ipsec-esp-01.txt), > AND the next higher-level document after that (draft-ietf-ipsec-arch-02.txt) > ALL maintain that the encryption mechanism provides integrity. Phil, do I have to spell it out yet again? ESP *does* potentially provide integrity. Thats why the language is in there. ESP is *not* the "encryption mechanism". The architecture defines it simply as the the way to encapsulate opaque IPSP packets. Thats why the "E" doesn't stand for "encrypton". One is free to define an ESP transform that combines integrity and privacy. Thats why the documents say what they do. > Either DES CBC encryption is architecturally non-compliant (and so > the mechanism has to be changed), or else all of the above > statements about the encryption buying you integrity need to be > changed. There is a third possibility, which I will leave to people's imaginations. > > As for counters, assuming that DES does in fact work as advertised, > > flipping one bit in the IV should flip, on average, 50% of the output > > bits. Do you have evidence that this is insufficient for purposes of > > disguising identical initial blocks, which is all an IV does in life? > Maybe you don't understand the purpose of the IV: properly used in CBC > encryption the method achieves semantic security; improperly used, it > does not. What is "semantic security"? This is a term I have yet to hear in many years of work in the field of cryptography. Doubtless its just my ignorance at play. I always thought that an IV was just a way to assure identical plaintext doesn't turn to identical cyphertext. Silly me. > A one-line proof of this: simply note that if the IV takes > on values <0>, <1>, ... then the adversary can distinguish the encryption of > message <0> followed by the encryption of message <0> FROM the > encryption of message <0> followed by the encryption of message <1>. > (Here means the 64-bit encoding of integer i). What are you talking about here? Pardon me, but I don't understand your "one line proof". > (Perry - further discussion on these particular issues need not involve > the entire mailing list.) Thank you. In the future, feel free to send private mail. Perry From ipsec-request@ans.net Fri Jun 30 11:10:28 1995 Received: from interlock.ans.net by ftp.ans.net with SMTP id AA12693 (5.65c/IDA-1.4.4 for ); Fri, 30 Jun 1995 16:00:33 -0400 Received: by interlock.ans.net id AA56788 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Fri, 30 Jun 1995 15:49:05 -0400 Message-Id: <199506301949.AA56788@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Fri, 30 Jun 1995 15:49:05 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Fri, 30 Jun 1995 15:49:05 -0400 Date: Fri, 30 Jun 95 15:10:28 EDT From: hugo@watson.ibm.com To: ho@cs.arizona.edu Cc: ipsec@ans.net Subject: response to Last Call on: IP Authentication using Keyed MD5 Ref: Your note of Tue, 27 Jun 1995 15:21:54 -0700 (attached) Hillary and all, The draft I posted was intended to have the minimal information needed for implementation of the keyed-MD5 primitive and not to explain the rationale of the choice of this particular mechanism. Explaining this rationale in a consistent and accurate way is not easy. It requires getting into the mathematical details of the analysis. However, I have sketched the ideas in notes to this list in the past. In a separate message I am sending another (more extensive) explanation of these ideas. As for the cited papers: The Preneel-VanOOrschot paper is now available. I've just learned that the RSA Cryptobytes publication is not yet in electronic form (I am told that it will be soon). As for my own paper with Bellare and Canetti [BCK], which is the strongest basis for the analysis I have, it is currently written in a "very mathematical" form, including detailed proofs of the main results. However, it lacks a good "human interface" which may be more useful for most people in this list (e.g., the practical meaning of these results, the difference in approach to previous work, etc.). This will still take a while until done (we are all busy with many other things). However, I may make the proofs available to you or other specifically interested people; let me know if you are interested. In the meantime, the high level description I am sending in the next message will hopefully help to clarify some of these issues. Hugo ----------------------------- Note follows ------------------------------ Date: Tue, 27 Jun 1995 15:21:54 -0700 From: Hilarie Orman To: hugo@watson.ibm.com Cc: ipsec@ans.net In-Reply-To: Yourmessage <199506270121.AA40361@interlock.ans.net> Subject: Re: response to Last Call on: IP Authentication using Keyed MD5 The draft repeats a defect that Van Oorschot noted with respect to draft-ietf-ipsec-ah-md5-03.txt, that it does not address the desired security properties of the transform. I realize that "better than brand X and costs no more" is meant to be a compelling argument, but some reference to absolute criteria would be useful. Why is the padding is changed from 128-bits to 512-bits in the initial key setup? Is this to allow pre-computation? If so, this should be noted so that it is not confused with a security consideration. I cannot find any of the references for the security of the method. I was only able to see a copy of the preprint of Crypto '95 paper for a few minutes and have received no replies to requests for a copy, the URL http://www.rsa.com/rsalabs/cryptobytes/ is non-existent, another reference is a "manuscript". It seems unreasonable to ask the group to make a decision if none of the background material is available to it. From ipsec-request@ans.net Fri Jun 30 11:49:32 1995 Received: from interlock.ans.net by ftp.ans.net with SMTP id AA13031 (5.65c/IDA-1.4.4 for ); Fri, 30 Jun 1995 16:29:19 -0400 Received: by interlock.ans.net id AA31556 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Fri, 30 Jun 1995 16:19:49 -0400 Message-Id: <199506302019.AA31556@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Fri, 30 Jun 1995 16:19:49 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Fri, 30 Jun 1995 16:19:49 -0400 Date: Fri, 30 Jun 95 15:49:32 EDT From: hugo@watson.ibm.com To: IPSEC@ans.net, iesg@cnri.reston.va.us, ietf@cnri.reston.va.us Subject: Rationale behind draft-krawczyk-keyed-md5-00.txt I am appending here a high-level and informal presentation of the rationale and analysis of keyed-MD5 that makes the basis for the choice of the particular mode of keyed-MD5 (for message authentication) presented in draft-krawczyk-keyed-md5-00.txt. I assume the reader is familiar with the iterative structure of MD5 but not necessarily with the details of the compression function. All the information that follows is based on the upcoming paper [BCK] by Bellare, Canetti and Krawczyk (as referenced in the above draft). Hugo ANALYSIS OF KEYED MD5 (sketch) ****************************** The basic issue with analyzing keyed-MD5 as a message authentication function is that it builds on MD5, a function that was originally designed for a different goal, namely, as a *keyless* collision-resistant hash function. What follows is a high-level and informal description of the analysis in [BCK] which is intended to identify the cryptographic requirements from a function as MD5 (more precisely, its compression function) that would guarantee that keyed-MD5 be a good MAC. The specific mode of keyed-MD5 presented in draft-krawczyk-keyed-md5-00.txt is an adaptation of the results of this analysis. KEYED COMPRESSION FUNCTIONS AND PSEUDORANDOM FUNCTIONS: Our approach for the analysis of keyed-MD5 (or keying any other iterative hash function) is to look at the compression function as a function *keyed via its IV* (the initial registers of MD5). We consider the set of the resultant (compression) functions (one function for each 128 bit key) as a "family of pseudorandom functions". This is a well-known notion in cryptography which captures the "proximity" of such functions to a set of truly random functions, and generalizes the more common concept of pseudorandom generators. The notion of security of a pseudorandom function (more precisely, a family of such functions) can be related to the famous Turing test for "intelligent computers". In Turing's test a human asks questions and gets responses; then this human has to decide if he was talking to another human being or to a machine. A computer that passes such a test, i.e., is not distinguished from a human being, is proven "intelligent". With pseudorandom functions the game is similar. But the one that asks the questions (inputs to the function) is the adversary and the responses may come from a truly random function or from a pseudorandom function (whose key is unknown to the adversary). The adversary wins if he decided correctly (with probability better than half!) on whether the function used was truly random or pseudorandom. The adversary could distinguish the pseudorandom function from random by recovering the secret key that defines the function, or just by being able to predict its output, etc. The parameters that define the adversary success are the resources it uses: time and number of queries, and the probability (beyond half) with which it successfully distinguishes. This probability is denoted by eps (this eps is a function of the adversary resources, the family of pseudorandom functions in use, the length of key, etc). An example of a (conjectured) good family of pseudorandom functions (or permutations) is DES. In this example each DES key determines a function in the family. If you know the key then you can compute the function in any point, but if not you can hardly predict a single bit of output. DES in MAC-CBC mode is also an example of pseudorandom functions (and the reason why it makes a good MAC). MAC FUNCTION: In general, a good pseudorandom function (i.e., one with small eps for reasonable resources by the adversary) makes a good MAC. A MAC (for message authentication code) is a function that uses a secret key and computes tags or checksums on information that only parties possessing the secret key can generate. The game for the adversary (that doesn't know the key) is that he can request the result of the checksum computed on a sequence of messages of his choice. At the end, after asking enough queries, the adversary needs to come with a message that he didn't ask before, but for which he can generate the checksum by himself. (This represents a "chosen message attack", and the new message for which the adversary can generate the checksum is a "forged message"). The more time and/or queries an adversary needs to reach a certain probability of forging a message the better the MAC function is. The goal of the design of keyed-MD5 is to come with a scheme that makes a good MAC. FROM PSEUDORANDOM COMPRESSION FUNCTION TO SECURE MAC: What we [BCK] essentially prove is that *if the keyed compression function* of MD5 makes a good pseudorandom function, then its iterations preserve this condition, and then the whole keyed-MD5 function makes a good MAC. Moreover, we give a precise reduction of the form: if you give me a forgery attack on keyed-MD5 we construct from it an explicit distinguishing attack on the basic compression function, where the success parameters (eps, etc) of both attacks are precisely related in our analysis. This approach is a formalization of the intuitive reasoning that assumes MD5 and similar functions to "behave as random functions". The pure intuitive approach, if not taken carefully, can be very misleading. In particular, one can prove (with different levels of sophistication) that the MD5 function does not behave as a random function (e.g., through extension attacks, statistical collisions, etc). However, in our formal analysis we prove that if the *keyed* compression function is close enough to random then the iterations are not far from random. This methodology of relating the security of the iterated function to that of the compression function is analogous to the traditional approach to constructing collision-resistant hash functions. For the later, the resistance of the compression function to collision search guarantees that property for the iterated function. In our case, it is the pseudorandom property that is propagated through the iterations, to provide a secure MAC. THE PSEUDORANDOMNESS ASSUMPTION: To this date we do not know of significant weaknesses of MD5's keyed compression function as a pseudorandom function. Still this property is a conjecture and not something that can be expected to be proven (soon). It is important to remark that it is the same property that is implicitly assumed by everybody that uses these functions to generate (pseudo) random keys (this is done "everywhere" these days: in Photuris, SSL, MKMP, the Preneel-van OOrschot paper [PV], just to mention some places that come to my mind). Interestingly, in the case of SHA the pseudorandomness of the function is claimed by the designers who recommend (in the DSS standard) the use of SHA for pseudorandom key generation. (In other words, if you consider your keys generated using MD5 as "random" then you can safely assume keyed-MD5 is a good MAC.) On the other hand, we do not prove the *necessity* of the pseudorandomness condition on the compression function in order for keyed-MD5 to be a secure MAC. Thus, it may be the case that even if the compression function is not pseudorandom still keyed-MD5 is a good MAC. Indeed, we have a more subtle analysis of some of the modes of keyed-MD5 in which pseudorandomness can be traded by different assumptions on the compression function. (I won't get into these details here). MAC AND COLLISION-RESISTANCE: It is important to remark that our approach reflects a significant distinction between keyed and keyless hash functions, namely, that the *traditional* security requirement of collision-resistance for keyless hash functions does not apply to a (keyed) MAC. Namely, the feasibility of finding (traditional) collisions in a given function is *not* (by itself) a sign that the function does not make a good MAC. The reason being that collision search (for MD5 and similar functions) concentrates on finding collision when the IV is *known* (or even chosen). In keyed-MD5 the IV is the key and then *random and secret*. A good search engine designed for known IV's (e.g. Van Oorschot-Wiener) may be useless to attack keyed-MD5. A good example for the independence between the collision resistance aspect and being a good MAC is (again) DES. If you know the key for DES-CBC-MAC you can find as many collisions as you want (using the invertibilty of DES with known key), but if you do not know the key, then collisions are hard to find (except for the fact that 64 bits of output allows for attacks in the order of 2^32 known/chosen message attacks). In other words, even if you hear tomorrow of (real) collisions in your favorite hash function it does not mean the function becomes insecure as a keyed function. (Though, that could be the case depending on the effect of that analysis on the pseudorandomness of the compression function). On the other hand, if collisions can be found (more than statistically expected) even if the IV is secret, that will have a significant negative effect on the security of the MAC. However, this kind of collisions are very different than the traditional ones. In particular, the adversary will need the "assistance" of the legal user to collect MAC results on known and/or chosen messages; this is in sharp contrast to known-IV collisions that can be searched by the adversary off-line and independently of any user or secret key. THE PROPOSED MODE OF KEYED-MD5: Now back to the keyed-MD5 function as described in my draft, namely, MD5(K,pad,text,K). As you can see this mode does not directly use a keyed-IV. Indeed, in order *not to change* the MD5 code, we are applying regular MD5 (with its regular "magic IV") to the actual key (which is padded to complete a full block), and the result of this first application becomes the "random secret IV" for the rest of the function. The appended key has two roles: to prevent extension attacks, and to serve as yet another (implicit) transformation on the output of MD5. Notice that the appended key is not padded (see below for its rationale). On the other hand, the padding of the prepended key is done due to *security reasons*. One is to achieve a transformation of the key into a pseudorandom IV (as explained above), the other is to avoid, in the case of short messages having a single iteration of MD5 (Kaliski and Robshaw pointed out that a single iteration may be more vulnerable to linear cryptanalysis - though, no such weakness is known today). The use of keys of length less that 128 bits is not recommended. Keys longer than 128 bits may not add any significant security given that the actual strength is given by the resultant IV which is 128 bit long. As said in an note I sent a few days ago, this particular choice of keyed-MD5 is intended to satisfy the following properties: * it is based on MD5 (or similar functions) * no change to the MD5 code required * no degradation of MD5 speed * simple key requirements Departing from these conditions, other constructions with better analytical properties can be suggested . For example, directly keying the MD5 function via its initial registers as proposed in [BCK] (and [PV]) (this requires less assumptions on the compression function of MD5 at the cost of a minimal change in MD5 code). However, the proposed scheme does not suffer of any practical weakness known today. On the other hand, if the above properties are to be relaxed then other designs which may prove more robust to future attacks are possible. This includes functions that may be completely unrelated to MD5 or similar hash functions; indeed such an approach may prove more secure and/or more efficient than basing the MAC on iterated hash functions. THE BIRTHDAY ATTACK: The best attack on keyed-MD5 that we know is a 2^64 chosen/known message attack that we sketch next. For simplicity, consider the application of keyed-MD5 (denoted KMD5) on messages of the form AB where A is a 512-bit block and B a 320-bit block. KMD5(AB) results on three iterations of the compression function of MD5 on the information (K, pad, A , B, K, length), where K is the 128-bit key, pad is '1' followed by 383 0's, and length is the 64 bit encoding of the total length (i.e, 960) as added by MD5. An attacker fixes a block B, and asks for the KMD5 of (Ai,B), for i=1,2,...,2^64, where the Ai's are 2^64 (arbitrary and different) blocks of 512 bits each. With good probability (by the birthday paradox), there exist i<>j with KMD5(Ai,B)=KMD5(Aj,B). In particular,with good probability it happens in this case that MD5(K,Ai)=MD5(K,Aj) (this is the result of the first iteration of MD5, i.e. no length appended). The adversary then asks for KMD5(Ai,C) for any value of C<>B. It then "guesses" the value of KMD5(Aj,C) to be the same as KMD5(Ai,C). If, indeed, it happened that (K,Ai) collided with (K,Aj) after the first iteration of MD5 then the adversary is right. That is, with high probability the adversary correctly forged KMD5(Aj,C). (Clearly, improvements for the adversary are possible such as testing whether the latter collision happened by using some other value of C, but the above is enough for a forgery with good probability). Strictly speaking the above attack requires 2^64 *chosen* messages since it requires keeping the last block unchanged. The blocks Ai, however, can be arbitrary. They need to be known to the adversary (at least those that generate collisions) but not to be chosen by him. In some scenarios a common trailing block may be available as part of standard encoding of information in which case the attack may become a known-only attack. (This is a reason not to pad the appended key in keyed-MD5 to a full block and for keeping the appended length of MD5). In addition, the attack works with messages of any length (even variable length) and the more common trailing blocks in the messages being queried the better the success probability of the attack. However, these attacks require, in any case, a huge amount of information (2^64 blocks) being MAC-ed with the *same key*. To be avoided one just needs to change keys before processing that much information. We note that the same type of attack applies to all proposed modes for keying MD5, and more generally it applies to all iterative constructions of MAC (including CBC-MAC). As said, it is the best attack we know on keyed-MD5. In [BCK] we show that this attack is optimal if the compression function is a truly random function. However, for functions like keyed-MD5 this may very well not be the case. It is important to note the essential difference between the above attack and the traditional birthday attacks on collision-resistant hash functions as MD5. In the latter, the processing time for the attack is also 2^64 but is independent of any secret information and requires no interaction with the legitimate party. Thus, it is far more realistic than against keyed-MD5. The birthday attack on iterative MAC described above was independently discovered by [BCK] and by Preneel and Van Oorschot. A detailed description of the attack can be found in the upcoming Crypto'95 paper by the later authors [PV]. REFERENCES [BCK] M. Bellare, R. Canetti, and H. Krawczyk, "Keying MD5 -- Message Authentication via Iterated Pseudo-randomness", manuscript. [PV] B. Preneel and P. Van Oorschot, "Building fast MACs from hash functions", to appear Crypto'95. From ipsec-request@ans.net Fri Jun 30 20:33:46 1995 Received: from interlock.ans.net by ftp.ans.net with SMTP id AA11268 (5.65c/IDA-1.4.4 for ); Fri, 30 Jun 1995 16:43:28 -0400 Received: by interlock.ans.net id AA17830 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Fri, 30 Jun 1995 16:33:53 -0400 Message-Id: <199506302033.AA17830@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-4); Fri, 30 Jun 1995 16:33:53 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-3); Fri, 30 Jun 1995 16:33:53 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Fri, 30 Jun 1995 16:33:53 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Fri, 30 Jun 1995 16:33:53 -0400 To: hugo@watson.ibm.com Cc: ipsec@ans.net Subject: Re: response to Last Call on: IP Authentication using Keyed MD5 In-Reply-To: Your message of "Fri, 30 Jun 1995 15:10:28 EDT." <199506301949.AA56788@interlock.ans.net> Reply-To: perry@imsi.com X-Reposting-Policy: redistribute only with permission Date: Fri, 30 Jun 1995 16:33:46 -0400 From: "Perry E. Metzger" It appears that all that is needed to incorporate Hugo's suggestion is a change of a line or two of the MD5 AH draft to specify that the prepended part of the key be padded out with a 1 bit and some number of 0 bits to 512 bits. Am I correct on this, Hugo? Given the simplicity of this change, I'm inclined to see if we can insert it before RFC publication, in spite of the late timing. Again, this depends on what my co-authors say and on general consensus. It would also be nice if Hugo were to post a message explaining the rationale for this in approximate laymans terms. (I'd still like him to write the language to insert but I don't have much hope that he'll do it.) Perry From ipsec-request@ans.net Fri Jun 30 12:38:39 1995 Received: from interlock.ans.net by ftp.ans.net with SMTP id AA12045 (5.65c/IDA-1.4.4 for ); Fri, 30 Jun 1995 16:46:07 -0400 Received: by interlock.ans.net id AA40195 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Fri, 30 Jun 1995 16:38:46 -0400 Message-Id: <199506302038.AA40195@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-3); Fri, 30 Jun 1995 16:38:46 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Fri, 30 Jun 1995 16:38:46 -0400 From: rivest@theory.lcs.mit.edu (Ron Rivest) Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Fri, 30 Jun 1995 16:38:46 -0400 Date: Fri, 30 Jun 95 16:38:39 EDT To: ipsec@ans.net Subject: Some comments on IPSEC proposals To: IPSEC Community, IESG (iesg@cnri.reston.va.us, ietf@cnri.reston.va.us, ipsec@ans.net) From: Ronald L. Rivest Date: June 30, 1995 Re: Comments on IPSEC Internet Drafts This is response to the call for comments on the following documents, which are proposed for consideration as Proposed Standards: [SA] Security Architecture for the Internet Protocol [AH] IP Authentication Header [AHMD] IP Authentication using Keyed MD5 [ESP] IP Encapsulating Security Payload (ESP) [ESPDES] The ESP DES-CBC Transform 0. EXECUTIVE SUMMARY I believe these documents are in need of significant further work before they are ready for adoption as proposed standards. 1. INTRODUCTION These documents propose techniques for securing network communications at the IP layer. The first gives a general overview of the proposed security architecture. The next two discuss the use of authentication headers to authenticate IP packets. The last two discuss methods for achieving confidentiality (and authentication) of IP packets. This note will critique these documents collectively, emphasizing the areas where I believe further work is needed, rather than discussing areas that are already well done. Since I have not actively followed the dialogue leading up to these proposals, and am not an expert at IP/Internet protocols, some of my concerns may reflect my own ignorance of the context or intent of these proposals. If so, this may be an indication of where these documents should be improved, without necessarily changing the proposals themselves. I was stimulated in part to provide these comments by Phil Rogaway's note: [ROG] Problems with Proposed IP Cryptography Some of my comments will be based on Phil Rogaway's excellent critique. I have also found the following excellent document very relevant and interesting: [PO] MDx-MAC and Building Fast MACs from Hash Functions by Bart Preeneel and Paul C. van Oorschot available by ftp from K.U.Leuven: ftp server: ftp.esat.kuleuven.ac.be directory: pub/COSIC/preneel file: mdxmac_crypto95.ps 2. DISCUSSION OF PHIL ROGAWAY'S COMMENTS I begin by reviewing Phil Rogaway's comments. 2.1 "AUTHENTICITY = INTEGRITY" [cf ROG 1.] I agree entirely with Phil here; the distinction between message authenticity and message integrity is vacuous here, and the proposed documents should be rewritten to use just a single term (message authenticity) for this notion. (I support Phil's recommendation 1.) 2.2 "ENCRYPTION DOES NOT GUARANTEE INTEGRITY" [cf ROG 2.] Again, Phil is on target here. The proposed documents have a confused and ambiguous discussion as to how authenticity is to be achieved. The confidentiality and authenticity techniques should be cleanly separated orthogonal mechanisms. (I strongly support Phil's recommendation 2.) 2.3. "IT IS WORTHLESS TO ENCRYPT KNOWN HEADERS" [cf ROG 3.] Here Phil recommends (his recommendation 3) that the encryption of known headers should be forbidden, on the grounds that AH, and not ESP, should be used for authenticity. I agree. (I support Phil's recommendation 3.) 2.4 "DON'T ENCRYPT MESSAGE AUTHENTICATION CODES" [cf ROG 4.] Although it is not uncommon to encrypt MACs, Phil is exhibiting excellent taste by suggesting that the scope of the authentication header should include the encrypted packet, rather than vice versa. While I don't know of any security weaknesses from the proposed organization, Phil's suggestion is cleaner and preferable. (I support Phil's recommendation 4.) 2.5 "DEFINE TRANSFORMS GENERICALLY" [cf ROG 5.] This recommendation is just common sense in support of better modularity in the description of what is being proposed. (I support Phil's recommendation 5.) 2.6 "MANDATE HARDWARE-EFFICIENT *AND* SOFTWARE-EFFICIENT TRANSFORMS"[cf ROG 6.] Efficiency is clearly an important issue when we are talking about operations that affect potentially every packet on the Internet. I think that the main point here is that there should be considerable freedom to choose alternative encryption techniques. (I have no problem with Phil's recommendation 6.) 2.7 "USE 128-BIT KEYS" [cf ROG 7] The key sizes should either be totally arbitrary (perhaps up to some generous limit, such as 4096 bits), at the user's discretion, or else be fixed at 128 bits as Phil proposes. I prefer the former approach, as it provides flexibility that may be necessary to accomodate different algorithms or other considerations (such as export control). (I think that the key sizes should be at the user's discretion.) 2.8 "THE MAC MECHANISM" [cf ROG 8] I begin by noting that Burt Kaliski and Matt Robshaw have written an excellent article that is relevant: "Message Authentication with MD5" by Burt Kaliski and Matt Robshaw CRYPTOBYTES, vol 1, number 1 (spring 1995), pages 5--8. (available from the authors at burt@rsa.com or matt@rsa.com) Phil criticizes the proposed use of MD5 as a MAC mechanism for: (1) being too slow, (2) having no theoretical foundations for the proposed mode of use of MD5. (3) having no manifest parallelism in the design of MD5. Unfortunately, at this point in time we faced with choosing from what is available. Phil proposes an excellent direction in his recommendation 8, but this is still research, not something that is ready for standardization. Phil says he is working on something, and this may turn out to be a better proposal than the current MD5 proposal. I have also been thinking about new hash function designs that might provide superior performance. However, at this point in time there are no concrete alternatives on the table. Keyed-MD5 may be a plausible choice at the current instant, but we should be prepared for the fact that in the very near future we may see significantly better alternatives proposed and sufficiently evaluated to be considered as replacements. (Also, the use of hash functions with more than 128 bits of output may become routine good practice.) There may be some confusion as to whether the current proposal is (1) MAC_a(x) = MD5(MD5(x).a) or (2) MAC_a(x) = MD5(a.x.a) Phil seems to say that the current proposal is (1), whereas [AH] says that it is (2); I believe Phil's comment here is based on an earlier proposal. The general question of how to best design a (keyed-)MAC from a one-way hash function is still quite open, and under vigorous research. The paper [PO] provides some excellent discussion and analysis of the proposed methods (1) and (2), among others. I think that our understanding of this area is likely to improve significantly in the very near term. The best solution in the end is likely to be an approach one that is designed to be a keyed-MAC from the start. We are still at the early stages of understanding how to do this, but I think that efficient and workable proposals may arise very quickly from the crypto community, now that attention has been drawn to this issue. (I think Phil's recommendation 8 is an excellent goal; but it doesn't answer the question as to what one should do something immediately, or if one should do something immediately.) The best approach may be not to commit to a keyed-MAC function at this time, but rather to explicitly nominate a "straw-man" proposal that is obviously weak and which MUST clearly be replaced at a later date (but soon!) when we know a little more. The straw-man algorithm could be used in trial implementations for testing purposes, but would provide no real authentication. For example, choosing as a straw-man algorithm MD5 with NO key input would be such a straw-man algorithm. This can be used as a place-holder until there is a better consensus in the cryptographic community as to how to proceed with a (keyed-)MAC. I believe that such an approach is better than nominating one of the current proposals (e.g. (2) above) as a "straw-man", since there might then be too much pressure to leave it in place, even if it turned out to have significant deficiencies under further analysis (such as is begun with [PO].) Having an explicitly weak "straw-man standard" in place as an acknowledgement that we are not really sure yet of what we are doing will put intense pressure on the crypto community to get its act together on this matter quickly, and I would hope that within six to eighteen months a consensus will evolve (so this issue could be resolved during '96 at the latest). The current workings of the ipsec community have generally been outside the purview of much of the crypto community, although a few cryptographers have paid attention to ipsec issues and have contributed generously of their time. The straw-man proposal would provide a very high-profile challenge that there is a still a felt need for efficient, secure, keyed-MACs for standardization purposes. 2.9 "THE ENCRYPTION MECHANISM" [cf ROG 9] Phil suggests 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." I agree. The proposal to use triple-DES in a mode that is potentially compatible with single-DES (due originally, I believe, to Walt Tuchman), can satisfy those users who want the efficiency (and security) of single-DES. (I agree with Phil's recommendation number 9.) Phil also criticizes the proposal for lack of specificity in describing how the DES-CBC is to be performed. I think that his comments here are well-motivated. (I agree with Phil's recommendation number 10, although I think that this is a minor point.) 3. ADDITONAL COMMENTS AND DISCUSSION I give here some additional comments, in no particular order. Some of these may reflect real concern about the security or feasibility of the proposed schemes, whereas others may merely reflect my misunderstanding of the proposal. Some of these comments may repeat themes already addressed above. 3.1 KEY DISTRIBUTION / KEY AGREEMENT These proposals are incomplete and essentially unusable without at least one specific proposal for non-manual key distribution or key agreement. While individual parties can clearly set up ad-hoc mechanism for key distribution or key agreement, the proposals studied here are not going to have any widespread deployment or utility until some standards for key distribution or key agreement are also available. While there is some discussion of this issue in [SA], there is nothing yet usable provided in terms of a proposal for a standard. I think that the current proposals should be held in abeyance (and worked on) until a complete package including key distribution and/or key agreement is also ready for consideration; I see little harm, and much potential good, in doing so. 3.2 LACK OF SPECIFICITY OR CLARITY There are many places where the proposals are insufficiently clear about what is intended, so much so that an implementor can not proceed. Here is a small list of items I noticed. (This is not intended to be comprehensive.) [SA] p 6: "SHOULD let that SPI become stale..." (when is an SPI stale?) [AH] (page 6) It is recommended here and in other places [e.g. AHMD p. 1] to use "pseudo-random" values (here for the SPI, in AHMD for the authentication key). How is a user to pick a "pseudo-random" value? Are counters suitable for the SPI? Is a linear-congruential generator suitable? (page 7-8) "This requirement is placed in order to allow for future IP optional headers which the receiver might not know about but the sender necessarily knows about if it is including such options in the packet." (I have no idea what this means.) [AHMD] [ESP] (page 6) "If strict red/black separation is being enforced..." (This term needs a reference or a definition.) (page 7) "If no key exists for this session or the attempt to decrypt fails," It is not clear what it means for the decryption to fail. The authors seem to imply that the it means that the next layer of protocol has a problem with the decrypted text, which is, in my opinion, a poor choice. I think that the only reason decryption should "fail" is that decryption is impossible (e.g. the ciphertext is not a multiple of the cipher block size). Authentication failure should be used to detect all other problems. (page 8) If user-oriented keying is not in use..." This paragraph makes no sense to me. It should be elaborated. What is the attack that is being prevented here? [ESPDES] (page 3) "The session key SHOULD be changed at least as frequently as every 2**32 datagrams." What is the justification for this condition? What attack is being prevented here? (page 3) "This field is considered to be transparent, though most users will not be able to make sense of its contents." This sentence pretends to be transparent, but this reader could not make sense of its contents. 3.3 HOST-ORIENTED vs USER-ORIENTED KEYING In [SA, section 4.4] it is stated that "support for user-oriented keying SHOULD be present in all IP implementations". Since "users" as such are not named principals at the IP protocol level, we are getting into strange territory here. It is not clear what "support for user-oriented keying" means. Does this merely mean that each user can be associated with a separate SPI, or does it mean that the host system must support secure multi-user processing somehow (e.g., so one user can not read another user's key by probing memory addresses assigned to the other user)? If I send encrypted traffice to an SPI that is associated with a particular user, what am I guaranteed about the security of that traffic from other users on the same host as the receiver? If nothing is guaranteed, why have this feature? The entire discussion on user-oriented keying seems confused (or at least confusing). This capability ought to be more carefully described, or dropped. I'm tempted to recommend just dropping it. More broadly, these documents need to have a clearer philosophical position as to what their goals are. In particular, these documents should make it clear how what they are doing differs from security protocols that work at higher layers of the protocol stack. It would seem sensible to think that a protocol at this IP layer should ONLY worry about security between hosts, and let protocols at higher layers take care of security between end-users or their applications. Bringing in users and userids to this protocol risks great confusion and muddled systems. 3.4 USE OF MD5 The language in [AH, section 4] says "If a block-oriented authentication algorithm (e.g. MD5 or MD4) is in use and the IP packet is not an integral number of blocks, the authentication data calculation is performed using zero bytes at the end to pad the length out to an integral number of blocks [Riv92]." This is VERY confused, since MD5 (and MD4) are byte-oriented algorithms that are specified to normally take variable-length byte-strings as input. It is not necessary (and may even be dangerous) for the user to supply his own padding! 3.5 AUDIT LOGS In [AH, page 9] and other places, it is stated that the system "MUST record the authentication failure in the system log or audit log." Given the rate at which bad packets can be delivered to a system by a malicious adversary, it may not be too hard for the adversary to fill up the disk of a complying implementation with the audit log. I think the "MUST" should be downgraded to "SHOULD". 4. CONCLUSIONS I feel that the proposed protocols are not sufficiently worked out to allow proceedings with them as a proposed standard. Ronald L. Rivest Room 324 545 Technology Square Cambridge, MA 02139 617-646-0504 http://theory.lcs.mit.edu/~rivest rivest@theory.lcs.mit.edu From ipsec-request@ans.net Fri Jun 30 21:52:26 1995 Received: from interlock.ans.net by ftp.ans.net with SMTP id AA14072 (5.65c/IDA-1.4.4 for ); Fri, 30 Jun 1995 18:04:17 -0400 Received: by interlock.ans.net id AA51137 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Fri, 30 Jun 1995 17:53:54 -0400 Message-Id: <199506302153.AA51137@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-4); Fri, 30 Jun 1995 17:53:54 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-3); Fri, 30 Jun 1995 17:53:54 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Fri, 30 Jun 1995 17:53:54 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Fri, 30 Jun 1995 17:53:54 -0400 To: rivest@theory.lcs.mit.edu (Ron Rivest) Cc: ipsec@ans.net Subject: Re: Some comments on IPSEC proposals In-Reply-To: Your message of "Fri, 30 Jun 1995 16:38:39 EDT." <199506302038.AA40195@interlock.ans.net> Reply-To: perry@imsi.com X-Reposting-Policy: redistribute only with permission Date: Fri, 30 Jun 1995 17:52:26 -0400 From: "Perry E. Metzger" It appears that by failing to be as vicious as possible about Phil Rogaway's lack of understanding of the architecture of IPSP that I have inspired people to take him seriously. It also appears that Phil has been lobbying people to have them comment. I can understand how even an intelligent reader, going through his comments, could become confused about the architectural issues here. However, let me say that I found his comments to be almost completely without merit. Other than a few comments about places where the text used ambiguous language (i.e. textual ambiguity) I found almost nothing of value in what he had to say. Ron Rivest writes: > I was stimulated in part to provide these comments by Phil Rogaway's note: > > [ROG] Problems with Proposed IP Cryptography > Phil doesn't understand the architecture. > 2.1 "AUTHENTICITY = INTEGRITY" [cf ROG 1.] > > I agree entirely with Phil here; the distinction between message authenticity > and message integrity is vacuous here, and the proposed documents should be > rewritten to use just a single term (message authenticity) for this notion. > (I support Phil's recommendation 1.) This is a serious problem? It's a textual change. > 2.2 "ENCRYPTION DOES NOT GUARANTEE INTEGRITY" [cf ROG 2.] > > Again, Phil is on target here. No he isn't. > The proposed documents have a confused and ambiguous discussion as > to how authenticity is to be achieved. They are completely clear. The problem is that Phil doesn't undstand that "ESP can provide authentication" doesn't mean "ESP provies authentication". As for how it is achieved, that depends on the individual transform. The DES transform, as defined, does *not* provide authentication. Each transform provides authentication and/or privacy in a transform dependant manner. > 2.3. "IT IS WORTHLESS TO ENCRYPT KNOWN HEADERS" [cf ROG 3.] > > Here Phil recommends (his recommendation 3) that the encryption of > known headers should be forbidden, on the grounds that AH, and not ESP, > should be used for authenticity. I agree. > (I support Phil's recommendation 3.) I'm not sure what you mean here. > 2.4 "DON'T ENCRYPT MESSAGE AUTHENTICATION CODES" [cf ROG 4.] > > Although it is not uncommon to encrypt MACs, Phil is exhibiting excellent > taste by suggesting that the scope of the authentication header should > include the encrypted packet, rather than vice versa. While I don't know > of any security weaknesses from the proposed organization, Phil's suggestion > is cleaner and preferable. This is a transform issue, not an architectural issue. Because Phil seemed to have no understanding of how the architecture works, of course... > (I support Phil's recommendation 4.) > > 2.5 "DEFINE TRANSFORMS GENERICALLY" [cf ROG 5.] > > This recommendation is just common sense in support of better modularity > in the description of what is being proposed. > (I support Phil's recommendation 5.) There is no good reason for this and there is lots of reason not to want it. > 2.6 "MANDATE HARDWARE-EFFICIENT *AND* SOFTWARE-EFFICIENT TRANSFORMS"[cf ROG 6 .] > > Efficiency is clearly an important issue when we are talking about > operations that affect potentially every packet on the Internet. > I think that the main point here is that there should be considerable > freedom to choose alternative encryption techniques. And the drafts make it clear that sides are free to negotiate any security transform they wish. What is the issue here? > (I have no problem with Phil's recommendation 6.) > > 2.7 "USE 128-BIT KEYS" [cf ROG 7] > > The key sizes should either be totally arbitrary (perhaps up to some > generous limit, such as 4096 bits), at the user's discretion, or else > be fixed at 128 bits as Phil proposes. Pardon, but as I've noted, this is a transform issue, not an architectural issue, and individual tranforms are free to pick what parameters they want. We are mandating a few baseline transforms for interoperability, but thats it. > 2.8 "THE MAC MECHANISM" [cf ROG 8] Let me point out that the fact that we have modular transforms renders this entire issue fairly unimportant. We can replace transforms as we like. > Keyed-MD5 may be a plausible choice at the current instant, but we should be > prepared for the fact that in the very near future we may see > significantly better alternatives proposed and sufficiently evaluated > to be considered as replacements. And that is why the architecture makes it easy to replace transforms at will. > 2.9 "THE ENCRYPTION MECHANISM" [cf ROG 9] > > Phil suggests 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." I agree. The proposal to use triple-DES > in a mode that is potentially compatible with single-DES (due originally, > I believe, to Walt Tuchman), can satisfy those users who want the efficiency > (and security) of single-DES. I wanted to mandate 3DES but the feeling was that it wasn't a good idea for a variety of reasons. A 3DES transform has been defined but is not being made explicitly part of the baseline -- however it is my expectation that vritually everyone is going to implement it. > 3.1 KEY DISTRIBUTION / KEY AGREEMENT > > These proposals are incomplete and essentially unusable without at > least one specific proposal for non-manual key distribution or key > agreement. We understand that. Thats why we are working on a key distribution proposal. We aren't stupid. It looks like Photuris, which is a variant on the Diffie-Hellman based STS protocol, is going to be used. > I think that the current proposals should be held in abeyance (and worked on) > until a complete package including key distribution and/or key agreement > is also ready for consideration; I see little harm, and much potential > good, in doing so. I see enormous harm. The current proposals do us a lot of good RIGHT NOW. There are dozens of manufacturers preparing to unleash incompatible versions of this same thing on the world. The IPSEC working group has delayed its output for years already -- there is no reason not to move forward to draft right now. > 3.2 LACK OF SPECIFICITY OR CLARITY > > There are many places where the proposals are insufficiently clear about > what is intended, so much so that an implementor can not proceed. Here > is a small list of items I noticed. (This is not intended to be comprehensive .) > [SA] > p 6: "SHOULD let that SPI become stale..." > (when is an SPI stale?) After sufficient time has elapsed for it to be reasonable that the counterparty would not attempt to reuse the value. It is hard to set a time value on this in stone because it is dependant on too many things that will change with time and technology. There are plenty of similar magic values in the TCP documents and we've survived it. > [AH] > (page 6) It is recommended here and in other > places [e.g. AHMD p. 1] to use "pseudo-random" values > (here for the SPI, Actually, the SPI is an *arbitrary* value, not a randomly generated number. The rest of the document makes this clear. in AHMD for the authentication key). > How is a user to pick a "pseudo-random" value? Security considerations makes it clear that the authentication key must selected as any other key is selected -- i.e. it can't be guessable and otherwise can be selected by some random process. We don't specify a process because that is up to the key management system, which might assign it using Diffie-Hellman, a voting mechanism, selection based on a key generator box on one of the machines, etc. > Are > counters suitable for the SPI? Is a linear-congruential generator > suitable? ANY mechanism is suitable. The documents make this clear. Some implementations may wish to assign them in a way that makes hashing efficient. Some may wish to assign them with a counter. Some may wish to assign them by counting upwards by the value of the national debt of Vanuatu modulo the phase of the moon. It makes no difference. > (page 7-8) "This requirement is placed in order to allow for > future IP optional headers which the receiver might not know about > but the sender necessarily knows about if it is including such > options in the packet." (I have no idea what this means.) You removed the context. " The sender MUST compute the authentication over the packet as that packet will appear at the receiver." The construction is awkward but makes it clear that you do the authentication over the packet as it will look when the receiver gets it, excluding things that will be stripped along the way. > [AHMD] > [ESP] > (page 6) "If strict red/black separation is being enforced..." > (This term needs a reference or a definition.) Its a DOD term of art. > (page 7) "If no key exists for this session or the attempt to > decrypt fails," > It is not clear what it means for the decryption to fail. ESP doesn't just mean "privacy", it can also mean "authentication". Also, there are checksums in the underlying packet, like IP layer checksums, that can fail. > The authors seem to imply that the it means that the next > layer of protocol has a problem with the decrypted text, which > is, in my opinion, a poor choice. What is your alternative? > I think that the only reason > decryption should "fail" is that decryption is impossible > (e.g. the ciphertext is not a multiple of the cipher block > size). Authentication failure should be used to detect all > other problems. This is a matter of pragmatism. In practice, there often won't be any other way to detect the problem. > (page 8) If user-oriented keying is not in use..." > This paragraph makes no sense to me. It should be elaborated. > What is the attack that is being prevented here? Bellovin's attack, among others. > [ESPDES] > (page 3) "The session key SHOULD be changed at least as frequently > as every 2**32 datagrams." > What is the justification for this condition? What attack > is being prevented here? Attacks. 1)IV replication and 2) attacks based on excessive use of the key. Its a SHOULD, not a MUST. > (page 3) "This field is considered to be transparent, though most > users will not be able to make sense of its contents." > This sentence pretends to be transparent, but this reader could > not make sense of its contents. Do you grok the Transparent/Opaque boundary in the datagram? The IV is an arbitrary number and thus has no meaning, but it is in the transparent part of the datagram, not the opaque part. > 3.3 HOST-ORIENTED vs USER-ORIENTED KEYING > > In [SA, section 4.4] it is stated that "support for user-oriented keying > SHOULD be present in all IP implementations". > > Since "users" as such are not named principals at the IP protocol level, > we are getting into strange territory here. This has been discussed in detail. Please read the extremely extensive archives and IETF proceedings. > It is not clear what "support for user-oriented keying" means. Does > this merely mean that each user can be associated with a separate SPI, > or does it mean that the host system must support secure multi-user > processing somehow (e.g., so one user can not read another user's key > by probing memory addresses assigned to the other user)? Neither. It really means that there has to be support to allow use of different keys for different TCP or UDP sessions in process between two hosts. The reason is to allow users to avoid sharing keys. There are attacks, due to Bellovin, among others, if two mutually hostile users are sharing a key that they do not know. > The entire discussion on user-oriented keying seems confused (or at least > confusing). This capability ought to be more carefully described, or > dropped. I'm tempted to recommend just dropping it. Perhaps that is because you are stepping in to the middle of a discussion that lasted for a very long time (over a year) without having carefully read all the rationale behind all the components of the design. > More broadly, these documents need to have a clearer philosophical position > as to what their goals are. In particular, these documents should make it > clear how what they are doing differs from security protocols that work > at higher layers of the protocol stack. It would seem sensible to think > that a protocol at this IP layer should ONLY worry about security between > hosts, and let protocols at higher layers take care of security between > end-users or their applications. That isn't the goal. > Bringing in users and userids to this protocol risks great confusion > and muddled systems. Users and userids are NOT in this protocol. The requirement is much simpler than that and has several good justifications. > 3.4 USE OF MD5 > > The language in [AH, section 4] says "If a block-oriented authentication > algorithm (e.g. MD5 or MD4) is in use and the IP packet is not an integral > number of blocks, the authentication data calculation is performed using > zero bytes at the end to pad the length out to an integral number of blocks > [Riv92]." > > This is VERY confused, since MD5 (and MD4) are byte-oriented algorithms > that are specified to normally take variable-length byte-strings as input. > It is not necessary (and may even be dangerous) for the user to supply his > own padding! The examples were perhaps bad, but MACs in the general case may be block oriented. > 3.5 AUDIT LOGS > > In [AH, page 9] and other places, it is stated that the system "MUST > record the authentication failure in the system log or audit log." > > Given the rate at which bad packets can be delivered to a system by a > malicious adversary, it may not be too hard for the adversary to fill > up the disk of a complying implementation with the audit log. I think > the "MUST" should be downgraded to "SHOULD". The requirement is prehaps inapropriate. > 4. CONCLUSIONS > > I feel that the proposed protocols are not sufficiently worked out to > allow proceedings with them as a proposed standard. 1) We are attempting to proceed with them as a draft standard. 2) a proposed or draft standard is not a standard. Perry From ipsec-request@ans.net Fri Jun 30 22:51:53 1995 Received: from interlock.ans.net by ftp.ans.net with SMTP id AA12679 (5.65c/IDA-1.4.4 for ); Fri, 30 Jun 1995 19:04:00 -0400 Received: by interlock.ans.net id AA12437 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Fri, 30 Jun 1995 18:52:18 -0400 Message-Id: <199506302252.AA12437@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-3); Fri, 30 Jun 1995 18:52:18 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Fri, 30 Jun 1995 18:52:18 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Fri, 30 Jun 1995 18:52:18 -0400 Date: Fri, 30 Jun 1995 15:51:53 -0700 From: Hilarie Orman To: perry@imsi.com Cc: rivest@theory.lcs.mit.edu, ipsec@ans.net In-Reply-To: Yourmessage <199506302153.AA51137@interlock.ans.net> Subject: Re: Some comments on IPSEC proposals > It appears that by failing to be as vicious as possible ... No, the wolverine approach to technical consensus has been highly unprofitable in this group. A revival may well be the end of it. Almost everyone who has read the drafts has been confused by many of the points that Ron and Phil have raised. I, too, would like to see almost all of these things clarified. I'd be willing to take another editorial pass over the arch and mode docs, perhaps less tentative this time, now that I've some implementation experience. I'm don't think that the documents should be held up if there is an obvious and ongoing good faith effort to address the concerns. I'd like to hear more discussion of the relevance of recent work MD5 collisions, and to thank Paul and Hugo for making some of the background material available. From ipsec-request@ans.net Fri Jun 30 23:03:53 1995 Received: from interlock.ans.net by ftp.ans.net with SMTP id AA04801 (5.65c/IDA-1.4.4 for ); Fri, 30 Jun 1995 19:12:51 -0400 Received: by interlock.ans.net id AA32236 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Fri, 30 Jun 1995 19:04:03 -0400 Message-Id: <199506302304.AA32236@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-4); Fri, 30 Jun 1995 19:04:03 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-3); Fri, 30 Jun 1995 19:04:03 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Fri, 30 Jun 1995 19:04:03 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Fri, 30 Jun 1995 19:04:03 -0400 To: Hilarie Orman Cc: rivest@theory.lcs.mit.edu, ipsec@ans.net Subject: Re: Some comments on IPSEC proposals In-Reply-To: Your message of "Fri, 30 Jun 1995 15:51:53 PDT." <9506302251.AA00044@uncial.CS.Arizona.EDU> Reply-To: perry@imsi.com X-Reposting-Policy: redistribute only with permission Date: Fri, 30 Jun 1995 19:03:53 -0400 From: "Perry E. Metzger" Hilarie Orman writes: > > It appears that by failing to be as vicious as possible ... > > No, the wolverine approach to technical consensus has been highly > unprofitable in this group. A revival may well be the end of it. > > Almost everyone who has read the drafts has been confused by many of > the points that Ron and Phil have raised. I, too, would like to see > almost all of these things clarified. I've got no problems with clarifying the language. Language can almost always stand to be improved. I have problems, however, with Phil Rogaway's characterization of difficulties in wording as fatal flaws in the architecture, which they obviously are not. I also see a clear distinction between a minor but very useful techincal change like Hugo's and Phil's desire to interpose another layer of indirection purely for the sake of having "generic" transforms. > I'd be willing to take another editorial pass over the arch and mode > docs, perhaps less tentative this time, now that I've some > implementation experience. The documents could use lots of little wording changes. However, I believe we both agree that... > I don't think that the documents should be held up if there is an > obvious and ongoing good faith effort to address the concerns. In any case, we are discussing going to the lowest of the three stages of standardization. There is plenty of opportunity even for significant technical improvements, let alone wording changes, before the thing becomes a standard. We need a lot more implementation experience before we can really complete that portion of the work. Perry From ipsec-request@ans.net Fri Jun 30 11:49:32 1995 Received: from interlock.ans.net by ftp.ans.net with SMTP id AA05109 (5.65c/IDA-1.4.4 for ); Fri, 30 Jun 1995 19:42:13 -0400 Received: by interlock.ans.net id AA10470 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Fri, 30 Jun 1995 19:32:24 -0400 Message-Id: <199506302332.AA10470@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-8); Fri, 30 Jun 1995 19:32:24 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-7); Fri, 30 Jun 1995 19:32:24 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-6); Fri, 30 Jun 1995 19:32:24 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-5); Fri, 30 Jun 1995 19:32:24 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-4); Fri, 30 Jun 1995 19:32:24 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-3); Fri, 30 Jun 1995 19:32:24 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Fri, 30 Jun 1995 19:32:24 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Fri, 30 Jun 1995 19:32:24 -0400 Date: Fri, 30 Jun 95 15:49:32 EDT Sender: ietf-request@IETF.CNRI.Reston.VA.US From: hugo@watson.ibm.com To: IPSEC@ans.net, iesg@CNRI.Reston.VA.US, ietf@CNRI.Reston.VA.US Subject: Rationale behind draft-krawczyk-keyed-md5-00.txt I am appending here a high-level and informal presentation of the rationale and analysis of keyed-MD5 that makes the basis for the choice of the particular mode of keyed-MD5 (for message authentication) presented in draft-krawczyk-keyed-md5-00.txt. I assume the reader is familiar with the iterative structure of MD5 but not necessarily with the details of the compression function. All the information that follows is based on the upcoming paper [BCK] by Bellare, Canetti and Krawczyk (as referenced in the above draft). Hugo ANALYSIS OF KEYED MD5 (sketch) ****************************** The basic issue with analyzing keyed-MD5 as a message authentication function is that it builds on MD5, a function that was originally designed for a different goal, namely, as a *keyless* collision-resistant hash function. What follows is a high-level and informal description of the analysis in [BCK] which is intended to identify the cryptographic requirements from a function as MD5 (more precisely, its compression function) that would guarantee that keyed-MD5 be a good MAC. The specific mode of keyed-MD5 presented in draft-krawczyk-keyed-md5-00.txt is an adaptation of the results of this analysis. KEYED COMPRESSION FUNCTIONS AND PSEUDORANDOM FUNCTIONS: Our approach for the analysis of keyed-MD5 (or keying any other iterative hash function) is to look at the compression function as a function *keyed via its IV* (the initial registers of MD5). We consider the set of the resultant (compression) functions (one function for each 128 bit key) as a "family of pseudorandom functions". This is a well-known notion in cryptography which captures the "proximity" of such functions to a set of truly random functions, and generalizes the more common concept of pseudorandom generators. The notion of security of a pseudorandom function (more precisely, a family of such functions) can be related to the famous Turing test for "intelligent computers". In Turing's test a human asks questions and gets responses; then this human has to decide if he was talking to another human being or to a machine. A computer that passes such a test, i.e., is not distinguished from a human being, is proven "intelligent". With pseudorandom functions the game is similar. But the one that asks the questions (inputs to the function) is the adversary and the responses may come from a truly random function or from a pseudorandom function (whose key is unknown to the adversary). The adversary wins if he decided correctly (with probability better than half!) on whether the function used was truly random or pseudorandom. The adversary could distinguish the pseudorandom function from random by recovering the secret key that defines the function, or just by being able to predict its output, etc. The parameters that define the adversary success are the resources it uses: time and number of queries, and the probability (beyond half) with which it successfully distinguishes. This probability is denoted by eps (this eps is a function of the adversary resources, the family of pseudorandom functions in use, the length of key, etc). An example of a (conjectured) good family of pseudorandom functions (or permutations) is DES. In this example each DES key determines a function in the family. If you know the key then you can compute the function in any point, but if not you can hardly predict a single bit of output. DES in MAC-CBC mode is also an example of pseudorandom functions (and the reason why it makes a good MAC). MAC FUNCTION: In general, a good pseudorandom function (i.e., one with small eps for reasonable resources by the adversary) makes a good MAC. A MAC (for message authentication code) is a function that uses a secret key and computes tags or checksums on information that only parties possessing the secret key can generate. The game for the adversary (that doesn't know the key) is that he can request the result of the checksum computed on a sequence of messages of his choice. At the end, after asking enough queries, the adversary needs to come with a message that he didn't ask before, but for which he can generate the checksum by himself. (This represents a "chosen message attack", and the new message for which the adversary can generate the checksum is a "forged message"). The more time and/or queries an adversary needs to reach a certain probability of forging a message the better the MAC function is. The goal of the design of keyed-MD5 is to come with a scheme that makes a good MAC. FROM PSEUDORANDOM COMPRESSION FUNCTION TO SECURE MAC: What we [BCK] essentially prove is that *if the keyed compression function* of MD5 makes a good pseudorandom function, then its iterations preserve this condition, and then the whole keyed-MD5 function makes a good MAC. Moreover, we give a precise reduction of the form: if you give me a forgery attack on keyed-MD5 we construct from it an explicit distinguishing attack on the basic compression function, where the success parameters (eps, etc) of both attacks are precisely related in our analysis. This approach is a formalization of the intuitive reasoning that assumes MD5 and similar functions to "behave as random functions". The pure intuitive approach, if not taken carefully, can be very misleading. In particular, one can prove (with different levels of sophistication) that the MD5 function does not behave as a random function (e.g., through extension attacks, statistical collisions, etc). However, in our formal analysis we prove that if the *keyed* compression function is close enough to random then the iterations are not far from random. This methodology of relating the security of the iterated function to that of the compression function is analogous to the traditional approach to constructing collision-resistant hash functions. For the later, the resistance of the compression function to collision search guarantees that property for the iterated function. In our case, it is the pseudorandom property that is propagated through the iterations, to provide a secure MAC. THE PSEUDORANDOMNESS ASSUMPTION: To this date we do not know of significant weaknesses of MD5's keyed compression function as a pseudorandom function. Still this property is a conjecture and not something that can be expected to be proven (soon). It is important to remark that it is the same property that is implicitly assumed by everybody that uses these functions to generate (pseudo) random keys (this is done "everywhere" these days: in Photuris, SSL, MKMP, the Preneel-van OOrschot paper [PV], just to mention some places that come to my mind). Interestingly, in the case of SHA the pseudorandomness of the function is claimed by the designers who recommend (in the DSS standard) the use of SHA for pseudorandom key generation. (In other words, if you consider your keys generated using MD5 as "random" then you can safely assume keyed-MD5 is a good MAC.) On the other hand, we do not prove the *necessity* of the pseudorandomness condition on the compression function in order for keyed-MD5 to be a secure MAC. Thus, it may be the case that even if the compression function is not pseudorandom still keyed-MD5 is a good MAC. Indeed, we have a more subtle analysis of some of the modes of keyed-MD5 in which pseudorandomness can be traded by different assumptions on the compression function. (I won't get into these details here). MAC AND COLLISION-RESISTANCE: It is important to remark that our approach reflects a significant distinction between keyed and keyless hash functions, namely, that the *traditional* security requirement of collision-resistance for keyless hash functions does not apply to a (keyed) MAC. Namely, the feasibility of finding (traditional) collisions in a given function is *not* (by itself) a sign that the function does not make a good MAC. The reason being that collision search (for MD5 and similar functions) concentrates on finding collision when the IV is *known* (or even chosen). In keyed-MD5 the IV is the key and then *random and secret*. A good search engine designed for known IV's (e.g. Van Oorschot-Wiener) may be useless to attack keyed-MD5. A good example for the independence between the collision resistance aspect and being a good MAC is (again) DES. If you know the key for DES-CBC-MAC you can find as many collisions as you want (using the invertibilty of DES with known key), but if you do not know the key, then collisions are hard to find (except for the fact that 64 bits of output allows for attacks in the order of 2^32 known/chosen message attacks). In other words, even if you hear tomorrow of (real) collisions in your favorite hash function it does not mean the function becomes insecure as a keyed function. (Though, that could be the case depending on the effect of that analysis on the pseudorandomness of the compression function). On the other hand, if collisions can be found (more than statistically expected) even if the IV is secret, that will have a significant negative effect on the security of the MAC. However, this kind of collisions are very different than the traditional ones. In particular, the adversary will need the "assistance" of the legal user to collect MAC results on known and/or chosen messages; this is in sharp contrast to known-IV collisions that can be searched by the adversary off-line and independently of any user or secret key. THE PROPOSED MODE OF KEYED-MD5: Now back to the keyed-MD5 function as described in my draft, namely, MD5(K,pad,text,K). As you can see this mode does not directly use a keyed-IV. Indeed, in order *not to change* the MD5 code, we are applying regular MD5 (with its regular "magic IV") to the actual key (which is padded to complete a full block), and the result of this first application becomes the "random secret IV" for the rest of the function. The appended key has two roles: to prevent extension attacks, and to serve as yet another (implicit) transformation on the output of MD5. Notice that the appended key is not padded (see below for its rationale). On the other hand, the padding of the prepended key is done due to *security reasons*. One is to achieve a transformation of the key into a pseudorandom IV (as explained above), the other is to avoid, in the case of short messages having a single iteration of MD5 (Kaliski and Robshaw pointed out that a single iteration may be more vulnerable to linear cryptanalysis - though, no such weakness is known today). The use of keys of length less that 128 bits is not recommended. Keys longer than 128 bits may not add any significant security given that the actual strength is given by the resultant IV which is 128 bit long. As said in an note I sent a few days ago, this particular choice of keyed-MD5 is intended to satisfy the following properties: * it is based on MD5 (or similar functions) * no change to the MD5 code required * no degradation of MD5 speed * simple key requirements Departing from these conditions, other constructions with better analytical properties can be suggested . For example, directly keying the MD5 function via its initial registers as proposed in [BCK] (and [PV]) (this requires less assumptions on the compression function of MD5 at the cost of a minimal change in MD5 code). However, the proposed scheme does not suffer of any practical weakness known today. On the other hand, if the above properties are to be relaxed then other designs which may prove more robust to future attacks are possible. This includes functions that may be completely unrelated to MD5 or similar hash functions; indeed such an approach may prove more secure and/or more efficient than basing the MAC on iterated hash functions. THE BIRTHDAY ATTACK: The best attack on keyed-MD5 that we know is a 2^64 chosen/known message attack that we sketch next. For simplicity, consider the application of keyed-MD5 (denoted KMD5) on messages of the form AB where A is a 512-bit block and B a 320-bit block. KMD5(AB) results on three iterations of the compression function of MD5 on the information (K, pad, A , B, K, length), where K is the 128-bit key, pad is '1' followed by 383 0's, and length is the 64 bit encoding of the total length (i.e, 960) as added by MD5. An attacker fixes a block B, and asks for the KMD5 of (Ai,B), for i=1,2,...,2^64, where the Ai's are 2^64 (arbitrary and different) blocks of 512 bits each. With good probability (by the birthday paradox), there exist i<>j with KMD5(Ai,B)=KMD5(Aj,B). In particular,with good probability it happens in this case that MD5(K,Ai)=MD5(K,Aj) (this is the result of the first iteration of MD5, i.e. no length appended). The adversary then asks for KMD5(Ai,C) for any value of C<>B. It then "guesses" the value of KMD5(Aj,C) to be the same as KMD5(Ai,C). If, indeed, it happened that (K,Ai) collided with (K,Aj) after the first iteration of MD5 then the adversary is right. That is, with high probability the adversary correctly forged KMD5(Aj,C). (Clearly, improvements for the adversary are possible such as testing whether the latter collision happened by using some other value of C, but the above is enough for a forgery with good probability). Strictly speaking the above attack requires 2^64 *chosen* messages since it requires keeping the last block unchanged. The blocks Ai, however, can be arbitrary. They need to be known to the adversary (at least those that generate collisions) but not to be chosen by him. In some scenarios a common trailing block may be available as part of standard encoding of information in which case the attack may become a known-only attack. (This is a reason not to pad the appended key in keyed-MD5 to a full block and for keeping the appended length of MD5). In addition, the attack works with messages of any length (even variable length) and the more common trailing blocks in the messages being queried the better the success probability of the attack. However, these attacks require, in any case, a huge amount of information (2^64 blocks) being MAC-ed with the *same key*. To be avoided one just needs to change keys before processing that much information. We note that the same type of attack applies to all proposed modes for keying MD5, and more generally it applies to all iterative constructions of MAC (including CBC-MAC). As said, it is the best attack we know on keyed-MD5. In [BCK] we show that this attack is optimal if the compression function is a truly random function. However, for functions like keyed-MD5 this may very well not be the case. It is important to note the essential difference between the above attack and the traditional birthday attacks on collision-resistant hash functions as MD5. In the latter, the processing time for the attack is also 2^64 but is independent of any secret information and requires no interaction with the legitimate party. Thus, it is far more realistic than against keyed-MD5. The birthday attack on iterative MAC described above was independently discovered by [BCK] and by Preneel and Van Oorschot. A detailed description of the attack can be found in the upcoming Crypto'95 paper by the later authors [PV]. REFERENCES [BCK] M. Bellare, R. Canetti, and H. Krawczyk, "Keying MD5 -- Message Authentication via Iterated Pseudo-randomness", manuscript. [PV] B. Preneel and P. Van Oorschot, "Building fast MACs from hash functions", to appear Crypto'95. From ipsec-request@ans.net Fri Jun 30 11:49:32 1995 Received: from interlock.ans.net by ftp.ans.net with SMTP id AA04964 (5.65c/IDA-1.4.4 for ); Fri, 30 Jun 1995 22:50:46 -0400 Received: by interlock.ans.net id AA12607 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Fri, 30 Jun 1995 22:42:42 -0400 Message-Id: <199507010242.AA12607@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-14); Fri, 30 Jun 1995 22:42:42 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-13); Fri, 30 Jun 1995 22:42:42 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-12); Fri, 30 Jun 1995 22:42:42 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-11); Fri, 30 Jun 1995 22:42:42 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-10); Fri, 30 Jun 1995 22:42:42 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-9); Fri, 30 Jun 1995 22:42:42 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-8); Fri, 30 Jun 1995 22:42:42 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-7); Fri, 30 Jun 1995 22:42:42 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-6); Fri, 30 Jun 1995 22:42:42 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-5); Fri, 30 Jun 1995 22:42:42 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-4); Fri, 30 Jun 1995 22:42:42 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-3); Fri, 30 Jun 1995 22:42:42 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Fri, 30 Jun 1995 22:42:42 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Fri, 30 Jun 1995 22:42:42 -0400 Date: Fri, 30 Jun 95 15:49:32 EDT X-Orig-Sender: ietf-request@IETF.CNRI.Reston.VA.US Sender: ietf-request@IETF.CNRI.Reston.VA.US From: hugo@watson.ibm.com To: IPSEC@ans.net, iesg@CNRI.Reston.VA.US, ietf@CNRI.Reston.VA.US Subject: Rationale behind draft-krawczyk-keyed-md5-00.txt I am appending here a high-level and informal presentation of the rationale and analysis of keyed-MD5 that makes the basis for the choice of the particular mode of keyed-MD5 (for message authentication) presented in draft-krawczyk-keyed-md5-00.txt. I assume the reader is familiar with the iterative structure of MD5 but not necessarily with the details of the compression function. All the information that follows is based on the upcoming paper [BCK] by Bellare, Canetti and Krawczyk (as referenced in the above draft). Hugo ANALYSIS OF KEYED MD5 (sketch) ****************************** The basic issue with analyzing keyed-MD5 as a message authentication function is that it builds on MD5, a function that was originally designed for a different goal, namely, as a *keyless* collision-resistant hash function. What follows is a high-level and informal description of the analysis in [BCK] which is intended to identify the cryptographic requirements from a function as MD5 (more precisely, its compression function) that would guarantee that keyed-MD5 be a good MAC. The specific mode of keyed-MD5 presented in draft-krawczyk-keyed-md5-00.txt is an adaptation of the results of this analysis. KEYED COMPRESSION FUNCTIONS AND PSEUDORANDOM FUNCTIONS: Our approach for the analysis of keyed-MD5 (or keying any other iterative hash function) is to look at the compression function as a function *keyed via its IV* (the initial registers of MD5). We consider the set of the resultant (compression) functions (one function for each 128 bit key) as a "family of pseudorandom functions". This is a well-known notion in cryptography which captures the "proximity" of such functions to a set of truly random functions, and generalizes the more common concept of pseudorandom generators. The notion of security of a pseudorandom function (more precisely, a family of such functions) can be related to the famous Turing test for "intelligent computers". In Turing's test a human asks questions and gets responses; then this human has to decide if he was talking to another human being or to a machine. A computer that passes such a test, i.e., is not distinguished from a human being, is proven "intelligent". With pseudorandom functions the game is similar. But the one that asks the questions (inputs to the function) is the adversary and the responses may come from a truly random function or from a pseudorandom function (whose key is unknown to the adversary). The adversary wins if he decided correctly (with probability better than half!) on whether the function used was truly random or pseudorandom. The adversary could distinguish the pseudorandom function from random by recovering the secret key that defines the function, or just by being able to predict its output, etc. The parameters that define the adversary success are the resources it uses: time and number of queries, and the probability (beyond half) with which it successfully distinguishes. This probability is denoted by eps (this eps is a function of the adversary resources, the family of pseudorandom functions in use, the length of key, etc). An example of a (conjectured) good family of pseudorandom functions (or permutations) is DES. In this example each DES key determines a function in the family. If you know the key then you can compute the function in any point, but if not you can hardly predict a single bit of output. DES in MAC-CBC mode is also an example of pseudorandom functions (and the reason why it makes a good MAC). MAC FUNCTION: In general, a good pseudorandom function (i.e., one with small eps for reasonable resources by the adversary) makes a good MAC. A MAC (for message authentication code) is a function that uses a secret key and computes tags or checksums on information that only parties possessing the secret key can generate. The game for the adversary (that doesn't know the key) is that he can request the result of the checksum computed on a sequence of messages of his choice. At the end, after asking enough queries, the adversary needs to come with a message that he didn't ask before, but for which he can generate the checksum by himself. (This represents a "chosen message attack", and the new message for which the adversary can generate the checksum is a "forged message"). The more time and/or queries an adversary needs to reach a certain probability of forging a message the better the MAC function is. The goal of the design of keyed-MD5 is to come with a scheme that makes a good MAC. FROM PSEUDORANDOM COMPRESSION FUNCTION TO SECURE MAC: What we [BCK] essentially prove is that *if the keyed compression function* of MD5 makes a good pseudorandom function, then its iterations preserve this condition, and then the whole keyed-MD5 function makes a good MAC. Moreover, we give a precise reduction of the form: if you give me a forgery attack on keyed-MD5 we construct from it an explicit distinguishing attack on the basic compression function, where the success parameters (eps, etc) of both attacks are precisely related in our analysis. This approach is a formalization of the intuitive reasoning that assumes MD5 and similar functions to "behave as random functions". The pure intuitive approach, if not taken carefully, can be very misleading. In particular, one can prove (with different levels of sophistication) that the MD5 function does not behave as a random function (e.g., through extension attacks, statistical collisions, etc). However, in our formal analysis we prove that if the *keyed* compression function is close enough to random then the iterations are not far from random. This methodology of relating the security of the iterated function to that of the compression function is analogous to the traditional approach to constructing collision-resistant hash functions. For the later, the resistance of the compression function to collision search guarantees that property for the iterated function. In our case, it is the pseudorandom property that is propagated through the iterations, to provide a secure MAC. THE PSEUDORANDOMNESS ASSUMPTION: To this date we do not know of significant weaknesses of MD5's keyed compression function as a pseudorandom function. Still this property is a conjecture and not something that can be expected to be proven (soon). It is important to remark that it is the same property that is implicitly assumed by everybody that uses these functions to generate (pseudo) random keys (this is done "everywhere" these days: in Photuris, SSL, MKMP, the Preneel-van OOrschot paper [PV], just to mention some places that come to my mind). Interestingly, in the case of SHA the pseudorandomness of the function is claimed by the designers who recommend (in the DSS standard) the use of SHA for pseudorandom key generation. (In other words, if you consider your keys generated using MD5 as "random" then you can safely assume keyed-MD5 is a good MAC.) On the other hand, we do not prove the *necessity* of the pseudorandomness condition on the compression function in order for keyed-MD5 to be a secure MAC. Thus, it may be the case that even if the compression function is not pseudorandom still keyed-MD5 is a good MAC. Indeed, we have a more subtle analysis of some of the modes of keyed-MD5 in which pseudorandomness can be traded by different assumptions on the compression function. (I won't get into these details here). MAC AND COLLISION-RESISTANCE: It is important to remark that our approach reflects a significant distinction between keyed and keyless hash functions, namely, that the *traditional* security requirement of collision-resistance for keyless hash functions does not apply to a (keyed) MAC. Namely, the feasibility of finding (traditional) collisions in a given function is *not* (by itself) a sign that the function does not make a good MAC. The reason being that collision search (for MD5 and similar functions) concentrates on finding collision when the IV is *known* (or even chosen). In keyed-MD5 the IV is the key and then *random and secret*. A good search engine designed for known IV's (e.g. Van Oorschot-Wiener) may be useless to attack keyed-MD5. A good example for the independence between the collision resistance aspect and being a good MAC is (again) DES. If you know the key for DES-CBC-MAC you can find as many collisions as you want (using the invertibilty of DES with known key), but if you do not know the key, then collisions are hard to find (except for the fact that 64 bits of output allows for attacks in the order of 2^32 known/chosen message attacks). In other words, even if you hear tomorrow of (real) collisions in your favorite hash function it does not mean the function becomes insecure as a keyed function. (Though, that could be the case depending on the effect of that analysis on the pseudorandomness of the compression function). On the other hand, if collisions can be found (more than statistically expected) even if the IV is secret, that will have a significant negative effect on the security of the MAC. However, this kind of collisions are very different than the traditional ones. In particular, the adversary will need the "assistance" of the legal user to collect MAC results on known and/or chosen messages; this is in sharp contrast to known-IV collisions that can be searched by the adversary off-line and independently of any user or secret key. THE PROPOSED MODE OF KEYED-MD5: Now back to the keyed-MD5 function as described in my draft, namely, MD5(K,pad,text,K). As you can see this mode does not directly use a keyed-IV. Indeed, in order *not to change* the MD5 code, we are applying regular MD5 (with its regular "magic IV") to the actual key (which is padded to complete a full block), and the result of this first application becomes the "random secret IV" for the rest of the function. The appended key has two roles: to prevent extension attacks, and to serve as yet another (implicit) transformation on the output of MD5. Notice that the appended key is not padded (see below for its rationale). On the other hand, the padding of the prepended key is done due to *security reasons*. One is to achieve a transformation of the key into a pseudorandom IV (as explained above), the other is to avoid, in the case of short messages having a single iteration of MD5 (Kaliski and Robshaw pointed out that a single iteration may be more vulnerable to linear cryptanalysis - though, no such weakness is known today). The use of keys of length less that 128 bits is not recommended. Keys longer than 128 bits may not add any significant security given that the actual strength is given by the resultant IV which is 128 bit long. As said in an note I sent a few days ago, this particular choice of keyed-MD5 is intended to satisfy the following properties: * it is based on MD5 (or similar functions) * no change to the MD5 code required * no degradation of MD5 speed * simple key requirements Departing from these conditions, other constructions with better analytical properties can be suggested . For example, directly keying the MD5 function via its initial registers as proposed in [BCK] (and [PV]) (this requires less assumptions on the compression function of MD5 at the cost of a minimal change in MD5 code). However, the proposed scheme does not suffer of any practical weakness known today. On the other hand, if the above properties are to be relaxed then other designs which may prove more robust to future attacks are possible. This includes functions that may be completely unrelated to MD5 or similar hash functions; indeed such an approach may prove more secure and/or more efficient than basing the MAC on iterated hash functions. THE BIRTHDAY ATTACK: The best attack on keyed-MD5 that we know is a 2^64 chosen/known message attack that we sketch next. For simplicity, consider the application of keyed-MD5 (denoted KMD5) on messages of the form AB where A is a 512-bit block and B a 320-bit block. KMD5(AB) results on three iterations of the compression function of MD5 on the information (K, pad, A , B, K, length), where K is the 128-bit key, pad is '1' followed by 383 0's, and length is the 64 bit encoding of the total length (i.e, 960) as added by MD5. An attacker fixes a block B, and asks for the KMD5 of (Ai,B), for i=1,2,...,2^64, where the Ai's are 2^64 (arbitrary and different) blocks of 512 bits each. With good probability (by the birthday paradox), there exist i<>j with KMD5(Ai,B)=KMD5(Aj,B). In particular,with good probability it happens in this case that MD5(K,Ai)=MD5(K,Aj) (this is the result of the first iteration of MD5, i.e. no length appended). The adversary then asks for KMD5(Ai,C) for any value of C<>B. It then "guesses" the value of KMD5(Aj,C) to be the same as KMD5(Ai,C). If, indeed, it happened that (K,Ai) collided with (K,Aj) after the first iteration of MD5 then the adversary is right. That is, with high probability the adversary correctly forged KMD5(Aj,C). (Clearly, improvements for the adversary are possible such as testing whether the latter collision happened by using some other value of C, but the above is enough for a forgery with good probability). Strictly speaking the above attack requires 2^64 *chosen* messages since it requires keeping the last block unchanged. The blocks Ai, however, can be arbitrary. They need to be known to the adversary (at least those that generate collisions) but not to be chosen by him. In some scenarios a common trailing block may be available as part of standard encoding of information in which case the attack may become a known-only attack. (This is a reason not to pad the appended key in keyed-MD5 to a full block and for keeping the appended length of MD5). In addition, the attack works with messages of any length (even variable length) and the more common trailing blocks in the messages being queried the better the success probability of the attack. However, these attacks require, in any case, a huge amount of information (2^64 blocks) being MAC-ed with the *same key*. To be avoided one just needs to change keys before processing that much information. We note that the same type of attack applies to all proposed modes for keying MD5, and more generally it applies to all iterative constructions of MAC (including CBC-MAC). As said, it is the best attack we know on keyed-MD5. In [BCK] we show that this attack is optimal if the compression function is a truly random function. However, for functions like keyed-MD5 this may very well not be the case. It is important to note the essential difference between the above attack and the traditional birthday attacks on collision-resistant hash functions as MD5. In the latter, the processing time for the attack is also 2^64 but is independent of any secret information and requires no interaction with the legitimate party. Thus, it is far more realistic than against keyed-MD5. The birthday attack on iterative MAC described above was independently discovered by [BCK] and by Preneel and Van Oorschot. A detailed description of the attack can be found in the upcoming Crypto'95 paper by the later authors [PV]. REFERENCES [BCK] M. Bellare, R. Canetti, and H. Krawczyk, "Keying MD5 -- Message Authentication via Iterated Pseudo-randomness", manuscript. [PV] B. Preneel and P. Van Oorschot, "Building fast MACs from hash functions", to appear Crypto'95. From ipsec-request@ans.net Fri Jun 30 11:49:32 1995 Received: from interlock.ans.net by ftp.ans.net with SMTP id AA13020 (5.65c/IDA-1.4.4 for ); Sat, 1 Jul 1995 01:43:04 -0400 Received: by interlock.ans.net id AA23187 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Sat, 1 Jul 1995 01:34:26 -0400 Message-Id: <199507010534.AA23187@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-20); Sat, 1 Jul 1995 01:34:26 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-19); Sat, 1 Jul 1995 01:34:26 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-18); Sat, 1 Jul 1995 01:34:26 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-17); Sat, 1 Jul 1995 01:34:26 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-16); Sat, 1 Jul 1995 01:34:26 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-15); Sat, 1 Jul 1995 01:34:26 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-14); Sat, 1 Jul 1995 01:34:26 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-13); Sat, 1 Jul 1995 01:34:26 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-12); Sat, 1 Jul 1995 01:34:26 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-11); Sat, 1 Jul 1995 01:34:26 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-10); Sat, 1 Jul 1995 01:34:26 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-9); Sat, 1 Jul 1995 01:34:26 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-8); Sat, 1 Jul 1995 01:34:26 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-7); Sat, 1 Jul 1995 01:34:26 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-6); Sat, 1 Jul 1995 01:34:26 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-5); Sat, 1 Jul 1995 01:34:26 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-4); Sat, 1 Jul 1995 01:34:26 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-3); Sat, 1 Jul 1995 01:34:26 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Sat, 1 Jul 1995 01:34:26 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Sat, 1 Jul 1995 01:34:26 -0400 Date: Fri, 30 Jun 95 15:49:32 EDT X-Orig-Sender: ietf-request@IETF.CNRI.Reston.VA.US X-Orig-Sender: ietf-request@IETF.CNRI.Reston.VA.US Sender: ietf-request@IETF.CNRI.Reston.VA.US From: hugo@watson.ibm.com To: IPSEC@ans.net, iesg@CNRI.Reston.VA.US, ietf@CNRI.Reston.VA.US Subject: Rationale behind draft-krawczyk-keyed-md5-00.txt I am appending here a high-level and informal presentation of the rationale and analysis of keyed-MD5 that makes the basis for the choice of the particular mode of keyed-MD5 (for message authentication) presented in draft-krawczyk-keyed-md5-00.txt. I assume the reader is familiar with the iterative structure of MD5 but not necessarily with the details of the compression function. All the information that follows is based on the upcoming paper [BCK] by Bellare, Canetti and Krawczyk (as referenced in the above draft). Hugo ANALYSIS OF KEYED MD5 (sketch) ****************************** The basic issue with analyzing keyed-MD5 as a message authentication function is that it builds on MD5, a function that was originally designed for a different goal, namely, as a *keyless* collision-resistant hash function. What follows is a high-level and informal description of the analysis in [BCK] which is intended to identify the cryptographic requirements from a function as MD5 (more precisely, its compression function) that would guarantee that keyed-MD5 be a good MAC. The specific mode of keyed-MD5 presented in draft-krawczyk-keyed-md5-00.txt is an adaptation of the results of this analysis. KEYED COMPRESSION FUNCTIONS AND PSEUDORANDOM FUNCTIONS: Our approach for the analysis of keyed-MD5 (or keying any other iterative hash function) is to look at the compression function as a function *keyed via its IV* (the initial registers of MD5). We consider the set of the resultant (compression) functions (one function for each 128 bit key) as a "family of pseudorandom functions". This is a well-known notion in cryptography which captures the "proximity" of such functions to a set of truly random functions, and generalizes the more common concept of pseudorandom generators. The notion of security of a pseudorandom function (more precisely, a family of such functions) can be related to the famous Turing test for "intelligent computers". In Turing's test a human asks questions and gets responses; then this human has to decide if he was talking to another human being or to a machine. A computer that passes such a test, i.e., is not distinguished from a human being, is proven "intelligent". With pseudorandom functions the game is similar. But the one that asks the questions (inputs to the function) is the adversary and the responses may come from a truly random function or from a pseudorandom function (whose key is unknown to the adversary). The adversary wins if he decided correctly (with probability better than half!) on whether the function used was truly random or pseudorandom. The adversary could distinguish the pseudorandom function from random by recovering the secret key that defines the function, or just by being able to predict its output, etc. The parameters that define the adversary success are the resources it uses: time and number of queries, and the probability (beyond half) with which it successfully distinguishes. This probability is denoted by eps (this eps is a function of the adversary resources, the family of pseudorandom functions in use, the length of key, etc). An example of a (conjectured) good family of pseudorandom functions (or permutations) is DES. In this example each DES key determines a function in the family. If you know the key then you can compute the function in any point, but if not you can hardly predict a single bit of output. DES in MAC-CBC mode is also an example of pseudorandom functions (and the reason why it makes a good MAC). MAC FUNCTION: In general, a good pseudorandom function (i.e., one with small eps for reasonable resources by the adversary) makes a good MAC. A MAC (for message authentication code) is a function that uses a secret key and computes tags or checksums on information that only parties possessing the secret key can generate. The game for the adversary (that doesn't know the key) is that he can request the result of the checksum computed on a sequence of messages of his choice. At the end, after asking enough queries, the adversary needs to come with a message that he didn't ask before, but for which he can generate the checksum by himself. (This represents a "chosen message attack", and the new message for which the adversary can generate the checksum is a "forged message"). The more time and/or queries an adversary needs to reach a certain probability of forging a message the better the MAC function is. The goal of the design of keyed-MD5 is to come with a scheme that makes a good MAC. FROM PSEUDORANDOM COMPRESSION FUNCTION TO SECURE MAC: What we [BCK] essentially prove is that *if the keyed compression function* of MD5 makes a good pseudorandom function, then its iterations preserve this condition, and then the whole keyed-MD5 function makes a good MAC. Moreover, we give a precise reduction of the form: if you give me a forgery attack on keyed-MD5 we construct from it an explicit distinguishing attack on the basic compression function, where the success parameters (eps, etc) of both attacks are precisely related in our analysis. This approach is a formalization of the intuitive reasoning that assumes MD5 and similar functions to "behave as random functions". The pure intuitive approach, if not taken carefully, can be very misleading. In particular, one can prove (with different levels of sophistication) that the MD5 function does not behave as a random function (e.g., through extension attacks, statistical collisions, etc). However, in our formal analysis we prove that if the *keyed* compression function is close enough to random then the iterations are not far from random. This methodology of relating the security of the iterated function to that of the compression function is analogous to the traditional approach to constructing collision-resistant hash functions. For the later, the resistance of the compression function to collision search guarantees that property for the iterated function. In our case, it is the pseudorandom property that is propagated through the iterations, to provide a secure MAC. THE PSEUDORANDOMNESS ASSUMPTION: To this date we do not know of significant weaknesses of MD5's keyed compression function as a pseudorandom function. Still this property is a conjecture and not something that can be expected to be proven (soon). It is important to remark that it is the same property that is implicitly assumed by everybody that uses these functions to generate (pseudo) random keys (this is done "everywhere" these days: in Photuris, SSL, MKMP, the Preneel-van OOrschot paper [PV], just to mention some places that come to my mind). Interestingly, in the case of SHA the pseudorandomness of the function is claimed by the designers who recommend (in the DSS standard) the use of SHA for pseudorandom key generation. (In other words, if you consider your keys generated using MD5 as "random" then you can safely assume keyed-MD5 is a good MAC.) On the other hand, we do not prove the *necessity* of the pseudorandomness condition on the compression function in order for keyed-MD5 to be a secure MAC. Thus, it may be the case that even if the compression function is not pseudorandom still keyed-MD5 is a good MAC. Indeed, we have a more subtle analysis of some of the modes of keyed-MD5 in which pseudorandomness can be traded by different assumptions on the compression function. (I won't get into these details here). MAC AND COLLISION-RESISTANCE: It is important to remark that our approach reflects a significant distinction between keyed and keyless hash functions, namely, that the *traditional* security requirement of collision-resistance for keyless hash functions does not apply to a (keyed) MAC. Namely, the feasibility of finding (traditional) collisions in a given function is *not* (by itself) a sign that the function does not make a good MAC. The reason being that collision search (for MD5 and similar functions) concentrates on finding collision when the IV is *known* (or even chosen). In keyed-MD5 the IV is the key and then *random and secret*. A good search engine designed for known IV's (e.g. Van Oorschot-Wiener) may be useless to attack keyed-MD5. A good example for the independence between the collision resistance aspect and being a good MAC is (again) DES. If you know the key for DES-CBC-MAC you can find as many collisions as you want (using the invertibilty of DES with known key), but if you do not know the key, then collisions are hard to find (except for the fact that 64 bits of output allows for attacks in the order of 2^32 known/chosen message attacks). In other words, even if you hear tomorrow of (real) collisions in your favorite hash function it does not mean the function becomes insecure as a keyed function. (Though, that could be the case depending on the effect of that analysis on the pseudorandomness of the compression function). On the other hand, if collisions can be found (more than statistically expected) even if the IV is secret, that will have a significant negative effect on the security of the MAC. However, this kind of collisions are very different than the traditional ones. In particular, the adversary will need the "assistance" of the legal user to collect MAC results on known and/or chosen messages; this is in sharp contrast to known-IV collisions that can be searched by the adversary off-line and independently of any user or secret key. THE PROPOSED MODE OF KEYED-MD5: Now back to the keyed-MD5 function as described in my draft, namely, MD5(K,pad,text,K). As you can see this mode does not directly use a keyed-IV. Indeed, in order *not to change* the MD5 code, we are applying regular MD5 (with its regular "magic IV") to the actual key (which is padded to complete a full block), and the result of this first application becomes the "random secret IV" for the rest of the function. The appended key has two roles: to prevent extension attacks, and to serve as yet another (implicit) transformation on the output of MD5. Notice that the appended key is not padded (see below for its rationale). On the other hand, the padding of the prepended key is done due to *security reasons*. One is to achieve a transformation of the key into a pseudorandom IV (as explained above), the other is to avoid, in the case of short messages having a single iteration of MD5 (Kaliski and Robshaw pointed out that a single iteration may be more vulnerable to linear cryptanalysis - though, no such weakness is known today). The use of keys of length less that 128 bits is not recommended. Keys longer than 128 bits may not add any significant security given that the actual strength is given by the resultant IV which is 128 bit long. As said in an note I sent a few days ago, this particular choice of keyed-MD5 is intended to satisfy the following properties: * it is based on MD5 (or similar functions) * no change to the MD5 code required * no degradation of MD5 speed * simple key requirements Departing from these conditions, other constructions with better analytical properties can be suggested . For example, directly keying the MD5 function via its initial registers as proposed in [BCK] (and [PV]) (this requires less assumptions on the compression function of MD5 at the cost of a minimal change in MD5 code). However, the proposed scheme does not suffer of any practical weakness known today. On the other hand, if the above properties are to be relaxed then other designs which may prove more robust to future attacks are possible. This includes functions that may be completely unrelated to MD5 or similar hash functions; indeed such an approach may prove more secure and/or more efficient than basing the MAC on iterated hash functions. THE BIRTHDAY ATTACK: The best attack on keyed-MD5 that we know is a 2^64 chosen/known message attack that we sketch next. For simplicity, consider the application of keyed-MD5 (denoted KMD5) on messages of the form AB where A is a 512-bit block and B a 320-bit block. KMD5(AB) results on three iterations of the compression function of MD5 on the information (K, pad, A , B, K, length), where K is the 128-bit key, pad is '1' followed by 383 0's, and length is the 64 bit encoding of the total length (i.e, 960) as added by MD5. An attacker fixes a block B, and asks for the KMD5 of (Ai,B), for i=1,2,...,2^64, where the Ai's are 2^64 (arbitrary and different) blocks of 512 bits each. With good probability (by the birthday paradox), there exist i<>j with KMD5(Ai,B)=KMD5(Aj,B). In particular,with good probability it happens in this case that MD5(K,Ai)=MD5(K,Aj) (this is the result of the first iteration of MD5, i.e. no length appended). The adversary then asks for KMD5(Ai,C) for any value of C<>B. It then "guesses" the value of KMD5(Aj,C) to be the same as KMD5(Ai,C). If, indeed, it happened that (K,Ai) collided with (K,Aj) after the first iteration of MD5 then the adversary is right. That is, with high probability the adversary correctly forged KMD5(Aj,C). (Clearly, improvements for the adversary are possible such as testing whether the latter collision happened by using some other value of C, but the above is enough for a forgery with good probability). Strictly speaking the above attack requires 2^64 *chosen* messages since it requires keeping the last block unchanged. The blocks Ai, however, can be arbitrary. They need to be known to the adversary (at least those that generate collisions) but not to be chosen by him. In some scenarios a common trailing block may be available as part of standard encoding of information in which case the attack may become a known-only attack. (This is a reason not to pad the appended key in keyed-MD5 to a full block and for keeping the appended length of MD5). In addition, the attack works with messages of any length (even variable length) and the more common trailing blocks in the messages being queried the better the success probability of the attack. However, these attacks require, in any case, a huge amount of information (2^64 blocks) being MAC-ed with the *same key*. To be avoided one just needs to change keys before processing that much information. We note that the same type of attack applies to all proposed modes for keying MD5, and more generally it applies to all iterative constructions of MAC (including CBC-MAC). As said, it is the best attack we know on keyed-MD5. In [BCK] we show that this attack is optimal if the compression function is a truly random function. However, for functions like keyed-MD5 this may very well not be the case. It is important to note the essential difference between the above attack and the traditional birthday attacks on collision-resistant hash functions as MD5. In the latter, the processing time for the attack is also 2^64 but is independent of any secret information and requires no interaction with the legitimate party. Thus, it is far more realistic than against keyed-MD5. The birthday attack on iterative MAC described above was independently discovered by [BCK] and by Preneel and Van Oorschot. A detailed description of the attack can be found in the upcoming Crypto'95 paper by the later authors [PV]. REFERENCES [BCK] M. Bellare, R. Canetti, and H. Krawczyk, "Keying MD5 -- Message Authentication via Iterated Pseudo-randomness", manuscript. [PV] B. Preneel and P. Van Oorschot, "Building fast MACs from hash functions", to appear Crypto'95.