Received: from ietf.nri.reston.va.us by IETF.CNRI.Reston.VA.US id aa01310; 8 Jun 95 6:57 EDT Received: from CNRI.Reston.VA.US by IETF.CNRI.Reston.VA.US id aa01306; 8 Jun 95 6:57 EDT Received: from interlock.ans.net by CNRI.Reston.VA.US id aa03142; 8 Jun 95 6:57 EDT 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 Sender:ietf-archive-request@IETF.CNRI.Reston.VA.US 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   Received: from ietf.nri.reston.va.us by IETF.CNRI.Reston.VA.US id aa05029; 8 Jun 95 12:07 EDT Received: from CNRI.Reston.VA.US by IETF.CNRI.Reston.VA.US id aa05025; 8 Jun 95 12:07 EDT Received: from interlock.ans.net by CNRI.Reston.VA.US id aa09392; 8 Jun 95 12:07 EDT 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 Sender:ietf-archive-request@IETF.CNRI.Reston.VA.US 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   Received: from ietf.nri.reston.va.us by IETF.CNRI.Reston.VA.US id aa07973; 9 Jun 95 12:29 EDT Received: from CNRI.Reston.VA.US by IETF.CNRI.Reston.VA.US id aa07969; 9 Jun 95 12:29 EDT Received: from interlock.ans.net by CNRI.Reston.VA.US id aa09543; 9 Jun 95 12:29 EDT 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 Sender:ietf-archive-request@IETF.CNRI.Reston.VA.US From: Luke Nelson Subject: subscribe X-Mailer: subscribe ipsec   Received: from ietf.nri.reston.va.us by IETF.CNRI.Reston.VA.US id aa01754; 12 Jun 95 14:17 EDT Received: from CNRI.Reston.VA.US by IETF.CNRI.Reston.VA.US id aa01750; 12 Jun 95 14:17 EDT Received: from interlock.ans.net by CNRI.Reston.VA.US id aa05536; 12 Jun 95 12:07 EDT 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 Sender:ietf-archive-request@IETF.CNRI.Reston.VA.US 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   Received: from ietf.nri.reston.va.us by IETF.CNRI.Reston.VA.US id aa09167; 16 Jun 95 16:04 EDT Received: from CNRI.Reston.VA.US by IETF.CNRI.Reston.VA.US id aa09163; 16 Jun 95 16:04 EDT Received: from interlock.ans.net by CNRI.Reston.VA.US id aa15526; 16 Jun 95 16:04 EDT 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 Sender:ietf-archive-request@IETF.CNRI.Reston.VA.US 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 X-Orig-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   Received: from ietf.nri.reston.va.us by IETF.CNRI.Reston.VA.US id aa01825; 18 Jun 95 11:11 EDT Received: from CNRI.Reston.VA.US by IETF.CNRI.Reston.VA.US id aa01821; 18 Jun 95 11:11 EDT Received: from interlock.ans.net by CNRI.Reston.VA.US id aa05847; 18 Jun 95 11:11 EDT Received: by interlock.ans.net id (InterLock SMTP Gateway 3.0 for IETF-Archive@cnri.reston.va.us); Sun, 18 Jun 1995 11:11:33 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Sun, 18 Jun 1995 11:11:33 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Sun, 18 Jun 1995 11:11:33 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-0); Sun, 18 Jun 1995 11:11:33 -0400 Date: Sun, 18 Jun 1995 06:35:08 -0700 Sender:ietf-archive-request@IETF.CNRI.Reston.VA.US 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 Message-ID: <9506181111.aa05847@CNRI.Reston.VA.US> 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.   Received: from ietf.nri.reston.va.us by IETF.CNRI.Reston.VA.US id aa02719; 18 Jun 95 14:04 EDT Received: from CNRI.Reston.VA.US by IETF.CNRI.Reston.VA.US id aa02715; 18 Jun 95 14:04 EDT Received: from pad-thai.cam.ov.com by CNRI.Reston.VA.US id aa07903; 18 Jun 95 14:04 EDT Received: from MIT.EDU by pad-thai.cam.ov.com (8.6.12/) with SMTP id ; Sun, 18 Jun 1995 09:36:06 -0400 Received: from darkstar.isi.edu by MIT.EDU with SMTP id AA00519; Sun, 18 Jun 95 09:35:26 EDT Received: by darkstar.isi.edu (5.65c/5.61+local-20) id ; Sun, 18 Jun 1995 06:35:08 -0700 Date: Sun, 18 Jun 1995 06:35:08 -0700 Message-Id: <199506181335.AA04754@darkstar.isi.edu> Sender:ietf-archive-request@IETF.CNRI.Reston.VA.US 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.   Received: from ietf.nri.reston.va.us by IETF.CNRI.Reston.VA.US id aa09524; 18 Jun 95 23:30 EDT Received: from CNRI.Reston.VA.US by IETF.CNRI.Reston.VA.US id aa09520; 18 Jun 95 23:30 EDT Received: from interlock.ans.net by CNRI.Reston.VA.US id aa14736; 18 Jun 95 23:30 EDT 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) Sender:ietf-archive-request@IETF.CNRI.Reston.VA.US 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---   Received: from ietf.nri.reston.va.us by IETF.CNRI.Reston.VA.US id aa14131; 19 Jun 95 1:01 EDT Received: from CNRI.Reston.VA.US by IETF.CNRI.Reston.VA.US id aa14127; 19 Jun 95 1:01 EDT Received: from interlock.ans.net by CNRI.Reston.VA.US id aa16010; 19 Jun 95 1:01 EDT 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) Sender:ietf-archive-request@IETF.CNRI.Reston.VA.US 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---   Received: from ietf.nri.reston.va.us by IETF.CNRI.Reston.VA.US id aa01097; 19 Jun 95 6:36 EDT Received: from CNRI.Reston.VA.US by IETF.CNRI.Reston.VA.US id aa01093; 19 Jun 95 6:36 EDT Received: from interlock.ans.net by CNRI.Reston.VA.US id aa02841; 19 Jun 95 6:36 EDT 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 Sender:ietf-archive-request@IETF.CNRI.Reston.VA.US From: 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/ ! +=============================================================+   Received: from ietf.nri.reston.va.us by IETF.CNRI.Reston.VA.US id aa08038; 19 Jun 95 15:35 EDT Received: from CNRI.Reston.VA.US by IETF.CNRI.Reston.VA.US id aa08031; 19 Jun 95 15:35 EDT Received: from interlock.ans.net by CNRI.Reston.VA.US id aa13916; 19 Jun 95 15:35 EDT 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 Sender:ietf-archive-request@IETF.CNRI.Reston.VA.US 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.   Received: from ietf.nri.reston.va.us by IETF.CNRI.Reston.VA.US id aa01424; 20 Jun 95 7:17 EDT Received: from CNRI.Reston.VA.US by IETF.CNRI.Reston.VA.US id aa01420; 20 Jun 95 7:17 EDT Received: from interlock.ans.net by CNRI.Reston.VA.US id aa03436; 20 Jun 95 7:17 EDT 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 Sender:ietf-archive-request@IETF.CNRI.Reston.VA.US 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   Received: from ietf.nri.reston.va.us by IETF.CNRI.Reston.VA.US id aa03029; 20 Jun 95 9:35 EDT Received: from CNRI.Reston.VA.US by IETF.CNRI.Reston.VA.US id aa03025; 20 Jun 95 9:35 EDT Received: from interlock.ans.net by CNRI.Reston.VA.US id aa06089; 20 Jun 95 9:35 EDT 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 Sender:ietf-archive-request@IETF.CNRI.Reston.VA.US 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   Received: from ietf.nri.reston.va.us by IETF.CNRI.Reston.VA.US id aa21008; 20 Jun 95 22:56 EDT Received: from CNRI.Reston.VA.US by IETF.CNRI.Reston.VA.US id aa21004; 20 Jun 95 22:56 EDT Received: from interlock.ans.net by CNRI.Reston.VA.US id aa22089; 20 Jun 95 22:56 EDT 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 Sender:ietf-archive-request@IETF.CNRI.Reston.VA.US 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]   Received: from ietf.nri.reston.va.us by IETF.CNRI.Reston.VA.US id aa06085; 21 Jun 95 13:52 EDT Received: from CNRI.Reston.VA.US by IETF.CNRI.Reston.VA.US id aa06081; 21 Jun 95 13:52 EDT Received: from interlock.ans.net by CNRI.Reston.VA.US id aa11441; 21 Jun 95 13:52 EDT 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 Sender:ietf-archive-request@IETF.CNRI.Reston.VA.US 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   Received: from ietf.nri.reston.va.us by IETF.CNRI.Reston.VA.US id aa14577; 22 Jun 95 18:04 EDT Received: from CNRI.Reston.VA.US by IETF.CNRI.Reston.VA.US id aa14573; 22 Jun 95 18:04 EDT Received: from interlock.ans.net by CNRI.Reston.VA.US id aa10278; 22 Jun 95 18:04 EDT 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 Sender:ietf-archive-request@IETF.CNRI.Reston.VA.US 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: 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   Received: from ietf.nri.reston.va.us by IETF.CNRI.Reston.VA.US id aa03450; 24 Jun 95 17:16 EDT Received: from CNRI.Reston.VA.US by IETF.CNRI.Reston.VA.US id aa03446; 24 Jun 95 17:16 EDT Received: from interlock.ans.net by CNRI.Reston.VA.US id aa10607; 24 Jun 95 17:16 EDT 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 Sender:ietf-archive-request@IETF.CNRI.Reston.VA.US From: 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   Received: from ietf.nri.reston.va.us by IETF.CNRI.Reston.VA.US id aa06309; 26 Jun 95 12:28 EDT Received: from CNRI.Reston.VA.US by IETF.CNRI.Reston.VA.US id aa06305; 26 Jun 95 12:28 EDT Received: from interlock.ans.net by CNRI.Reston.VA.US id aa10045; 26 Jun 95 12:28 EDT 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 Sender:ietf-archive-request@IETF.CNRI.Reston.VA.US From: "Housley, Russ" Encoding: 305 Text To: ipsec@ans.net, 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   Received: from ietf.nri.reston.va.us by IETF.CNRI.Reston.VA.US id ab02224; 27 Jun 95 8:49 EDT Received: from CNRI.Reston.VA.US by IETF.CNRI.Reston.VA.US id aa02219; 27 Jun 95 8:49 EDT Received: from interlock.ans.net by CNRI.Reston.VA.US id aa04815; 27 Jun 95 8:49 EDT 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 Sender:ietf-archive-request@IETF.CNRI.Reston.VA.US 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   Received: from ietf.nri.reston.va.us by IETF.CNRI.Reston.VA.US id aa01135; 28 Jun 95 6:33 EDT Received: from CNRI.Reston.VA.US by IETF.CNRI.Reston.VA.US id aa01131; 28 Jun 95 6:33 EDT Received: from interlock.ans.net by CNRI.Reston.VA.US id aa02739; 28 Jun 95 6:33 EDT 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 Sender:ietf-archive-request@IETF.CNRI.Reston.VA.US 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 | -----------------------------------------------------------------   Received: from ietf.nri.reston.va.us by IETF.CNRI.Reston.VA.US id aa00730; 29 Jun 95 5:09 EDT Received: from CNRI.Reston.VA.US by IETF.CNRI.Reston.VA.US id aa00726; 29 Jun 95 5:09 EDT Received: from interlock.ans.net by CNRI.Reston.VA.US id aa01749; 29 Jun 95 5:09 EDT Received: by interlock.ans.net id AA39312 (InterLock SMTP Gateway 3.0 for ipsec-out@ans.net); Thu, 29 Jun 1995 04:56:37 -0400 Message-Id: <199506290856.AA39312@interlock.ans.net> Received: by interlock.ans.net (Protected-side Proxy Mail Agent-3); Thu, 29 Jun 1995 04:56:37 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-2); Thu, 29 Jun 1995 04:56:37 -0400 Received: by interlock.ans.net (Protected-side Proxy Mail Agent-1); Thu, 29 Jun 1995 04:56:37 -0400 Date: Thu, 29 Jun 1995 16:54:48 +0800 Sender:ietf-archive-request@IETF.CNRI.Reston.VA.US 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   Received: from ietf.nri.reston.va.us by IETF.CNRI.Reston.VA.US id aa01297; 30 Jun 95 6:57 EDT Received: from CNRI.Reston.VA.US by IETF.CNRI.Reston.VA.US id aa01293; 30 Jun 95 6:57 EDT Received: from interlock.ans.net by CNRI.Reston.VA.US id aa03076; 30 Jun 95 6:57 EDT 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 Sender:ietf-archive-request@IETF.CNRI.Reston.VA.US 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.   Received: from ietf.nri.reston.va.us by IETF.CNRI.Reston.VA.US id aa17085; 30 Jun 95 16:19 EDT Received: from CNRI.Reston.VA.US by IETF.CNRI.Reston.VA.US id aa17081; 30 Jun 95 16:19 EDT Received: from ietf.cnri.reston.va.us by CNRI.Reston.VA.US id aa18078; 30 Jun 95 16:19 EDT Received: from ietf.nri.reston.va.us by IETF.CNRI.Reston.VA.US id aa17066; 30 Jun 95 16:19 EDT Received: from CNRI.Reston.VA.US by IETF.CNRI.Reston.VA.US id aa17059; 30 Jun 95 16:19 EDT Received: from watson.ibm.com by CNRI.Reston.VA.US id aa18054; 30 Jun 95 16:19 EDT Received: from YKTVMV by watson.ibm.com (IBM VM SMTP V2R3) with BSMTP id 7345; Fri, 30 Jun 95 16:19:17 EDT Date: Fri, 30 Jun 95 15:49:32 EDT X-Orig-Sender:iesg-request@IETF.CNRI.Reston.VA.US Sender:ietf-archive-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 Message-ID: <9506301619.aa18054@CNRI.Reston.VA.US> 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.   Received: from ietf.nri.reston.va.us by IETF.CNRI.Reston.VA.US id aa17701; 30 Jun 95 16:30 EDT Received: from CNRI.Reston.VA.US by IETF.CNRI.Reston.VA.US id aa17697; 30 Jun 95 16:30 EDT Received: from interlock.ans.net by CNRI.Reston.VA.US id aa18457; 30 Jun 95 16:30 EDT 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 Sender:ietf-archive-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.   Received: from ietf.nri.reston.va.us by IETF.CNRI.Reston.VA.US id aa18341; 30 Jun 95 16:46 EDT Received: from CNRI.Reston.VA.US by IETF.CNRI.Reston.VA.US id aa18332; 30 Jun 95 16:46 EDT Received: from interlock.ans.net by CNRI.Reston.VA.US id aa18962; 30 Jun 95 16:46 EDT 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 Sender:ietf-archive-request@IETF.CNRI.Reston.VA.US From: 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   Received: from ietf.nri.reston.va.us by IETF.CNRI.Reston.VA.US id aa22456; 30 Jun 95 19:42 EDT Received: from CNRI.Reston.VA.US by IETF.CNRI.Reston.VA.US id aa22452; 30 Jun 95 19:42 EDT Received: from interlock.ans.net by CNRI.Reston.VA.US id aa22697; 30 Jun 95 19:42 EDT 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 X-Orig-Sender: ietf-request@IETF.CNRI.Reston.VA.US Sender:ietf-archive-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.   Received: from ietf.nri.reston.va.us by IETF.CNRI.Reston.VA.US id aa03495; 30 Jun 95 22:50 EDT Received: from CNRI.Reston.VA.US by IETF.CNRI.Reston.VA.US id aa03491; 30 Jun 95 22:50 EDT Received: from interlock.ans.net by CNRI.Reston.VA.US id aa29180; 30 Jun 95 22:50 EDT 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 X-Orig-Sender: ietf-request@IETF.CNRI.Reston.VA.US Sender:ietf-archive-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.