idnits 2.17.1 

draft-jivsov-ecc-compact-02.txt:

  Checking boilerplate required by RFC 5378 and the IETF Trust (see
  https://trustee.ietf.org/license-info):
  ----------------------------------------------------------------------------

     No issues found here.

  Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt:
  ----------------------------------------------------------------------------

     No issues found here.

  Checking nits according to https://www.ietf.org/id-info/checklist :
  ----------------------------------------------------------------------------

     No issues found here.

  Miscellaneous warnings:
  ----------------------------------------------------------------------------

  == The copyright year in the IETF Trust and authors Copyright Line does not
     match the current year

  -- The document date (June 4, 2013) is 3971 days in the past.  Is this
     intentional?

  -- Found something which looks like a code comment -- if you have code
     sections in the document, please surround them with '<CODE BEGINS>' and
     '<CODE ENDS>' lines.


  Checking references for intended status: Informational
  ----------------------------------------------------------------------------

     No issues found here.

     Summary: 0 errors (**), 0 flaws (~~), 1 warning (==), 2 comments (--).

     Run idnits with the --verbose option for more detailed information about
     the items above.
--------------------------------------------------------------------------------


2	Network Workign Group                                          A. Jivsov
3	Internet-Draft                                      Symantec Corporation
4	Intended status: Informational                              June 4, 2013
5	Expires: December 6, 2013

7	           Compact representation of an elliptic curve point
8	                      draft-jivsov-ecc-compact-02

10	Abstract

12	   This document defines a format for efficient storage representation
13	   of an elliptic curve point over prime fields, suitable for use with
14	   any IETF format or protocol.

16	Status of this Memo

18	   This Internet-Draft is submitted in full conformance with the
19	   provisions of BCP 78 and BCP 79.

21	   Internet-Drafts are working documents of the Internet Engineering
22	   Task Force (IETF).  Note that other groups may also distribute
23	   working documents as Internet-Drafts.  The list of current Internet-
24	   Drafts is at http://datatracker.ietf.org/drafts/current/.

26	   Internet-Drafts are draft documents valid for a maximum of six months
27	   and may be updated, replaced, or obsoleted by other documents at any
28	   time.  It is inappropriate to use Internet-Drafts as reference
29	   material or to cite them other than as "work in progress."

31	   This Internet-Draft will expire on December 6, 2013.

33	Copyright Notice

35	   Copyright (c) 2013 IETF Trust and the persons identified as the
36	   document authors.  All rights reserved.

38	   This document is subject to BCP 78 and the IETF Trust's Legal
39	   Provisions Relating to IETF Documents
40	   (http://trustee.ietf.org/license-info) in effect on the date of
41	   publication of this document.  Please review these documents
42	   carefully, as they describe your rights and restrictions with respect
43	   to this document.  Code Components extracted from this document must
44	   include Simplified BSD License text as described in Section 4.e of
45	   the Trust Legal Provisions and are provided without warranty as
46	   described in the Simplified BSD License.

48	Table of Contents

50	   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
51	   2.  Conventions used in this document  . . . . . . . . . . . . . .  3
52	   3.  Overview of the compact representation in IETF protocols . . .  3
53	   4.  The definition of the compact representation . . . . . . . . .  4
54	     4.1.  Encoding and decoding of an elliptic curve point . . . . .  5
55	     4.2.  The algorithms to generate a key pair  . . . . . . . . . .  5
56	       4.2.1.  The black box key generation algorithm . . . . . . . .  6
57	       4.2.2.  The deterministic key generation algorithm . . . . . .  6
58	     4.3.  The efficient square root algorithm for p=4*k+3  . . . . .  7
59	   5.  Interoperability considerations  . . . . . . . . . . . . . . .  7
60	   6.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . .  8
61	   7.  Security Considerations  . . . . . . . . . . . . . . . . . . .  8
62	   8.  References . . . . . . . . . . . . . . . . . . . . . . . . . . 10
63	     8.1.  Normative References . . . . . . . . . . . . . . . . . . . 10
64	     8.2.  Informative References . . . . . . . . . . . . . . . . . . 10
65	   Appendix A.  Sample code change to add compliant key
66	                generation to libgcrypt and openssl . . . . . . . . . 11
67	     A.1.  libgcrypt changes  . . . . . . . . . . . . . . . . . . . . 11
68	     A.2.  OpenSSL changes  . . . . . . . . . . . . . . . . . . . . . 12
69	   Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 13

71	1.  Introduction

73	   The National Security Agency (NSA) of the United States specifies
74	   elliptic curve cryptography (ECC) for use in its [SuiteB] set of
75	   algorithms.  The NIST elliptic curves over the prime fields
76	   [FIPS-186], which include [SuiteB] curves, or the Brainpool curves
77	   [RFC5639] are the examples of curves over prime fields.

79	   This document provides an efficient format for compact representation
80	   of a point on an elliptic curve over a prime field.  It is intended
81	   as an open format that other IETF protocols can rely on to minimize
82	   space required to store an ECC point.  This document complements the
83	   [RFC6090] with the on-the-wire definition of an ECC point.

85	   One of the benefits of the ECC is the small size of field elements.
86	   The compact representation reduces the encoded size of an ECC element
87	   in half, which can be a substantial saving in cases such as
88	   encryption of a short message sent to multiple recipients.

90	2.  Conventions used in this document

92	   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
93	   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
94	   document are to be interpreted as described in [RFC2119].

96	3.  Overview of the compact representation in IETF protocols

98	   IETF protocols often use the [SEC1] representation of a point on an
99	   elliptic curve, which is a sequence of the following fields:

101	   Field  Description
102	   ------ --------------------------------------------------------------
103	   B0     {02, 03, 04}, where 02 or 03 represent a compressed point (x
104	          only), while 04 represents a complete point (x,y)
105	   X      x coordinate of a point
106	   Y      y coordinate of a point, optional (present only for B0=04)

108	                         SEC1 point representation

110	   The [SEC1] is an example of a general-purpose elliptic curve point
111	   compression.  The idea behind these methods is the following:

113	   o  For the given point P=(x,y) the y coordinate can be derived from x
114	      by solving the corresponding equation of the ECC.

116	   o  There are two possible y coordinates for any x of a given P

118	   o  The either of the two possibilities for y is encoded in some way
119	      in the compressed representation

121	   There are a few undesirable properties of the above representation:

123	   o  The requirement to store one bit to identify the 'y' means that
124	      the whole byte is required.

126	   o  For most well-known elliptic curves the extra byte removes the
127	      power of two alignment for the encoded point.

129	   o  The requirement for the balanced security calls for the ECC curve
130	      size to be equal the hash output size, yet the storage length of
131	      the ECC point is equal to the hash output size + 1.

133	   o  The encoded point is not a multi-precision integer, but a
134	      structured sequence of bytes.  For example, special wording is
135	      required to define the encoding of the [FIPS-186] P-521 to clarify
136	      how odd number of bits for x and y, or a bit representing y, are
137	      packed into bytes.

139	   o  Some protocols, such as ECDH, don't depend on the exact value of
140	      the y.  It is unnecessary to track the precise point P=(x,y) in
141	      such protocols.

143	4.  The definition of the compact representation

145	   This document is an improvement to the idea by [Miller] to not
146	   transmit the y coordinate of an ECC point in the elliptic curve
147	   Diffie-Hellman (ECDH) protocol.

149	   We will use the following notations for the ECC point Q and the
150	   features of the corresponding elliptic curve:

152	      Q = k*G, where

154	      Q = (x,y) is the point on an elliptic curve (the canonical
155	      represenation)

157	      k - the private key (a scalar)

159	      G - the elliptic curve generator point

161	      y^2 = x^3 + a*x + b is the standard Weierstrass equation linking x
162	      and y
163	      p - the order of the underlying finite field to which x and y
164	      belong

166	      Ord - the order of the elliptic curve field, i.e. the number of
167	      points on the curve ( Ord*G = O, where O is the identity element )

169	   Q is a point that we need to represent in the compact form.  The
170	   integer operations considered in this document are performed modulo
171	   prime p and "(mod p)" is assumed in every formula with x and y.

173	   The steps to create and interpret the compact representation of a
174	   point are described next.  A special key generation algorithm is
175	   needed to make them possible, defined later in Section 4.2.

177	4.1.  Encoding and decoding of an elliptic curve point

179	   Encoding:  Given the canonical representation of Q=(x,y), return the
180	        x as the compact representation.

182	   Decoding:  Given the compact representation of Q, return canonical
183	        representation of Q=(x,y) as follows:

185	        1.   y' = sqrt( x^3 + a*x + b ), where y'>0

187	        2.   y = min(y',p-y')

189	        3.   Q=(x,y) is the canonical representation of the point

191	   Recall that the x is an element in the underlying finite field,
192	   represented by an integer.  Its precise encoding SHOULD be consistent
193	   with encoding of other multi-precision integers in the application,
194	   for example, it would be the same encoding as used for the r or s
195	   integer that is a part of the DSA signature and it is typically a
196	   sequence of big-endian bytes.

198	   The efficient algorithm to recover y for [SuiteB] or the Brainpool
199	   curves [RFC5639], among others, is given in Section 4.3.

201	   min(y,p-y) can be calculated with the help of the pre-calculated
202	   value p2=(p-1)/2. min(y,p-y) is y if y<p2 and p-y otherwise.

204	   The efficient encoding and decoding algorithms are possible with the
205	   special key generation algorithm, defined next.

207	4.2.  The algorithms to generate a key pair

209	   This document specifies two algorithms, called the "black box" and
210	   the "deterministic" key generation algorithms, to generate a key pair
211	   {k, Q=k*G=(x,y)}, where k is the private key and Q=(x,y) is the
212	   public key.  A key pair generated according to the requirements in
213	   this section is called a compliant key pair, and the public key of
214	   such a key pair -- a compliant public key.  A compliant public key
215	   Q=(x,y) allows compact representation as x, as defined in
216	   Section 4.1.

218	   Both key generation algorithms can be built with any general purpose
219	   key generation algorithm which would be needed in any ECC
220	   implementation that generates keys, regardless of the support for any
221	   method defined in this document.  Such a general purpose key
222	   generation algorithm is referred in this section as "KG".

224	   The black box algorithm works in scenarios when the KG doesn't allow
225	   any adjustments to the private key.  The disadvantage of this
226	   algorithm is that multiple KGs may be needed to generate a single key
227	   pair {k, Q}.  The deterministic algorithm is similar, except that it
228	   is allowed to perform a simple and fast modification to the private
229	   key after the KG.  The advantage of the second algorithm is
230	   performance, in particular, the guarantee that only a single KG is
231	   needed.

233	4.2.1.  The black box key generation algorithm

235	   The following algorithm calculates a key pair {k, Q=k*G=(x,y)}, where
236	   k is the private key and Q=(x,y) is the public key.

238	   Black box generation:

240	        1.   Generate a key pair {k, Q=k*G=(x,y)} with KG

242	        2.   if( y != min(y,p-y) ) goto step 1

244	        3.   output {k, Q=(x,y)} as a key pair

246	   Note that the step 1 is a general purpose key generation algorithm,
247	   such as an algorithm compliant with [NIST-SP800-133].  Step 1 assumes
248	   neither changes to existing key generation methods nor access to the
249	   private key in clear.

251	   The expected number of iterations in the loop in the above algorithm
252	   is 2.  The step 2 is not needed for the ECDH keys.

254	4.2.2.  The deterministic key generation algorithm

256	   The following algorithm calculates a key pair {k, Q=k*G=(x,y)}, where
257	   k is the private key and Q=(x,y) is the public key.

259	   Deterministic generation:

261	        1.   Generate a key pair {k, Q=k*G=(x,y)} with KG

263	        2.   if( y != min(y,p-y) ) k = Ord - k; y = p - y

265	        3.   output {k, Q=(x,y)} as a key pair

267	   The step 2 is not needed for the ECDH keys.

269	4.3.  The efficient square root algorithm for p=4*k+3

271	   When p mod 4 = 3, as is the case of [SuiteB] and the Brainpool curves
272	   [RFC5639], there is an efficient square root algorithm to recover the
273	   y, as follows:

275	      Given the compact representation of Q as x,

277	      y2 = x^3 + a*x + b

279	      y' = y2^((p+1)/4)

281	      y = min(y',p-y')

283	      Q=(x,y) is the canonical representation of the point

285	   See [Lehmer] for details.

287	5.  Interoperability considerations

289	   The compact representation described in this document allows two-
290	   phase introduction.

292	   First, key pairs must be generated as defined in Section 4.2 to allow
293	   compact representation.  No accompanied changes are needed elsewhere
294	   to use these keys.  This allows safe deployment of the new key
295	   generation, which, in turn, allows encoding and decoding of in
296	   compact representation, possibly at a later time.

298	   Finally, the encoding of public keys in the new compact
299	   representation format can be enabled after there is confidence in the
300	   universal support of new compact representation.  This event would
301	   not need to change any private key material, only public key
302	   representation.

304	   The above two phases can be implemented at once for new formats.

306	   Most ECC cryptographic protocols, such as ECDSA [FIPS-186], are
307	   intended to work with persistently stored public keys that are
308	   generated as fresh key pairs, as opposed to some derivation function
309	   that transforms an ECC point.  The algorithm described in Section 4.2
310	   is possible in all these cases.  Furthermore, a typical instantiation
311	   of the ECDH protocol, such as ECDH specified in [NIST-SP800-56A],
312	   makes any ECC key used in a DH key key agreement automatically
313	   compliant for the purpose of this specification ( this was noted in
314	   the Section 4.2 ).  The algorithm in Section 4.2 will even work for
315	   secure devices that never reveal the private key, such as smartcards
316	   or Hardware Security Modules.  A public key that is generated
317	   according to the Section 4.2 can be used without limitations in
318	   existing protocols that use ECC points encoded in other ways, such as
319	   [SEC1], with compression or not, with the added advantage that the
320	   keys generated according to the method in Section 4.2 will allow the
321	   Section 4.1 encoding.

323	6.  IANA Considerations

325	   This document defines the low-level format that may be suitable for a
326	   wide range of applications.  However, it is responsibility of the
327	   application that adopts this format to define the IDs that will
328	   enable the ECC compact point representation in that application.

330	   A new ID may not be always necessary.  For example, an application
331	   that currently allows the [SEC1] encoding may allow the compact
332	   representation defined in this document as an extension to the [SEC1]
333	   as follows.  Consider the encoding of a compressed [FIPS-186] P-256
334	   point, for example.  The [SEC1] compressed representation of a P-256
335	   point will always occupy exactly 33 bytes.  On the other hand, the
336	   compact representation defined in this document will never exceed 32
337	   bytes (it may occupy fewer that 32 bytes when the most significant
338	   byte has happened to be zero).  This size will allow reliable
339	   discrimination between two encoding formats.

341	7.  Security Considerations

343	   The key pair generation process in Section 4.2 excludes exactly half
344	   of the points on the elliptic curve.  What is left is the subset of
345	   points suitable for compact representation.  The filtering of points
346	   is based on a public criteria that are applied to the public output
347	   of the ECC one-way function.

349	   The set of Ord points on the elliptic curve can be subdivided as
350	   follows.  First, remove the point O, which leaves Ord-1 points.  Of
351	   these points there are exactly (Ord-1)/2 points that have unique x
352	   coordinate.  This document specifies a method to form the (Ord-1)/2
353	   of points, each having a unique x coordinate.  These points are
354	   called compliant public keys in Section 4.2.

356	   For any two public keys P=(x,y) and P=(x,y') there is up to one bit
357	   of entropy in y' v.s. y and this information is public.  This bit of
358	   entropy doesn't contribute to the difficulty of the underlying hard
359	   problem of the ECC: the elliptic curve discrete logarithm problem
360	   (ECDLP).

362	   It will be shown next that breaking the ECDLP with a key generated
363	   according to Section 4.2 is not easier than breaking the ECDLP with a
364	   key obtained through a standard key generation algorithm, referred to
365	   as the KG algorithm in the Section 4.2.

367	   Let us assume that there is an algorithm A that solves the ECDLP for
368	   the KG.  The algorithm A can be transformed into the algorithm A' as
369	   follows.

371	   o  If P=(x,y) is a compliant public key, the ECDLP is solved with A
372	      for the point (x,y): the result is k, such that k*G=(x,y)

374	   o  If P=(x,y) is not a compliant public key, the ECDLP is solved with
375	      A for the point (x,p-y); assuming the output produced by A is k,
376	      the output produced by A' is set to (Ord-k).  Note that (Ord-k)*G
377	      = (x,y), which means that the output of A' is the correct
378	      solution.

380	   A' is equivalent to A. The complexity of one additional substraction
381	   in the prime field is negligible even to the complexity of a single
382	   elliptic curve addition.  Observe that A' works for all public keys
383	   by performing the actual work only on compliant public keys.

385	   If we now consider only the compliant public keys, which cuts the
386	   number of points in half, we observe that the ECDLP solving algorithm
387	   A' doesn't get to break fewer public keys.  This concludes the proof.

389	   The same result can be observed based on the details of the current
390	   state of the art attacks on the ECDLP.  These attacks use Pollard's
391	   rho algorithm, which uses the collision search in the sequence(s) of
392	   generated points with the goal to produce the points P1=(x1,y1) and
393	   P2=(x2,y2), such that x1=x2 and y1=y2.  The match in the x coordinate
394	   is the sufficient event for the successful attack.  After this event
395	   has ocurred, the sequence(s) that led to x1=x2 collision can be
396	   adjusted in a constant number of steps to ensure that y1=y2, if this
397	   is not already the case.  Furthermore, collision search requires the
398	   storage of candidates for the collision.  It's wasteful to store
399	   (x,y) v.s. storing x and only calculating y when the collision in x
400	   is detected.  Thus, the ECDLP attack does not benefit from the
401	   unpredictability of the y.

403	   Finally, note that a common design feature of an ECDH-based system is
404	   not to depend on the y coordinate, such as the one defined in the
405	   [NIST-SP800-56A].  Thus, the security of the system is unaffected if
406	   we fix either of the two possibilities for the point with the given x
407	   coordinate.

409	8.  References

411	8.1.  Normative References

413	   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
414	              Requirement Levels", BCP 14, RFC 2119, March 1997.

416	8.2.  Informative References

418	   [FIPS-186]
419	              National Institute of Standards and Technology, "Digital
420	              Signature Standard (DSS)", FIPS 186-3, June 2009,
421	              <http://csrc.nist.gov/publications/PubsSPs.html>.

423	   [Lehmer]   Lehmer, D., "Computer technology applied to the theory of
424	              numbers", 1969.

426	   [Miller]   Miller, V., "Use of elliptic curves in cryptography",
427	              Proceedings Lecture notes in computer sciences; 218 on
428	              Advances in cryptology -- CRYPTO 85, June 1986.

430	   [NIST-SP800-133]
431	              National Institute of Standards and Technology,
432	              "Recommendation for Cryptographic Key Generation", SP 800-
433	              133, November 2012,
434	              <http://csrc.nist.gov/publications/PubsSPs.html>.

436	   [NIST-SP800-56A]
437	              National Institute of Standards and Technology,
438	              "Recommendation for Pair-Wise Key Establishment Schemes
439	              Using Discrete Logarithm Cryptography", SP 800-56A
440	              Revision 1, March 2007,
441	              <http://csrc.nist.gov/publications/PubsSPs.html>.

443	   [RFC5639]  Lochter, M. and J. Merkle, "Elliptic Curve Cryptography
444	              (ECC) Brainpool Standard Curves and Curve Generation",
445	              RFC 5639, March 2010.

447	   [RFC6090]  McGrew, D., Igoe, K., and M. Salter, "Fundamental Elliptic
448	              Curve Cryptography Algorithms", RFC 6090, February 2011.

450	   [SEC1]     STANDARDS FOR EFFICIENT CRYPTOGRAPHY, "SEC 1: Elliptic
451	              Curve Cryptography", September 2000, <www.secg.org/
452	              collateral/sec1_final.pdf>.

454	   [SuiteB]   National Security Agency, "NSA Suite B Cryptography",
455	              March 2010,
456	              <http://www.nsa.gov/ia/programs/suiteb_cryptography/>.

458	   [openssl]  Jivsov, A., "An enhancement to EC key generation to enable
459	              compact point representation", June 2013,
460	              <http://rt.openssl.org/Ticket/History.html?id=3069>.

462	Appendix A.  Sample code change to add compliant key generation to
463	             libgcrypt and openssl

465	   The complete changes that were needed to make libgcrypt library
466	   generate a compliant key are shown inline in this section, followed
467	   by pending changes to OpenSSL.

469	A.1.  libgcrypt changes

471	   In the following changes, the Q is the initial public key, G
472	   generator, and d is the corresponding private key. "-" prefix marks
473	   the two lines that were replaced with the lines starting with "+".
474	   Lines starting with "+" represent the code that adds compliant key
475	   generation to libgcrypt.

477	   @@ generate_key (ECC_secret_key *sk,
478	        unsigned int nbits,
479	        const char *name,
480	      point_set (&sk->E.G, &E.G);
481	      sk->E.n = mpi_copy (E.n);
482	      point_init (&sk->Q);
483	   -  point_set (&sk->Q, &Q);
484	   -  sk->d    = mpi_copy (d);
485	   +
486	   +  /* We want the Q=(x,y) be a "compliant key" in terms of the
487	   +   * http://tools.ietf.org/html/draft-jivsov-ecc-compact,
488	   +   * which simply means that we choose either Q=(x,y) or -Q=(x,p-y)
489	   +   * such that we end up with the min(y,p-y) as the y coordinate.
490	   +   * Such a public key allows the most efficient compression: y can
491	   +   * simply be dropped because we know that it's a minimum of
492	   +   * the two possibilities without any loss of security.
493	   +   */
494	   +  {
495	   +    gcry_mpi_t x, p_y, y;
496	   +    const unsigned int nbits = mpi_get_nbits (E.p);
497	   +
498	   +    x = mpi_new (nbits);
499	   +    p_y = mpi_new (nbits);
500	   +    y = mpi_new (nbits);
501	   +
502	   +    if (_gcry_mpi_ec_get_affine (x, y, &Q, ctx))
503	   +      log_fatal ("ecgen: Failed to get affine coordinates for Q\n");
504	   +
505	   +    mpi_sub( p_y, E.p, y );  /* p_y = p-y */
506	   +
507	   +    if( mpi_cmp( p_y /*p-y*/, y ) < 0 )  {  /* is p-y < p ? */
508	   +      gcry_mpi_t z = mpi_copy( mpi_const (MPI_C_ONE) );
509	   +      /* we need to end up with -Q; this assures that new Q's y
510	   +       * is the smallest one */
511	   +      sk->d = mpi_new (nbits);
512	   +      mpi_sub( sk->d, E.n, d );  /* d = order-d */
513	   +      /* log_mpidump ("ecgen d after ", sk->d); */
514	   +      gcry_mpi_point_set (&sk->Q, x, p_y/*p-y*/, z);  /* Q = -Q */
515	   +      if (DBG_CIPHER)
516	   +      {
517	   +        log_debug   ("ecgen converted Q to a compliant point\n");
518	   +      }
519	   +      mpi_free (z);
520	   +    }
521	   +    else
522	   +    {
523	   +      /* no change is needed exactly 50% of the time: just copy */
524	   +      sk->d = mpi_copy (d);
525	   +      point_set (&sk->Q, &Q);
526	   +      if (DBG_CIPHER)
527	   +      {
528	   +        log_debug   ("ecgen didn't need to convert Q to "
529	   +                     "a compliant point\n");
530	   +      }
531	   +    }
532	   +    mpi_free (x);
533	   +    mpi_free (p_y);
534	   +    mpi_free (y);
535	   +  }

537	A.2.  OpenSSL changes

539	   OpenSSL changes are even more compact than in Appendix A.1.  They are
540	   tracked at [openssl].

542	Author's Address

544	   Andrey Jivsov
545	   Symantec Corporation

547	   Email: openpgp@brainhub.org