Re: [Cfrg] normative references

[Paul Lambert <[e-mail]>]

On 1/15/14, 4:54 AM, "David McGrew" <[e-mail]> wrote:

>On 01/15/2014 03:25 AM, Yaron Sheffer wrote:
>> Hi David,
>>
>> Somewhere down the Safe Curves thread you mention that you expect a
>> CFRG draft to contain "stable normative references" to definitions of
>> crypto mechanisms. I share this wish in part, in particular I would
>> appreciate "stable" references (e.g., to academic papers). However
>> many/most crypto publications are not aimed at implementors. Often
>> they are not well-specified enough to implement. And we don't want to
>> wait a few years for NIST to create normative versions. So I would
>> actually expect the new CFRG document to become the "normative"
>> reference.
>
>This is a good point, Yaron.
Yes!!!

I¹ve just been through the web sites and many/most references and find it
extremely frustrating to find any clear and consistent implementation
details.

Example issues include:
 - changes in notation and terminology
   E.g. For Edwards point addition , is it:
        y3 = (y1*y2   +    x1*x2) * inv(1-d*x1*x2*y1*y2)
      or is it:
        y3 = (y1*y2   -    x1*x2) * inv(1-d*x1*x2*y1*y2)
   Š It depends on the way the curve class is named, it¹s actually
        y3 = (y1*y2  +  a*x1*x2) * inv(1-d*x1*x2*y1*y2)
        and usually a=1

 - unclear guidelines on important security topics
    E.g. 
      ed25519 has restrictions on the secret key structure for ECDH
      Does this extend to other curves?
     
 - references describe the poofs, but hand wave the actual way
   you would send and receive and process as data
   E.g.  Hand waving of when and if to use projective coordinates

 - Lack of clarity on edge conditions (small subgroups, special points)

 - Unclear algorithm selection guidelines
   E.g. Scalar multiplication and point addition
     - fastest algorithms no longer have all the Œsafe¹ properties

 - unclear implications of use of the cofactor (since it is not =1)

 - no guidelines on use of different EC algorithms with the curve types
   E.g.  ECDSA with Montgomery curve using just x-coordinate math ???
    Do we use cofactor DH since  cofactor >1?

 - Terms in the references are used in papers in an inconsistent manner
   With respect to an implementation
   E.g. ³Twist²

 - math is represented inconsistently and imprecisely for an implementation
    E.g.  + versus * for   ECDH
          ^  versus **  on curve equationss
          Œmod¹  imply all math is in field versus as an operation at a
specific operation

 - no test vectors or example calculations readily available
      
It appears that much of the interest and ability to use some of these
curves comes from their availability in a few specific C libraries.  These
might be used as a reference, but are curve specific and it¹s unclear how
to extract generic guidelines for more than the implemented curve.

There is a significant body of work on implementing Weierstrass curves
(ANSI, IEEE, NIST, NSA, etc.).  Edwards, Twisted Edwards and Montgomery
need the same level of documentation to progress.

So Š. lot¹s of issues, but they could be solved by a clear specification.

Initial Recommendations:
 1) Always use the most general form of any of the representations
     Replace any algorithms for Edwards with Twisted Edwards (more general)
     E.g.  Curve as:
          (a*y**2+x**2) % p == (1 + d*x**2*y**2) % p
           and 
            y3 = (y1**2  +  a*x1**2) * inv(1-d*x1*x2*y1*y2)

     One question here Š I also see alternate form with Œc'
            (y**2+x**2) % p == c*(1 + d*x**2*y**2) % p

                or
            (y**2+x**2) % p == c**4*(1 + d*x**2*y**2) % p

         Not sure if any advantages versus Œa¹ or both Œa¹ and Œc'
            (a*y**2+x**2) % p == c*(1 + d*x**2*y**2) % p
     
  2) reuse where possible terminology and variables from Weierstrass ECC
     E.g.  P for prime defining Fp,  n for order, h for cofactor
         This would allow all classes of curves to viewed equally in
         an implementation catalog
          E.g.

        curveId = 'curve25519'
        strength = 127
        oid = None
        p  = 2**255-19
        a  = 486662
        xG = 9
        yG = 
147816194475895447910205935684099868872646061346164752889648818377555862374
01
        n  = 2**252 + 27742317777372353535851937790883648493
        h  = 8
    Also Š long numbers should be consistently represented hex versus
decimal
    Note also - Weierstrass Œa¹ is not the same as Edwards Œa¹, but
    can be written around Š and we should keep Edwards equations consistent
    where possible with literature


  3) Use math representation in RFCs that maps directly to a computer
     language notation - Python would be a good choice for
     readability.  
     E.g. Twisted Edwards point addition definition

       x3 = ((x1*y2+x2*y1) * inv(1+d*x1*x2*y1*y2)) % p
       y3 = ((y1*y2-a*x1*x2) * inv(1-d*x1*x2*y1*y2)) % p

   4) curve names need consolidation and should clearly indicate curve type




Paul



>
>David
>
>>
>> Thanks,
>>     Yaron
>>
>> _______________________________________________
>> Cfrg mailing list
>> [e-mail]
>> http://www.irtf.org/mailman/listinfo/cfrg
>>
>
>_______________________________________________
>Cfrg mailing list
>[e-mail]
>http://www.irtf.org/mailman/listinfo/cfrg