Internet Draft R. Zuccherato(Entrust Technologies) CAT Working Group C. Adams(Entrust Technologies) expires in six months August 1999 Using Elliptic Curve Diffie-Hellman in the SPKM GSS-API Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. 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 inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Copyright (C) The Internet Society (1999). All Rights Reserved. Abstract Elliptic curve cryptography is rapidly gaining acceptance and is being increasingly used in applications that are constrained in memory and bandwidth. Efforts are underway to standardize the use of elliptic curves for authentication [ECDSA], [X962] and key agreement [ISO15946], [P1363], [X963]. However, none of these efforts describe the Elliptic Curve Diffie-Hellman (ECDH) method in a form suitable for inclusion in SPKM [RFC2025]. This document will define a new OID and AlgorithmIdentifier which is suitable for use in SPKM and describe how the ECDH algorithm is to be used in SPKM. 1. Introduction The Simple Public-Key Mechanism (SPKM) is a GSS-API mechanism which "provides authentication, key establishment, data integrity, and data confidentiality in an on-line distributed application environment using a public key infrastructure." The mandatory key establishment algorithm in SPKM is RSA encryption as defined by the RSAEncryption OID. However, any key establishment algorithm which can be specified by an AlgorithmIdentifier may be used. Elliptic curve cryptography uses the group of points defined on an elliptic curve over a finite field to obtain variants of the conventional DSA signature scheme and Diffie-Hellman key agreement Zuccherato, Adams Page 1 algorithm, for example. The security of these schemes is based on the difficulty of the elliptic curve discrete logarithm problem. Unlike cryptography which is based on the integer factorization problem or the traditional discrete logarithm problem, no index calculus method is known for solving the elliptic curve discrete logarithm problem. Thus, elliptic curve cryptosystems can be used which provide similar security to "conventional" public-key systems, but with a much smaller key size. This is particularly useful in certain constrained devices. Other efforts to standardize the use of elliptic curves for key agreement exist. However, they do not provide an obvious way to include their techniques within SPKM. The [P1363] and [ISO15946] drafts describe the ECDH algorithm as it would be used in SPKM, but they do not define OIDs and AlgorithmIdentifiers that SPKM requires in order to specify the algorithm in a REQ-TOKEN, for example. The description of the ECDH algorithm in this document will be consistent with the Elliptic Curve Key Agreement Scheme, Diffie-Hellman version, where each party contributes one key pair (ECKAS-DH1) using Elliptic Curve Secret Value Derivation Primitive, Diffie-Hellman version (ECSVDP-DH) in [P1363] and also with the Key agreement of Diffie-Hellman type in [ISO15946]. The [X963] draft also describes the ECDH algorithm as it would be used in SPKM, but requires that it be implemented in one of several schemes that it describes and also mandates the use of particular key derivation functions. SPKM, however, uses a different, incompatible, key derivation function. The description of ECDH in this document will be consistent with the Ephemeral Unified Model Scheme in [X963] except that the SPKM key derivation function will be used. Implementations conformant with this specification must also be conformant with [RFC2025]. 2. Elliptic Curve Diffie-Hellman This Section will describe the ECDH algorithm as it is to be used in SPKM. Necessary elliptic curve background can be found in [X962]. The required elliptic curve parameters will be specified in the K-ALG AlgorithmIdentifier parameters. These parameters will include the curve to be used, the underlying finite field and its representation, the generating point (P), and the order of P (n). Each party A will generate a random integer r_A in the range [1,n-1] and compute the ECDH public key r_A*P. This public key will then be sent to the other party in the SPKM session. Upon receiving the public key r_B*P from the other party, each party will then compute the shared secret point Z=r_A*(r_B*P). The point Z will be used to create the context_key for use in the Subkey Derivation Algorithm. 3. ECDH Public Keys An ECDH public key, r_a*P, is a point on the elliptic curve. Elliptic curve points are represented by the ASN.1 type: Zuccherato, Adams Page 2 ECPoint ::= OCTET STRING The value of ECPoint shall be the octet string representation of an elliptic curve point following the conversion routine in [X962, Section 4.3.6]. Within SPKM ECDH keys are carried in the key-estb-req field of a REQ- TOKEN, the key-estb-str field of a REP-TI-TOKEN and the key-estb-rep field of a REP-IT-TOKEN. These fields are all BIT STRINGs. The ECDH public key OCTET STRING is mapped to a BIT STRING as follows: the most significant bit of the OCTET STRING becomes the most significant bit of the BIT STRING, etc.; the least significant bit of the OCTET STRING becomes the least significant bit of the BIT STRING. 4. Algorithm Identifier and Parameters The negotiation of ECDH as a K-ALG in SPKM requires that an AlgorithmIdentifer{{ECDHAlgorithm}} be specified in the key-estb-set field of REQ-TOKEN and the key-estb-id field of REP-TI-TOKEN. The use of the OID id-SPKM-ECDH and AlgorithmIdentifier{{ECDHAlgorithm}} as described in this section implies the use of ECDH as described in this document. A reference to parameterized type AlgorithmIdentifier{} tightly binds a set of algorithm object identifiers to their associated parameters types. Type AlgorithmIdentifier{} is defined as: AlgorithmIdentifier { ALGORITHM:IOSet } ::= SEQUENCE { Algorithm ALGORITHM.&id({IOSet}), Parameters ALGORITHM.&Type({IOSet}{@algorithm}) } A single parameter in the reference of type AlgorithmIdentifier{}, the information object set of class ALGORITHM, ECDHAlgorithm, specifies all of the pairs of valid values of this type. This set contains only one object ecdhspkmAlgorithm, as defined in this Standard. ECDHAlgorithm ALGORITHM ::= { ecdhspkmAlgorithm, ... } ecdhspkmAlgorithm ALGORITHM ::= { Parameters IDENTIFIED BY id-SPKM-ECDH } ALGORITHM ::= TYPE-IDENTIFIER The object identifier id-SPKM-ECDH names the ECDH algorithm defined in this Standard. It has the following value: id-SPKM-ECDH OBJECT IDENTIFIER ::= {iso(1) identified-organization(3) dod(6) internet(1) security(5) mechanisms(5) spkm(1) id-SPKM-ECDH(20) } The public key Parameters are defined in this Standard as a choice of Zuccherato, Adams Page 3 two alternatives. This allows detailed specification of all required values using choice ecParameters or the use of a namedCurve as an object identifier substitute for a particular set of elliptic curve domain parameters. Parameters ::= CHOICE { ecParameters ECParameters, namedCurve OBJECT IDENTIFIER } When parameters are specified by reference, the parameters field shall contain the namedCurve choice, which is an object identifier. See [X9.62,Section 6.4] and [X9.63] for OIDs that represent certain sets of parameters defined by ANSI. ANSI and other standards bodies may define other OIDs to represent other elliptic curve parameters which they may recommend. Users are encouraged to consult relevant standards and specifications to determine which OIDs (if any) they should use. When the parameters are explicitly included, they shall be encoded in the ASN.1 structure ECParameters: ECParameters ::= SEQUENCE { version INTEGER { ecpVer1(1) } (ecpVer1), -- version is always 1 fieldID FieldID { {FieldTypes} }, -- identifies the finite field over which the curve is defined curve Curve, -- coefficients a and b of the elliptic curve base ECPoint, -- specifies the base point P on the elliptic curve order INTEGER, -- the order n of the base point cofactor INTEGER OPTIONAL, ... } FieldElement ::= OCTET STRING The value of FieldElement shall be the octet string representation of a field element following the conversion routine in [X9.62,Section 4.3.3] Curve ::= SEQUENCE { a FieldElement, b FieldElement, seed BIT STRING OPTIONAL} The components of type ECParameters have the following meanings: * version specifies the version number of the elliptic curve parameters. It shall have the value 1 for this version of the Standard. The notation above creates an INTEGER named ecpVer1 and gives it a value of one. It is used to constrain version to a single value. * fieldID identifies the finite field over which the elliptic curve is defined. Finite fields are represented by values of the parameterized type FieldID, constrained to the values of the objects defined in the information object set FieldTypes. Additional detail regarding fieldID Zuccherato, Adams Page 4 is provided below. * curve specifies the coefficients a and b of the elliptic curve E. Each coefficient shall be represented as a value of type FieldElement, an OCTET STRING. seed is an optional parameter used to derive the coefficients of a randomly generated elliptic curve. * base specifies the base point P on the elliptic curve. The base point shall be represented as a value of type ECPoint, an OCTET STRING. * order specifies the order n of the base point. * cofactor is the integer h = #E(Fq)/n. Note: This optional parameter is not used in this version of ECDH, except in parameter validation. Parameter validation is not required by this specification. FieldID { FIELD-ID:IOSet } ::= SEQUENCE { fieldType FIELD-ID.&id({IOSet}), parameters FIELD-ID.&Type({IOSet}{@fieldType}) OPTIONAL} FieldTypes FIELD-ID ::= { { Prime-p IDENTIFIED BY prime-field } | { Characteristic-two IDENTIFIED BY characteristic-two-field }, ... } FIELD-ID ::= TYPE-IDENTIFIER FieldID is a parameterized type composed of two components, fieldType and parameters. These components are specified by the fields &id and &Type, which form a template for defining sets of information objects, instances of the class FIELD-ID. This class is based on the useful information object class TYPE-IDENTIFIER, described in X.681 Annex A. In an instance of FieldID, "fieldType" will contain an object identifier value that uniquely identifies the type contained in "parameters". The effect of referencing "fieldType" in both components of the fieldID sequence is to tightly bind the object identifier and its type. The information object set FieldTypes is used as the single parameter in a reference to type FieldID. FieldTypes contains two objects followed by the extension marker ("..."). Each object, which represents a finite field, contains a unique object identifier and its associated type. The values of these objects define all of the valid values that may appear in an instance of fieldID. The extension marker allows backward compatibility with future versions of this standard which may define objects to represent additional kinds of finite fields. The object identifier id-fieldType represents the root of a tree containing the object identifiers of each field type. It has the following value: ansi-X9-62 OBJECT IDENTIFIER ::= {iso(1) member-body(2) us(840) 10045 } id-fieldType OBJECT IDENTIFIER ::= { ansi-X9-62 fieldType(1) } The object identifiers prime-field and characteristic-two-field name the Zuccherato, Adams Page 5 two kinds of fields defined in this Standard. They have the following values: prime-field OBJECT IDENTIFIER ::= { id-fieldType 1 } characteristic-two-field OBJECT IDENTIFIER ::= { id-fieldType 2 } Prime-p ::= INTEGER -- Field size p (p in bits) Characteristic-two ::= SEQUENCE { m INTEGER, -- Field size 2^m (m in bits) basis CHARACTERISTIC-TWO.&id({BasisTypes}), parameters CHARACTERISTIC-TWO.&Type({BasisTypes}{@basis})} BasisTypes CHARACTERISTIC-TWO::= { { NULL IDENTIFIED BY gnBasis } | { Trinomial IDENTIFIED BY tpBasis } | { Pentanomial IDENTIFIED BY ppBasis }, ... } Trinomial ::= INTEGER Pentanomial ::= SEQUENCE { k1 INTEGER, k2 INTEGER, k3 INTEGER } CHARACTERISTIC-TWO ::= TYPE-IDENTIFIER The object identifier id-characteristic-two-basis represents the root of a tree containing the object identifiers for each type of basis for the characteristic-two finite fields. It has the following value: id-characteristic-two-basis OBJECT IDENTIFIER ::= { characteristic-two-field basisType(1) } The object identifiers gnBasis, tpBasis and ppBasis name the three kinds of basis for characteristic-two finite fields defined by [X9.62]. They have the following values: gnBasis OBJECT IDENTIFIER ::= { id-characteristic-two-basis 1 } tpBasis OBJECT IDENTIFIER ::= { id-characteristic-two-basis 2 } ppBasis OBJECT IDENTIFIER ::= { id-characteristic-two-basis 3 } 5. Computation of the Context Key After computation of the shared secret point Z (as described in Section 2) each party must compute a context_key, which is a bit string, for input to the Subkey Derivation Algorithm. The secret value Z is an elliptic curve point and thus consists of an ordered pair of field elements (x,y). To obtain the context_key first apply the conversion routine in [X962, Section 4.3.3] to the field Zuccherato, Adams Page 6 element x to obtain an octet string. The octet string can be converted to a bit string as follows: the most significant bit of the octet string becomes the most significant bit of the bit string, etc.; the least significant bit of the octet string becomes the least significant bit of the bit string. 6. Security Considerations The random number r_A which is used to compute the ECDH public key should be generated by a quality random number generator and be unique for each session. The use of predictable random numbers voids all security provided by ECDH. It is recommended that only elliptic curves whose base point, P, has order greater than 2^160 be used. It is generally accepted that curves that do not satisfy this condition are not suitable for cryptographic use. Also note that some curves are less secure than others. See [X962,Section H.1] for a discussion of the difficulty of solving the elliptic curve discrete logarithm problem. It is recommended that before accepting any session using ECDH, both parties should validate the proposed parameters. A method for validating parameters can be found in [X9.62,Section 5.1]. It may also be desirable to generate the elliptic curve at random using a method that can be verified by others. One such method is described in [X962, Section A.3.3]. However, there are no known attacks against curves not generated in this way. Since the key establishment in SPKM is always protected for integrity third party attackers cannot alter the exchanged public keys. Therefore, the only entity capable of mounting a "small-subgroup" type attack [smallsubgroup] on ECDH key agreement in SPKM is the other legitimate entity in the key establishment. However, this entity already has access to all data being passed through the session. Thus, as long as fresh keys are generated for each session, protection from "small-subgroup" attacks using public key validation or any other method is not required. 7. Intellectual Property Rights The IETF takes no position regarding the validity or scope of any intellectual property or other rights that might be claimed to per- tain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; neither does it represent that it has made any effort to identify any such rights. Information on the IETF's procedures with respect to rights in standards-track and standards- related documentation can be found in BCP-11. Copies of claims of rights made available for publication and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementors or users of this specification can be obtained from the IETF Secretariat. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary Zuccherato, Adams Page 7 rights which may cover technology that may be required to practice this standard. Please address the information to the IETF Executive Director. 8. References [ECDSA] L. Bassham, D. Johnson, W. Polk, "Representation of Elliptic Curve Digital Signature Algorithm (ECDSA) Keys and Signatures in Internet X.509 Public Key Infrastructure Certificates", draft-ietf-pkix- ipki-ecdsa-0X.txt, work in progress, 1999. [ISO15946] ISO/IEC CD 15946-3, "Information Technology - Security Techniques - Cryptographic Techniques Based on Elliptic Curves - Part 3: Key Establishment", Committee Draft, April 24, 1999. [P1363] IEEE P1363/D11, "Standard Specifications for Public Key Cryptography", Draft 11, July 29, 1999. [RFC2025] C. Adams, "The Simple Public-Key GSS-API Mechanism (SPKM)", RFC 2025. [smallsubgroup] R. Zuccherato, "Methods for Avoiding the "Small- Subgroup" Attacks on the Diffie-Hellman Key Agreement Method for S/MIME", draft-ietf-smime-small-subgroup-0X.txt, work in progress, 1999. [X962] ANSI X9.62-1999, "Public Key Cryptography For The Financial Service Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA)". [X963] ANSI X9.63-199x, "Public Key Cryptography For The Financial Services Industry: Key Agreement and Key Transport Using Elliptic Curve Cryptography", Working Draft, April 20, 1999. 9. Author's Address Robert Zuccherato Entrust Technologies 750 Heron Road Ottawa, Ontario Canada K1V 1A7 robert.zuccherato@entrust.com Carlisle Adams Entrust Technologies 750 Heron Road Ottawa, Ontario Canada K1V 1A7 cadams@entrust.com Zuccherato, Adams Page 8 Appendix A. ASN.1 Module Definition SpkmECDH {iso(1) identified-organization(3) dod(6) internet(1) security(5) mechanisms(5) spkm(1) spkmECDH(20) } DEFINITIONS IMPLICIT TAGS ::= BEGIN --EXPORTS ALL IMPORTS ECParameters FROM ANSI-X9-62 { iso(1) member-body(2) us(840) 10045 module(4) 1 } AlgorithmIdentifier { ALGORITHM:IOSet } ::= SEQUENCE { Algorithm ALGORITHM.&id({IOSet}), Parameters ALGORITHM.&Type({IOSet}{@algorithm}) } ECDHPKAlgorithm ALGORITHM ::= { ecdhspkmAlgorithm, ... } ecdhspkmAlgorithm ALGORITHM ::= { Parameters IDENTIFIED BY id-SPKM-ECDH } ALGORITHM ::= TYPE-IDENTIFIER id-SPKM-ECDH OBJECT IDENTIFIER ::= {iso(1) identified-organization(3) dod(6) internet(1) security(5) mechanisms(5) spkm(1) id-SPKM-ECDH(20) } Parameters ::= CHOICE { ecParameters ECParameters, namedCurve OBJECT IDENTIFIER } END Appendix B. Imported Types This appendix contains (for completeness) the relevant ASN.1 types imported from ANSI-X9-62 ([X962] and [ECDSA]). ECParameters ::= SEQUENCE { version INTEGER { ecpVer1(1) } (ecpVer1), -- version is always 1 fieldID FieldID { {FieldTypes} }, -- identifies the finite field over which the curve is defined curve Curve, -- coefficients a and b of the elliptic curve base ECPoint, -- specifies the base point P on the elliptic curve Zuccherato, Adams Page 9 order INTEGER, -- the order n of the base point cofactor INTEGER OPTIONAL, ... } FieldElement ::= OCTET STRING ECPoint ::= OCTET STRING Curve ::= SEQUENCE { a FieldElement, b FieldElement, seed BIT STRING OPTIONAL} FieldID { FIELD-ID:IOSet } ::= SEQUENCE { fieldType FIELD-ID.&id({IOSet}), parameters FIELD-ID.&Type({IOSet}{@fieldType}) OPTIONAL} FieldTypes FIELD-ID ::= { { Prime-p IDENTIFIED BY prime-field } | { Characteristic-two IDENTIFIED BY characteristic-two-field }, ... } FIELD-ID ::= TYPE-IDENTIFIER ansi-X9-62 OBJECT IDENTIFIER ::= {iso(1) member-body(2) us(840) 10045 } id-fieldType OBJECT IDENTIFIER ::= { ansi-X9-62 fieldType(1) } prime-field OBJECT IDENTIFIER ::= { id-fieldType 1 } characteristic-two-field OBJECT IDENTIFIER ::= { id-fieldType 2 } Prime-p ::= INTEGER -- Field size p (p in bits) Characteristic-two ::= SEQUENCE { m INTEGER, -- Field size 2^m (m in bits) basis CHARACTERISTIC-TWO.&id({BasisTypes}), parameters CHARACTERISTIC-TWO.&Type({BasisTypes}{@basis})} BasisTypes CHARACTERISTIC-TWO::= { { NULL IDENTIFIED BY gnBasis } | { Trinomial IDENTIFIED BY tpBasis } | { Pentanomial IDENTIFIED BY ppBasis }, ... } Trinomial ::= INTEGER Pentanomial ::= SEQUENCE { k1 INTEGER, k2 INTEGER, Zuccherato, Adams Page 10 k3 INTEGER } CHARACTERISTIC-TWO ::= TYPE-IDENTIFIER id-characteristic-two-basis OBJECT IDENTIFIER ::= { characteristic-two-field basisType(1) } gnBasis OBJECT IDENTIFIER ::= { id-characteristic-two-basis 1 } tpBasis OBJECT IDENTIFIER ::= { id-characteristic-two-basis 2 } ppBasis OBJECT IDENTIFIER ::= { id-characteristic-two-basis 3 } Appendix C. Full Copyright Statement Copyright (C) The Internet Society (date). All Rights Reserved. This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. In addition, the ASN.1 modules presented in Appendices A and B may be used in whole or in part without inclusion of the copyright notice. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of develop- ing Internet standards in which case the procedures for copyrights defined in the Internet Standards process shall be followed, or as required to translate it into languages other than English. The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns. This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Zuccherato, Adams Page 11