Network Working Group Phil Karn Internet Draft Qualcomm expires in six months December 1994 The Photuris Key Management Protocol draft-karn-photuris-00.txt Status of this Memo This document is a submission to the IP-Security Working Group of the Internet Engineering Task Force (IETF). Comments should be submitted to the ipsec@ans.net mailing list. Distribution of this memo is unlimited. 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 six months, and 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 a ``working draft'' or ``work in progress.'' To learn the current status of any Internet-Draft, please check the ``1id-abstracts.txt'' listing contained in the internet-drafts Shadow Directories on ds.internic.net (US East Coast), nic.nordu.net (Europe), ftp.isi.edu (US West Coast), or munnari.oz.au (Pacific Rim). Abstract Photuris [1] is an experimental key management protocol intended for use with the IP Security Protocol (IPSP) in a point-to-point mode. Photuris is still in the early design stages and has not yet been completely implemented. Detailed packet formats are not yet specified, but it is hoped that this draft will stimulate discussion about the merits of the design philosophy. Karn expires in six months [Page i] DRAFT Photuris December 1994 1. Introduction Users must have confidence in every Internet Security component, including key management. Users will rely on Internet Security to protect the confidentiality of the traffic they send across the Internet, and they depend on it to block unauthorized external access to their internal hosts and networks. Otherwise, they will either erect barriers that impede legitimate use of the Internet, or they will forego the Internet entirely. Photuris combines Diffie-Hellman key exchange with RSA authentication to provide perfect forward secrecy, as defined by Diffie [2]. The protocol is also designed to thwart certain types of active denial of service attacks on host resources. This draft assumes familiarity with both the Diffie-Hellman and RSA public-key algorithms. Good descriptions can be found in [5]. 1.1. Use of Public-Key Cryptography Widespread deployment and use of an Internet Security protocol is possible without public-key cryptography. For example, Kerberos [6] can generate host-pair keys for use in Internet Security much as it now generates session keys for use by encrypted telnet and other kerberized applications. The Kerberos model has some widely recognized drawbacks. Foremost is the requirement for a highly available on-line key distribution center with a database containing every principal's secret key. This carries significant security risks. Public-key cryptography decentralizes things considerably. Entities authenticate themselves to each other, and generate shared session keys, without real-time communication with any other party. Photuris is based on public-key cryptography, specifically Diffie- Hellman and RSA. Photuris uses RSA only for signature purposes, so in principle it could be replaced by the Digital Signature Standard (DSS). 1.2. Defense against Sabotage The ultimate goal of Internet Security is to facilitate direct IP connectivity between sensitive internal hosts and the external Karn expires in six months [Page 1] DRAFT Photuris December 1994 Internet. Protecting sensitive data on these hosts against compromise -- either by interception or by unauthorized access -- is necessary, but not sufficient. The computing resources themselves must also be protected against malicious attack or sabotage. This is accomplished mainly by the authentication facilities in Internet Security. If a packet does not pass an authentication check, it can be immediately discarded at relatively little cost, given the speed of fast cryptographic hash functions (such as MD5). Internet Security does not place any significance on easily forged IP source addresses. It relies instead on proof of possession of secret knowledge: that is, a cryptographic key. But there is a potential Achilles heel in the key management protocol. If we are to grant access to authorized users regardless of location, we must be able to cheaply detect and discard bogus packets. Otherwise, an attacker intent on sabotage might rapidly send them to exhaust the host's CPU or memory resources. This is easily done with manual (null) key management, since each packet encounters only the fast crypto-hash functions just mentioned. But key management schemes based on public-key cryptography are potentially vulnerable because of their use of CPU-intensive operations, such as modular exponentiation. Although a complete defense against such attacks is impossible, a simple feature makes them much more difficult. Photuris exchanges a "cookie" before initiating public-key operations, thwarting the saboteur from using random IP source addresses. He must then either: 1) use his own IP address, 2) gain access to a transmission link to a subnet whose addresses he appropriates, or 3) subvert Internet routing for the same purpose. The first option allows the target to detect and filter out such attacks, and significantly increases the likelihood of identifying the attacker. The latter two options are much more difficult than merely sending large numbers of datagrams with randomly chosen IP source addresses from an arbitrary point on the Internet. Karn expires in six months [Page 2] DRAFT Photuris December 1994 1.3. Perfect Forward Secrecy As Diffie points out, many security breaches in government cryptographic systems have been facilitated by designs that generate traffic-encrypting keys (or their equivalents) well before they are needed, and then keep them around longer than necessary. This creates many opportunities for compromise, especially by insiders. A carefully designed public-key system can avoid this problem. The rule is to avoid using any long-lived keys (such as an RSA key pair) to encrypt session keys or actual traffic. Such keys should be used solely for authentication purposes. All keys for traffic encryption should be randomly generated immediately before use, and then destroyed immediately after use, so that they cannot be recovered. Photuris uses a combination of Diffie-Hellman (for key exchange) and RSA (for authentication), as follows: 1. Agree on a session key using the Diffie-Hellman algorithm. 2. Authenticate the Diffie-Hellman exchanges with a digital signature algorithm, such as RSA or DSS. This authenticates the parties to each other, and thwarts the "man in the middle" active attack against Diffie-Hellman. When the session key generated in step 1 is eventually destroyed, it is gone for good. The generating information is not based on any other stored information. Theft of the secret key used to sign the exchanges in step 2 would allow the thief to impersonate the party in future conversations, but it would not allow him to decode any past traffic that he might have recorded. 1.4. Mobile Traffic Anonymity A fundamental role of a key management protocol is to verify the identities of the communicating parties to each other. But one would often like to deny this information to an eavesdropper, especially when this would reveal the location of a mobile user. Although each packet carries a cleartext IP destination address, the ultimate destination could be hidden by "laundering" it through an encrypted tunnel. A mobile user's IP source address could be hidden in the same manner. Karn expires in six months [Page 3] DRAFT Photuris December 1994 If the address has been dynamically allocated, it provides no useful information to an eavesdropper. This leaves the identifying information that the mobile user sends during key exchange. This identification can be easily protected in the two-step DH/RSA protocol by encrypting the RSA signature exchanges with the key just established with Diffie-Hellman. This keeps a passive eavesdropper from learning the identities of the parties, either by checking the signatures against a known database of public keys, or by intercepting possible exchanges of public keys and certificates. The scheme is not foolproof. By posing as the home system, an active attacker could trick the mobile user into revealing his identity. But an active attack is considerably more difficult than passive vacuum-cleaner monitoring. And unless the attacker can steal the RSA secret key belonging to the user's home system, the mobile user will discover the deception when checking the RSA signature in the home system's key exchange message. 1.5. Multicast Support Key management is much more difficult in a multicast environment. The author is not convinced that it is possible to provide all the features just described in a multicast key management protocol. Since the most common use of Internet Security will be in conventional point-to-point IP communications, the author feels that the lack of multicast support in Photuris is acceptable. Nothing in this proposal is meant to discourage the development of other key management protocols with multicast support. If such a protocol can also provide all of the design features of Photuris with reasonable complexity, this author is willing to withdraw this proposal. The author is also open to suggestions on how multicast capability might be added to Photuris, without compromising its fundamental features. Karn expires in six months [Page 4] DRAFT Photuris December 1994 2. Protocol Description The Photuris protocol combines all these elements into a single protocol. The protocol consists of three phases: 1. A "cookie" exchange to guard against simple flooding attacks with bogus IP source addresses. 2. A Diffie-Hellman key exchange to establish a session key for conventional encryption. 3. An encrypted exchange of RSA signatures on the Diffie-Hellman messages that were sent in step 2 to verify their integrity and the identities of the two parties. Regular operation of the Internet Security protocol (encryption and/or authentication of user packets) then begins. Either party may initiate a key exchange. This party is the initiator, while the other party is the responder. The initiator is responsible for recovering from all packet losses by retransmission. 3. Cookie Exchange 3.1. Cookie Request The initiator initializes local state, and sends a COOKIE_REQUEST message to the responder containing the initiator's cookie. The initiator starts a retransmission timer. If no response is obtained within the time limit, the same COOKIE_REQUEST is retransmitted. 3.2. Cookie Response On receipt of the COOKIE_REQUEST, the responder generates a cookie for the incoming IP source address, and returns it in a COOKIE_RESPONSE message, along with the initiator's cookie. Note that the responder creates no state at this time. 3.3. Cookie Generation The exact method in which a Photuris entity generates a cookie is Karn expires in six months [Page 5] DRAFT Photuris December 1994 implementation dependent. The function chosen must satisfy some basic requirements: 1. The cookie must depend on the remote IP address. This prevents an attacker from obtaining a cookie with his real IP address, and then using it to swamp the victim with Diffie-Hellman requests from randomly chosen IP addresses. 2. It must not be possible for anyone other than the issuing entity to generate cookies that will be accepted by that entity. This implies that the issuing entity must use local secret information in the generation and subsequent verification of a cookie, and it must not be possible to deduce this secret information from any particular cookie. 3. The cookie generation function must be fast to thwart attacks intended to sabotage CPU resources. A recommended method is to run a cryptographic one-way hash function (such as MD5) over the remote IP address and a locally generated random value. An incoming cookie can be verified at any time by regenerating it locally from the incoming IP address and the local random value. The random value may be generated once at boot time and remain static until the next reboot. It is kept secret. 4. Diffie-Hellman Exchange 4.1. Diffie-Hellman Request On receipt of a valid COOKIE_RESPONSE, the initiator sends a DH_REQUEST message containing the following items: a) The initiator's cookie. b) The responder's cookie. c) The public part of the initiator's Diffie-Hellman exchange. d) The prime modulus used to compute (c). e) A list of transport protocols supported by the initiator f) A list of Internet Security encapsulation modes (encryption and authentication algorithms) supported by the initiator. g) A policy indicator showing whether the initiator requires the use Karn expires in six months [Page 6] DRAFT Photuris December 1994 of authentication on incoming Internet Security protected packets. The initiator then starts a timer that runs until it receives a DH_RESPONSE message. If the timer expires, the same DH_REQUEST is retransmitted. 4.2. Diffie-Hellman Response On receipt of a valid DH_REQUEST message, the responder returns a DH_RESPONSE message with the following items: a) The initiator's cookie. b) The responder's cookie. c) The public part of the responder's Diffie-Hellman exchange, computed using the prime modulus received in the DH_REQUEST message. d) A list of transport protocols supported by the responder. e) A list of Internet Security encapsulation modes (encryption and authentication algorithms) supported by the responder. f) A policy indicator showing whether the responder requires the use of authentication on incoming Internet Security protected packets. At this time, the responder begins execution of the final modular exponentiation step in Diffie-Hellman that yields a shared key. The responder keeps a copy of the incoming DH_REQUEST message, and its DH_RESPONSE message. If a duplicate DH_REQUEST is received, it merely resends the previous DH_RESPONSE message, and takes no further action. 4.3. Session Key Computation On receipt of the DH_RESPONSE message, the initiator begins execution of the final modular exponentiation step in Diffie-Hellman that yields a shared key. This final step is executed in parallel with the responder's computation, minimizing delay. Karn expires in six months [Page 7] DRAFT Photuris December 1994 Both the initiator and responder use the resulting shared key to encrypt all subsequent exchanges, with the exception of any DH_RESPONSE retransmissions. Each party selects an encryption mode (if any) according to its own local policy database, and the list of encryption functions supported by the other party. Each party additionally selects an authentication function according to the requirements and facilities of the other party. Note that the encryption and authentication modes, as well as the IP-IP encapsulation mode (if any), need not be the same in both directions. 4.4. Random Number Generation The security of Diffie-Hellman depends critically on the quality of the secret random numbers generated by each party. A poor random number generator at either end will compromise the shared key produced by the algorithm. Generating cryptographic quality random numbers on a general purpose computer without hardware assistance is a very tricky problem. In general, this requires using a cryptographic hash function to "distill" the entropy from a large number of semi-random external events, such as the timing of key strokes. An excellent discussion can be found in [4]. 4.5. Moduli It is envisioned that a small set of recommended strong primes for use as Diffie-Hellman moduli will be specified in the Photuris standard. The preferred modulus will be 1024 bits long. The modulus indicated in the "Diffie-Hellman Request" may then take the form of a one-byte index into a well-known table, with a reserved escape value allowing an arbitrary modulus. Use of a very limited number of moduli (preferably one) has one minor and one very significant advantage: Minor advantage: Avoiding the overhead of sending the full modulus in every DH_REQUEST packet. Karn expires in six months [Page 8] DRAFT Photuris December 1994 Major advantage: Allowing each party to precompute the public DH part in the DH_REQUEST and DH_RESPONSE, and for the RSA signatures (described later). A background process can periodically destroy the old values, generate a new random secret, and recalculate the public DH part and the RSA signature. This limits the exposure of the secret, as past secrets are not kept for possible discovery by a future intrusion, protecting earlier communications. Also, the secret currently in use is less likely to be anticipated, as the element of random timing is introduced. Since these operations involve several time-consuming modular exponentiations, moving them to the "background" substantially speeds up the apparent execution speed of the Photuris protocol. It also allows a single DH key pair and associated RSA signature to be used in several closely spaced Photuris executions, when setting up security associations with several different hosts over a short period of time, thus reducing total CPU loading. 4.6. Size of Secret DH Components There is surprisingly little guidance in the literature about how large the randomly chosen secret exponent in Diffie-Hellman should be. The size of this exponent dramatically affects the speed of both modular exponentiations involved in Diffie-Hellman. For example, a single modular exponentiation on a 486-66DX2 processor using RSAREF and Borland C under MS-DOS took 20 seconds with a 1024- bit prime modulus and a 1024-bit random exponent. This dropped to about 1 to 1.5 seconds when the random exponent was shortened to 128 bits, with the same 1024-bit modulus. Therefore, it is desirable to use the smallest random exponent that is consistent with good security. The most conservative advice received to date [3] is to make the random exponent twice as long as the intended session key. This ensures that any space/time "meet in the middle" attack on the discrete logarithm problem will be at least as complex as a brute-force search on the resulting session key space. Karn expires in six months [Page 9] DRAFT Photuris December 1994 5. Signature Exchange 5.1. Signature Transmission When each party completes its parallel computation of the Diffie- Hellman key agreement, and encryption has begun, each party sends the other a RSA_SIG message containing the following items: a) The initiator's cookie. b) The responder's cookie. c) An RSA signature on the public part of the sender's Diffie-Hellman exchange. d) The corresponding RSA public key, or an indicator of same. e) Certificates on the RSA public key (optional). Each party keeps a copy of its RSA_SIG message and starts a timer. When it receives the other party's RSA_SIG message, it stops the timer. If it does not receive the other party's RSA_SIG message before the timer expires, it retransmits its own RSA_SIG message and restarts the timer. If it receives a duplicate of the other party's RSA_SIG message (after its timer has been stopped), it retransmits its own RSA_SIG message without restarting the timer. 5.2. Signature Verification The two parties now verify the RSA signatures just received. If they fail, the users are notified, and the security association is destroyed. If they succeed, normal operation begins with the encryption and/or authentication of user packets. Each party implements local policy that determines what access, if any, is granted to the holder of a particular RSA key pair. Exchange of RSA public key certificates is optional; early implementations may wish to keep their own trusted public key databases, and accept only those users found there. Any encrypted and/or authenticated user packets received before the completion of RSA signature verification are placed on a queue pending completion of this step. If the RSA verification succeeds, the queue is processed as though the packets had arrived subsequent Karn expires in six months [Page 10] DRAFT Photuris December 1994 to the verification. If the verification fails, the queue is discarded. Karn expires in six months [Page 11] DRAFT Photuris December 1994 A. Strong Primes This 1024-bit prime p, expressed in hex, has the property that both p and (p-1)/2 are prime: 1 a4788e2184b8d68bfe02690e4dbe485b17a80bc5f21d680f1a8413139734f7f2b0 db4e253750018aad9e86d49b6004bbbcf051f52fcb66d0c5fca63fbfe634173485 bbbf7642e9df9c74b85b6855e94213b8c2d89162abeff43424350e96be41edd42d e99a6961638c1dac598bc90da069b50c414d8eb8652adcff4a270d567f The recommended generator g for this prime is 5. Although this prime is suggested for use in this protocol, cooperating installations might use additional primes. This prime was randomly generated by a freely available program written by the author. Karn expires in six months [Page 12] DRAFT Photuris December 1994 Security Considerations Security issues are the topic of this memo. References [1] "Photuris" is the latin name for the firefly. "Firefly" is in turn the name for NSA's (classified) key exchange protocol for the STU- III secure telephone. Informed speculation has it that Firefly is based on very similar design principles. [2] Whitfield Diffie, "Authenticated Key Exchange and Secure Interactive Communication", Northern Telecom, Securicom '90, Paris France, 16 March 1990. [3] Martin Hellman, personal communication. [4] Eastlake, Crocker & Schiller, "Randomness Requirements for Security", work in progress. [5] Bruce Schneier, "Applied Cryptography", ISBN 0- 471-59756-2. [6] Kerberos? Acknowledgements Thanks go to Bill Simpson for his protocol suggestions, editorial changes and NROFF formatting. Author's Address Questions about this memo can also be directed to: Phil Karn Qualcomm, Inc. 6455 Lusk Blvd. San Diego, California 92121-2779 Karn expires in six months [Page 13] DRAFT Photuris December 1994 karn@qualcomm.com karn@unix.ka9q.ampr.org Karn expires in six months [Page 14] DRAFT Photuris December 1994 Table of Contents 1. Introduction .......................................... 1 1.1 Use of Public-Key Cryptography .................. 1 1.2 Defense against Sabotage ........................ 1 1.3 Perfect Forward Secrecy ......................... 3 1.4 Mobile Traffic Anonymity ........................ 3 1.5 Multicast Support ............................... 4 2. Protocol Description .................................. 5 3. Cookie Exchange ....................................... 5 3.1 Cookie Request .................................. 5 3.2 Cookie Response ................................. 5 3.3 Cookie Generation ............................... 5 4. Diffie-Hellman Exchange ............................... 6 4.1 Diffie-Hellman Request .......................... 6 4.2 Diffie-Hellman Response ......................... 7 4.3 Session Key Computation ......................... 7 4.4 Random Number Generation ........................ 8 4.5 Moduli .......................................... 8 4.6 Size of Secret DH Components .................... 9 5. Signature Exchange .................................... 10 5.1 Signature Transmission .......................... 10 5.2 Signature Verification .......................... 10 APPENDICES ................................................... 12 A. Strong Primes ......................................... 12 SECURITY CONSIDERATIONS ...................................... 13 REFERENCES ................................................... 13 ACKNOWLEDGEMENTS ............................................. 13 AUTHOR'S ADDRESS ............................................. 13