IPSec Working Group P. Panjwani and Y. Poeluev INTERNET-DRAFT Certicom Corp Expires November 29, 2000 May 30, 2000 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 may be found at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories may be found at http://www.ietf.org/shadow.html. Abstract This document describes new ECC groups for use in IKE [IKE] in addition to the Oakley groups included therein. 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 [IKE]. Table of Contents 1. Introduction ............................................... 2 2. Additional Oakley Groups ................................... 3 2.1. Sixth Group .............................................. 3 2.2. Seventh Group ............................................ 5 2.3. Eighth Group ............................................. 6 2.4. Ninth Group .............................................. 7 3. Security Considerations .................................... 8 4. Intellectual Property Rights ............................... 8 5. Acknowledgments ............................................ 8 6. References ................................................. 9 7. Authors' Addresses .........................................10 Panjwani and Poeluev [Page 1] INTERNET-DRAFT Additional ECC Groups For IKE May 30, 2000 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]. The document assumes that the reader is familiar with the IKE protocol and the concept of Oakley Groups, as defined in RFC 2409 [IKE]. RFC2409 [IKE] defines five standard Oakley Groups - three modular exponen- tiation groups and two elliptic curve groups over GF[2^N]. One modular exp- onentiation group (768 bits - Oakley Group 1) is mandatory for all implemen- tations to support, while the other 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 users of elliptic curve groups can signifi- cantly improve their performance by using groups other than the Oakley Groups 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 adding 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 the 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]), they use base points whose prime order is greater than 2^160 (as required by ANSI [X9.62, 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 -- concerns highlighted by the recent attack on such curves due to Gaudry, Hess, and Smart [WEIL]. - The four groups proposed are amongst those recently standardized by NIST in FIPS 186-2 [DSS] and the SECG in SEC2 [SEC2]. 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 given above. 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. Panjwani and Poeluev [Page 2] INTERNET-DRAFT Additional ECC Groups For IKE May 30, 2000 The groups proposed here have been assigned identifiers by IANA [IANA]. Thus the full list of assigned values for the Group Description class within IKE is the following. (The first four groups may be found in RFC 2409 [IKE]; the last four groups are defined in this document.) Group Description Value ----------------- ----- Default 768-bit MODP group 1 Alternate 1024-bit MODP group 2 EC2N group over GF[2^155] 3 EC2N group over GF[2^185] 4 Reserved to IANA 5 EC2N group over GF[2^163] (Section 2.1) 6 EC2N group over GF[2^163] (Section 2.2) 7 EC2N group over GF[2^283] (Section 2.3) 8 EC2N group over GF[2^283] (Section 2.4) 9 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^283]. These field sizes correspond to 80-bit and 128-bit symmetric key strengths, 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 (as defined in ANSI [X9.62]). The groups are assigned numbers numbers 6 to 9 by IANA [IANA]. 2. Additional Oakley Groups The notation adopted in RFC2409 [IKE] is used below to describe the new Oakley Groups proposed. 2.1 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 Panjwani and Poeluev [Page 3] INTERNET-DRAFT Additional ECC Groups For IKE May 30, 2000 Irreducible polynomial: 0x0800000000000000000000000000000000000000C9 Group Curve a: 0x07B6882CAAEFA84F9554FF8428BD88E246D2782AE2 Group Curve b: 0x0713612DCDDCB40AAB946BDA29CA91F73AF958AFD9 Group Generator point P (compressed): 0x030369979697AB43897789566789567F787A7876A654 Group Generator point P (uncompressed): 0x040369979697AB43897789566789567F787A7876A654 00435EDB42EFAFB2989D51FEFCE3C80988F41FF883 The order of the base point P defined above 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 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 octet string representation specified in ANSI X9.62, ANSI X9.63, FIPS 186-2, 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 this payload differs from the payload specified for groups 3 and 4 - it is aligned instead with other recent standardization efforts in ECC. This group corresponds to the curve sect163r1 in SEC 2 [SEC2]. It is also recommended in ANSI X9.63 [X9.63] and echeck [ECHECK]. Panjwani and Poeluev [Page 4] INTERNET-DRAFT Additional ECC Groups For IKE May 30, 2000 2.2 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^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: 0x000000000000000000000000000000000000000001 Group Curve b: 0x000000000000000000000000000000000000000001 Group Generator point P (compressed): 0x0302FE13C0537BBC11ACAA07D793DE4E6D5E5C94EEE8 Group Generator point P (uncompressed): 0x0402FE13C0537BBC11ACAA07D793DE4E6D5E5C94EEE8 0289070FB05D38FF58321F2E800536D538CCDAA3D9 The order of the base point P 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, ANSI X9.63, FIPS 186-2, 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 format used with Oakley Group 6 (six). This group corresponds to the curve K-163 in FIPS 186-2 [DSS] and sect163k1 in SEC 2 [SEC2]. It is also recommended in ANSI [X9.63], echeck [ECHECK], and WAP [WTLS]. Panjwani and Poeluev [Page 5] INTERNET-DRAFT Additional ECC Groups For IKE May 30, 2000 2.3 Eighth Group IKE implementations SHOULD support a EC2N group with the following charac- teristics. This group is assigned id 8 (eight). The curve is based on the Galois Field GF[2^283]. The field size is 283. The irreducible polynomial used to represent the field is: u^283 + u^12 + u^7 + 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: 283 Irreducible polynomial: 0x0800000000000000000000000000000000000000000000000000000000000000000010A1 Group Curve a: 0x000000000000000000000000000000000000000000000000000000000000000000000001 Group Curve b: 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. The group was chosen verifiably at random in normal basis representation using SHA-1 as specified in [X9.62] from the seed: 0x77E2B07370EB0F832A6DD5B62DFC88CD06BB84BE The data in the KE payload when using this group is the octet string representation specified in ANSI X9.62, ANSI X9.63, FIPS 186-2, 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 format used with Oakley Group 6 (six). This group corresponds to the curve B-283 (in the polynomial basis) in FIPS 186-2 [DSS] and sect283r1 in SEC 2 [SEC2]. It is also recommended in ANSI [X9.63] and echeck [ECHECK]. Panjwani and Poeluev [Page 6] INTERNET-DRAFT Additional ECC Groups For IKE May 30, 2000 2.4 Ninth Group IKE implementations SHOULD support a EC2N group with the following charac- teristics. This group is assigned id 9 (nine). The curve is based on the Galois Field GF[2^283]. The field size is 283. The irreducible polynomial used to represent the field is: u^283 + u^12 + u^7 + 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: 283 Irreducible polynomial: 0x0800000000000000000000000000000000000000000000000000000000000000000010A1 Group Curve a: 0x000000000000000000000000000000000000000000000000000000000000000000000000 Group Curve b: 0x000000000000000000000000000000000000000000000000000000000000000000000001 Group Generator point P (compressed): 0x020503213F78CA44883F1A3B8162F188E553CD265F23C1567A16876913B0C2AC2458492836 Group Generator point P (uncompressed): 0x040503213F78CA44883F1A3B8162F188E553CD265F23C1567A16876913B0C2AC2458492836 01CCDA380F1C9E318D90F95D07E5426FE87E45C0E8184698E45962364E34116177DD2259 The order of the base point P is the prime: 0x01FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE9AE2ED07577265DFF7F94451E061E163C61 The group order is four times this prime. The data in the KE payload when using this group is the octet string representation specified in ANSI X9.62, ANSI X9.63, FIPS 186-2, 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 format used with Oakley Group 6 (six). This group corresponds to the curve K-283 (in the polynomial basis) in FIPS 186-2 [DSS] and sect283k1 in SEC 2 [SEC2]. It is also recommended in ANSI [X9.63] and echeck [ECHECK]. Panjwani and Poeluev [Page 7] INTERNET-DRAFT Additional ECC Groups For IKE May 30, 2000 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 (eighth and ninth groups) offer higher strength than those proposed in RFC 2409, since they are defined over field size of 283 bits. In addition, since all the new groups are defined over GF[2^N] with N prime, they address the concerns expressed regarding the elliptic curve groups included in RFC 2409, which are curves defined over GF[2^N] with N composite. The work of Gaudry, Hess, and Smart [WEIL] reveal some of the weaknesses in such groups. 4. Intellectual Property Rights The 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 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 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. 5. Acknowledgments The authors would like to thank Simon Blake-Wilson and John O. Goyo (Certicom Corp.) for their comments and recommendations. Panjwani and Poeluev [Page 8] INTERNET-DRAFT Additional ECC Groups For IKE May 30, 2000 6. References [IKE] Harkins, D. and Carrel, D., The Internet Key Exchange, RFC 2409, November 1998. [X9.62] American National Standards Institute. ANSI 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, October 1999. [ECHECK] Financial Services Technology Consortium. FSML - Financial Services Markup Language. Working draft, August 1999. (http://www.echeck.org) [IANA] Internet Assigned Numbers Authority. Attribute Assigned Numbers. (http://www.isi.edu/in-notes/iana/assignments/ipsec-registry) [P1363] Institute of Electrical and Electronics Engineers. IEEE P1363, Standard for Public Key Cryptography. IEEE Microprocessor Standards Committee. March 2000. (http://grouper.ieee.org/groups/1363/index.html) [Kob] Koblitz, N., CM curves with good cryptographic properties. Proceedings of Crypto '91. Pages 279-287. Springer-Verlag, 1992. [DSS] U.S. Department of Commerce/National Institute of Standards and Technology. Digital Signature Standard (DSS), FIPS PUB 186-2, 2000 January 27. (http://csrc.nist.gov/fips/fips186-2.pdf) [NSA] Solinas, J., An improved algorithm for arithmetic on a family of elliptic curves, Proceedings of Crypto '97, Pages 357-371, Springer-Verlag, 1997. [SEC2] Standards for Efficient Cryptography Group. SEC 2 - Recommended Elliptic Curve Domain Parameters. Working Draft Ver. 0.6., 1999. (http://www.secg.org) [WEIL] Gaudry, P., Hess, F., Smart, Nigel P. Constructive and Destruc- tive Facets of Weil Descent on Elliptic Curves, HP Labs Technical Report No. HPL-2000-10, 2000. (http://www.hpl.hp.com/techreports/2000/HPL-2000-10.html) [WTLS] Wireless Application Forum. WAP WTLS - Wireless Application Protocol Wireless Transport Layer Security Specification, February 1999. (http://www.wapforum.org) Panjwani and Poeluev [Page 9] INTERNET-DRAFT Additional ECC Groups For IKE May 30, 2000 7. Authors' Addresses Authors: Prakash Panjwani Certicom Corp. ppanjwani@certicom.com Yuri Poeluev Certicom Corp. ypoeluev@certicom.com Panjwani and Poeluev [Page 10]