One document matched: draft-ietf-cat-ecdh-spkm-00.txt

        Using Elliptic Curve Diffie-Hellman in the SPKM GSS-API 
                    <draft-ietf-cat-ecdh-spkm-00.txt>


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