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
                    <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