view Side-By-Side changes

Date: Tue, 09 Apr 2002 04:16:14 GMT
Server: Apache/1.3.20 (Unix)
Last-Modified: Mon, 13 Sep 1999 12:42:00 GMT
ETag: "2f543c-45b1-37dcf118"
Accept-Ranges: bytes
Content-Length: 17841
Connection: close
Content-Type: text/plain

IPSec Working Group                             P. Panjwani and Y. Poeluev
INTERNET-DRAFT                                               Certicom Corp
Expires November 20, December 15, 1999                              May 26,                               September 13, 1999


                       Additional ECC Groups For IKE
                  <draft-ietf-ipsec-ike-ecc-groups-00.txt>
                  <draft-ietf-ipsec-ike-ecc-groups-01.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 made obsolete 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.This document is an Internet-Draft.
   http://www.ietf.org/shadow.html.


                               Abstract

   This document describes new ECC groups for use in IKE [RFC2409] [RFC2409, IKE]
   in addition to the Oakley groups included in RFC 2409. [IKE].  These groups
   are defined to align IKE with other ECC implementations and standards,
   and in addition, some of them provide higher strength than the Oakley
   groups. It should be noted that this document is not self-contained.
   It uses the notations and definitions of [RFC2409]. [IKE].


 
   Table of Contents


   1. Introduction ............................................... 2
   2. Additional Oakley Groups ................................... 3
   2.1. Fifth Sixth Group .............................................. 3
   2.2. Sixth Seventh Group .............................................. ............................................ 4
   2.3. Seventh Eighth Group ............................................ ............................................. 5
   2.4. Eighth Ninth Group ............................................. .............................................. 6
   3. Security Considerations .................................... 7
   4. Patent Statements .......................................... Intellectual Property Rights ............................... 7
   5. Acknowledgments ............................................ 7
   6. References ................................................. 8
   7. Authors' Addresses ......................................... 8



Panjwani and Poeluev                                              [Page 1]


INTERNET-DRAFT       Additional ECC Groups For IKE          May 26,      September 13, 1999



1.  Introduction

This document describes default groups for use in elliptic curve Diffie-
Hellman in IKE [RFC2409] in addition to the Oakley groups included in RFC 2409. [IKE].
The document assumes that the reader is familiar with the IKE protocol,
and the concept of Oakley Groups, as defined in RFC 2409. 

RFC 2409 [RFC2409, IKE].

[IKE] defines four five standard Oakley Groups - two three modular exponentiation
groups and two elliptic curve groups over GF[2^N]. One modular exponentia-
tion group (768 bits - Oakley Group 1) is mandatory for all implementations
to support, while other three four are optional. Both elliptic curve groups
(Oakley Groups 3 and 4) are defined over GF[2^N] with N composite.

Implementations have shown that use of elliptic curve groups can signifi-
cantly improve performance over using Oakley Groups 1 and 2. 1, 2, or 5. The purpose
of this document is to expand the options available to implementers of
elliptic curve groups by adding four new groups. The reasons for addition
of these new groups include the following:

- The groups proposed encourage alignment with other elliptic curve
  standards. Oakley Groups 3 and 4 were defined prior to availability of
  other elliptic curve standards, and they are therefore not aligned with
  other efforts. Specifically, unlike Oakley groups 3 and 4, the proposed
  groups use base points whose order is prime as required by IEEE [P1363]
  and ANSI [X9.62, X9.63], and they use base points whose prime order is
  greater than 2^160, as required by ANSI [X9.62, X9.63]. X9.63], and they use the
  octet string representation for points recommended in IEEE [P1363] and
  ANSI [X9.62,X9.63].

- Two of the new groups proposed offer higher strength than the existing
  Oakley Groups. As computing power increases and other standards such as
  the AES are specified it becomes increasingly desirable to make higher
  strength groups available to implementers. 

- The four groups proposed in this document use elliptic curves over
  GF[2^N] with N prime unlike the existing Oakley Groups. This addresses
  concerns expressed by many experts regarding curves defined over GF[2^N]
  with N composite. It also aligns the groups with plans recently announced
  by NIST. NIST have indicated that they will only support curves over
  GF[2^N] when the curves over GF[2^N] have N prime.

  (It may also be desirable to represent points in the form specified in
   IEEE [P1363] and ANSI [X9.62, X9.63] in the key exchange payload
   instead of sending only the x-coordinate as currently specified in
   [RFC2409]. Since it is unclear  exactly how use of a variable length
   key exchange payload affects IKE, this has not been suggested at this
   time.)








Panjwani and Poeluev                                              [Page 2]



INTERNET-DRAFT         Additional ECC Groups For IKE          May 26, 1999 [NIST].

These groups could also be defined using the New Group Mode, but including
them in this RFC will encourage interoperability of IKE implementations
based upon elliptic curve groups. This is particularly critical, since the
available Oakley Groups based on elliptic curves are insufficient for the
reasons mentioned above. In addition, availability of standardized groups
will result in optimizations for a particular curve and fields size as
well as precomputations that could result in faster implementations.






Panjwani and Poeluev                                              [Page 2]


INTERNET-DRAFT       Additional ECC Groups For IKE      September 13, 1999


In summary, due to the performance advantages of elliptic curve groups in
IKE implementations and the need for standardized groups as alternatives
to Oakley Groups 3 and 4, this document defines four new groups based on
elliptic curve groups. The groups are defined at two field sizes: GF[2^163]
and GF[2^277]. GF[2^283]. These field sizes correspond to 80-bit and 128-bit symmetric
key strengths and 1,024-bit and 3,044-bit Diffie-Hellman respectively. Two
curves are defined at each strength - a Koblitz curve that enables espe-
cially efficient implementations due to the special structure of the curve
[Kob, NSA], and a curve chosen verifiably at random.



2. Additional Oakley Groups

The notation adopted in [RFC2409] [RFC2409, IKE] is used below to describe the new
Oakley Groups proposed.


2.1 Fifth Sixth Group

IKE implementations SHOULD support a EC2N group with the following charac-
teristics. This group is assigned id 5 (five). 6 (six). The curve is based on the
Galois Field GF[2^163]. The field size is 163. The irreducible polynomial
used to represent the field is:
           u^163 + u^7 + u^6 + u^3 + 1.
The equation for the elliptic curve is:
           y^2 + xy = x^3 + ax^2 + b.

Specifically the group is defined by the following characteristics:

Field size:
  163

Irreducible polynomial:
  0x0800000000000000000000000000000000000000C9

Group Curve a:
  0x07B6882CAAEFA84F9554FF8428BD88E246D2782AE2

Group Curve b:
  0x0713612DCDDCB40AAB946BDA29CA91F73AF958AFD9





Panjwani and Poeluev                                              [Page 3]



INTERNET-DRAFT         Additional ECC Groups For IKE          May 26, 1999

Group Generator One: 
  0x0369979697AB43897789566789567F787A7876A654 point P (compressed): 
  0x030369979697AB43897789566789567F787A7876A654

Group Generator Two: 
  0x00435EDB42EFAFB2989D51FEFCE3C80988F41FF883

Group Order:
  0x07FFFFFFFFFFFFFFFFFFFE91556D1385394E204F36 point P (uncompressed): 
  0x040369979697AB43897789566789567F787A7876A654
  00435EDB42EFAFB2989D51FEFCE3C80988F41FF883

The order of the base point P defined by Group Generator One and Group
Generator Two above is the prime:
  0x03FFFFFFFFFFFFFFFFFFFF48AAB689C29CA710279B



Panjwani and Poeluev                                              [Page 3]


INTERNET-DRAFT       Additional ECC Groups For IKE      September 13, 1999


The group order is twice this prime.

The group was chosen verifiably at random using SHA-1 as specified in
[X9.62] from the seed:
  0x24B7B137C8A14D696E6768756151756FD0DA2E5C

However, for historical reasons, the method to generate the group from the
seed differs slightly from the method described in [X9.62]. Specifically
the coefficient Group Generator Two Curve b produced from the seed is the reverse
of the coefficient that would have been produced by the method described
in [X9.62].

The data in the KE payload when using this group is the value x from the
solution (x,y), octet string
representation specified in ANSI X9.62 and IEEE P1363 of the point on the
curve chosen by taking the randomly chosen secret Ka and computing Ka*P,
where * is the repetition of the group addition and double operations, P is operations.
Note that this payload differs from the curve point with x-coor-
dinate equal to Group Generator One payload specified for groups 3
and y-coordinate equal to Group
Generator Two. 4 - it is aligned instead with other recent standardization efforts
in ECC.

This group is identical to the method used by Oakley Groups
3 also recommended in echeck [ECHECK] and 4. SECG [GEC1].


2.2 Sixth Seventh Group

IKE implementations SHOULD support a EC2N group with the following charac-
teristics. This group is assigned id 6 (six). 7 (seven). The curve is based on the
Galois Field GF[2^163]. The field size is 163. The irreducible polynomial
used to represent the field is:
           u^163 + u^7 + u^6 + u^3 + 1.
The equation for the elliptic curve is:
           y^2 + xy = x^3 + ax^2 + b.

Specifically the group is defined by the following characteristics:

Field size:
  163

Irreducible polynomial:
  0x0800000000000000000000000000000000000000C9


Panjwani and Poeluev                                              [Page 4]



INTERNET-DRAFT         Additional ECC Groups For IKE          May 26, 1999

Group Curve a:
  0x000000000000000000000000000000000000000001

Group Curve b: 
  0x000000000000000000000000000000000000000001

Group Generator One: 
  0x02FE13C0537BBC11ACAA07D793DE4E6D5E5C94EEE8 point P (compressed): 
  0x0302FE13C0537BBC11ACAA07D793DE4E6D5E5C94EEE8

Group Generator Two: 
  0x0289070FB05D38FF58321F2E800536D538CCDAA3D9

Group Order:
  0x0800000000000000000004021145C1981B33F14BDE point P (uncompressed):
  0x0402FE13C0537BBC11ACAA07D793DE4E6D5E5C94EEE8
  0289070FB05D38FF58321F2E800536D538CCDAA3D9

Panjwani and Poeluev                                              [Page 4]


INTERNET-DRAFT       Additional ECC Groups For IKE      September 13, 1999


The order of the base point P defined by Group Generator One and Group
Generator Two above is the prime:
  0x04000000000000000000020108A2E0CC0D99F8A5EF

The group order is twice this prime.

The data in the KE payload when using this group is the octet string
representation specified in ANSI X9.62 and IEEE P1363 of the point on the
curve chosen by taking the randomly chosen secret Ka and computing Ka*P,
where * is the repetition of the group addition and double operations.
Note that the format of this data is identical to the data format used with
Oakley Groups 3, 4, Group 6 (six).

This group is also recommended in ANSI [X9.63], echeck [ECHECK], NIST
[NIST], SECG [GEC1], and 5. WAP [WTLS].


2.3 Seventh Eighth Group

IKE implementations SHOULD support a EC2N group with the following charac-
teristics. This group is assigned id 7 (seven). 8 (eight). The curve is based on the
Galois Field GF[2^277]. GF[2^283]. The field size is 277. 283. The irreducible polynomial
used to represent the field is:
           u^277
           u^283 + u^12 + u^6 u^7 + u^3 u^5 + 1.
The equation for the elliptic curve is:
           y^2 + xy = x^3 + ax^2 + b.

Specifically the group is defined by the following characteristics:

Field size:
  277
  283

Irreducible polynomial:
  0x2000000000000000000000000000000000000000000000000000000000000000001049
  0x0800000000000000000000000000000000000000000000000000000000000000000010A1

Group Curve a:
  0x1853044E52AC1959E666EB976840794626756389C3084E1C0E8EE58B5ADE55B0E94F06
  0x000000000000000000000000000000000000000000000000000000000000000000000001

Group Curve b:
  0x12709B9501DBD0C98DC5E7E17AF396B445303DFDBDEA0AAE05840A8204625E0B9157B9
  0x027B680AC8B8596DA5A4AF8A19A0303FCA97FD7645309FA2A581485AF6263E313B79A2F5

Group Generator point P (compressed):
  0x0305F939258DB7DD90E1934F8C70B0DFEC2EED25B8557EAC9C80E2E198F8CDBECD86B12053

Group Generator point P (uncompressed):
  0x0405F939258DB7DD90E1934F8C70B0DFEC2EED25B8557EAC9C80E2E198F8CDBECD86B12053
  03676854FE24141CB98FE6D4B20D02B4516FF702350EDDB0826779C813F0DF45BE8112F4

The order of the base point P is the prime:
  0x03FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEF90399660FC938A90165B042A7CEFADB307

The group order is twice this prime.



Panjwani and Poeluev                                              [Page 5]


INTERNET-DRAFT       Additional ECC Groups For IKE          May 26,      September 13, 1999



Group Generator One: 
  0x180949B3BBF7F5168DA7647F9BBAE716F02F6174EC79DE0A5AC9AEC5FF48E4D696323B

Group Generator Two: 
  0x1CB7297D452004A0F2C34F33E5A6900122103B5F78BE5B838AA97848CCFEDD01F60618

Group Order:
  0x1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF7049860E759CB2BDBEF59DD8C6B43EAE816


The group was chosen verifiably at random in normal basis
representation using SHA-1 as specified in [X9.62] from the seed:
  0xAC2F14783E695F34335EB4D696E6768756151753
  0x77E2B07370EB0F832A6DD5B62DFC88CD06BB84BE
 
The order data in the KE payload when using this group is the octet string
representation specified in ANSI X9.62 and IEEE P1363 of the base point P defined on the
curve chosen by Group Generator One taking the randomly chosen secret Ka and Group
Generator Two computing Ka*P,
where * is the prime:
  0x0FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFB824C3073ACE595EDF7ACEEC635A1F5740B

The repetition of the group order is twice this prime.
 
The data in addition and double operations.
Note that the KE payload when using format of this group data is identical to the data format used with
Oakley Groups 3, 4, 5, Group 6 (six).

This group is also recommended in ANSI [X9.63], echeck [ECHECK], NIST
[NIST], and 6. SECG [GEC1].


2.4 Eighth Ninth Group

IKE implementations SHOULD support a EC2N group with the following charac-
teristics. This group is assigned id 7 (seven). 9 (nine). The curve is based on the
Galois Field GF[2^277]. GF[2^283]. The field size is 277. 283. The irreducible polynomial
used to represent the field is:
           u^277
           u^283 + u^12 + u^6 u^7 + u^3 u^5 + 1.
The equation for the elliptic curve is:
           y^2 + xy = x^3 + ax^2 + b.

Specifically the group is defined by the following characteristics:

Field size:
  277
  283

Irreducible polynomial:
  0x2000000000000000000000000000000000000000000000000000000000000000001049
  0x0800000000000000000000000000000000000000000000000000000000000000000010A1

Group Curve a:
  0x0000000000000000000000000000000000000000000000000000000000000000000000
  0x000000000000000000000000000000000000000000000000000000000000000000000000

Group Curve b:
  0x0000000000000000000000000000000000000000000000000000000000000000000001
  0x000000000000000000000000000000000000000000000000000000000000000000000001

Group Generator One: 
  0x1F548FD1F2A95B49A515F99E1933746460B57E47C1AF27AC3E101A1C175C92A741061A




Panjwani and Poeluev                                              [Page 6]



INTERNET-DRAFT         Additional ECC Groups For IKE          May 26, 1999 point P (compressed):
  0x020503213F78CA44883F1A3B8162F188E553CD265F23C1567A16876913B0C2AC2458492836

Group Generator Two: 
  0x070B258D9BE112C22B9BAA56BBBA6BB9CA38BC0F5E7E95BFD65FBBBC64BC3317DAF873

Group Order:
  0x1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFB42A2D15E3F4D2F69828D921E5BB03C3EEC point P (uncompressed):
  0x040503213F78CA44883F1A3B8162F188E553CD265F23C1567A16876913B0C2AC2458492836
  01CCDA380F1C9E318D90F95D07E5426FE87E45C0E8184698E45962364E34116177DD2259

The order of the base point P defined by Group Generator One and Group
Generator Two is the prime:
  0x07FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED0A8B4578FD34BDA60A3648796EC0F0FBB
  0x01FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE9AE2ED07577265DFF7F94451E061E163C61

The group order is four times this prime.




Panjwani and Poeluev                                              [Page 6]


INTERNET-DRAFT       Additional ECC Groups For IKE      September 13, 1999


The data in the KE payload when using this group is the octet string
representation specified in ANSI X9.62 and IEEE P1363 of the point on the
curve chosen by taking the randomly chosen secret Ka and computing Ka*P,
where * is the repetition of the group addition and double operations.
Note that the format of this data is identical to the data format used with
Oakley Groups 3, 4, 5, 6, Group 6 (six).

This group is also recommended in ANSI [X9.63], echeck [ECHECK], NIST
[NIST], and 7. SECG [GEC1].



3. Security Considerations

Since this document proposes new groups for use within IKE, many of the
security considerations contained within RFC 2409 apply here as well.

Two of the groups proposed in this document (seventh (eighth and eighth ninth groups)
offer higher strength than those proposed in RFC 2409, since they are
defined over field size of 277 283 bits. In addition, since all the new
groups are defined over GF[2^N] with N prime, they address concerns
expressed regarding elliptic curve groups included in RFC 2409, which
are curves defined over GF[2^N] with N composite.



4. Patent Statements

To be provided.

[NOTE: Intellectual Property Rights

The readers should be aware IETF has been notified of intellectual property rights claimed in
regard to the specification contained in this document.
For more information, consult the online list of claimed rights
(http://www.ietf.org/ipr.html).

The IETF takes no position regarding the possibility validity or scope of any
intellectual property or other rights that might be claimed to
pertain to the implementation or use of the technology described in
this draft may require 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 inventions covered such
proprietary rights by patent
       rights.] implementors or users of this specification can
be obtained from the IETF Secretariat.



5. Acknowledgments

The authors would like to thank Simon Blake-Wilson (Certicom Corp.),
editor for ANSI X9.63 [X9.63], Corp.)
for his comments and recommendations.

Panjwani and Poeluev                                              [Page 7]


INTERNET-DRAFT       Additional ECC Groups For IKE          May 26,      September 13, 1999



6. References

[RFC2409] Harkins, D. and Carrel, D., The Internet Key Exchange (RFC 2409).
November, 1998.

[IKE] Harkins, D. and Carrel, D., The Internet Key Exchange
(draft-ietf-ipsec-ike-01.txt), May 1999.

[X9.62] American National Standards Institute. ANSI X9.62-1999, X9.62-1998, Public Key
Cryptography for the Financial Services Industry: The Elliptic Curve Digital
Signature Algorithm. January, 1999.

[X9.63] American National Standards Institute. ANSI X9.63-199x, Public Key
Cryptography for the Financial Services Industry: Key Agreement and Key
Transport using Elliptic Curve Cryptography. Working Draft. January, September, 1999.

[ECHECK] Financial Services Technology Consortium. FSML - Financial
Services Markup Language. Working draft. August 1999.

[P1363] Institute of Electrical and Electronics Engineers. IEEE P1363,
Standard for Public Key Cryptography. IEEE Microporcessor Standards
Committee. Working Draft. September 1998. July 1999.

[Kob] Koblitz, N., CM curves with good cryptographic properties.
Proceedings of Crypto '91. Pages 279-287. Springer-Verlag. 1992.

[NIST] National Institute of Standards and Technology. Recommended
Elliptic Curves for Federal Government Use. July 1999.

[NSA] Solinas, J., An improved algorithm for arithmetic on a
family of elliptic curves. Proceedings of Crypto '97.
Pages 357-371. Springer-Verlag. 1997.

[GEC1] Standards for Efficient Cryptography Group. GEC 1 - Recommended
Elliptic Curve Domain Parameters. Working Draft. August 1999.

[WTLS] Wireless Application Forum. WAP WTLS - Wireless Application
Protocol Wireless Transport Layer Security Specification. February 1999.



7. Authors' Addresses

    Authors:

           Prakash Panjwani
           Certicom Corp.
           ppanjwani@certicom.com

           Yuri Poeluev
           Certicom Corp.
           ypoeluev@certicom.com

Panjwani and Poeluev                                              [Page 8]

----