HTTP/1.1 200 OK Date: Tue, 09 Apr 2002 09:26:46 GMT Server: Apache/1.3.20 (Unix) Last-Modified: Tue, 11 Apr 1995 22:00:00 GMT ETag: "323f44-f0f4-2f8afbe0" Accept-Ranges: bytes Content-Length: 61684 Connection: close Content-Type: text/plain Network Working Group Phil Karn Internet Draft Qualcomm W A Simpson DayDreamer expires in six months March 1995 The Photuris Session Key Management Protocol draft-karn-photuris-01.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: ftp.is.co.za (Africa) nic.nordu.net (Europe) ds.internic.net (US East Coast) ftp.isi.edu (US West Coast) munnari.oz.au (Pacific Rim) Abstract Photuris [1] is an experimental session-key management protocol intended for use with the IP Security Protocols (AH and ESP) in a point-to-point mode. Karn & Simpson expires in six months [Page i] DRAFT Photuris March 1995 Photuris is still in the early design stages and has not yet been completely specified. It is hoped that this draft will stimulate discussion about the merits of the design philosophy. Karn & Simpson expires in six months [Page ii] DRAFT Photuris March 1995 1. Introduction The ultimate goal of Internet Security is to facilitate direct IP connectivity between sensitive hosts and users across the Internet. 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 depend on it to block unauthorized external access to their internal hosts and networks. Without this confidence, users may erect barriers that impede legitimate use of the Internet, or forego the Internet entirely. 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. Photuris combines Diffie-Hellman key exchange with authentication to provide perfect forward secrecy, as defined by Diffie [2]. The protocol is also designed to thwart certain types of denial of service attacks on host resources. This draft assumes familiarity with the Diffie-Hellman public-key algorithm. A good description can be found in [5]. 1.1. Terminology Initiator The key establishment party which sends the first Photuris session request. public/private key-pair A pair of keys, one of which is publically distributable, the other of which is kept secret. public-value As used in this document, the publically distributable value used in the D-H exchange to calculate a shared-secret. Responder The key establishment party which receives the first Photuris session request. shared-secret As used in this document, the calculated result of the D-H exchange. Karn & Simpson expires in six months [Page 1] DRAFT Photuris March 1995 secret-key A single key which is not publically distributable and not part of a public/private key-pair. Security Association A collection of parameters describing the security relationship between two nodes. These parameters include the transform (including algorithm and algorithm mode), the key(s) (such as a secret-key, or appropriate public/private key-pair), and possibly other information such as sensitivity labelling. For further details, see [A-SA]. 1.2. Use of Public-Key Cryptography Photuris is based on public-key cryptography, specifically Diffie- Hellman key exchange. Exchange of D-H public-values based on private/secret values results in a mutual shared-secret between the parties. This shared-secret can be used on its own, or to generate a series of session-keys for authentication and encryption of subsequent traffic. 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 (KDC), with a database containing every principal's secret- key. This carries significant security risks. Public-key cryptography enables decentralization. Entities generate session-keys without real-time communication with any other party. 1.3. Authentication It has been shown in [DOW92] that key exchange must be coupled to authentication. Photuris supports the use of a variety of digital signature methods. The Photuris messages include selection of authentication algorithms, and facilitate the exchange of any chosen certificate type. The DSS and RSA are examples of digital signatures which will provide strong Karn & Simpson expires in six months [Page 2] DRAFT Photuris March 1995 authentication. Details of DSS, RSA, and other signature algorithms may be found in [5]. 1.4. Defense against Clogging Protecting sensitive data on the Internet 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. To grant access to authorized users regardless of location, it must be possible to cheaply detect and discard bogus datagrams. Otherwise, an attacker intent on sabotage might rapidly send datagrams to exhaust the host's CPU or memory resources. Using Internet Security authentication facilities, when a datagram does not pass an authentication check, it can be discarded without further processing. This is easily done with manual (null) key management between trusted hosts at relatively little cost, given the speed of cryptographic hash functions compared to public-key algorithms. Unfortunately, such a trusted host will have only a fixed number of keys available. The keys will tend to have long lifetimes. This carries significant security risks. Automatic key management is necessary to generate keys between parties without prior arrangement. But, there is a potential Achilles heel in the key management protocol. Because of their use of CPU-intensive operations, such as modular exponentiation, key management schemes based on public-key cryptography are vulnerable to resource clogging attacks. 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. The simple validation of this cookie uses the same level of resources as other Internet Security authentication mechanisms. This limits an attacker to methods which intercept the cookie, forcing the attacker to: 1) use her own IP address, Karn & Simpson expires in six months [Page 3] DRAFT Photuris March 1995 2) gain access to a transmission link to a subnet whose addresses she 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. The cookie does not protect against an observer which can copy a valid cookie, or an interceptor which can modify or substitute another cookie. These attacks are mitigated through using time- variant cookies, and the elimination of receiver state during initial exchanges of the protocol. 1.5. Perfect Forward Secrecy Many security breaches in cryptographic systems have been facilitated by designs which 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 digital signature authentication, as follows: 1. Agree on a shared-secret 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, thwarting the "man in the middle" active attack against Diffie-Hellman. When the shared-secret generated in step 1 is eventually destroyed, it is unrecoverable. The generating information is not based on any other stored information. Karn & Simpson expires in six months [Page 4] DRAFT Photuris March 1995 Theft of the private/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 decode any past traffic that might have been recorded. 1.6. Traffic Anonymity As noted above, a fundamental role of a key management protocol is to verify the identities of the communicating parties to each other. One would often like to deny this information to an eavesdropper, especially when this would reveal the location of a user. Although each datagram carries a cleartext IP Destination address, the ultimate destination could be hidden by "laundering" it through an encrypted tunnel. A user's IP Source address could be hidden in the same manner. If the address has been dynamically allocated, it provides no useful information to an eavesdropper. This leaves the identifying authentication information that the user sends during key exchange. The identification can be easily protected in the Photuris protocol by encrypting the digital signature exchanges with the key just established with Diffie- Hellman. This keeps a passive eavesdropper from learning the identities of the parties by intercepting possible exchanges of public keys and certificates, or by checking the signatures against a known database of public keys. The scheme is not foolproof. By posing as the Responder, an active attacker could trick the Initiator into revealing her identity. However, this active attack is considerably more difficult than passive vacuum-cleaner monitoring. Unless the attacker can steal the private/secret key belonging to the Responsder, the Initiator will discover the deception when checking the digital signature of the key exchange. 1.7. Security Parameters In addition to the key(s) used to encrypt, decrypt or authenticate the payload, the key management mechanism is used to determine a number of parameters for each Security Association between the communicating parties. This includes the particular authentication and/or encryption transforms. Karn & Simpson expires in six months [Page 5] DRAFT Photuris March 1995 The key management implementation usually maintains a table containing the several parameters for each current Security Association. The implementation needs to access that security parameter table to determine how to process each datagram. The Security Parameters Index (SPI) is assigned by the entity controlling the IP Destination address. A session between two parties will normally have two SPI values (one in each direction). The parties use the combination of SPI and IP Destination to distinguish the correct association. The selection mechanism used for the SPI is implementation dependent. However, selection of a random value can help prevent attacks which depend on a predicatable sequence of values. To provide protection against an interceptor which can modify or substitute another SPI, the SPI is used in creating a separate session-key in each direction. While alteration of the SPI will interrupt communication, the attacker will gain no additional information. 1.8. Multicast Support Key management is more difficult in a multicast environment. Senders to a multicast group may share common a Security Parameters Index, if all communications are using the same security configuration parameters. In this case, the receiver only knows that the message came from a node knowing the SPI for the group, and cannot authenticate which member of the group sent the datagram. Multicast groups may also use a separate SPI value for each Source. If each sender is keyed separately and asymmetric algorithms are used, data origin authentication is also provided. A given Destination is not necessarily in control of the selection process. In the case of multicast groups, a single node or cooperating subset of the multicast group may work on behalf of the entire group to set up a Security Association. The author is also open to suggestions on how multicast capability might be added to Photuris, without compromising its fundamental features. Karn & Simpson expires in six months [Page 6] DRAFT Photuris March 1995 2. Protocol Description The Photuris protocol consists of several simple phases: 1. A "cookie" exchange to guard against simple flooding attacks with bogus IP Source addresses. 2. A Diffie-Hellman exchange to establish a session-key for conventional authentication or encryption. 3. An exchange of digital signatures on the Diffie-Hellman messages that were sent in phase 2, to verify their integrity and the identities of the two parties. This exchange may be encrypted to protect the privacy of the parties. 4. Once an initial Security Association has been established, regular operation of the Internet Security protocol begins encryption and/or authentication of user datagrams. 5. Additional messages may be exchanged to periodically change the session-key and to establish new security parameters. Either party may initiate a session at any time. For example, the Initiator need not be a "caller" in a telephony link. The Initiator is responsible for recovering from all message losses by retransmission. The Responder remains stateless until a session- key has been created. Once the session-key calculation has been initiated, the Responder cooperates in creating a second serendipitous session-key, in order to save the effort of another round of key establishment in the other direction. When both parties initiate Photuris key establishment concurrently, or one party initiates more than one Photuris session, the UDP Ports keep the sessions separate. This results in more than one SPI for each Destination. There is no requirement that all such SPIs be used. The sender chooses the SPI for each transmission. Old SPI simply expires after a short period of time (typically 30 seconds), and is purged sometime later (typically 10 minutes). LifeTimes are implementation dependent. Should an expired SPI (which is not yet purged) arrive from an IP Source, a new COOKIE_REQUEST is sent, and the Photuris exchange begins again. Karn & Simpson expires in six months [Page 7] DRAFT Photuris March 1995 Implementation Notes: To provide user-oriented keying, or create multiple Security Associations with different parameters, the sender can initiate multiple Photuris exchanges. It is the responsibility of the sender to assign and segregate the different session-keys. The Destination SHOULD be capable of maintaining multiple SPI values for each Source. 2.1. UDP All Photuris messages use the User Datagram Protocol header [RFC- 768]. The Initiator sends to UDP Destination Port . The Responder reverses the IP Source and Destination, and the UDP Source and Destination Ports. The UDP checksum is required. Any message with an incorrect or zero UDP checksum is silently discarded. 2.2. Variable Precision Numbers Many of the message fields require a value which may vary in the number of bits. These bits may not make up an integral number of octets. Each variable precision number is composed of two parts. Size 2 octets. Number of bits used in the value. Always transmitted most significant octet first. Value variable. The bits used are right justified and zero filled on octet boundaries; that is, any unused bits are in the most significant octet. Always transmitted most significant octet first. 2.3. Transforms Whether authenticating or encrypting, selection among several different transforms is needed to enable future implementation changes without affecting the basic protocol. Each party specifies a list of the transforms supported. Karn & Simpson expires in six months [Page 8] DRAFT Photuris March 1995 The list includes authentication, encryption, and signature types. These are mixed in the same list for simplicity. The implementation can easily distinguish between the separate uses of each supported type. This is not a "negotiation". The Destination indicates what facilities it supports in order of preference, and the Source selects from that list. Each party selects an authentication function from the list of mechanisms supported by the other party. Authentication policy is in the receiver direction. Only the receiver can determine that arriving traffic is authentic. It indicates its need for authentication by including authentication transforms, and/or authenticated encryption transforms, in its transform list. It enforces the authentication through the simple expedient of dropping all datagrams that don't arrive with authentication. Each party additionally selects an encryption mode (if any) according to its own local policy database. Encryption policy is in the transmitter direction. Only the sender knows whether each datagram needs privacy protection. If no, it picks an authentication-only algorithm SPI. If yes, it picks an encryption algorithm SPI. Note that the authentication, encryption and signature mechanisms, as well as the encapsulation mode (if any), need not be the same in both directions. Up-to-date values for the Transform are specified in the most recent "Assigned Numbers" [RFC-1700]. Initial values are assigned as follows: Transforms K INR S 0 Administratively Configured + + + 1 SHA + + + 2 MD2 + + + 3 unassigned 4 MD4 + + + 5* MD5 + + + 6 RSA + 7 DSS + 8 PGP certificate + 9 X.509 certificate + 10 DNS-SIG certificate + 11 unassigned 12 RC2 + 13 unassigned Karn & Simpson expires in six months [Page 9] DRAFT Photuris March 1995 14 RC4 + 15 IDEA + 16 DES-CBC, 0-bit IV + 17* DES-CBC, 32-bit IV + 18* DES-CBC, 64-bit IV + 19 unassigned 20 Triple DES-CBC, 0-bit IV + 21 Triple DES-CBC, 32-bit IV + 22 Triple DES-CBC, 64-bit IV + 24 unassigned * (implementation required) 2.4. Modular Exponentiation Groups The original Diffie-Hellman technique 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 two of these public-values are exchanged between parties, the parties can calculate a shared-secret value between themselves. Each modular exponentiation prime (p) must have the property that both p and (p-1)/2 are prime. A small set of such recommended strong primes for use as Photuris moduli are specified. The modulus-index takes the form of a small index into a well-known table (see "Group Table" Appendix). Since only the first few indices will be published, the remaining values may be used by cooperating parties to indicate private moduli. Use of a very limited number of moduli (preferably one) has one minor and two very significant advantages: Overhead Avoiding the overhead of sending the full modulus. Prime and Generator Pair Selection Discovery of strong primes is extremely computationally intensive, and practically impossible for commercially available processors to find in a reasonable interactive time. Thus, the primes used will be well-known, and embedded in the implementations. Karn & Simpson expires in six months [Page 10] DRAFT Photuris March 1995 The generator (g) should be chosen such that the secret exponents will generate all possible public exponential values, evenly distributed throughout the range, without cycling through a smaller subset. Such a generator is called a "primitive root" (which is trivial to find when p is strong) [!!! reference]. When the strong prime and generator pair are well chosen, the difficulty of a discrete log attack is maximized. By choosing the pairs in advance, thorough analysis of the pair characteristics is possible. This analysis can promote confidence in the security of the implementations. Precomputation Each party can precompute the D-H public-value. A background process can periodically destroy the old values, generate a new random secret exponent, and recalculate the public-value. This limits the exposure of both the secret exponenent and shared-secret, as past secrets are not kept for possible discovery by a future intrusion, protecting earlier communications. Also, the secret exponent 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 reduces CPU loading sufficiently to allow a single public/private key-pair to be used in several closely spaced Photuris executions, when setting up Security Associations with several different hosts over a short period of time. Other precomputation suggestions are described in [w]. 2.5. Elliptic Curve Groups The points on an elliptic curve form a group under addition CITE[x]. This group can be used as the basis for the efficient implementation of the Diffie-Hellman operations. In order to uniquely specify the computation, the implementor must know the finite field for representation of the point coordinates, the elliptic curve, and the generator. Note that while the literature uses the term "addition" for the group operation, it is directly analogous to "multiplication" in modular Karn & Simpson expires in six months [Page 11] DRAFT Photuris March 1995 exponentiation groups. Thus, the analogous term for "g**r" is "r*g" (that is, the scalar multiple r of g). The generator is specified as the (x,y) coordinates of an elliptic curve point, and the representation of x and y is given with respect to a finite field. Multiples of the generator are (x,y) pairs. Thus, the Initiator and Responder D-H public-values are to be interpreted as two concatenated bit values in the order (x,y). The lengths of the numbers are implicit in the specification of the field. The field representation is uniquely determined by the irreducible polynomial specified in the group description. The elliptic curve addition formulas are more complicated than straight-forward component-wise addition, and the use of finite fields further complicates the description of the algorithms. A good reference for a succinct description of elliptic curves with finite fields is CITE[y]; a more general treatment can be found in CITE[y]. (same cite ???) Use of a very limited number of fields has similar advantages to those cited for modular exponentiation: reduced overhead, generator selection, and precomputation of the public-values. Karn & Simpson expires in six months [Page 12] DRAFT Photuris March 1995 3. Cookie Exchange 3.1. Cookie Request +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Initiator-Cookie ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Groups ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- Type 0 Reserved Unused. Zero filled. Initiator-Cookie 16 octets. A randomized value which identifies the exchange. Groups variable. A list of one or more groups supported by the Responder, in order of preference (see "Group Table" Appendix). Each value is one octet. The end of the list is indicated by the Length of the UDP datagram. The Initiator initializes local state, and sends a COOKIE_REQUEST message to the Responder. The Initiator also starts a retransmission timer. If no COOKIE_RESPONSE is obtained within the time limit, a new COOKIE_REQUEST is retransmitted. The I-Cookie value in each successive request SHOULD be different. Karn & Simpson expires in six months [Page 13] DRAFT Photuris March 1995 3.2. Cookie Response +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Group-Index | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Initiator-Cookie ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Responder-Cookie ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Responder-Public-Value ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Transforms ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- Type 1 Group-Index A Responder selected value which indicates which group will be used for the exchange (see "Group Table" Appendix). Reserved Unused. Zero filled. Initiator-Cookie 16 octets. Copied from the COOKIE_REQUEST. Responder-Cookie 16 octets. A randomized value which identifies the exchange. Responder-Public-Value variable precision number. The format is indicated by the Group-Index. Must not be zero or one. Transforms variable. A list of one or more transforms supported by the Responder, in order of preference. Each value is one octet. The end of the list is indicated by the Length of the UDP datagram. On receipt of a COOKIE_REQUEST, the Responder generates a cookie, and returns it in a COOKIE_RESPONSE message. The R-Cookie value in each successive response MAY be different. Karn & Simpson expires in six months [Page 14] DRAFT Photuris March 1995 When too many SPI values are already in use, the COOKIE_REQUEST Is ignored. Note that the Responder creates no state at this time. 3.3. Cookie Generation The exact method by which a Photuris party generates a cookie is implementation dependent. The function chosen must satisfy some basic requirements: 1. The cookie must depend on the specific parties. This prevents an attacker from obtaining a cookie using a real IP address and UDP port, and then using it to swamp the victim with Diffie- Hellman requests from randomly chosen IP addresses or ports. 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. 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 calculate a fast cryptographic one-way hash function (such as MD5) over the IP Source and Destination addresses, the UDP Source and Destination ports, and a locally generated secret random value. An incoming cookie can be verified at any time by regenerating it locally from values contained in the incoming IP datagram and the local secret random value. When an old (or invalid) cookie is detected by the Initiator, the message is silently discarded. When an old (or invalid) cookie is detected by the Responder, it is indicated to the Initiator in an ERROR_MESSAGE, which begins the Photuris exchange again from the COOKIE_REQUEST. Implementation Notes: The Initiator secret random value which affects the cookie SHOULD change for each new COOKIE_REQUEST, and is thereafter cached on a Responder basis. This provides improved synchronization and protection against replay attacks. Karn & Simpson expires in six months [Page 15] DRAFT Photuris March 1995 The Responder secret random value is changed whenever the Responder D-H public-value is changed, in order to detect changes between COOKIE_RESPONSE and KEY_REQUEST. Karn & Simpson expires in six months [Page 16] DRAFT Photuris March 1995 4. Security Parameter Exchange 4.1. Key Request +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | I-Transform | I-Parameters | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Initiator-Security-Parameter-Index | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Initiator-Cookie ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Responder-Cookie ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LifeTime | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Initiator-Public-Value ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Transforms ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- Type 2 I-Transform An authentication or encryption transform selected by the Initiator from the list of Transforms in the COOKIE_RESPONSE. I-Parameters The format and contents of this field are specific to the I-Transform chosen. The formats are detailed in the transform specifications. Common transform formats are included in the "Transform Parameters" Appendix. Initiator-Security-Parameter-Index (I-SPI) The SPI to be used for communicating with the Initiator. Initiator-Cookie 16 octets. Copied from the COOKIE_RESPONSE. Responder-Cookie 16 octets. Copied from the COOKIE_RESPONSE. LifeTime The number of seconds remaining before the I-SPI Karn & Simpson expires in six months [Page 17] DRAFT Photuris March 1995 expires. Initiator-Public-Value variable precision number. The format is indicated by the Group-Index in the COOKIE_RESPONSE. Must not be zero or one. Transforms variable. A list of one or more transforms supported by the Initiator, in order of preference. Each value is one octet. The end of the list is indicated by the Length of the UDP datagram. On receipt of a COOKIE_RESPONSE, the Initiator validates the Initiator-Cookie. Invalid messages are silently discarded. When a valid COOKIE_RESPONSE has been received, a KEY_REQUEST is sent. Later COOKIE_RESPONSES between the same parties are silently discarded, until a new COOKIE_REQUEST is sent. The Initiator also starts a retransmission timer. If no KEY_RESPONSE is obtained within the time limit, the same KEY_REQUEST is retransmitted. Implementation Notes: At this time, the Initiator can begin calculation of the D-H shared-secret. This may take a substantial amount of time. The implementor should ensure that retransmission is not blocked by this calculation. Typically, this is not a problem, as retransmission timeouts exceed calculation time. Karn & Simpson expires in six months [Page 18] DRAFT Photuris March 1995 4.2. Key Response +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | R-Transform | R-Parameters | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Responder-Security-Parameter-Index | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Initiator-Cookie ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Responder-Cookie ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LifeTime | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Reserved | K-Transform | K-Parameters | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Type 3 R-Transform An authentication or encryption transform selected by the Responder from the list of Transforms in the KEY_REQUEST. R-Parameters The format and contents of this field are specific to the R-Transform chosen. The formats are detailed in the transform specifications. Common transform formats are included in the "Transform Parameters" Appendix. Responder-Security-Parameter-Index (R-SPI) The SPI to be used for communicating with the Responder. Initiator-Cookie 16 octets. Copied from the KEY_REQUEST. Responder-Cookie 16 octets. Copied from the KEY_REQUEST. LifeTime The number of seconds remaining before the R-SPI expires. Reserved Unused. Zero filled. K-Transform A cryptographic hash function selected by the Responder from the intersection of the two lists of Karn & Simpson expires in six months [Page 19] DRAFT Photuris March 1995 Transforms, which is used to calculate the session- key. This transform is not necessarily the same as either SPI Transform in use. K-Parameters The format and contents of this field are specific to the K-Transform chosen. Common transform formats are included in the "Transform Parameters" Appendix. On receipt of a KEY_REQUEST, the Responder validates the Responder- Cookie. Invalid messages are silently discarded. The Responder keeps a copy of the incoming KEY_REQUEST message, and its KEY_RESPONSE message. If a duplicate KEY_REQUEST is received, it merely resends the previous KEY_RESPONSE message, and takes no further action. Implementation Notes: At this time, the Responder begins calculation of the D-H shared- secret. This may take a substantial amount of time. The implementor should ensure that retransmission is not blocked by this calculation. Typically, this is not a problem, as retransmission timeouts exceed calculation time. 4.3. Session-Key Computation Each session-key is the K-Transform cryptographic hash of the the computed D-H shared-secret, followed by (concatenated with) the SPI, followed by (concatenated with) the remote party (SPI owner) Cookie followed by (concatenated with) the local party Cookie. Since the SPI is likely to be different in each direction, and the order of the Cookies is different in each direction, the resulting session-key will usually be different in each direction. Both the Initiator and Responder use the resulting SPI session-keys to authenticate or encrypt subsequent messages, including the SIGNATURE_MESSAGE, REKEY_MESSAGE, and new instantiations of the Photuris exchange between the same nodes. Implementation Notes: Calculation of the D-H shared-secret by the Initiator and Responder is executed in parallel to minimize delay. The D-H public-values and resulting shared-secret SHOULD be cached for the LifeTime of the SPI. When multiple Photuris exchanges Karn & Simpson expires in six months [Page 20] DRAFT Photuris March 1995 occur between the same parties, and the public-values are discovered to be unchanged, the cached shared-secret can be used to rapidly generate new session-keys. Note that the Cookie order is reversed when calculating the Responder session-key. 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 party will compromise the shared-secret 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. Secret D-H 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. The exponent 0 will generate the public value 1, and exponent 1 will generate the public value g mod p. These exponents do not qualify as secret. In general, small secret exponent values should not be used. 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. Implementation Notes: A single modular exponentiation on a 486-66DX2 processor using RSAREF and Borland C under MS-DOS took 20 seconds with a 1024-bit Karn & Simpson expires in six months [Page 21] DRAFT Photuris March 1995 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. The size of the exponent is entirely implementation dependent, is unknown to the other party, and can be easily changed. Karn & Simpson expires in six months [Page 22] DRAFT Photuris March 1995 5. Signature Exchange 5.1. Signature Message +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | S-Transform | S-Parameters | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Initiator-Cookie ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Responder-Cookie ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Signature ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Certificate ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Type 4 S-Transform An authentication or certificate transform selected from the list of Transforms sent by the peer, which is used to calculate the Signature. This transform is not necessarily the same as any SPI Transform in use. S-Parameters The format and contents of this field are specific to the transform chosen. Common transform formats are included in the "Transform Parameters" Appendix. Reserved Unused. Zero filled. Initiator-Cookie 16 octets. Copied from the KEY_REQUEST. Responder-Cookie 16 octets. Copied from the KEY_REQUEST. Signature variable precision number. The indicated S- Transform is calculated over the SPI session-key for this direction, followed by (concatenated with) the Karn & Simpson expires in six months [Page 23] DRAFT Photuris March 1995 remote party (SPI owner) Public-Value, followed by (concatenated with) the local party Public-Value, and optionally followed by (concatenated with) an identifying public-key, certificate, or distinguishing name of the local party. Note that the order of the Public-Values is different in each direction. Certificate variable precision number. The presence or absence of this field is indicated by the Length of the UDP datagram. When the S-Transform indicates a certification method, such as X.509, PGP or DNS-SIG, the certificate is always included. When the Initiator completes its parallel computation of the D-H shared-secret, and upon receipt of a valid KEY_RESPONSE, it sends a SIGNATURE_MESSAGE to the Responder. This message is required to be authenticated or encrypted, using the R-SPI Transform indicated in the KEY_RESPONSE. The Initiator also starts a retransmission timer. If no SIGNATURE_MESSAGE is obtained within the time limit, the same SIGNATURE_MESSAGE is retransmitted. When the Responder completes its parallel computation of the D-H shared-secret, and upon receipt of a valid SIGNATURE_MESSAGE, it sends a SIGNATURE_MESSAGE to the Initiator. This message is required to be authenticated or encrypted, using the I-SPI Transform indicated in the KEY_REQUEST. The Responder keeps a copy of its SIGNATURE_MESSAGE. If a duplicate SIGNATURE_MESSAGE is received, it merely resends the previous SIGNATURE_MESSAGE, and takes no further action. 5.2. Signature Verification The two parties now verify the signatures 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 datagrams. Each party implements local policy that determines what access, if any, is granted to the holder of a particular certification. Karn & Simpson expires in six months [Page 24] DRAFT Photuris March 1995 Implementation Notes: Any encrypted and/or authenticated user datagrams received before the completion of signature verification can be placed on a queue pending completion of this step. If the verification succeeds, the queue is processed as though the datagrams had arrived subsequent to the verification. If the verification fails, the queue is discarded. Early implementations may wish to keep their own trusted public- key databases, such as the Pretty Good Privacy web of trust, and accept only those users found there. Karn & Simpson expires in six months [Page 25] DRAFT Photuris March 1995 6. Other Message Types 6.1. Re-Key Message +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | N-Transform | N-Parameters | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Security-Parameter-Index | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Initiator-Cookie ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Responder-Cookie ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LifeTime | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Type 5 N-Transform An authentication or encryption transform selected from the list of Transforms sent by the peer, which is used for the new SPI. This transform is not necessarily the same as any SPI Transform in use. N-Parameters The format and contents of this field are specific to the N-Transform chosen. Common transform formats are included in the "Transform Parameters" Appendix. Security-Parameter-Index The SPI to be used for incoming communications. This value is required to be different from existing SPI values. The value zero indicates all old SPIs for this IP Destination. Initiator-Cookie 16 octets. Copied from the KEY_REQUEST. Responder-Cookie 16 octets. Copied from the KEY_REQUEST. LifeTime The number of seconds remaining before the SPI expires. A value of zero indicates deletion of the indicated SPI. At any time after the validation of signatures, either party can send a REKEY_MESSAGE. The message has effect only in one direction. Karn & Simpson expires in six months [Page 26] DRAFT Photuris March 1995 When too many SPI values are already in use, an ERROR_MESSAGE is sent. No retransmission timer is necessary. Success of the re-keying is indicated by the peer use of the new SPI. Failure will be indicated at expiration of the old SPI, which begins the Photuris exchange again from the COOKIE_REQUEST. This message is required to be authenticated or encrypted. The new session-key is calculated in the same fashion as described previously. The resulting session-key will be different because the SPI value is different. Since the cached D-H shared-secret remains the same, no new exponentiation is needed. Karn & Simpson expires in six months [Page 27] DRAFT Photuris March 1995 6.2. Error Message +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Code | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Initiator-Cookie ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Responder-Cookie ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Type 7 Code Indicates the problem: 0 reserved 1 invalid/expired cookie 2 too many concurrent key requests Reserved Unused. Zero filled. Initiator-Cookie 16 octets. Copied from the offending message. Responder-Cookie 16 octets. Copied from the offending message. Issued in response to Photuris state loss or other problems. The message has effect only in one direction. No retransmission timer is necessary. This message is not required to be authenticated or encrypted. Karn & Simpson expires in six months [Page 28] DRAFT Photuris March 1995 A. Group Table Although these groups are suggested for use in this protocol, cooperating installations might use additional groups. (1) Implementation Required. A 1024-bit strong prime (p), expressed in hex: a478 8e21 84b8 d68b fe02 690e 4dbe 485b 17a8 0bc5 f21d 680f 1a84 1313 9734 f7f2 b0db 4e25 3750 018a ad9e 86d4 9b60 04bb bcf0 51f5 2fcb 66d0 c5fc a63f bfe6 3417 3485 bbbf 7642 e9df 9c74 b85b 6855 e942 13b8 c2d8 9162 abef f434 2435 0e96 be41 edd4 2de9 9a69 6163 8c1d ac59 8bc9 0da0 69b5 0c41 4d8e b865 2adc ff4a 270d 567f The recommended generator (g) for this prime is 5. This prime was randomly generated by a freely available program written by the author. (2) Implementation Optional. Elliptic curve: curve: y^2 + xy = x^3 + 0x7338F generator: (0x7B, 0x1C8) irreducible polynomial: u^155 + u^62 + 1 Supplied by Hilarie Orman . (129) Moduli-indices of 129 to 254 are available for private use. B. Transform Parameters B.1. (Triple) DES-CBC B.2. MD5 There are no parameters. The Parameters field may be any (preferably random) value on transmission, and will be ignored on receipt. Karn & Simpson expires in six months [Page 29] DRAFT Photuris March 1995 Security Considerations Security issues are the topic of this memo. Acknowledgements This protocol has many elements in common with the Station-To-Station authentication protocol, described in [DOW92]. Hilarie Orman provided text regarding elliptic curves, and extensive review of the protocol details. Paul C van Oorschot suggested signing both the public exponents and the session-key, in order to provide an authentication-only version of signature verification. Randall Atkinson, Cheryl Madson, James Hughes, and Perry Metzger provided useful critiques of earlier versions of this document. Thanks to Bill Simpson for his protocol suggestions, editorial changes and NROFF formatting. All such mistakes are his responsibity. 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. Karn & Simpson expires in six months [Page 30] DRAFT Photuris March 1995 [6] Kerberos? [A-SA] Randall Atkinson, "Security Architecture for the Internet Protocol", work in progress. [DOW92] Whitfield Diffie, Paul C van Oorshot, Michael J Wiener, "Authentication and Authenticated Key Exchanges", Designs, Codes and Cryptography, v 2 pp 107-125, Kluwer Academic Publishers, 1992. [w] 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. [x] Alfred J. Menezes, "Elliptic Curve Public Key Cryptosystems", Kluwer Academic Publishers, 1993. [y] Alfred J. Menezes, Minghua Qu, and Scott A. Vanstone, "Standard for RSA, Diffie-Hellman and Related Public Key Cryptography", Working Draft of IEEE P1363 Standard, Oct. 30, 1994. http://www.rsa.com/pub/p1363/draft/ 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@qualcomm.com karn@unix.ka9q.ampr.org William Allen Simpson Daydreamer Computer Systems Consulting Services 1384 Fontaine Madison Heights, Michigan 48071 Bill.Simpson@um.cc.umich.edu bsimpson@MorningStar.com Karn & Simpson expires in six months [Page 31]