IPSec Working Group                                      J. Solinas, NSA
INTERNET-DRAFT
Expires October 2, November 27, 2005                                   March 31,                                   May 27, 2005

                           ECP Groups For IKE
                <draft-ietf-ipsec-ike-ecp-groups-00.txt>
                <draft-ietf-ipsec-ike-ecp-groups-01.txt>

                          Status of this Memo

   By submitting this Internet-Draft, each author represents that any
   applicable patent or other IPR claims of which he or she is aware
   have been or will be disclosed, and any of which he or she becomes
   aware will be disclosed, in accordance with Section 6 of BCP 79.

   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/1id-abstracts.html

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html

                                Abstract

   This document describes new ECC groups for use in the Internet Key
   Exchange (IKE) protocol in addition to previously defined groups.
   Specifically, the new curve groups are based on modular arithmetic
   rather than binary arithmetic.  These new groups are defined to align
   IKE with other ECC implementations and standards, particularly NIST
   standards.  In addition, the curves defined here can provide more
   efficient implementation than previously defined ECC groups.

1.  Introduction

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

   RFC 2409 [IKE] defines five standard Oakley Groups - three modular
   exponentiation groups and two elliptic curve groups over GF[2^N].
   One modular exponentiation group (768 bits - Oakley Group 1) is
   mandatory for all implementations to support, while the other four
   are optional.  Thirteen additional groups subsequently have
   been defined and assigned values by IANA.  All of these additional
   groups are optional.  Of the eighteen groups defined so far, eight
   are modular exponentiation groups and ten are elliptic curve groups
   over GF[2^N] with N composite. GF[2^N].

   The purpose of this document is to expand the options available to
   implementers of elliptic curve groups by adding three new elliptic
   curve groups.  Unlike the previous elliptic curve groups, the three
   groups proposed in this document are defined over GF[p] with p prime.
   The reasons for adding these new groups include the following.

   - The groups proposed afford efficiency advantages in software
     applications since the underlying arithmetic is integer arithmetic
     modulo a prime rather than binary field arithmetic.  (Additional
     computational advantages for these groups are presented in [GMN].)

   - The groups proposed encourage alignment with other elliptic curve
     standards.  The proposed groups are among those standardized by
     NIST, by the SECG, by ISO, and by ANSI.  (See section 3 for
     details.)

   - The groups proposed are capable of providing security consistent
     with the new Advanced Encryption Standard.

   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.  In addition, the
   availability of standardized groups will result in optimizations for
   a particular curve and field size as well as allowing precomputation
   that could result in faster implementations.

   It is anticipated that the groups proposed here will be assigned
   identifiers by IANA [IANA].  In that case the full list of assigned
   values for the Group Description class within IKE will be the
   following.  (The groups defined in this document are listed as
   19, 20, and 21.)
   Group Description                                           Value
   -----------------                                           -----
   Default 768-bit MODP group                [IKE]               1
   Alternate 1024-bit MODP group             [IKE]               2
   EC2N group over GF[2^155]                 [IKE]               3
   EC2N group over GF[2^185]                 [IKE]               4
   1536-bit MODP group                       [RFC-3526]          5
   EC2N group over GF[2^163]                 [BBPS]              6
   EC2N group over GF[2^163]                 [BBPS]              7
   EC2N group over GF[2^283]                 [BBPS]              8
   EC2N group over GF[2^283]                 [BBPS]              9
   EC2N group over GF[2^409]                 [BBPS]             10
   EC2N group over GF[2^409]                 [BBPS]             11
   EC2N group over GF[2^571]                 [BBPS]             12
   EC2N group over GF[2^571]                 [BBPS]             13
   2048-bit MODP group                       [RFC-3526]         14
   3072-bit MODP group                       [RFC-3526]         15
   4096-bit MODP group                       [RFC-3526]         16
   6144-bit MODP group                       [RFC-3526]         17
   8192-bit MODP group                       [RFC-3526]         18
   256-bit ECP group  (EC group modulo a 256-bit prime)         19
   384-bit ECP group  (EC group modulo a 384-bit prime)         20
   521-bit ECP group  (EC group modulo a 521-bit prime)         21

   The IANA group type [IANA] of the three new groups is 2 (ECP -
   elliptic curve group over GF(P)).  The previous eighteen groups all
   have group types 1 or 3.

   In summary, due to the performance advantages of elliptic curve
   groups in IKE implementations and the need for further alignment with
   other standards, this document defines three elliptic curve groups
   based on modular arithmetic.

2. Additional ECC Groups

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

2.1 Nineteenth Group

   IKE implementations SHOULD support an ECP group with the following
   characteristics.  This group is assigned id 19 (nineteen).  The curve
   is based on the integers modulo the generalized Mersenne prime p
   given by

                  p = 2^(256)-2^(224)+2^(192)+2^(96)-1 .

   The equation for the elliptic curve is:

                  y^2 = x^3 - 3 x + b.

Field size:
 256

Group Prime/Irreducible Polynomial:
 FFFFFFFF 00000001 00000000 00000000 00000000 FFFFFFFF FFFFFFFF FFFFFFFF

Group Curve b:
 5AC635D8 AA3A93E7 B3EBBD55 769886BC 651D06B0 CC53B0F6 3BCE3C3E 27D2604B

Group Generator point P (x coordinate):
 6B17D1F2 E12C4247 F8BCE6E5 63A440F2 77037D81 2DEB33A0 F4A13945 D898C296

Group Generator point P (y coordinate):
 4FE342E2 FE1A7F9B 8EE7EB4A 7C0F9E16 2BCE3357 6B315ECE CBB64068 37BF51F5

Group order:
 FFFFFFFF 00000000 FFFFFFFF FFFFFFFF BCE6FAAD A7179E84 F3B9CAC2 FC632551

The group was chosen verifiably at random using SHA-1 as specified in
[IEEE-1363] from the seed:

 C49D3608 86E70493 6A6678E1 139D26B7 819F7E90

The data in the KE payload when using this group represents the
point on the curve obtained by taking the scalar multiple Ka*P,
where Ka is the randomly chosen secret.

2.2 Twentieth Group

IKE implementations SHOULD support an ECP group with the following
characteristics.  This group is assigned id 20 (twenty).  The curve is
based on the integers modulo the generalized Mersenne prime p given by

                  p = 2^(384)-2^(128)-2^(96)+2^(32)-1 .

The equation for the elliptic curve is:

                  y^2 = x^3 - 3 x + b.

Field size:
 384

Group Prime/Irreducible Polynomial:
                                     FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF
 FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFFFF 00000000 00000000 FFFFFFFF

Group Curve b:
                                     B3312FA7 E23EE7E4 988E056B E3F82D19
 181D9C6E FE814112 0314088F 5013875A C656398D 8A2ED19D 2A85C8ED D3EC2AEF

Group Generator point P (x coordinate):
                                     AA87CA22 BE8B0537 8EB1C71E F320AD74
 6E1D3B62 8BA79B98 59F741E0 82542A38 5502F25D BF55296C 3A545E38 72760AB7

Group Generator point P (y coordinate):
                                     3617DE4A 96262C6F 5D9E98BF 9292DC29
 F8F41DBD 289A147C E9DA3113 B5F0B8C0 0A60B1CE 1D7E819D 7A431D7C 90EA0E5F

Group order:
                                     FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF
 FFFFFFFF FFFFFFFF C7634D81 F4372DDF 581A0DB2 48B0A77A ECEC196A CCC52973

The group was chosen verifiably at random using SHA-1 as specified in
[IEEE-1363] from the seed:

 A335926A A319A27A 1D00896A 6773A482 7ACDAC73

The data in the KE payload when using this group represents the
point on the curve obtained by taking the scalar multiple Ka*P,
where Ka is the randomly chosen secret.

2.3 Twenty-First Group

   IKE implementations SHOULD support an ECP group with the following
   characteristics.  This group is assigned id 21 (twenty-one).  The
   curve is based on the integers modulo the Mersenne prime p given by

                  p = 2^(521)-1 .

   The equation for the elliptic curve is:

                  y^2 = x^3 - 3 x + b.

Field size:
 521

Group Prime/Irreducible Polynomial:
                                                                000001FF
 FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF
 FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF

Group Curve b:
                                                                00000051
 953EB961 8E1C9A1F 929A21A0 B68540EE A2DA725B 99B315F3 B8B48991 8EF109E1
 56193951 EC7E937B 1652C0BD 3BB1BF07 3573DF88 3D2C34F1 EF451FD4 6B503F00

Group Generator point P (x coordinate):
                                                                000000C6
 858E06B7 0404E9CD 9E3ECB66 2395B442 9C648139 053FB521 F828AF60 6B4D3DBA
 A14B5E77 EFE75928 FE1DC127 A2FFA8DE 3348B3C1 856A429B F97E7E31 C2E5BD66

Group Generator point P (y coordinate):
                                                                00000118
 39296A78 9A3BC004 5C8A5FB4 2C7D1BD9 98F54449 579B4468 17AFBD17 273E662C
 97EE7299 5EF42640 C550B901 3FAD0761 353C7086 A272C240 88BE9476 9FD16650

Group order:
                                                                000001FF
 FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFA
 51868783 BF2F966B 7FCC0148 F709A5D0 3BB5C9B8 899C47AE BB6FB71E 91386409

The group was chosen verifiably at random using SHA-1 as specified in
[IEEE-1363] from the seed:

 D09E8800 291CB853 96CC6717 393284AA A0DA64BA

The data in the KE payload when using this group represents the
point on the curve obtained by taking the scalar multiple Ka*P,
where Ka is the randomly chosen secret.

3. Alignment with Other Standards

   The following table summarizes the appearance of these three
   elliptic curve groups in other standards.

   Standard                 Group 19        Group 20        Group 21

   NIST     [DSS]           P-256           P-384           P-521

   ISO/IEC  [ISO-15946-1]   P-256

   ISO/IEC  [ISO-18031]     P-256           P-384           P-521

   ANSI     [X9.62-1998]    Sect. J.5.3,
                            Example 1

   ANSI     [X9.62-2003]    Sect. J.6.5.3   Sect. J.6.6     Sect. J.6.7

   ANSI     [X9.63]         Sect. J.5.4,    Sect. J.5.5     Sect. J.5.6
                            Example 2

   SECG     [SEC2]          secp256r1       secp384r1       secp521r1

   See also [NIST], [ISO-14888-3], [ISO-15946-2], [ISO-15946-3], and
    [ISO-15946-4].

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

   The groups proposed in this document correspond to the symmetric key
   sizes 128 bits, 192 bits, and 256 bits.  This allows the IKE key
   exchange to offer security comparable with the AES algorithms [AES].

5. IANA Considerations

   Before this document can become an RFC, it is required that IANA
   update its registry of Diffie-Hellman groups for IKE in [IANA] to
   include the three groups defined above.

6. References

6.1 Normative

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

6.2 Informative

  [AES] U.S. Department of Commerce/National Institute of Standards
     and Technology, Advanced Encryption Standard (AES), FIPS PUB 197,
     November 2001.  (http://csrc.nist.gov/publications/fips/index.html)

  [BBPS] S. Blake-Wilson, D. Brown, Y. Poeluev, M. Salter, Additional
     ECC Groups for IKE, draft-ietf-ipsec-ike-ecc-groups-04.txt,
     July 2002.

  [DSS] U.S. Department of Commerce/National Institute of Standards
     and Technology, Digital Signature Standard (DSS), FIPS PUB 186-2,
     January 2000.  (http://csrc.nist.gov/publications/fips/index.html)

  [GMN] J. Solinas, Generalized Mersenne Numbers, Combinatorics
     and Optimization Research Report 99-39, 1999.
     (http://www.cacr.math.uwaterloo.ca/)

  [IANA] Internet Assigned Numbers Authority, Internet Key Exchange
     (IKE) Attributes.  (http://www.iana.org/assignments/ipsec-registry)

  [IEEE-1363] Institute of Electrical and Electronics Engineers. IEEE
     1363-2000, Standard for Public Key Cryptography.
     (http://grouper.ieee.org/groups/1363/index.html)

  [ISO-14888-3]  International Organization for Standardization and
     International Electrotechnical Commission, ISO/IEC First
     Committee Draft 14888-3 (2nd ed.), Information Technology:
     Security Techniques: Digital Signatures with Appendix: Part 3 -
     Discrete Logarithm Based Mechanisms.

  [ISO-15946-1]   International Organization for Standardization and
     International Electrotechnical Commission, ISO/IEC 15946-1:
     2002-12-01, Information Technology: Security Techniques:
     Cryptographic Techniques based on Elliptic Curves: Part 1 -
     General.

  [ISO-15946-2]   International Organization for Standardization and
     International Electrotechnical Commission, ISO/IEC 15946-2:
     2002-12-01, Information Technology: Security Techniques:
     Cryptographic Techniques based on Elliptic Curves: Part 2 -
     Digital Signatures.

  [ISO-15946-3]   International Organization for Standardization and
     International Electrotechnical Commission, ISO/IEC 15946-3:
     2002-12-01, Information Technology: Security Techniques:
     Cryptographic Techniques based on Elliptic Curves: Part 3 -
     Key Establishment.

  [ISO-15946-4]   International Organization for Standardization and
     International Electrotechnical Commission, ISO/IEC 15946-4:
     2004-10-01, Information Technology: Security Techniques:
     Cryptographic Techniques based on Elliptic Curves: Part 4 -
     Digital Signatures giving Message Recovery.

  [ISO-18031] International Organization for Standardization and
     International Electrotechnical Commission, ISO/IEC Final
     Committee Draft 18031, Information Technology: Security
     Techniques: Random Bit Generation, October 2004.

  [NIST] U.S. Department of Commerce/National Institute of Standards
     and Technology. Recommendation for Key Establishment Schemes
     Using Discrete Logarithm Cryptography, NIST Special Publication
     800-56. (http://csrc.nist.gov/CryptoToolkit/KeyMgmt.html)

  [RFC-3526] T. Kivinen and M. Kojo, More Modular Exponential (MODP)
     Diffie-Hellman groups for Internet Key Exchange (IKE), RFC
     3526, May 2003.

  [SEC2] Standards for Efficient Cryptography Group. SEC 2 -
     Recommended Elliptic Curve Domain Parameters, v. 1.0, 2000.
     (http://www.secg.org)

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

  [X9.62-2003] American National Standards Institute, X9.62-1998:
     Public Key Cryptography for the Financial Services Industry: The
     Elliptic Curve Digital Signature Algorithm,
     Revised-Draft-2003-02-26, February 2003.

  [X9.63] American National Standards Institute. X9.63-2001,
     Public Key Cryptography for the Financial Services Industry: Key
     Agreement and Key Transport using Elliptic Curve Cryptography.
     November 2001.

7. Author's Address

           Jerome A. Solinas
           National Security Agency
           jsolinas@orion.ncsc.mil
           jasolin@orion.ncsc.mil

   Comments are solicited and should be addressed to the author.

   Copyright (C) The Internet Society (2005).

   This document is subject to the rights, licenses and restrictions
   contained in BCP 78, and except as set forth therein, the authors
   retain all their rights.

   This document and the information contained herein are provided on an
   "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
   OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
   ENGINEERING TASK FORCE DISCLAIM 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.

   Expires October 2, November 27, 2005