IPSec Working Group P. Panjwani and Y. Poeluev INTERNET-DRAFT Certicom Corp Expires November 20, 1999 May 26, 1999 Additional ECC Groups For IKE 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. Abstract This document describes new ECC groups for use in IKE [RFC2409] in addition to the Oakley groups included in RFC 2409. These groups are defined to align 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]. Table of Contents 1. Introduction ............................................... 2 2. Additional Oakley Groups ................................... 3 2.1. Fifth Group .............................................. 3 2.2. Sixth Group .............................................. 4 2.3. Seventh Group ............................................ 5 2.4. Eighth Group ............................................. 6 3. Security Considerations .................................... 7 4. Patent Statements .......................................... 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, 1999 1. Introduction This document describes default groups for use in IKE [RFC2409] in addition to the Oakley groups included in RFC 2409. 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 defines four standard Oakley Groups - two 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 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. 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 base points whose prime order is greater than 2^160, as required by 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 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. 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]. 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] is used below to describe the new Oakley Groups proposed. 2.1 Fifth Group IKE implementations SHOULD support a EC2N group with the following charac- teristics. This group is assigned id 5 (five). 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 Group Generator Two: 0x00435EDB42EFAFB2989D51FEFCE3C80988F41FF883 Group Order: 0x07FFFFFFFFFFFFFFFFFFFE91556D1385394E204F36 The order of the base point P defined by Group Generator One and Group Generator Two is the prime: 0x03FFFFFFFFFFFFFFFFFFFF48AAB689C29CA710279B 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 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), 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 the curve point with x-coor- dinate equal to Group Generator One and y-coordinate equal to Group Generator Two. This is identical to the method used by Oakley Groups 3 and 4. 2.2 Sixth Group IKE implementations SHOULD support a EC2N group with the following charac- teristics. This group is assigned id 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 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 Group Generator Two: 0x0289070FB05D38FF58321F2E800536D538CCDAA3D9 Group Order: 0x0800000000000000000004021145C1981B33F14BDE The order of the base point P defined by Group Generator One and Group Generator Two is the prime: 0x04000000000000000000020108A2E0CC0D99F8A5EF The group order is twice this prime. The data in the KE payload when using this group identical to the data used with Oakley Groups 3, 4, and 5. 2.3 Seventh Group IKE implementations SHOULD support a EC2N group with the following charac- teristics. This group is assigned id 7 (seven). The curve is based on the Galois Field GF[2^277]. The field size is 277. The irreducible polynomial used to represent the field is: u^277 + u^12 + 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: 277 Irreducible polynomial: 0x2000000000000000000000000000000000000000000000000000000000000000001049 Group Curve a: 0x1853044E52AC1959E666EB976840794626756389C3084E1C0E8EE58B5ADE55B0E94F06 Group Curve b: 0x12709B9501DBD0C98DC5E7E17AF396B445303DFDBDEA0AAE05840A8204625E0B9157B9 Panjwani and Poeluev [Page 5] INTERNET-DRAFT Additional ECC Groups For IKE May 26, 1999 Group Generator One: 0x180949B3BBF7F5168DA7647F9BBAE716F02F6174EC79DE0A5AC9AEC5FF48E4D696323B Group Generator Two: 0x1CB7297D452004A0F2C34F33E5A6900122103B5F78BE5B838AA97848CCFEDD01F60618 Group Order: 0x1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF7049860E759CB2BDBEF59DD8C6B43EAE816 The group was chosen verifiably at random using SHA-1 as specified in [X9.62] from the seed: 0xAC2F14783E695F34335EB4D696E6768756151753 The order of the base point P defined by Group Generator One and Group Generator Two is the prime: 0x0FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFB824C3073ACE595EDF7ACEEC635A1F5740B The group order is twice this prime. The data in the KE payload when using this group identical to the data used with Oakley Groups 3, 4, 5, and 6. 2.4 Eighth Group IKE implementations SHOULD support a EC2N group with the following charac- teristics. This group is assigned id 7 (seven). The curve is based on the Galois Field GF[2^277]. The field size is 277. The irreducible polynomial used to represent the field is: u^277 + u^12 + 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: 277 Irreducible polynomial: 0x2000000000000000000000000000000000000000000000000000000000000000001049 Group Curve a: 0x0000000000000000000000000000000000000000000000000000000000000000000000 Group Curve b: 0x0000000000000000000000000000000000000000000000000000000000000000000001 Group Generator One: 0x1F548FD1F2A95B49A515F99E1933746460B57E47C1AF27AC3E101A1C175C92A741061A Panjwani and Poeluev [Page 6] INTERNET-DRAFT Additional ECC Groups For IKE May 26, 1999 Group Generator Two: 0x070B258D9BE112C22B9BAA56BBBA6BB9CA38BC0F5E7E95BFD65FBBBC64BC3317DAF873 Group Order: 0x1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFB42A2D15E3F4D2F69828D921E5BB03C3EEC The order of the base point P defined by Group Generator One and Group Generator Two is the prime: 0x07FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED0A8B4578FD34BDA60A3648796EC0F0FBB The group order is four times this prime. The data in the KE payload when using this group identical to the data used with Oakley Groups 3, 4, 5, 6, and 7. 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 and eighth groups) offer higher strength than those proposed in RFC 2409, since they are defined over field size of 277 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: The readers should be aware of the possibility that implementation of this draft may require use of inventions covered by patent rights.] 5. Acknowledgments The authors would like to thank Simon Blake-Wilson (Certicom Corp.), editor for ANSI X9.63 [X9.63], for his comments and recommendations. Panjwani and Poeluev [Page 7] INTERNET-DRAFT Additional ECC Groups For IKE May 26, 1999 6. References [RFC2409] Harkins, D. and Carrel, D., The Internet Key Exchange (RFC 2409). November, 1998. [X9.62] American National Standards Institute. ANSI X9.62-1999, 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, 1999. [P1363] Institute of Electrical and Electronics Engineers. IEEE P1363, Standard for Public Key Cryptography. IEEE Microporcessor Standards Committee. Working Draft. September 1998. [Kob] Koblitz, N., CM curves with good cryptographic properties. Proceedings of Crypto '91. Pages 279-287. Springer-Verlag. 1992. [NSA] Solinas, J., An improved algorithm for arithmetic on a family of elliptic curves. Proceedings of Crypto '97. Pages 357-371. Springer-Verlag. 1997. 7. Authors' Addresses Authors: Prakash Panjwani Certicom Corp. ppanjwani@certicom.com Yuri Poeluev Certicom Corp. ypoeluev@certicom.com Panjwani and Poeluev [Page 8]