Subject: Re: [Cfrg] normative references

From: Yaron Sheffer <[email-masked]>
Date: Wed, 15 Jan 2014 10:25:16 +0200

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.

Thanks,
	Yaron

---

From: David McGrew <[email-masked]>
Date: Wed, 15 Jan 2014 07:54:06 -0500

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.

David

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

---

From: Paul Lambert <[email-masked]>
Date: Wed, 15 Jan 2014 10:02:01 -0800

>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

---

From: Watson Ladd <[email-masked]>
Date: Wed, 15 Jan 2014 12:05:20 -0800

> extremely frustrating to find any clear and consistent implementation

(sidenote: I got mojobake in this email. Check your encodings are set
correctly. And please, can we ban rich text from this list?)

I think it is important to remember that normative references specify
what, not how. How would be informative,
as it doesn't affect compliance.

>    E.g.  Hand waving of when and if to use projective coordinates

Affine of course: the same is true for Weierstrass form. One uses
projective form for intermediate calculations.
I'll make this clear in the draft if it isn't already. The security
issues cofactors present I will be sure to discuss: I thought
they were well known because over F_p^{\times} you always have a cofactor.

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

This is important and I will definitely try to address it.

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

I'll explain the group structure and the necessary changes to DH.
For algorithms, you can get away with the fast ones
if you are careful to show that the problems won't matter. For
instance if I have a point that
isn't of small order, I can multiply using the 2008 algorithms if I
take care never to add two points that
might be the same in my multiplication algorithm.

The safe method is still pretty fast. If you use an unsafe method,
it's your responsibility to check that it
will work, and not mine.

>     Do we use cofactor DH since  cofactor >1?

I'm not sure what you mean by cofactor DH, but yes, the implication of
the cofactor is you need to represent your
private keys as coercive, forcing points into the large subgroup, or
you leak a few bits. (Basically the same from a security standpoint).

>    With respect to an implementation

I'm going to avoid discussing math on the quadratic or cubic twist of
a curve, because it isn't necessary for implementions.
Just plug in the formulas and the algorithms, and it will all work.

>           Œmod¹  imply all math is in field versus as an operation at a

The notation issue won't get fixed anytime soon. I'll be consistent in
the draft, but that means
being inconsistent with half of everyone else. The operations issue is
the sort of thing where a little bit
of reading comprehension goes a long way: spelling out what exactly +
means at any given time is annoying,
especially when it is always obvious.

>  - no test vectors or example calculations readily available

This cannot be said about Curve25519: "Cryptography in NaCL" contains a Python
test program together with an example DH exchange, but in little-endian.

For the other curves I agree this is an issue. I'll do a black-box
interop test with you and other
interested people before we publish.

> need the same level of documentation to progress.

Or the same level of C library support. I'd much rather have everyone copy a
well-made library then write their own bugs we have to deal with down
the line/that
the SIGINT people exploit. But yes, better documentation about how to
implement is necessary.

>             (a*y**2+x**2) % p == c*(1 + d*x**2*y**2) % p

If we aren't specifying any twisted Edwards curves, why would we
define the formulas?
I suppose for use with Montgomery form, ala Ransom's suggestion.

>          an implementation catalog

Strength is the base 2 log of the operations to break, right?
Also, different things should be written differently.

>     Also Š long numbers should be consistently represented hex versus

Why hex? Most math papers use decimal, and more importantly GP/PARI
doesn't accept hex.
MAGMA, PARI and Sage are going to be used for test vector validation.

>     where possible with literature.

When we define DH exchange on a group yes. With setting the parameters
like you did we're tempting
fate.

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

The math notation I am using maps directly to that of most CAS
systems. Anyway, at some point I will be done with
the major revision, and kick it around for comments.

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

Blame Tanja. I really do not like the idea of changing existing names
especially when referring people to papers with them. SEC/NIST has
already caused enough confusing as it is.

---

From: Adam Back <[email-masked]>
Date: Wed, 15 Jan 2014 21:06:26 +0100

>      Does this extend to other curves?

Actually on this narrow topic re Ed25519 curve for EdDSA uses, I noticed
this also.  I think bit 254 being 1 could be optional so (Curve25519 has the
same private key restrictions for ECDH) so long as constant time montgomery
addition starts from bit 254 regardless.  And the remaining hard code is the
lowest 3 bits 000 but that which I presume is precomputed multiplication by
the cofactor, as seen in the verification relation 8sG=8R+8H(R,Q,m)Q. 
(Using ECDSA labelling G is base, Q=dG pub key).

The paper seems quite unclear and hard to pick apart and maybe the algorithm
just a little too much speed hacked.  The above seems to break
composability.  Ie derived public keys (Q_i = Q+M(c,i)G) where c is a
shared-secret, i is a counter; bitcoin uses this for backup and offline
security reasons.  Similar examples abound: threshold signatures, blind
signatures; one of the exciting thing to me about seeing EdDSA adopted is
that it is a Schnorr variant, and Schnorr has much simpler multiparty,
threshold and even blinding.  ECDSA has no blinding and DSA blinding is a
monstrosity involving Damgard-Jurik's generalized variant of Paillier as a
substep!  But some of these things are lost or complicated by the unusual
private key restrictions, which I think if I'm not mistaken are just related
to tiny optimizations or otherise redundant defenses against variable time
execution which can be otherwise restated.

These kind of questions might or might not be in scope for the draft,
depending on your point of view.  (But anyway if anyone feels like
expounding on the above, on list or offlist, I would quite practically
interested :)

Adam

---

From: Paul Lambert <[email-masked]>
Date: Wed, 15 Jan 2014 12:50:57 -0800

⨳|-----Original Message-----
 ⨳|From: Watson Ladd [mailto:[email-masked]]
 ⨳|Sent: Wednesday, January 15, 2014 12:05 PM
 ⨳|To: Paul Lambert
 ⨳|Cc: David McGrew; Yaron Sheffer; [email-masked]
 ⨳|Subject: Re: [Cfrg] normative references
 ⨳|
 ⨳|On Jan 15, 2014 10:02 AM, "Paul Lambert" <[email-masked]> wrote:
 ⨳|>
 ⨳|>
 ⨳|>
 ⨳|> On 1/15/14, 4:54 AM, "David McGrew" <[email-masked]> 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.
 ⨳|
 ⨳|(sidenote: I got mojobake in this email. Check your encodings are set
 ⨳|correctly. And please, can we ban rich text from this list?)
 ⨳|
 ⨳|I think it is important to remember that normative references specify
 ⨳|what, not how. How would be informative, as it doesn't affect
 ⨳|compliance.
 ⨳|
 ⨳|>
 ⨳|> 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
 ⨳|
 ⨳|Affine of course: the same is true for Weierstrass form. One uses
 ⨳|projective form for intermediate calculations.
 ⨳|I'll make this clear in the draft if it isn't already. The security
 ⨳|issues cofactors present I will be sure to discuss: I thought they
 ⨳|were well known because over F_p^{\times} you always have a cofactor.
 ⨳|
 ⨳|>
 ⨳|>  - Lack of clarity on edge conditions (small subgroups, special
 ⨳|> points)
 ⨳|
 ⨳|This is important and I will definitely try to address it.
 ⨳|
 ⨳|>
 ⨳|>  - 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)
 ⨳|
 ⨳|I'll explain the group structure and the necessary changes to DH.
 ⨳|For algorithms, you can get away with the fast ones if you are careful
 ⨳|to show that the problems won't matter. For instance if I have a point
 ⨳|that isn't of small order, I can multiply using the 2008 algorithms if
 ⨳|I take care never to add two points that might be the same in my
 ⨳|multiplication algorithm.
 ⨳|
 ⨳|The safe method is still pretty fast. If you use an unsafe method,
 ⨳|it's your responsibility to check that it will work, and not mine.
 ⨳|
 ⨳|>
 ⨳|>  - 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?
 ⨳|
 ⨳|I'm not sure what you mean by cofactor DH, but yes, the implication of
 ⨳|the cofactor is you need to represent your private keys as coercive,
 ⨳|forcing points into the large subgroup, or you leak a few bits.
 ⨳|(Basically the same from a security standpoint).	
NIST defined ...   

[ ⨳] 
 ⨳|
 ⨳|>
 ⨳|>  - Terms in the references are used in papers in an inconsistent
 ⨳|manner
 ⨳|>    With respect to an implementation
 ⨳|>    E.g. ³Twist²
 ⨳|
 ⨳|I'm going to avoid discussing math on the quadratic or cubic twist of
 ⨳|a curve, because it isn't necessary for implementions.
 ⨳|Just plug in the formulas and the algorithms, and it will all work.
 ⨳|
 ⨳|>
 ⨳|>  - 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
 ⨳|
 ⨳|The notation issue won't get fixed anytime soon. I'll be consistent in
 ⨳|the draft, but that means being inconsistent with half of everyone
 ⨳|else. The operations issue is the sort of thing where a little bit of
 ⨳|reading comprehension goes a long way: spelling out what exactly +
 ⨳|means at any given time is annoying, especially when it is always
 ⨳|obvious.	
On plus ... no need to define every operator, I was referring to
to EC notation conventions of point addition versus multiplication
e.g.  s*G   versus G**s
I'm partial to the notation based on scalar multiplies of points for DH

 ⨳|
 ⨳|>
 ⨳|>  - no test vectors or example calculations readily available
 ⨳|
 ⨳|This cannot be said about Curve25519: "Cryptography in NaCL" contains
 ⨳|a Python test program together with an example DH exchange, but in
 ⨳|little-endian.	
Badly represented. Vectors could be extracted from the C code examples.

 ⨳|
 ⨳|For the other curves I agree this is an issue. I'll do a black-box
 ⨳|interop test with you and other interested people before we publish.
 ⨳|
 ⨳|>
 ⨳|> 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.
 ⨳|
 ⨳|Or the same level of C library support. I'd much rather have everyone
 ⨳|copy a well-made library then write their own bugs we have to deal
 ⨳|with down the line/that the SIGINT people exploit. But yes, better
 ⨳|documentation about how to implement is necessary.	
We're in the documentation business here - not code libraries. Plus we're
supposed to have multiple interoperable different implementations.

 ⨳|
 ⨳|>
 ⨳|> 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
 ⨳|
 ⨳|If we aren't specifying any twisted Edwards curves, why would we
 ⨳|define the formulas?
 ⨳|I suppose for use with Montgomery form, ala Ransom's suggestion.	
[ ⨳] 
Yes ... and why did you leave out Ed25519?  	 It's being used and should at least be discussed/reviewed/

 ⨳|
 ⨳|>
 ⨳|>   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 =
 ⨳|>
 ⨳|1478161944758954479102059356840998688726460613461647528896488183775558
 ⨳|> 62374
 ⨳|> 01
 ⨳|>         n  = 2**252 + 27742317777372353535851937790883648493
 ⨳|>         h  = 8
 ⨳|
 ⨳|Strength is the base 2 log of the operations to break, right?	
Yes
 ⨳|Also, different things should be written differently.
[ ⨳] 

On the Edwards curves with cofactors >1 I believe the strength estimate may be a little less
than simply taking the bit length of the size / 2

Advice on this small adjustment would be appreciated.

 ⨳|
 ⨳|>     Also Š long numbers should be consistently represented hex
 ⨳|versus
 ⨳|> decimal
 ⨳|
 ⨳|Why hex? Most math papers use decimal, and more importantly GP/PARI
 ⨳|doesn't accept hex.
 ⨳|MAGMA, PARI and Sage are going to be used for test vector validation.	
[ ⨳] 
By you maybe ...

Hex fits better in an RFC ...  decimal would be fine also.

 ⨳|
 ⨳|>     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.
 ⨳|
 ⨳|When we define DH exchange on a group yes. With setting the parameters
 ⨳|like you did we're tempting fate.
Not really ... just another area for clear specification, eg:

Suggested RFC text:

    The ECC definitions include three classes of curves defined over the field
    of integers modulo a prime p (Fp).  Each class of curve has an equation and
    assoicated parameters unique to the class type.  Three classes of curves
    are described:
    
      SmallWeierstrassCurveFp       y**2 = x**3 + a*x + b  mod p
      EdwardsCurveFp         x**2 + y**2 = c*(1 + d*x**2 * y**2)  mod p
      MontgomeryCurveFp             y**2 = x**3 + a*x**2 + x  mod p
       
    The defintions include for each curve type:
    
      curveId - An ASCII string used to identify the curve parameters      
      strength - an integer providing the estimated cryptographic strength
                 of the curve as a power of 2                 
      oid - a list of integers that correspond to the associated ASN.1 object
            identifier. The oid is listed as 'None' if there is no assigned oid           
      p - The prime modulus of the group (Fp). Often p is a Mersenne prime
          to facilitate more efficient modular inversion
      xG - the x-coordinate of a generator point G for the curve        
      yG - the y-coordinate of a generator point G for the curve
      n  - the order of the generator point G        
      seed - included for reference when available
      h - the cofactor of the curve
        
    Each curve type has the following unique parameters
    
      Small Wierstrass      y**2 = x**3 + a*x + b  mod p     
        a - often set to p-3 for efficiency        
        b - elected for the security properties of the curve shape
        z - used by 'twisted' Brainpool curves for isogenous transform
            of untwisted curve to a curve with a = p-3
        
      Montgomery            y**2 = x**3 + c*x**2 + x  mod p     
        a - selected for the security properties of the curve shape
              
      Edwards               x**2 + y**2 = c*(1 + d*x**2 * y**2) mod p    
        c - typically set to 1 so the equation is reduced to:
                            x**2 + y**2 = 1 + d*x**2 * y**2  mod p               
        d - selected for the security properties of the curve shape  

Hummm .. could add Twisted Edwards to the above 

 ⨳|
 ⨳|>
 ⨳|>
 ⨳|>   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
 ⨳|
 ⨳|The math notation I am using maps directly to that of most CAS
[ ⨳] 
No - for example:
" On Montgomery curves, curves of the form y^2=x^3+Ax^2+x, the typical"
is Ax a variable 'Ax' or A*x ... this is sloppy non-parseable notation
 ⨳|systems. Anyway, at some point I will be done with the major revision,
 ⨳|and kick it around for comments.
[ ⨳] 
CAS???
I prefer running code useable for a protocol implementation.

Paul

 ⨳|
 ⨳|>
 ⨳|>    4) curve names need consolidation and should clearly indicate
 ⨳|curve
 ⨳|> type
 ⨳|
 ⨳|Blame Tanja. I really do not like the idea of changing existing names
 ⨳|especially when referring people to papers with them. SEC/NIST has
 ⨳|already caused enough confusing as it is.
[ ⨳] 
No need to blame, just make the change but  include reference to original author and curve name.	
NIST did not add confusion ... just branded the results.
CFRG branding would be valuable.  More curves will happen and  a consistent notation is a good thing.

Paul

 ⨳|
 ⨳|>
 ⨳|>
 ⨳|>
 ⨳|>
 ⨳|> Paul
 ⨳|>
 ⨳|>
 ⨳|>
 ⨳|> >
 ⨳|> >David
 ⨳|> >
 ⨳|> >>
 ⨳|> >> Thanks,
 ⨳|> >>     Yaron
 ⨳|> >>
 ⨳|> >> _______________________________________________
 ⨳|> >> Cfrg mailing list
 ⨳|> >> [email-masked]
 ⨳|> >> http://www.irtf.org/mailman/listinfo/cfrg
 ⨳|> >>
 ⨳|> >
 ⨳|> >_______________________________________________
 ⨳|> >Cfrg mailing list
 ⨳|> >[email-masked]
 ⨳|> >http://www.irtf.org/mailman/listinfo/cfrg
 ⨳|>
 ⨳|> _______________________________________________
 ⨳|> Cfrg mailing list
 ⨳|> [email-masked]
 ⨳|> http://www.irtf.org/mailman/listinfo/cfrg

---

From: David McGrew <[email-masked]>
Date: Wed, 15 Jan 2014 16:01:26 -0500

On 01/15/2014 03:06 PM, Adam Back wrote:
> just a little too much speed hacked. 

That's my impression too.

I think that one of the goals of this work is to follow US patent 
4,995,082 (Schnorr's signature scheme, which includes elliptic curve 
groups in its claims and which is expired).   In that case, it would 
make a lot of sense for a standard based on this work to cite that 
patent explicitly, and follow it closely.   Hopefully the good "speed 
hacks" are consistent with this approach, but I am not yet sure.

David

> The above seems to break
> .

---

From: Watson Ladd <[email-masked]>
Date: Wed, 15 Jan 2014 13:30:52 -0800

> I'm partial to the notation based on scalar multiplies of points for DH

Of course I'm going to use additive notation for an abelian group! The
multiplicative
notation is a legacy from F_{p}^{\times} crypto where it really was
multiplication.

> supposed to have multiple interoperable different implementations.

Do you really think everyone implementing P256 does it themselves? Or do they
take example code from the Internet?

> Yes ... and why did you leave out Ed25519?       It's being used and should at least be discussed/reviewed/

It's the same as Curve25519, and not in safecurves. Let's be real
clear: isogenies don't change anything substantial.
If you want to discuss it separately, go ahead: plenty of people have
been discussing alternatives on this list already.

I'm also going to explain the Montgomery ladder and double-and-add on
Edwards and that's it. RFC 6090 doesn't talk about
radix-k either, nor does it explain Shamir's trick, or fun with the
Brier-Joyce ladder, or w-NAF, etc.
>  ⨳|>         curveId = 'curve25519'

I still don't see why this form is much better than a paragraph
listing these things.

> Advice on this small adjustment would be appreciated.

Size of the group generated by g, not the size of the curve.

> Hex fits better in an RFC ...  decimal would be fine also.

Six of one, half-dozen of the other.

> Hummm .. could add Twisted Edwards to the above

But none of the curves in safecurves are presented in twisted Edwards form,
I'm not going to rehash short Weierstrass here, (RFC 6090 already exists).

Anyway, I think this conversation would be far more productive when I
finish the revisions and put it before
the group again. You can follow on github in between.

> I prefer running code useable for a protocol implementation.

So I can just copy the relevant parts of tweetnacl.c and be done with it?

> CFRG branding would be valuable.  More curves will happen and  a consistent notation is a good thing.

What do you propose for the name scheme? E,M with prime in the expc
format is my best proposal, but this might not be unique all the time.

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: Paul Hoffman <[email-masked]>
Date: Wed, 15 Jan 2014 13:51:05 -0800

In general: RFCs are used by different people for wildly different reasons. If you make a statement in an RFC that could use some deeper explanation and you leave that explanation out, you can rest assured that someone will implement (or try to correct a working implementation) and not understand what you left out. We have 40 years of experience with this problem.

It is fine for you to create an RFC that just lists curves and does not show how to implement them interoperably. However, if you do, you need to say that is what you are doing right up front *and* resist the temptation to help on implementation at all. Also, you then need to deal with the fact that there will be five other RFCs afterwards that will show how to implement for TLS / IPsec / S/MIME / PGP ..., and they may or may not all line up. Again, there are plenty of people here with tooth marks on our asses from this.

And: this is a volunteer effort on everyone's part. We all want everything so that we don't have to deal with the inevitable problems later. But none of us did this before you, even though the data has been there. So: thank you and we have more requests. :-) :-(

> take example code from the Internet?

"Or" is unfortunately the wrong conjunction. Plenty of people take sample code from the Internet *and* then tweak it because they think they're smart. If you don't warn about things that they can do wrong but still be interoperable, someone is likely to do it. A fair amount of practical cryptography is hand-holding (and trying to move the most dangerous choices further out of reach...).

> Six of one, half-dozen of the other.

You would think, until you see a "10" and don't get that is in hex. If you use hex anywhere (and you will), you should try to use it everywhere except for one-digit values less than 0xa.

> format is my best proposal, but this might not be unique all the time.

With respect to naming: given enough elapsed time, your name system will *always* fail. Pick something that fill all of your needs now and has a hopefully-reasonable extension mechanism and hope for the best.

--Paul Hoffman

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Wed, 15 Jan 2014 23:09:02 +0100

> take example code from the Internet?
It seems to me that the whole goals of standards is to allow multiple
interoperable implementations, as Paul says. (Besides, they often give much more
information than existing code if you want to modify/extend anything, make
different trade-offs, etc.)

> clear: isogenies don't change anything substantial.

Of course they don't change anything to the DLOG security. But they change
everything on actual computations and representations.

My opinion is you should explain how to compute the isogeny or (inclusive)
include Ed25519 as a "different" curve and explain which formulas to use with
it. I honestly don't know which is the more helpful.

> Brier-Joyce ladder, or w-NAF, etc.

I fully agree that the document should only discuss the most "basic" (and safe)
algorithms for computing the necessary operations. However, if other algorithms
are know that have (potential) security issues (like, not being constant-time,
having special cases) it would be great if the document could point out these
dangers.

> I still don't see why this form is much better than a paragraph
Much easier to access each piece of information. Almost like an array compared
to a linked list (at least in my opinion).

> Six of one, half-dozen of the other.
I'm not sure I understand you comment. Anyway, in my experience, I feel like
I've seen much more (large) constants in hex than in decimal in RFCs.

On the very down-to-earth practical side, hex is more compact, so it means less
line breaks, so easier copy-pasting (yeah, I know, gory details).

Manuel.

---

From: "Dan Harkins" <[email-masked]>
Date: Wed, 15 Jan 2014 14:15:01 -0800 (PST)

> take example code from the Internet?

  The number of libraries is not equal to the number of people that use
them (i.e. no, "everyone" is not implementing it themselves) but the number
of libraries is also much greater than 1 (i.e. everyone is not using the
same "well-made" library).

  You're writing a document that must be implemented by _multiple_
people _independently_. If there was just going to be one implementation
that everyone used there would be no need for the document you're
writing-- the code would be the document.

> Six of one, half-dozen of the other.

  Let me express a strong preference for hex. It's more natural when
dealing with bit strings.

  Dan.

---

From: Paul Lambert <[email-masked]>
Date: Wed, 15 Jan 2014 15:05:58 -0800

Watson,

>take example code from the Internet?
I have seen a large number of P256 implementations … few if any from the
public domain.

Existence of an open source library is not an excuse for a sloppy RFC.  If
this is the direction you are going, we would just need to write a
one-line pointer to the source code.

Real products implement in hardware, on multiple processor types … etc.

I’ve been trying to be helpful, but your arguments against well intended
suggestions is frustrating.   It’s difficult to contribute if you’re
arguing for a sloppy RFC because the code is the reference.

I was pointing to specific examples that we could emulate in a perhaps
more simple manner.  The next step would be get a summary of the relevant
details required and emulate one or more of these documents.

>clear: isogenies don't change anything substantial.
Substantial???
Curve22519 is not interoperable with Ed25519. What could be more
substantial.  A point on one curve would have a different x and y value
than a curve on the other.
This is one of my core issues with having mathematicians write protocols …
the apparent mathematical precision make the implementations very fuzzy.

>been discussing alternatives on this list already.
Discuss …  no, let me be clear and rephrase.  Please add Ed25519 to the
RFC.

>>...

...
>Size of the group generated by g, not the size of the curve.
Oh … of course, thanks.

>I'm not going to rehash short Weierstrass here, (RFC 6090 already exists).

Ok … but introducing Weierstrass allows comparisons and clarity of
specification.
No eed to fully define Weierstrass … it’s just easier to have a complete
view
of all options.

Paul

---

From: Watson Ladd <[email-masked]>
Date: Wed, 15 Jan 2014 15:33:56 -0800

> arguing for a sloppy RFC because the code is the reference.

I'm arguing for a precise statement of what needs to be calculated,
and nothing else. That's not sloppy. And in fact I'm supplying
what has been requested in terms of implementation details, against my
preference for black-box standards. The next
version is almost done in fact.

> than a curve on the other.

If I transmit to you a Curve25519 point, you can treat it as an
Ed25519 point (after appropriate transformations) and I
will never know the difference. Again, implementations are different
from the results
they calculate.

> Discuss …  no, let me be clear and rephrase.  Please add Ed25519 to the

By Ed25519 do you mean the twisted Edwards curve, or the Edwards curve? Becuase
the Ed25519 paper uses the Edwards curve, which has a giant parameter,
and the twisted
Edwards curve is going to be a unique form in the RFC. Either way
there is a lot of revising to do, also
to the explanation of why the curves were chosen.

Do you want to basepoint that corresponds to the choice of basepoint
9, or should I pick one?

> No eed to fully define Weierstrass … it’s just easier to have a complete

Unless I include operation counts and real timings from optimized code, that
won't be a complete guide to the choice to make. Look at eBATS for performance
info.

RFC's are standards, not how to guides for the terminally lazy.