Schneier95]. DH76] specified modular exponentiation. A public-value is generated using a generator (g), raised to a private-secret exponent (x), modulo a prime (p): (g**x) mod p. When these public-values are exchanged between parties, the parties can calculate a shared-secret value between themselves: (g**xy) mod p. The generator (g) and modulus (p) are established by the Scheme- Choice (see the "Basic Exchange-Schemes" for details). They are offered in the Cookie_Response, and one pair is chosen in the Value_Request. The private exponents (x) and (y) are kept secret by the parties. Only the public-value result of the modular exponentiation with (x) or (y) is sent as the Initiator and Responder Exchange-Value. These public-values are represented in single Variable Precision Integers. The Size of these Exchange-Values will match the Size of the modulus (p).
For 512-bit moduli, current estimates would provide 64 (pessimistic) bit-equivalents of cryptographic strength. For 1024-bit moduli, current estimates would range from 80 (pessimistic) through 98 (optimistic) bit-equivalents of cryptographic strength. These estimates are used when choosing moduli that are appropriate for the desired Security Parameter attributes.
Implementation Notes: One useful technique is to select the generator, and then limit the modulus selection sieve to primes with that generator: 2 when p (mod 24) = 11. 3 when p (mod 12) = 5. 5 when p (mod 10) = 3 or 7. The required generator (2) improves efficiency in multiplication performance. It is usable even when it is not a primitive root, as it still covers half of the space of possible residues.
RFC-1321] is used as a pseudo-random-function for generating the key(s). The key(s) begin with the most significant bits of the hash. MD5 is iterated as needed to generate the requisite length of key material. When an individual key does not use all 128-bits of the last hash, any remaining unused (least significant) bits of the last hash are discarded. When combined with other uses of key generation for the same purpose, the next key will begin with a new hash iteration. RFC-1321] hash over the concatenation of MD5( key, keyfill, data, datafill, key, md5fill ) where the key is the computed verification-key. The keyfill and datafill use the same pad-with-length technique defined for md5fill. This padding and length is implicit, and does not appear in the datagram. The resulting Verification field is a 128-bit Variable Precision Integer (18 bytes including Size). When used in calculations, the Verification data includes both the Size and Value fields.
RFC-1700]. For example, when encrypting an entire IP datagram, this field will contain the value 4, indicating IP- in-IP encapsulation. When a list of Attributes is specified, this Attribute begins the section of the list which applies to the Encapsulating Security Payload (ESP). When listed as an Offered-Attribute, the PayloadType is set to 255. When selected as an Attribute-Choice, the PayloadType is set to the actual value to be used.
RFC-1321] hash over the concatenation of: MD5( key, keyfill, data, datafill, key, md5fill ) where the key is the computed verification-key. The keyfill and datafill use the same pad-with-length technique defined for md5fill. This padding and length is implicit, and does not appear in the datagram. The resulting Verification field is a 128-bit Variable Precision Integer (18 bytes including Size). When used in calculations, the Verification data includes both the Size and Value fields. For both "Identity Verification" and "Validity Verification", the verification-key is the MD5 [RFC-1321] hash of the following concatenated values:
+ the symmetric secret-key, + the computed shared-secret. For "Session-Key Computation", the symmetric secret-key is used directly as the generation-key. Regardless of the internal representation of the symmetric secret- key, when used in calculations it is in the same form as the Value part of a Variable Precision Integer: - most significant byte first. - bits used are right justified within byte boundaries. - any unused bits are in the most significant byte. - unused bits are zero filled. The symmetric secret-key does not include a Size field. RFC-1828]. The form of the authenticated message is: MD5( key, keyfill, datagram, datafill, key, md5fill ) where the key is the SPI session-key. The additional datafill protects against the (impractical) attack described in [PO96]. The keyfill and datafill use the same pad- with-length technique defined for md5fill. This padding and length is implicit, and does not appear in the datagram.
TO- = Timeout with counter expired UTO = Update TimeOut XTO = Exchange TimeOut Actions scq = Send Cookie_Request scr = Send Cookie_Response svq = Send Value_Request svr = Send Value_Response siq = Send Identity_Request sir = Send Identity_Response sum = Send SPI_Update se* = Send error message (see text) sbc = Send Bad Cookie srl = Send Resource Limit svf = Send Verification Failure brto = Backoff Retransmission TimeOut buto = Backoff Update TimeOut rto = Set Retransmission TimeOut uto = Set Update TimeOut xto = Set Exchange TimeOut log = log operator message
Initiator | 0 1 2 3 4 | Initial Cookie CookieBad Value ValueBad ------+-------------------------------------------------- DU13 |rto,scq/1 rto,scq/1 rto,scq/1 3 4 SF0 |rto,scq/1 1 2 3 4 SF4 |rto,scq/1 1 2 3 4 SF5 |rto,scq/1 1 2 3 4 WC |rto,scq/1 1 2 3 4 | RCR+ | - rto,svq/3 rto,svq/3 3 4 RCR- | 0 1 2 3 4 RVR+ | - - - rto,siq/5 rto,siq/5 RVR- | 0 1 2 3 4 RIR+ | - - - - - RIR- | 0 1 2 3 4 | RUN+ | - - - - - RUN- | sbc/0 sbc/1 sbc/2 sbc/3 sbc/4 RUM+ | - - - - - RUM- | sbc/0 sbc/1 sbc/2 sbc/3 sbc/4 | RBC | - - - 4 4 RRL | - brto/2 brto/2 brto/4 brto/4 RVF | - - - - - RMR | - - - - - | TO+ | - scq/1 scq/2 svq/3 svq/4 TO- | - 0 scq/1 0 scq/1 UTO | - - - - - XTO | - 0 0 0 0
Initiator | 5 6 8 |Identity IdentityBad Update ------+----------------------------- DU13 | 5 6 8 SF0 | 5 6 rto,scq/1 SF4 | 5 6 rto,scq/1 SF5 | 5 6 rto,scq/1 WC | 5 6 sun/8 | RCR+ | 5 6 8 RCR- | 5 6 8 RVR+ | 5 6 8 RVR- | 5 6 8 RIR+ | uto/8 uto/8 8 RIR- | svf/5 svf/6 8 | RUN+ | - - sum/8 RUN- | sbc/5 sbc/6 se*/8 RUM+ | - - 8 RUM- | sbc/5 sbc/6 se*/8 | RBC | 6 6 rto,scq/1 RRL | 5 6 buto/8 RVF | log/5 log/6 log/8 RMR | log/5 log/6 log/8 | TO+ | sim/5 sim/6 - TO- | 0 scq/1 - UTO | - - sum/8 XTO | 0 0 0
Responder | 0 7 8 | Initial Ready Update ------+----------------------------- WC | - 7 sun/8 | RCQ+ | scr/0 scr/7 scr/8 RCQ- | srl/0 srl/7 srl/8 RVQ+ |xto,svr/7 svr/7 svr/8 RVQ- | sbc/0 sbc/7 sbc/8 RIQ+ | - uto,sir/8 sir/8 RIQ- | sbc/0 se*/7 se*/8 | RUN+ | - - sum/8 RUN- | sbc/0 sbc/7 se*/8 RUM+ | - - 8 RUM- | sbc/0 sbc/7 se*/8 | RBC | - 7 rto,scq/1 RRL | - - buto/8 RVF | - - log/8 RMR | - - log/8 | UTO | - - sum/8 XTO | - 0 0
Identification field is "Tiny VPN 1995 November" and the SPI Owner secret-key is "abracadabra". When the Responder sends its Identity_Response, the SPI Owner Identification field is "Tiny VPN 1995 November" and the SPI Owner secret-key is "abracadabra". The SPI User Identification is "Tiny VPN 1995 November" (taken from the request), and the SPI User secret-key is "abracadabra". Note that even in the face of implementations with very poor random number generation yielding the same random numbers for both parties at every step, and with this completely identical configuration, the addition of the SPI User Verification field in the response calculation is highly likely to produce a different Verification value (see "Identity Verification"). In turn, the different Verification values affect the calculation of SPI session-keys that are highly likely to be different in each direction (see "Session-Key Computation").
Identification field is "Happy_Wanderer@router.site" and the SPI Owner secret-key is "FalDaRee". When the firewall Responder sends its Identity_Response, the SPI Owner Identification field is "firstname.lastname@example.org" and the SPI Owner secret-key is "FalDaRah". The SPI User Identification field is "Happy_Wanderer@router.site" (taken from the request), and the SPI User secret-key is "FalDaRee". In this example, the mobile user is already prepared for a monthly password changeover, where the router might identify itself as "email@example.com".
secret-key is "all for one".
specified in transform padding format and key generation. More than one value is permitted per scheme, giving greater latitude in choice for future extensions. The opportunity is taken to return party privacy to the base document, and make small semantic changes in automated updates and error recovery. All ESP transform attributes are moved to separate documents, to (hopefully) avoid future incompatible changes to the base document. Prime Commandment] Phil Karn was principally responsible for the design of the protocol phases, particularly the "cookie" anti-clogging defense, developed the initial testing implementation, and provided much of the design rationale text (now removed to a separate document). William Simpson was responsible for the packet formats and attributes, additional message types, editing and formatting. All such mistakes are his responsibility. This protocol was later discovered to have many elements in common with the Station-To-Station authentication protocol [DOW92]. Angelos Keromytis developed the first completely independent implementation (circa October 1995). Also, he suggested the cookie exchange rate limitation counter. Paul C van Oorschot suggested signing both the public exponents and the shared-secret, to provide an authentication-only version of identity verification. Also, he provided text regarding moduli, generator, and exponent selection (now removed to a separate document). Hilarie Orman suggested adding secret "nonces" to session-key generation for asymmetric public/private-key identity methods (now removed to a separate document), and provided extensive review of the protocol details. Bart Preneel and Paul C van Oorschot in [PO96] recommended padding between the data and trailing key when hashing for authentication. Niels Provos developed another independent implementation (circa May 1997), ported to AIX, Linux, OpenBSD, and Solaris. Also, he made
suggestions regarding automated update, and listing multiple moduli per scheme. Bill Sommerfeld suggested including the authentication symmetric secret-keys in the session-key generation, and using the Cookie values on successive exchanges to provide bi-directional user- oriented keying (now removed to a separate document). Oliver Spatscheck developed the second independent implementation (circa December 1995) for the Xkernel. International interoperability testing between early implementors provided the impetus for many of the implementation notes herein, and numerous refinements in the semantics of the protocol messages. Randall Atkinson, Steven Bellovin, Wataru Hamada, James Hughes, Brian LaMacchia, Cheryl Madson, Lewis McCarthy, Perry Metzger, Bob Quinn, Ron Rivest, Rich Schroeppel, and Norman Shulman provided useful critiques of earlier versions of this document. Special thanks to the Center for Information Technology Integration (CITI) for providing computing resources. [BGMW93] E. Brickell, D. Gordon, K. McCurley, and D. Wilson, "Fast Exponentiation with Precomputation (Extended Abstract)", Advances in Cryptology -- Eurocrypt '92, Lecture Notes in Computer Science 658 (1993), Springer-Verlag, 200-207. Also U.S. Patent #5,299,262, E.F. Brickell, D.M. Gordon, K.S. McCurley, "Method for exponentiating in cryptographic systems", 29 Mar 1994. [DH76] Diffie, W., and Hellman, H.E., "New Directions in Cryptography", IEEE Transactions on Information Theory, v IT-22 n 6 pp 644-654, November 1976. [DOW92] Whitfield Diffie, Paul C van Oorshot, and Michael J Wiener, "Authentication and Authenticated Key Exchanges", Designs, Codes and Cryptography, v 2 pp 107-125, Kluwer Academic Publishers, 1992. [Firefly] "Photuris" is the latin name for the firefly. "Firefly" is in turn the name for the USA National Security Administration's (classified) key exchange protocol for the STU-III secure telephone. Informed speculation has
it that Firefly is based on very similar design principles. [LL94] Lim, C.H., Lee, P.J., "More flexible exponentiation with precomputation", Advances in Cryptology -- Crypto '94, Lecture Notes in Computer Science 839 (1994), Springer- Verlag, pages 95-107. [Prime Commandment] A derivation of an apocryphal quote from the usenet list sci.crypt. [PO96] Bart Preneel, and Paul C van Oorshot, "On the security of two MAC algorithms", Advances in Cryptology -- Eurocrypt '96, Lecture Notes in Computer Science 1070 (May 1996), Springer-Verlag, pages 19-32. [RFC-768] Postel, J., "User Datagram Protocol", STD 6, USC/Information Sciences Institute, August 1980. [RFC-791] Postel, J., "Internet Protocol", STD 5, USC/Information Sciences Institute, September 1981. [RFC-1321] Rivest, R., "The MD5 Message-Digest Algorithm", MIT Laboratory for Computer Science, April 1992. [RFC-1700] Reynolds, J., and Postel, J., "Assigned Numbers", STD 2, USC/Information Sciences Institute, October 1994. [RFC-1812] Baker, F., Editor, "Requirements for IP Version 4 Routers", Cisco Systems, June 1995. [RFC-1828] Metzger, P., Simpson, W., "IP Authentication using Keyed MD5", July 1995. [RFC-1829] Karn, P., Metzger, P., Simpson, W., "The ESP DES-CBC Transform", July 1995. [RFC-2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, Harvard University, March 1997. [RFC-2521] Karn, P., and Simpson, W., "ICMP Security Failures Messages", March 1999. [Rooij94] P. de Rooij, "Efficient exponentiation using precomputation and vector addition chains", Advances in Cryptology -- Eurocrypt '94, Lecture Notes in Computer
Science, Springer-Verlag, pages 403-415. [Schneier95] Schneier, B., "Applied Cryptography Second Edition", John Wiley & Sons, New York, NY, 1995. ISBN 0-471-12845-7.
Full Copyright Statement Copyright (C) The Internet Society (1999). Copyright (C) Philip Karn and William Allen Simpson (1994-1999). All Rights Reserved. This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards (in which case the procedures for copyrights defined in the Internet Standards process must be followed), or as required to translate it into languages other than English. The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns. This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING (BUT NOT LIMITED TO) ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.