idnits 2.17.1 

draft-jivsov-ecc-compact-01.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 (May 31, 2013) is 3983 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                              May 31, 2013
5	Expires: December 2, 2013

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

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 2, 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 . . . . . . . . . . . . . . . 11
67	   Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 12

69	1.  Introduction

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

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

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

88	2.  Conventions used in this document

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

94	3.  Overview of the compact representation in IETF protocols

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

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

106	                         SEC1 point representation

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

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

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

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

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

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

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

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

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

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

141	4.  The definition of the compact representation

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

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

150	      Q = k*G, where

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

155	      k - the private key (a scalar)

157	      G - the elliptic curve generator point

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

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

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

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

175	4.1.  Encoding and decoding of an elliptic curve point

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

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

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

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

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

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

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

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

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

205	4.2.  The algorithms to generate a key pair

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

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

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

231	4.2.1.  The black box key generation algorithm

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

236	   Black box generation:

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

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

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

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

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

252	4.2.2.  The deterministic key generation algorithm

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

257	   Deterministic generation:

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

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

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

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

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

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

273	      Given the compact representation of Q as x,

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

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

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

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

283	   See [Lehmer] for details.

285	5.  Interoperability considerations

287	   The compact representation described in this document allows two-
288	   phase introduction.

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

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

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

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

320	6.  IANA Considerations

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

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

338	7.  Security Considerations

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

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

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

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

364	   Let us assume that there is an algorithm A that solves the ECDLP for
365	   the KG.  The algorithm A can be transformed into the algorithm A' as
366	   follows.

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

371	   o  If P=(x,y) is not a compliant public key, the ECDLP is solved with
372	      A for the point (x,p-y); assuming the result produced by A is k,
373	      the result produced by A' is set to (Ord-k).  Note that (Ord-k)*G
374	      = (x,p).

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

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

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

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

405	8.  References

407	8.1.  Normative References

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

412	8.2.  Informative References

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

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

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

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

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

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

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

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

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

454	Appendix A.  Sample code change to add compliant key generation to
455	             libgcrypt

457	   This section shows complete changes that were needed to make
458	   libgcrypt library generate a compliant key.  Note that Q is the
459	   initial public key, G generator, and d is the corresponding private
460	   key. "-" prefix marks the two lines that were replaced with the lines
461	   starting with "+".  Lines starting with "+" represent the code that
462	   adds compliant key generation to libgcrypt.

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

524	Author's Address

526	   Andrey Jivsov
527	   Symantec Corporation

529	   Email: openpgp@brainhub.org