Network Working Group Phil Karn Internet Draft Qualcomm W A Simpson DayDreamer expires in six months October 1995 The Photuris Session Key Management Protocol draft-ietf-ipsec-photuris-04.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 [Firefly] is an experimental session-key management protocol intended for use with the IP Security Protocols (AH and ESP). Karn & Simpson expires in six months [Page i] DRAFT Photuris October 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. However, secure manual distribution and maintainance of these keys is often cumbersome and problematic. Moreover, user distribution often leads to long-lived keys, with concommitant opportunity for compromise of the keys. In addition, it has been shown [DOW92] that key exchange must be coupled to authentication. Each party requires assurances that an exchanged key is not shared with an imposter. 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. With these criteria in mind, Photuris is designed: 1. for frequent exchange of short-lived individual session-keys, with a minimum of configuration and effort. 2. to support the use of a variety of digital signature methods, and facilitate the exchange of many identification certificate types. 3. to thwart certain types of denial of service attacks on host resources. Design Notes: Photuris was based on currently available tools, by experienced network protocol designers with an interest in cryptography, rather than by cryptographers with an interest in network Karn & Simpson expires in six months [Page 1] DRAFT Photuris October 1995 protocols. Although some review has been provided by the general cryptographic community, it is anticipated that design decisions and tradeoffs will be thoroughly analysed in many subsequent dissertations and debated for many years to come. Digital signatures are used to provide strong authentication. Details of MD5, DSS, RSA, and other digital signature algorithms may be found in [Schneier94]. 1.1. Terminology exchange-value The publically distributable value used to calculate a shared-secret. As used in this document, refers to a Diffie-Hellman exchange, as opposed to a public-key. private-key A key that is kept secret, and is part of a public/private key-pair. As used in this document, refers to RSA key pairs. public-key A publically distributable value that is part of a public/private key-pair. As used in this document, refers to RSA key pairs. secret-key A key which is not publically distributable, and not part of a public/private key-pair. An example is a user password. Security Association A collection of parameters describing the security relationship between two nodes. These parameters include the identities of the parties, the transform (including algorithm and algorithm mode), the key(s) (such as a session-key, secret-key, or appropriate public/private key-pair), and possibly other information such as sensitivity labelling. For further details, see [RFC-1825]. Security Parameters Index (SPI) A number which indicates the Security Association. session-key A key which is independently derived from a shared- secret by the parties, and used for keying one direction of traffic. This key is changed frequently. Karn & Simpson expires in six months [Page 2] DRAFT Photuris October 1995 shared-secret As used in this document, the calculated result of the Photuris exchange. transform A cryptographic manipulation of a particular set of data. As used in this document, refers to such specific methods (defined elsewhere). For example, MD5 [RFC-1828] transforms a specified set of fields into a hash, and DES [RFC-1829] transforms plaintext to ciphertext and back again. 1.2. Protocol Description The Photuris protocol consists of several simple phases: 1. A "Cookie" Exchange guards against simple flooding attacks with bogus IP Source addresses. 2. A Key Value Exchange establishes a shared-secret between the parties. The Responder remains stateless until a shared-secret has been created. 3. A Signature Exchange of digital signatures over values sent in phases 1 and 2 verifies their integrity, and identifies the parties to each other. The shared-secret provides a basis to generate Security Association session-keys, which are in turn used for conventional authentication or encryption. Additional security parameters are also exchanged as needed. This exchange may also be encrypted for privacy using the shared-secret. This protects the identities of the parties and hides the security parameter values. 4. Additional messages may be exchanged to periodically change the session-keys, and to establish new or revised security parameters. These exchanges may also be encrypted for privacy in the same fashion as above. Karn & Simpson expires in six months [Page 3] DRAFT Photuris October 1995 Initiator Responder ========= ========= Cookie_Request -> <- Cookie_Response offer schemes Key_Request -> pick scheme offer attributes <- Key_Response pick anonymity method offer attributes generate shared-secret Signature_Message -> make SPI pick key generation pick SPI attributes sign <- Signature_Message make SPI pick key generation pick SPI attributes sign (optional) Change_Message(s) -> <- Change_Message(s) Either party may initiate an exchange 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. When both parties initiate Photuris key establishment concurrently, or one party initiates more than one Photuris exchange, the Initiator Cookies (and UDP Ports) keep the sessions separate. This results in more than one initial SPI for each Destination. There is no requirement that all such outstanding SPIs be used. The SPI User (sender) chooses the appropriate SPI for each transmission. Implementation Notes: To provide user-oriented keying, or create multiple Security Karn & Simpson expires in six months [Page 4] DRAFT Photuris October 1995 Associations with different parameters, the sender can either initiate multiple Photuris exchanges, or send a Change_Message. The Destination MUST be capable of maintaining multiple Security Associations (SPI values) for each Source. It is the responsibility of the Source to internally segregate the different session-keys provided by the Destination. 1.3. Clogging Defense 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, Photuris features make them much more difficult. Cookie Exchange 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 forces the attacker to: Karn & Simpson expires in six months [Page 5] DRAFT Photuris October 1995 1) use its own valid IP address, or 2) gain access to a physical transmission link and appropriate those addresses, 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. However, these attacks are mitigated somewhat with time-variant cookies. State During the initial cookie exchange, Photuris does not maintain any state for the exchange. This prevents memory resource exhaustion from a simple flooding attack. However, later exchange stages require saving of state to perform the key establishment calculations and exchange verification. An attacker which is willing to expose itself to a larger window of detection can waste resources repeating all the steps of the Photuris process. Precomputation Once state has been established between parties, repetitive exchanges can use many of the same previously computed values. This prevents an attacker with more CPU power from easily exhausting the target. Expiration All retained state is subject to periodic expiration, usually related to the speed of the link (typically 30 to 300 seconds), and is purged sometime later (typically 10 minutes). These LifeTimes are implementation dependent. When an attacker has succeeded in overwhelming a target, the target will eventually recover as the expired state is purged. The periodic expiration and purge of retained state also reduces Karn & Simpson expires in six months [Page 6] DRAFT Photuris October 1995 the risk of compromise of keys and secrets, and is an important consideration in attaining perfect forward secrecy. 1.4. Security Parameters Photuris key management 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, and the key(s) used to authenticate, encrypt or decrypt the payload. The key management implementation usually maintains a table containing the several parameters for each concurrent 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 distinct 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 cryptographically 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.5. 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 Karn & Simpson expires in six months [Page 7] DRAFT Photuris October 1995 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. It is anticipated that Photuris would be used first to establish a distribution SPI and session-key, and that another orthogonal key distribution mechanism will use that SPI to send the group keys. Such a mechanism is outside the scope of this document. Karn & Simpson expires in six months [Page 8] DRAFT Photuris October 1995 2. Protocol Details 2.1. UDP All Photuris messages use the User Datagram Protocol header [RFC- 768]. The Initiator sends to UDP Destination Port 468. The Responder reverses the IP Source and Destination, and the UDP Source and Destination Ports. The UDP checksum MUST be correctly calculated when sent. When a message is received with an incorrect UDP checksum, it is silently discarded. Implementation Note: It is expected that installation of Photuris will ensure that UDP checksums are enabled for the computer operating system and later disabling by operators is prevented. 2.2. Header Format All of the messages have a format similar to the following, as transmitted left to right in network order (most significant to least significant): +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Initiator-Cookie ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Responder-Cookie ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | +-+-+-+-+-+-+-+-+ Initiator-Cookie 16 octets. Responder-Cookie 16 octets. Type Each message type has a unique value. Further details and differences are elaborated in the individual messages. Karn & Simpson expires in six months [Page 9] DRAFT Photuris October 1995 Design Note: The fixed size of the cookies was chosen for convenience, based on the output of commonly available cryptographic hashing functions. It is anticipated that this size is likely to be sufficient to protect against very high bit-rate flooding attacks. 2.3. Exchange Schemes Selection among several different exchange schemes is needed to enable experimental and proprietary extensions without affecting the basic protocol. The target of the exchange (Responder) specifies a list of the schemes supported, and the Initiator chooses one which it also supports. The scheme list includes alternative algorithms and distinguishing parameters. These are mixed in the same list for simplicity. The implementation can easily distinguish between the separate uses of each supported scheme, as indicated in the "Exchange Scheme List" Appendix. 2.4. Attributes Selection among several different security parameter attributes is needed to enable future implementation changes without affecting the basic protocol. Each party (the sender) offers a list of the attributes supported and its peer (the receiver) selects from that list when making its incoming Security Associations. The attribute list includes authentication, compression, encryption, labelling, operational, and signature types. These are mixed in the same list for simplicity. The implementation can easily distinguish between the separate uses of each supported attribute, as indicated in the "Attribute List" Appendix. Each party may select one or more encryption methods. Encryption policy is in the SPI User (sender) direction. Only the sender knows whether each datagram needs privacy protection, and it uses an encryption SPI created by the receiver, in addition to an authentication SPI (as needed). In the case that the sender needs privacy protection for a datagram, and the potential receiver has not yet created an encryption SPI, an Error_Message listing encryption attributes is sent and the original datagram is discarded. Karn & Simpson expires in six months [Page 10] DRAFT Photuris October 1995 Each party may select one or more authentication methods. Authentication policy is in the SPI Owner (receiver) direction. Only the receiver can determine that arriving traffic is authentic. Its need for authentication is indicated by choosing authentication attributes, and/or authenticated encryption attributes, when creating each SPI. It enforces the authentication through the simple expedient of dropping all datagrams with missing or invalid authentication. Implementation Notes: Support for some attributes is required (MD5 and DES-CBC), and MUST be present in every Offered-Attributes list. It is not required that a Security Association be created including every such attribute. Typically, an encryption method is chosen for the primary attribute of the SPI, and an authentication method is later added for the same SPI, or as an additional separate SPI. The authentication, compression, encryption and signature mechanisms, as well as the encapsulation mode (if any), need not be the same in both directions. 2.5. 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. Karn & Simpson expires in six months [Page 11] DRAFT Photuris October 1995 3. Cookie Exchange The Initiator initializes local state, and sends a Cookie_Request to the Responder. The Initiator also starts a retransmission timer. If no Cookie_Response is obtained within the time limit, the Cookie_Request is retransmitted. The Initiator-Cookie value in each such retransmission to the same IP Destination and UDP Port SHOULD be the same. On receipt of a Cookie_Request, the Responder determines if there are sufficient resources to begin another Photuris exchange. When too many SPI values are already in use for this particular peer, or some other resource limit is reached, an Error_Message is sent. Otherwise, the Responder generates a cookie, and returns it in a Cookie_Response. The Responder-Cookie value in each successive response MAY be different. Note that the Responder creates no additional state at this time. On receipt of a Cookie_Response, the Initiator validates the Initiator-Cookie. Invalid messages are silently discarded. Karn & Simpson expires in six months [Page 12] DRAFT Photuris October 1995 3.1. Cookie_Request +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Initiator-Cookie ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Responder-Cookie ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | +-+-+-+-+-+-+-+-+ Initiator-Cookie 16 octets. A randomized value which identifies the exchange. Responder-Cookie 16 octets. Unused, MUST be set to zero when transmitted, and MUST be ignored when received. Type 0 Karn & Simpson expires in six months [Page 13] DRAFT Photuris October 1995 3.2. Cookie_Response +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Initiator-Cookie ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Responder-Cookie ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Reserved | Offered-Schemes ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Initiator-Cookie 16 octets. Copied from the Cookie_Request. Responder-Cookie 16 octets. A randomized value which identifies the exchange. Type 1 Reserved 1 octet. Unused, MUST be set to zero when transmitted, and MUST be ignored when received. Offered-Schemes variable. A list of one or more exchange schemes supported by the Responder, in increasing order of preference. Each value is two octets (see "Exchange Scheme Table" Appendix). The end of the list is indicated by the UDP Length. 3.3. Cookie Generation The exact technique 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 requests from randomly chosen IP addresses or ports. 2. It must not be possible for anyone other than the issuing entity to generate cookies which will be accepted by that Karn & Simpson expires in six months [Page 14] DRAFT Photuris October 1995 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 and verification functions must be fast to thwart attacks intended to sabotage CPU resources. A recommended technique is to calculate a 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. Initiator The Initiator secret random value which affects the cookie SHOULD change for each new Photuris exchange, and is thereafter internally cached on a per Responder basis. This provides improved synchronization and protection against replay attacks. An alternative is to cache the cookie instead of the secret value. Incoming cookies can be compared directly without the computational cost of regeneration. Responder The Responder secret random value MAY remain the same for many different Initiators, and is not cached per Initiator to avoid saving state during the initial exchange. Instead, the secret SHOULD be changed at the same frequency as its Exchange-Value. During the initial Cookie Exchange, the Responder needs to regenerate its cookie. Once the Key_Request is received, both Initiator and Responder cookies are cached to identify the exchange. Karn & Simpson expires in six months [Page 15] DRAFT Photuris October 1995 4. Value Exchange When a valid Cookie_Response is received by the Initiator, a Key_Request is sent. Later Cookie_Responses from the same Responder are silently discarded, until a new Cookie_Request is sent. The Initiator also starts a retransmission timer. If no valid Key_Response is obtained within the time limit, the same Key_Request is retransmitted. On receipt of a Key_Request, the Responder validates the Responder- Cookie. Whenever an old (or invalid) cookie is detected by the Responder, an Error_Message is sent. When a valid Key_Request has been received, a Key_Response is sent. The Responder keeps a copy of the incoming Key_Request values, and its Key_Response. If a duplicate Key_Request is received, it merely resends its previous Key_Response, and takes no further action. Implementation Notes: At this time, the Responder begins calculation of the shared- secret. This may take a substantial amount of time. The implementor should ensure that retransmission is not blocked by this calculation. This is not usually a problem, as retransmission timeouts typically exceed calculation time. Karn & Simpson expires in six months [Page 16] DRAFT Photuris October 1995 4.1. Key_Request +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Initiator-Cookie ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Responder-Cookie ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Reserved | Scheme-Choice | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Initiator-Exchange-Value ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Initiator-Offered-Attributes ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- Initiator-Cookie 16 octets. Copied from the Cookie_Response. Responder-Cookie 16 octets. Copied from the Cookie_Response. Type 2 Reserved 1 octet. Unused, MUST be set to zero when transmitted, and MUST be ignored when received. Scheme-Choice 2 octets. A value selected by the Initiator from the list of Offered-Schemes in the Cookie_Response. Initiator-Exchange-Value variable precision number. Provided by the Initiator for calculating a shared-secret between the parties. The format is indicated by the Scheme-Choice. Although the field is depicted as 32-bit aligned for convenience, the size may be shorter or longer, as indicated by its integral Size field. Initiator-Offered-Attributes variable. A list of three or more Security Parameter attributes supported by the Initiator, in increasing order of preference. Karn & Simpson expires in six months [Page 17] DRAFT Photuris October 1995 The formats are specified in the "Attribute List" Appendix. The end of the list is indicated by the UDP Length. Karn & Simpson expires in six months [Page 18] DRAFT Photuris October 1995 4.2. Key_Response +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Initiator-Cookie ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Responder-Cookie ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Reserved | Anonymity-Choice | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Responder-Exchange-Value ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Responder-Offered-Attributes ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- Initiator-Cookie 16 octets. Copied from the Key_Request. Responder-Cookie 16 octets. Copied from the Key_Request. Type 3 Reserved 1 octet. Unused, MUST be set to zero when transmitted, and MUST be ignored when received. Anonymity-Choice variable. An optional encryption method selected by the Responder from the list of Initiator- Offered-Attributes in the Key_Request. This encryption method is used to protect the Signature_Messages and Change_Messages. It is separate from any encryption specified in later Security Associations. The fields protected are described for each method (see "Attribute List" Appendix). When no anonymity protection is in use, the value is two octets of zero. Although the field is depicted as 16-bits for convenience, the size may be longer, as indicated by its Length field. Karn & Simpson expires in six months [Page 19] DRAFT Photuris October 1995 Responder-Exchange-Value variable precision number. Provided by the Responder for calculating a shared-secret between the parties. The format is indicated by the Scheme-Choice. Although the field is depicted as 32-bit aligned for convenience, the size may be shorter or longer, as indicated by its integral Size field. Responder-Offered-Attributes variable. A list of three or more Security Parameter attributes supported by the Responder, in increasing order of preference. The formats are specified in the "Attribute List" Appendix. The end of the list is indicated by the UDP Length. Karn & Simpson expires in six months [Page 20] DRAFT Photuris October 1995 5. Signature Exchange On receipt of a valid Key_Response, the Initiator begins its parallel computation of the shared-secret. When the Initiator completes computation, it sends a Signature_Message to the Responder. The Initiator also starts a retransmission timer. If no Signature_Message response is obtained within the time limit, the same Signature_Message request is retransmitted. When the Responder completes its parallel computation of the shared- secret, and upon receipt of a valid Signature_Message, it sends a Signature_Message to the Initiator. The Responder keeps a copy of the incoming Signature_Message values, and its Signature_Message. If a duplicate Signature_Message is received, it merely resends its previous Signature_Message, and takes no further action. Implementation Notes: Calculation of the shared-secret by the Initiator and Responder is executed in parallel to minimize delay. The scheme, exchange-values, and resulting shared-secret SHOULD be cached. When multiple Photuris exchanges occur between the same parties, and the exchange-values are discovered to be unchanged, the cached shared-secret can be used to rapidly generate new session-keys. Karn & Simpson expires in six months [Page 21] DRAFT Photuris October 1995 5.1. Signature_Message +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Initiator-Cookie ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Responder-Cookie ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | LifeTime | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Security-Parameter-Index | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Signature-Choice | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | | ~ Signature ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Certificate ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Key-Generator-Choice | Attribute-Choices ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... Padding | Pad Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Initiator-Cookie 16 octets. Copied from the Key_Request. Responder-Cookie 16 octets. Copied from the Key_Request. Type 4 LifeTime 3 octets. The number of seconds remaining before the indicated SPI expires. Must be greater than zero. Security-Parameter-Index 4 octets. The SPI to be used for incoming communications. Signature-Choice variable. An authentication method or certificate attribute is selected from the list of Offered- Karn & Simpson expires in six months [Page 22] DRAFT Photuris October 1995 Attributes sent by the peer, and is used to calculate the Signature. This method is not necessarily the same as any SPI Attribute-Choices in use. Although the field is depicted as 16-bits for convenience, the size may be longer, as indicated by its Length field. Signature variable precision number. The result of the Signature-Choice. The content is outside the scope of this specification. Although the field is depicted as 32-bit aligned for convenience, the size may be shorter or longer, as indicated by its integral Size field. Certificate variable precision number. When the Signature- Choice indicates a certification method, such as X.509, PGP or DNS-SIG, the certificate is included. The content is outside the scope of this specification. Although the field is depicted as 32-bit aligned for convenience, the size may be shorter or longer, as indicated by its integral Size field. Key-Generator-Choice variable. A cryptographic hash function is selected from the peer's list of supported Attributes, and is used to calculate the session-key. This method is not necessarily the same as any SPI Attribute-Choices in use. Although the field is depicted as 16-bits for convenience, the size may be longer, as indicated by its Length field. Attribute-Choices variable. A list of one or more attributes for the Security Association. The formats are specified in the "Attribute List" Appendix. The end of the list is indicated by the UDP Length minus the Pad Length and Padding. Karn & Simpson expires in six months [Page 23] DRAFT Photuris October 1995 Padding variable. Prior to encryption, it is filled with unspecified implementation dependent (preferably random) values, to align the Pad Length field at a boundary appropriate to the Anonymity-Choice. After decryption, it MUST be ignored. Pad Length 1 octet. This field indicates the size of the Padding field. It does not include the Pad Length fields. The value typically ranges from 0 to 7, but may be up to 255 to permit hiding of the actual data length. This field is opaque. That is, the value is set prior to encryption, and is examined only after decryption. 5.2. Anonymity This message is encrypted using the Anonymity-Choice indicated in the Key_Response. The chosen algorithm need not provide integrity, as sufficient integrity is provided by the signature verification. The fields protected are described for each method. A single non- negotiable key generation mechanism is specified for each method to create a special anonymity session-key (see "Attribute List" Appendix). The Anonymity-Choice specified cryptographic hash is calculated over the following concatenated values: + the computed shared-secret, + the SPI Owner (receiver) Exchange-Value, + the SPI User (sender) Exchange-Value, + the SPI Owner (receiver) Cookie, + the SPI User (sender) Cookie, + the computed shared-secret again. Since the order of the Exchange-Values and Cookies is different in each direction, the resulting anonymity session-key will usually be different in each direction. 5.3. Verification The two parties now verify the signatures received. The indicated Signature-Choice is calculated over the following concatenated Karn & Simpson expires in six months [Page 24] DRAFT Photuris October 1995 values: + the computed shared-secret, + the Offered-Schemes, + the SPI Owner (receiver) Exchange-Value, + the SPI User (sender) Exchange-Value, + the SPI Owner (receiver) Offered-Attributes, + the SPI User (sender) Offered-Attributes, + the Type, LifeTime and SPI, + the Certificate (which may be specially handled), + the contents of the remainder of the message following the Certificate, + the authentication secret-key (if any), + the computed shared-secret again. Note that the order of the Exchange-Values and Offered-Attributes is different in each direction. If the verification fails, the users are notified, an Error_Message is sent, and the Security Association is destroyed. On success, normal operation begins with the authentication and/or encryption of user datagrams. Implementation Notes: Any authenticated and/or encrypted 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 key databases, such as the Pretty Good Privacy web of trust, and accept only those users found there. Each party implements local policy that determines what access, if any, is granted to the holder of a particular certification. 5.4. Session-Key Computation Each SPI session-key is generated from the Key-Generator-Choice cryptographic hash calculated over the following concatenated values: Karn & Simpson expires in six months [Page 25] DRAFT Photuris October 1995 + the computed shared-secret, + the SPI Owner (receiver) Signature, + the SPI User (sender) Signature, + the SPI Owner (receiver) Cookie, + the SPI User (sender) Cookie, + the SPI, + the computed shared-secret again. Since the SPI is likely to be different in each direction, and the order of the Signatures and Cookies is different in each direction, the resulting session-key will usually be different in each direction. Karn & Simpson expires in six months [Page 26] DRAFT Photuris October 1995 6. Other Message Types The use of these messages has been indicated earlier. 6.1. Change_Message +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Initiator-Cookie ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Responder-Cookie ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | LifeTime | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Security-Parameter-Index | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Validity-Choice | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | | ~ Verification ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Key-Generator-Choice | Attribute-Choices ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... Padding | Pad Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Initiator-Cookie 16 octets. Copied from the Key_Request. Responder-Cookie 16 octets. Copied from the Key_Request. Type 5 LifeTime 3 octets. The number of seconds remaining before the indicated SPI expires. The value zero indicates deletion of the indicated SPI. Security-Parameter-Index 4 octets. The SPI to be used for incoming communications. This may be a new SPI value (for creation), or an existing SPI value (for deletion). The value zero indicates all old SPIs for this IP Karn & Simpson expires in six months [Page 27] DRAFT Photuris October 1995 Destination (typically used for deletion). Validity-Choice variable. A cryptographic hash function is selected from the peer's list of supported Attributes, and used to provide message integrity. This method is not necessarily the same as any SPI Attribute-Choice in use. Although the field is depicted as 16-bits for convenience, the size may be longer, as indicated by its Length field. Verification variable precision number. The result of the Validity-Choice. The calculation of the value is described in the Verification section. Although the field is depicted as 32-bit aligned for convenience, the size may be shorter or longer, as indicated by its integral Size field. Key-Generator-Choice variable. A cryptographic hash function is selected from the peer's list of supported Attributes, and is used to calculate the session-key. This method is not necessarily the same as any SPI Attribute-Choices in use. Although the field is depicted as 16-bits for convenience, the size may be longer, as indicated by its Length field. Attribute-Choices variable. A list of one or more attributes for the Security Association, selected from the list of Attributes sent by the peer. The formats are specified in the "Attribute List" Appendix. The end of the list is indicated by the UDP Length minus the Pad Length and Padding. Padding variable. Prior to encryption, it is filled with unspecified implementation dependent (preferably random) values, to align the Pad Length field at a boundary appropriate to the Anonymity-Choice. Karn & Simpson expires in six months [Page 28] DRAFT Photuris October 1995 After decryption, it MUST be ignored. Pad Length This field indicates the size of the Padding field. It does not include the Pad Length fields. The value typically ranges from 0 to 7, but may be up to 255 to permit hiding of the actual data length. This field is opaque. That is, the value is set prior to encryption, and is examined only after decryption. At any time after the validation of signatures, either party can send a Change_Message. The message has effect in only one direction, from the SPI Owner to the SPI User. This message is required to be encrypted in the same fashion described for the Signature_Message. 6.2. Creation This message can be used to create a new Security Association. Frequently, this message is used to create a separate authentication SPI when the primary SPI is used for encryption. In addition, this message allows more rapid SPI creation for high bandwidth applications. The messages flow in the opposite direction from the primary traffic flow. A new session-key is calculated using the Key-Generator-Choice in the same fashion as the Signature_Message. The cached shared-secret remains the same; thus, no new exponentiation or signature verification is needed. Since the SPI value is different, the resulting session-key will necessarily be different from all others used in the same direction. When the peer's cookie or public-value has expired, it will send an Error_Message response. The party begins a new Photuris exchange again from the Cookie_Request. When the peer finds that too many SPI values are already in use for this party, or some other resource limit is reached, it will send an Error_Message response. No retransmission timer is necessary. Success is indicated by the peer use of the new SPI. Karn & Simpson expires in six months [Page 29] DRAFT Photuris October 1995 Should all creation attempts fail, eventually the peer will find that all existing SPIs have expired, and begin the Photuris exchange again from the Cookie_Request. 6.3. Deletion This message can be used to delete existing Security Associations. This is especially useful when all associations need deletion, such as when the application which needed them terminates. No retransmission timer is necessary. Should all deletion attempts fail, eventually the peer will expire all existing SPIs through the normal LifeTime, and begin the Photuris exchange again from the Cookie_Request. 6.4. Verification This message requires independent verification of integrity, to prevent malicious forgery of Security Attributes after the more computationally intensive Signature Exchange. The indicated Validity-Choice is calculated over the following concatenated values: + the computed shared-secret, + the SPI Owner (receiver) Signature, + the SPI User (sender) Signature, + the SPI Owner (receiver) Cookie, + the SPI User (sender) Cookie, + the contents of the message beginning with the UDP Header, + the computed shared-secret again. Note that the order of the Signatures and Cookies is different in each direction. If the verification fails, the users are notified, an Error_Message is sent, and the Security Association is destroyed. On success, normal operation begins with the authentication and/or encryption of user datagrams. Implementation Notes: The Verification value is calculated prior to anonymity Karn & Simpson expires in six months [Page 30] DRAFT Photuris October 1995 encryption, and verified after decryption. The Verification field is treated as zero during the calculation of the Validity-Choice. This validation value is different from the anonymity session-key which is used to protect the message. However, the initial octets of the concatenated values are the same, and the implementor may save some calculation effort when the generating functions are the same. Karn & Simpson expires in six months [Page 31] DRAFT Photuris October 1995 6.5. Error_Message +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Initiator-Cookie ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Responder-Cookie ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Code | Attributes-Needed ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- Initiator-Cookie 16 octets. Copied from the offending message. Responder-Cookie 16 octets. Copied from the offending message. Type 7 Code Indicates the problem: 0 reserved 1 invalid/expired 2 resource limit 3 verification failure 4 need attributes Attributes-Needed variable. A list of zero or more attributes (for Code 4). The formats are specified in the "Attribute List" Appendix. The end of the list is indicated by the UDP Length. Issued in response to Photuris state loss or other problems. The message has effect in only one direction. No retransmission timer is necessary. This message is not encrypted in the fashion described for the Signature_Message. Karn & Simpson expires in six months [Page 32] DRAFT Photuris October 1995 6.6. Invalid/Expired This Error_Message Code is sent when certain Photuris messages are received (as indicated in the accompanying description), and the receiver's cookie is invalid or the associated public-value has expired. When this Code is received, the shared-secret and other state between the parties is purged, and a new Cookie_Request is sent instead. However, existing SPIs are not deleted. They expire normally, and are purged sometime later. 6.7. Resource Limit This Error_Message Code is sent when a Cookie_Request or Change_Message is received, and too many SPI values are already in use for that peer, or some other Photuris resource is unavailable. When this Code is received, the party SHOULD NOT instantiate another SPI until it has deleted an existing SPI, or waited for a cached SPI entry to expire. 6.8. Verification Failure This Error_Message Code is sent when a Signature_Message or Change_Message is received, and verification fails. When this Code is received, the implementation SHOULD log the occurance, and notify an operator as appropriate. 6.9. Need Attributes This Error_Message Code is sent when a party needs particular attributes for a datagram (such as encryption), and the peer has not yet created a Security Association (SPI) which has those attributes. The missing attributes are included in the Error_Message. When this Code is received, the party SHOULD send a Change_Message which includes the necessary attributes. Karn & Simpson expires in six months [Page 33] DRAFT Photuris October 1995 7. Public Key Exchanges Photuris is based on public-key cryptography, specifically Diffie- Hellman key exchange. Exchange of D-H exchange-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 [Kerberos] 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. This draft assumes familiarity with the Diffie-Hellman public-key algorithm. A good description can be found in [Schneier94]. 7.1. 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. The keys should not be based on the values of any previous keys, or any other long-lived stored information. The Photuris exchange messages can provide perfect forward secrecy, Karn & Simpson expires in six months [Page 34] DRAFT Photuris October 1995 as defined by Diffie [Diffie90], using 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. 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. 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. 7.2. 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 shared-secret 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 its identity. However, this active attack is considerably more difficult than passive vacuum-cleaner monitoring. Unless the attacker can steal the Karn & Simpson expires in six months [Page 35] DRAFT Photuris October 1995 private/secret key belonging to the Responder, the Initiator will discover the deception when checking the digital signature of the key exchange. 7.3. Modular Exponentiation Groups The original Diffie-Hellman technique specified modular exponentiation. A exchange-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 values are exchanged between parties, the parties can calculate a shared-secret value between themselves. 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. 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. 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. 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 Karn & Simpson expires in six months [Page 36] DRAFT Photuris October 1995 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 exchange-value. A background process can periodically destroy the old values, generate a new random secret exponent, and recalculate the exchange-value. This limits the exposure of both the secret exponent 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 creating Security Associations with several different hosts over a short period of time. Other precomputation suggestions are described in [BGMW93]. 7.4. Elliptic Curve Groups The points on an elliptic curve form a group under addition. This group can be used as the basis for the efficient implementation of the Diffie-Hellman operations. To uniquely specify the computation, the implementor must know the finite field for representation of the point coordinates, the elliptic curve, and the generator. 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 [P1363]; a more general treatment can be found in [Menezes]. Note that while the literature uses the term "addition" for the group operation, it is directly analogous to "multiplication" in modular exponentiation groups. Thus, the analogous term for Karn & Simpson expires in six months [Page 37] DRAFT Photuris October 1995 "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 Exchange-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. See the "Exchange Scheme Table" Appendix. 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 exchange-values. 7.5. Exponent Selection There is surprisingly little guidance in the literature about the length of the randomly chosen secret exponents. The size of these exponents dramatically affects the speed of Diffie-Hellman operations. It is desirable to use the smallest random exponent that is consistent with good security. The strength of the shared-secret is dependent on the work factor for solving the secret exponents. Revealing the exponent(s) of either party will unravel the shared-secret. Each party depends upon the other to provide sufficiently strong exponents. The most conservative advice received to date [Hellman95] is to make the random exponents twice as long as the strength required of 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. Different attributes require different levels of session-key strength. Each party should use exponent(s) that provide the strength required for the strongest offered attribute. 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 prime modulus and a 1024-bit random exponent. This dropped to Karn & Simpson expires in six months [Page 38] DRAFT Photuris October 1995 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 39] DRAFT Photuris October 1995 A. Exchange Scheme Table The Exchange Scheme takes the form of a small index into a well-known table. Since only the first few indices will be published, the remaining values may be used by cooperating parties to indicate private schemes. (1) Implementation Optional. Elliptic curve: curve: y^2 + xy = x^3 + 0x7338F generator: (0x7B, 0x1C8) irreducible polynomial: u^155 + u^62 + 1 Provides 155 bits of keying material (in 160 bits). The cryptographic strength is 155/2 bits. Supplied by Hilarie Orman . (2) Implementation Required. A 1024-bit strong prime (p), expressed in hex: 97f6 4261 cab5 05dd 2828 e13f 1d68 b6d3 dbd0 f313 047f 40e8 56da 58cb 13b8 a1bf 2b78 3a4c 6d59 d5f9 2afc 6cff 3d69 3f78 b23d 4f31 60a9 502e 3efa f7ab 5e1a d5a6 5e55 4313 828d a83b 9ff2 d941 dee9 5689 fada ea09 36ad df19 71fe 635b 20af 4703 6460 3c2d e059 f54b 650a d8fa 0cf7 0121 c747 99d7 5871 32be 9b99 9bb9 b787 e8ab The recommended generator (g) for this prime is 2. Provides 1024 bits of keying material. The cryptographic strength is length/2 of the shortest exponent used. This prime was randomly generated by a freely available program written by the author. (3) Reserved. (4) Reserved. (5) Implementation Optional. A 1024-bit strong prime (p), expressed in hex: Karn & Simpson expires in six months [Page 40] DRAFT Photuris October 1995 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. Provides 1024 bits of keying material. The cryptographic strength is length/2 of the shortest exponent used. This prime was randomly generated by a freely available program written by the author. (8) Implementation Optional. A 2048-bit strong prime (p), expressed in hex: 72a9 25f7 60b2 f954 ed28 7f1b 0953 f3e6 aef9 2e45 6172 f9fe 86fd d882 2241 b9c9 788f bc28 9982 743e fbcd 2ccf 062b 242d 7a56 7ba8 bbb4 0d79 bca7 b8e0 b6c0 5f83 5a5b 938d 9858 16bc 6489 85ad cff5 402a a767 56b3 6c84 5a84 0a1d 059c e027 07e1 9cf4 7af0 b5a8 82f3 2315 c19d 1b86 a56c 5389 c5e9 bee1 6b65 fde7 b1a8 d74a 7675 de9b 707d 4c5a 4633 c029 0c95 ff30 a605 aeb7 ae86 4ff4 8370 f13c f01d 49ad b9f2 3d19 a439 f753 ee77 03cf 342d 87f4 3110 5c84 3c78 ca4d f639 931f 3458 fae8 a94d 1687 e99a 76ed 99d0 ba87 189f 42fd 31ad 8262 c54a 8cf5 914a e6c2 8c54 0d71 4a5f 6087 a171 fb74 f481 4c6f 968d 7238 6ef3 56a0 5180 c3be c7dd d5ef 6fe7 6b1f 717b The recommended generator (g) for this prime is 2. Provides 2048 bits of keying material. The cryptographic strength is length/2 of the shortest exponent used. This prime was randomly generated by a freely available program Karn & Simpson expires in six months [Page 41] DRAFT Photuris October 1995 written by the author. (256) Moduli-indices of 256 to 65535 are available for private use. Karn & Simpson expires in six months [Page 42] DRAFT Photuris October 1995 B. Attribute List +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Length | Value(s) ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Type A unique value indicating the authentication, compression, encryption, and signature types available for exchange between the parties. Length The length of the Value field in octets. When the Type is zero, no Length field is present. Value(s) Zero or more optional values. The size of the value list is indicated by the Length field. When the Length is zero, no Value(s) field is present. Up-to-date values for the Attribute Type are specified in the most recent "Assigned Numbers" [RFC-1700]. Initial values are assigned as follows: A K I/R S V Type 0 padding 1 reserved + + + + 2 MD2 3 reserved + + + + 4 MD4 * * * * 5 MD5 + + + + 6 SHA 7-11 unassigned + + 12 RC2 13 reserved + + 14 RC4 + + 15 RC5 + 16 DES-CBC, 0-bit IV * 17 DES-CBC, 32-bit IV * * 18 DES-CBC, 64-bit IV 19 reserved + 20 Triple DES-CBC, 0-bit IV + 21 Triple DES-CBC, 32-bit IV + + 22 Triple DES-CBC, 64-bit IV 23 reserved + + 24 IDEA + 25 DSS Karn & Simpson expires in six months [Page 43] DRAFT Photuris October 1995 + 26 PKCS + 27 DNS-SIG certificate + 28 PGP certificate + 29 X.509 certificate chain 30-31 unassigned + 32 Sensitivity Label + 33 VJ Header Compression + 34 LZ77 + 35 Stac LZS + 36 AH-Sequence 37-254 unassigned x x x x x 255 Organizational A Anonymity Choice K Key Choice I/R Initiator/Responder Attribute Choice S Signature Choice V Validity Choice * algorithm must be supported + feature must be supported when algorithm optionally supported x feature may be supported when algorithm optionally supported Attributes which are required to be supported are included in this document. Other attributes are specified elsewhere. Each attribute may have value fields which are multiple octets. To facilitate processing efficiency, these fields are aligned on integral (modulo 8) octet boundaries. Padding is accomplished by insertion of 1 to 7 padding octets (Type 0) before the attribute which needs alignment. No padding is used after the final attribute in a list. B.1. MD5 Type 5 Length 0 Key Choice When selected as a Key-Generator-Choice, generates 128-bits of Karn & Simpson expires in six months [Page 44] DRAFT Photuris October 1995 keying material. The strength of the generated key material is presumed to be the same strength as the shared-secret. Attribute Choice When selected as an Initiator or Responder Attribute-Choice, pursuant to [RFC-1828], its SPI session-key uses the entire Key-Generator- Choice generated keying material. The strength of the generated key material is recommended to be at least 64-bits. Signature Choice When selected as a Signature-Choice, the resulting Signature field is 128-bits (18 octets including Size). The Certificate field contains a value which identifies the party. Typically, the Certificate is an email address. The MD5 hash is calculated as described in "Signature Verification". The authentication secret-key is selected based on the contents of the Certificate field. Valid Certificates and secret-keys are preconfigured by the peers. Validity Choice When selected as a Validity-Choice, the resulting Verification field is 128-bits (18 octets including Size). The hash is calculated as described in "Change Verification". The leading shared-secret is not padded to any particular alignment. B.2. DES-CBC Type 16, 17 or 18 Length 0 Anonymity Choice When selected as an Anonymity-Choice, its anonymity session-key Karn & Simpson expires in six months [Page 45] DRAFT Photuris October 1995 always uses MD5 as the cryptographic hash. The most significant 64-bits of the generated hash are used. The least significant bit of each octet is ignored (parity). The 64-bit Initialization Vector (IV) is set to the Type, LifeTime, and SPI fields. Encryption begins with the next field, and continues to the end of the data indicated by the UDP Length. Attribute Choice When selected as an Initiator or Responder Attribute-Choice, pursuant to [RFC-1829], its SPI session-key uses the most significant 64-bits of Key-Generator-Choice generated material. The least significant bit of each octet is ignored (parity). The strength of the generated key material is recommended to be at least 56-bits. B.3. Organizational +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Length | OUI +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... | Kind | Value(s) ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Type 255 Length >= 4 OUI 3 Octets. The vendor's Organizationally Unique Identifier, assigned by IEEE 802 (see [RFC-1700] for contact details). The bits within the octet are in canonical order, and the most significant octet is transmitted first. Kind 1 octet. Indicates a sub-type for the OUI. There is no standardization for this field. Each OUI implements its own values. Value(s) Zero or more optional values. The size of the value list is indicated by the Length field. When the Length is four, no Value(s) field is present. Karn & Simpson expires in six months [Page 46] DRAFT Photuris October 1995 Some implementors might not need or want to publish their proprietary algorithms and attributes. This OUI mechanism is available to specify these without encumbering the IANA with proprietary number requests. Karn & Simpson expires in six months [Page 47] DRAFT Photuris October 1995 Security Considerations Security issues are the primary topic of this memo. The security of Photuris critically depends 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 [RFC-1750]. Each Photuris session generates a calculated shared-secret. The strength of the shared-secret is essential to the strength of the Security Associations. Discovery of the underlying shared-secret would compromise the Security Associations relying upon it. Therefore, the shared-secret is itself only indirectly used for creating those keys which actually protect session traffic. Discovery of one such key should not reveal related session-keys. This use of the calculated shared-secret, for both anonymity keys and for creating multiple session-keys by hashing with a new SPI, substantially depends on the quality of the chosen cryptographic hashing function(s) that generate the keys. This is mitigated by carefully organized differences in calculation of the anonymity and SPI session-keys in each direction, the opportunity for varying key generation algorithms for each SPI, and the optional concealment of the algorithms chosen for each SPI. The modular exponentiation, elliptic curve, and key generation algorithms provide a differing number of bits of keying material. It is important to distinguish the characteristics of these bits. A. The length of the shared-secret depends on the modulus or field size. B. The strength of the shared-secret depends on the minimum exponent size used by either party. C. The length of the generated keying material depends on the details of the key generation algorithm. D. The strength of the generated keying material depends on the Karn & Simpson expires in six months [Page 48] DRAFT Photuris October 1995 strength of the shared-secret, and is limited by the length of the generated keying material itself. E. The length of the session-key used by a transform depends on the details of the transform. F. The strength of the session-key used by a transform depends on the strength of the keying material, and is limited by the length of the session-key used by the transform itself. Use of an exponent(s) or a key generation algorithm which produces less strength than required for a selected transform results in less robust security than would otherwise be expected. It is the responsibility of the implementor to choose a useful set of attributes for each Security Association, which provide the best tradeoff of security and performance for a given application. In general, when more than one attribute providing the same function is offered, the strongest algorithm should be selected. Acknowledgements Phil Karn is principally responsible for the design of the protocol phases, particularly the clogging defense, and initial internet security protocol implementation experience spanning more than 4 years. William Simpson was responsible for adding attributes, other message types, editing and formatting. All such mistakes are his responsibity. This protocol was later discovered to have 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, to provide an authentication-only version of signature verification. Randall Atkinson, Cheryl Madson, James Hughes, Angelos Keromytis, and Perry Metzger provided useful critiques of earlier versions of this document. Karn & Simpson expires in six months [Page 49] DRAFT Photuris October 1995 References [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. [Diffie90] Whitfield Diffie, "Authenticated Key Exchange and Secure Interactive Communication", Northern Telecom, Securicom '90, Paris France, 16 March 1990. [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. [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. [Hellman95] Martin Hellman, personal communication. [Kerberos] Kerberos? [Menezes] Alfred J. Menezes, "Elliptic Curve Public Key Cryptosystems", Kluwer Academic Publishers, 1993. [P1363] 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/ [RFC-768] [RFC-1700] Reynolds, J., and Postel, J., "Assigned Numbers", STD 2, RFC-1700, USC/Information Sciences Institute, October 1994. [RFC-1750] Eastlake, Crocker & Schiller, "Randomness Recommendations for Security", December 1994. Karn & Simpson expires in six months [Page 50] DRAFT Photuris October 1995 [RFC-1825] Atkinson, R., "Security Architecture for the Internet Protocol", RFC-1825, Naval Research Laboratory, July 1995. [RFC-1828] [RFC-1829] [Schneier94] Schneier, B., "Applied Cryptography", John Wiley & Sons, New York, NY, 1994. ISBN 0-471-59756-2. Author's Address(es) 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 (prefered) William Allen Simpson Daydreamer Computer Systems Consulting Services 1384 Fontaine Madison Heights, Michigan 48071 Bill.Simpson@um.cc.umich.edu bsimpson@MorningStar.com (prefered) Karn & Simpson expires in six months [Page 51] DRAFT Photuris October 1995 Table of Contents 1. Introduction .......................................... 1 1.1 Terminology ..................................... 2 1.2 Protocol Description ............................ 3 1.3 Clogging Defense ................................ 5 1.4 Security Parameters ............................. 7 1.5 Multicast Support ............................... 7 2. Protocol Details ...................................... 9 2.1 UDP ............................................. 9 2.2 Header Format ................................... 9 2.3 Exchange Schemes ................................ 10 2.4 Attributes ...................................... 10 2.5 Variable Precision Numbers ...................... 11 3. Cookie Exchange ....................................... 12 3.1 Cookie_Request .................................. 12 3.2 Cookie_Response ................................. 14 3.3 Cookie Generation ............................... 14 4. Value Exchange ........................................ 16 4.1 Key_Request ..................................... 17 4.2 Key_Response .................................... 19 5. Signature Exchange .................................... 21 5.1 Signature_Message ............................... 21 5.2 Anonymity ....................................... 24 5.3 Verification .................................... 24 5.4 Session-Key Computation ......................... 25 6. Other Message Types ................................... 27 6.1 Change_Message .................................. 27 6.2 Creation ........................................ 29 6.3 Deletion ........................................ 30 6.4 Verification .................................... 30 6.5 Error_Message ................................... 32 6.6 Invalid/Expired ................................. 33 6.7 Resource Limit .................................. 33 6.8 Verification Failure ............................ 33 6.9 Need Attributes ................................. 33 7. Public Key Exchanges .................................. 34 7.1 Perfect Forward Secrecy ......................... 34 7.2 Traffic Anonymity ............................... 35 7.3 Modular Exponentiation Groups ................... 36 7.4 Elliptic Curve Groups ........................... 37 Karn & Simpson expires in six months [Page ii] DRAFT Photuris October 1995 7.5 Exponent Selection .............................. 38 APPENDICES ................................................... 40 A. Exchange Scheme Table ................................. 40 B. Attribute List ........................................ 43 B.1 MD5 ............................................. 44 B.2 DES-CBC ......................................... 45 B.3 Organizational .................................. 46 SECURITY CONSIDERATIONS ...................................... 48 ACKNOWLEDGEMENTS ............................................. 49 REFERENCES ................................................... 50 AUTHOR'S ADDRESS ............................................. 51