Subject: [Cfrg] Safecurves draft

From: Watson Ladd <[email-masked]>
Date: Wed, 8 Jan 2014 09:11:39 -0800

Dear all,
draft-ladd-safecurves contains the Safecurves with orders
2^255+\epsilon and higher.
I forgot to update the TOC, but that shouldn't stop the substantive
conversation.

Does anyone object to these curves being approved for IETF standard
body use/typos/general nastiness?
Sincerely,
Watson Ladd

---

From: Stephen Farrell <[email-masked]>
Date: Wed, 08 Jan 2014 17:21:53 +0000

> body use/typos/general nastiness?

No objection, but there's maybe some checking to be done
before we're ready to push the button.

One thing though is that rfc 3526 [1] is standards track
so if there's a reason for that (and there may or may not
be;-) then we might want these to be the same which'd
mean not doing 'em in cfrg. That can be figured out later
though.

S.

[1] http://tools.ietf.org/html/rfc3526

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

---

From: Watson Ladd <[email-masked]>
Date: Wed, 8 Jan 2014 09:58:17 -0800

> before we're ready to push the button.

Absolutely! Please double check I didn't make any typos, and if you have
MAGMA access, redo the verifications. This goes for everyone. The more eyeballs
on this, the less chance we make a bad mistake. safecurves.cr.yp.to comes with
a script to redo everything.

Also, if anyone knows something that DJB and Tanja Lange do not, please tell us!

> mean not doing 'em in cfrg. That can be figured out later

I have no opinions about how this gets to from draft to RFC. I
understand there are many channels, and
someone will have to pick one.

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

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Wed, 08 Jan 2014 19:40:24 +0100

> body use/typos/general nastiness?

I'm in favour of these curves being approved for IETF use.

I think the draft itself, however, should be expanded to go into some details
about the advantages of the curves and the differences with existing curves.

I have one question about the curves themselves: why are there two Montgomery
curves over GF(2^383-187)? I thought the curves were chosen by a deterministic
process, and the smallest 'a' coefficient giving the desired properties was
always used.

Also, is it on purpose that you didn't include E-521 in your draft?

Manuel.

---

From: Watson Ladd <[email-masked]>
Date: Wed, 8 Jan 2014 11:07:24 -0800

> process, and the smallest 'a' coefficient giving the desired properties was

It's because one has an Elligator map and the other does not. Some
applications require
it, but not all.

> Also, is it on purpose that you didn't include E-521 in your draft?

I simply copied the safecurves.cr.yp.to list starting at Curve25519.
There is no E-521 on that list.

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Wed, 08 Jan 2014 20:26:49 +0100

> It's because one has an Elligator map and the other does not. Some
Ok, thanks for the info.

Since their respective 'a' coefficients are of comparable sizes (18 vs 21 bits),
I expect their performances will be very comparable, so I wonder if it's worth
standardizing both of them, rather than just the one with the Elligator map.

> There is no E-521 on that list.
IMHO there should be :) See http://eprint.iacr.org/2013/647

Manuel.

---

From: "Dan Harkins" <[email-masked]>
Date: Wed, 8 Jan 2014 12:29:29 -0800 (PST)

On Wed, January 8, 2014 9:58 am, Watson Ladd wrote:
> I have no opinions about how this gets to from draft to RFC.

  Which is good because the process from draft to RFC is already
well-defined. It's on the IETF web site, check it out!

> I understand there are many channels, and

  And that someone would be you!

  While it's certainly useful to get these curves defined in an IETF
document, getting them used by any protocol will require some
more work from you. You should get OIDs defined for each of
them if they don't exist already. You should write up separate
drafts for inclusion of these curves into the protocols' various
IANA-managed repositories-- yes, sadly there are many. And
for protocols which allow for in-line passing of complete
domain parameter sets (like TLS) you'll need to modify the
data structure used (doesn't look like these could be used with
the "explicit_prime" ECCurveType, for instance).

  On the plus side, for the most part you can just follow the path
blazed by the brainpool folks, just follow what they did.

  Welcome to the tedious world of sausage making, don't mind
the blood on your hands, you get used to it.

  Dan.

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Wed, 08 Jan 2014 21:48:13 +0100

On 08/01/2014 21:29, Dan Harkins wrote:
> more work from you.

And/or from others :) For example, Simon Josefsson and I are already working on
a draft for using the Montgomery curves in TLS (for ECDHE at least).

> You should get OIDs defined for each of
Concerning TLS, it's probably not useful to allow online passing of the complete
domain parameters, since the NamedCurve way is used by (almost?)
everyone.

But yes, there is some per-protocol work to be done, obviously.

Manuel.

---

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

> -----Original Message-----
> From: Cfrg [mailto:[email-masked]] On Behalf Of Dan Harkins
...
> >> No objection, but there's maybe some checking to be done before
> we're
> >> ready to push the button.
> >
> > Absolutely! Please double check I didn't make any typos, and if you
> > have MAGMA access, redo the verifications. This goes for everyone.
> The
> > more eyeballs on this, the less chance we make a bad mistake.
> > safecurves.cr.yp.to comes with a script to redo everything.
> >
> >> One thing though is that rfc 3526 [1] is standards track so if
> >> there's a reason for that (and there may or may not
> >> be;-) then we might want these to be the same which'd mean not doing
> >> 'em in cfrg. That can be figured out later though.
> >
>   Which is good because the process from draft to RFC is already well-
> defined. It's on the IETF web site, check it out!
> 
> > I understand there are many channels, and someone will have to pick
> > one.
> 
> document, getting them used by any protocol will require some more work
> from you. You should get OIDs defined for each of them if they don't
> exist already. You should write up separate drafts for inclusion of
> these curves into the protocols' various IANA-managed repositories--
> yes, sadly there are many. And for protocols which allow for in-line
> passing of complete domain parameter sets (like TLS) you'll need to
> modify the data structure used (doesn't look like these could be used
> with the "explicit_prime" ECCurveType, for instance).
> 
You should also look at: RFC 6090
The math for Small Wierstrass curves is defined well - you need the equivalent of
6090 for Edwards curves.  Do note the authors of this excellent RFC
Include both chairs of this list.

> 
>   Welcome to the tedious world of sausage making, don't mind the blood
> on your hands, you get used to it.
> 
>   Dan.
> 
> 
>

---

From: Watson Ladd <[email-masked]>
Date: Wed, 8 Jan 2014 13:08:42 -0800

> Include both chairs of this list.

First, is this advising me on next steps, or is it an objection to the draft?
The group is [l]Jac(E(F_q)). There, done. In fact, this is in the introduction.
The equivalent to RFC 6090 is the Bernstein paper on addition on
Edwards (and twisted Edwards curves).
It's readily available. If you want to reformat it as an I-D, go right ahead.

Is it really that bad to have the EFD get cited for the formulas, or
to advise implementers
to read Handbook of Elliptic and Hyperelliptic Curve Cryptography?

---

From: Alyssa Rowan <[email-masked]>
Date: Wed, 08 Jan 2014 23:10:26 +0000

Glad to see this one get under way.

I'm strongly in favour of the meat of the proposal.

I have a couple of comments (mostly typographical and/or clarity).

Maybe we should give an estimate of security (bitwise). [SAFECURVES]
calculates that and otherwise it isn't crystal-clear from the names
which curves would be about suitable for which security level.

Any particular reason why Curve1174 wasn't included, as it's in the
same strength category as Curve25519? (See below, for roughly how it
would look if I think we did go for it?)

> I simply copied the safecurves.cr.yp.to list starting at 
> Curve25519. There is no E-521 on that list.

E-521 is in the revised reference in [2013 Aranha-Barreto-Pereira-
Ricardini] <http://eprint.iacr.org/2013/647.pdf>. It looks like djb
and Tanja Lange haven't finished putting it through all their own
checks yet; at present it's on some pages (fields, rho, transfers,
discriminants) but not others (base points, rigidity).

It looks like they're mid-way through checking it. It'll very probably
pass (identical design criteria; all its peers in the same paper did).
Put it in the draft, take it out if for some reason it doesn't?

>> why are there two Montgomery curves over GF(2^383-187)?
> It's because one has an Elligator map and the other does not.

You mean, an Elligator-1 map? (They all have Elligator-2 maps.)

[2013 Aranha-Barreto-Pereira-Ricardini] version 20131031:234129
replaces Curve383187 with an M-383 prototype with the following comment:
    "Replaced the curve over the 383-bit field by a more
     implementation-friendly curve."

A's a little higher in that exact revision, but it appears they found
a lower suitable one in November. The final M-383 is the one
SafeCurves reviewed, although the older Curve383187 also passed.

> Some applications require it, but not all.

Not sure if there's a lot of point in having two Monty curves of the
exact same field?

[Typographical notes]

The parameters for E-382 seem to be are miscopied in -00. Should be
2^382-105, and x²+y²=1-67254x²y² (not 2^382-15 and x²+y²=1-6725254x²y²).

I suggest considering taking the dashes out of the canonical names
People are going to refer to these in config files and command lines
and heaven knows where else, so avoiding punctuation may be convenient
(which I guess may be why none of the other curve names I can see used
in IETF standards have any).

For consistency, perhaps Curve1174, Curve25519, and Curve3617
could be called in the standard after the formula and prime size (as in
[2013 ABPR]), which would make them M255, E251, and E414 respectively?
I've done that below; how does it look?

I have honestly little idea about formatting of these things (other
than that the canonical version is ASCII, like this email), but the
way the basepoint and order are formatted is a little bit confusing as
it is in draft-00.

With the above in mind, how about something broadly like this?

==========================================================================

2. The Curves

   Each curve is given by an equation and a basepoint, together with an
   order. All curves are elliptic. Validation information is given at
   [SAFECURVES]. The names given in this document indicate the family:
   safecurveExxx for Edwards curves over a prime field GF(p), and
   safecurveMxxx for Montgomery curves over a prime field GF(p).

   * safecurveE251 (also known as Curve1174) [[ Do we want this one? ]]
     p: 2^251-9
     formula: x^2+y^2 = 1-1174x^2y^2
     basepoint:
        x: 1582619097725911541954547006453739763381091388846394833492
           296309729998839514
           (0x037FBB0C EA308C47 9343AEE7 C029A190
              C021D96A 492ECD65 16123F27 BCE29EDA)
        y: 3037538013604154504764115728651437646519513534305223422754
           827055689195992590
           (0x06B72F82 D47FB7CC 66568411 69840E0C
              4FE2DEE2 AF3F976B A4CCB1BF 9B46360E)
     [[ Rigidity note: This is the Edwards mapping of the Montgomery
        point x=4, y=192257776421116702304087124422055147834030127084
        09058383774613284963344096.
        <http://cr.yp.to/elligator/elligator-20130527.pdf> ]]
     Security versus rho: 2^124.3; twist: 2^124.3; combined: 2^123.3
     order: 2^249 - 11332719920821432534773113288178349711

   * safecurveM255 (also known as Curve25519)
     p: 2^255-19
     formula: y^2 = x^3+486662x^2+x
     basepoint:
        x: 9 (0x9)
        y: 1478161944758954479102059356840998688726460613461647528896
           4881837755586237401
           (0x20AE19A1 B8A086B4 E01EDD2C 7748D14C
              923D4D7E 6D7C61B2 29E9C5A2 7ECED3D9)
     Security versus rho: 2^125.8; twist: 2^126.3; combined: 2^124.3
     order: 2^252 + 27742317777372353535851937790883648493

   * safecurveE382
     p: 2^382-105
     formula: x^2+y^2 = 1-67254x^2y^2
     basepoint:
        x: 3914921414754292646847594472454013487047137431784830634731
           377862923477302047857640522480241298429278603678181725699
           (0x196F8DD0 EAB20391 E5F05BE9 6E8D20AE
              68F84003 2B0B6435 2923BAB8 53648411
              93517DBC E8105398 EBC0CC94 70F79603)
        y: 17 (0x11)
     [[ Note: <http://eprint.iacr.org/2013/647.pdf> has different
        basepoint y=13. Check: is that just a different mapping i.e.
        Monty vs Eddie, or has the basepoint changed? If so, why? ]]
     Security versus rho: 2^189.8; twist: 2^189.8; combined: 2^188.8
     order: 2^380 - 1030303207694556153926491950732314247062623204330
                    168346855

   * safecurveM383
     p: 2^383-187
     formula: y^2 = x^3+2065150x^2+x
     basepoint:
        x: 12 (0xC)
        y: 4737623401891753997660546300375902576839617167257703725630
           389791524463565757299203154901655432096558642117242906494
           (0x1EC7ED04 AAF834AF 310E304B 2DA0F328
              E7C165F0 E8988ABD 39928612 90F617AA
              1F1B2E7D 0B6E332E 969991B6 2555E77E)
     Security versus rho: 2^189.8; twist: 2^190.3; combined: 2^188.3
     order: 2^380 + 1662362759313735161052197949355421533080392344557
                    61613271

   * safecurveE414 (also known as Curve3617)
     p: 2^414-17
     formula: x^2+y^2 = 1+3617x^2y^2
     basepoint:
        x: 1731988647712118917771920249882261544355695730760434081525
           6226171904769976866975908866528699294134494857887698432266
           169206165
           (0x1A334905 14144330 0218C063 1C326E5F
              CD46369F 44C03EC7 F57FF354 98A4AB4D
              6D6BA111 301A73FA A8537C64 C4FD3812
              F3CBC595)
        y: 34 (0x22)
     Security versus rho: 2^205.3; twist: 2^205.3; combined: 2^203.8
     order: 2^411 - 3336414086375514252081017769409838517898472720041
                    1208589594759

   * safecurveM511
     p: 2^511-187
     formula: y^2 = x^3+530438x^2+x
     basepoint:
        x: 5 (0x5)
        y: 2500410645565072423368981149139213252211568685173608590070
           9792642482752286038997069505181278171765918786677842475821
           24505430745177116625808811349787373477
           (0x2FBDC0AD 8530803D 28FDBAD3 54BB488D
              32399AC1 CF8F6E01 EE3F9638 9B90C809
              422B9429 E8A43DBF 49308AC4 455940AB
              E9F1DBCA 542093A8 95E30A64 AF056FA5)
     Security versus rho: 2^253.8; twist: 2^254.3; combined: 2^252.3
     order: 2^508 + 1072475475963574762404453151406812184207075662743
                    4833028965540808827675062043

   * safecurveE521 [[ currently awaiting Safecurves approval ]]
     p: 2^521-1
     formula: x^2+y^2 = 1+376014x^2y^2
     basepoint:
        x: 2500410645565072423368981149139213252211568685173608590070
           9792642482752286038997069505181278171765918786677842475821
           24505430745177116625808811349787373477
           (0x2FBDC0AD 8530803D 28FDBAD3 54BB488D
              32399AC1 CF8F6E01 EE3F9638 9B90C809
              422B9429 E8A43DBF 49308AC4 455940AB
              E9F1DBCA 542093A8 95E30A64 AF056FA5)
        y: 6 (0x6)
     Security versus rho: 2^259.3; twist: 2^259.3; combined: 2^258.3
     order: 2^519 - 3375547632585017057891076304187826360719049612140
                    51226618635150085779108655765

==========================================================================

Thoughts?

(_Please_ cross-check the data thoroughly; I may well have made a
typographical or calculation error of my own, and of course, extra
checking is a good thing! Apologies in advance if I have; thanks for
any extra pairs of eyes.)

- -- 
/akr

---

From: Stephen Farrell <[email-masked]>
Date: Wed, 08 Jan 2014 23:17:25 +0000

In case it helps with formatting. A trick some people have
done from time to time is to include a shell script as an
appendix to a draft/RFC so that when you extract the script
and run it with the draft/RFC as input it pulls out the
examples/numbers and feeds them into a checker.

Can't think of an example right now, but someone here will
if you like the idea.

S.

On 01/08/2014 11:10 PM, Alyssa Rowan wrote:
> Maybe we should give an estimate of security (bitwise).
> [SAFECURVES] calculates that and otherwise it isn't crystal-clear
> from the names which curves would be about suitable for which
> security level.
> 
> Any particular reason why Curve1174 wasn't included, as it's in
> the same strength category as Curve25519? (See below, for roughly
> how it would look if I think we did go for it?)
> 
> Ricardini] <http://eprint.iacr.org/2013/647.pdf>. It looks like
> djb and Tanja Lange haven't finished putting it through all their
> own checks yet; at present it's on some pages (fields, rho,
> transfers, discriminants) but not others (base points, rigidity).
> 
> It looks like they're mid-way through checking it. It'll very
> probably pass (identical design criteria; all its peers in the same
> paper did). Put it in the draft, take it out if for some reason it
> doesn't?
> 
> replaces Curve383187 with an M-383 prototype with the following
> comment: "Replaced the curve over the 383-bit field by a more 
> A's a little higher in that exact revision, but it appears they
> found a lower suitable one in November. The final M-383 is the one 
> Not sure if there's a lot of point in having two Monty curves of
> the exact same field?
> 
> [Typographical notes]
> 
> The parameters for E-382 seem to be are miscopied in -00. Should
> be 2^382-105, and x²+y²=1-67254x²y² (not 2^382-15 and
> x²+y²=1-6725254x²y²).
> 
> People are going to refer to these in config files and command
> lines and heaven knows where else, so avoiding punctuation may be
> convenient (which I guess may be why none of the other curve names
> I can see used in IETF standards have any).
> 
> For consistency, perhaps Curve1174, Curve25519, and Curve3617 could
> be called in the standard after the formula and prime size (as in 
> [2013 ABPR]), which would make them M255, E251, and E414
> respectively? I've done that below; how does it look?
> 
> I have honestly little idea about formatting of these things
> (other than that the canonical version is ASCII, like this email),
> but the way the basepoint and order are formatted is a little bit
> confusing as it is in draft-00.
> 
> Each curve is given by an equation and a basepoint, together with
> an order. All curves are elliptic. Validation information is given
> at [SAFECURVES]. The names given in this document indicate the
> family: safecurveExxx for Edwards curves over a prime field GF(p),
> and safecurveMxxx for Montgomery curves over a prime field GF(p).
> 
> * safecurveE251 (also known as Curve1174) [[ Do we want this one?
> ]] p: 2^251-9 formula: x^2+y^2 = 1-1174x^2y^2 basepoint: x:
> 1582619097725911541954547006453739763381091388846394833492 
> 296309729998839514 (0x037FBB0C EA308C47 9343AEE7 C029A190 C021D96A
> 492ECD65 16123F27 BCE29EDA) y:
> 3037538013604154504764115728651437646519513534305223422754 
> 827055689195992590 (0x06B72F82 D47FB7CC 66568411 69840E0C 4FE2DEE2
> AF3F976B A4CCB1BF 9B46360E) [[ Rigidity note: This is the Edwards
> mapping of the Montgomery point x=4,
> y=192257776421116702304087124422055147834030127084 
> <http://cr.yp.to/elligator/elligator-20130527.pdf> ]] Security
> versus rho: 2^124.3; twist: 2^124.3; combined: 2^123.3 order: 2^249
> - 11332719920821432534773113288178349711
> 
> * safecurveM255 (also known as Curve25519) p: 2^255-19 formula: y^2
> = x^3+486662x^2+x basepoint: x: 9 (0x9) y:
> 1478161944758954479102059356840998688726460613461647528896 
> 4881837755586237401 (0x20AE19A1 B8A086B4 E01EDD2C 7748D14C 923D4D7E
> 6D7C61B2 29E9C5A2 7ECED3D9) Security versus rho: 2^125.8; twist:
> 2^126.3; combined: 2^124.3 order: 2^252 +
> 27742317777372353535851937790883648493
> 
> * safecurveE382 p: 2^382-105 formula: x^2+y^2 = 1-67254x^2y^2 
> basepoint: x:
> 3914921414754292646847594472454013487047137431784830634731 
> (0x196F8DD0 EAB20391 E5F05BE9 6E8D20AE 68F84003 2B0B6435 2923BAB8
> 53648411 93517DBC E8105398 EBC0CC94 70F79603) y: 17 (0x11) [[ Note:
> <http://eprint.iacr.org/2013/647.pdf> has different basepoint y=13.
> Check: is that just a different mapping i.e. Monty vs Eddie, or has
> the basepoint changed? If so, why? ]] Security versus rho: 2^189.8;
> twist: 2^189.8; combined: 2^188.8 order: 2^380 -
> 1030303207694556153926491950732314247062623204330 168346855
> 
> * safecurveM383 p: 2^383-187 formula: y^2 = x^3+2065150x^2+x 
> basepoint: x: 12 (0xC) y:
> 4737623401891753997660546300375902576839617167257703725630 
> (0x1EC7ED04 AAF834AF 310E304B 2DA0F328 E7C165F0 E8988ABD 39928612
> 90F617AA 1F1B2E7D 0B6E332E 969991B6 2555E77E) Security versus rho:
> 2^189.8; twist: 2^190.3; combined: 2^188.3 order: 2^380 +
> 1662362759313735161052197949355421533080392344557 61613271
> 
> * safecurveE414 (also known as Curve3617) p: 2^414-17 formula:
> x^2+y^2 = 1+3617x^2y^2 basepoint: x:
> 1731988647712118917771920249882261544355695730760434081525 
> 169206165 (0x1A334905 14144330 0218C063 1C326E5F CD46369F 44C03EC7
> F57FF354 98A4AB4D 6D6BA111 301A73FA A8537C64 C4FD3812 F3CBC595) y:
> 34 (0x22) Security versus rho: 2^205.3; twist: 2^205.3; combined:
> 2^203.8 order: 2^411 -
> 3336414086375514252081017769409838517898472720041 1208589594759
> 
> * safecurveM511 p: 2^511-187 formula: y^2 = x^3+530438x^2+x 
> basepoint: x: 5 (0x5) y:
> 2500410645565072423368981149139213252211568685173608590070 
> 24505430745177116625808811349787373477 (0x2FBDC0AD 8530803D
> 28FDBAD3 54BB488D 32399AC1 CF8F6E01 EE3F9638 9B90C809 422B9429
> E8A43DBF 49308AC4 455940AB E9F1DBCA 542093A8 95E30A64 AF056FA5) 
> * safecurveE521 [[ currently awaiting Safecurves approval ]] p:
> 2^521-1 formula: x^2+y^2 = 1+376014x^2y^2 basepoint: x:
> 2500410645565072423368981149139213252211568685173608590070 
> 24505430745177116625808811349787373477 (0x2FBDC0AD 8530803D
> 28FDBAD3 54BB488D 32399AC1 CF8F6E01 EE3F9638 9B90C809 422B9429
> E8A43DBF 49308AC4 455940AB E9F1DBCA 542093A8 95E30A64 AF056FA5) y:
> 6 (0x6) Security versus rho: 2^259.3; twist: 2^259.3; combined:
> 2^258.3 order: 2^519 -
> 3375547632585017057891076304187826360719049612140 
> checking is a good thing! Apologies in advance if I have; thanks
> for any extra pairs of eyes.)
> 
> _______________________________________________ Cfrg mailing list 
> [email-masked] http://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Alyssa Rowan <[email-masked]>
Date: Wed, 08 Jan 2014 23:21:18 +0000

On 08/01/2014 23:17, Stephen Farrell wrote:

> In case it helps with formatting. A trick some people have done
> from time to time is to include a shell script as an appendix to a
> draft/RFC so that when you extract the script and run it with the
> draft/RFC as input it pulls out the examples/numbers and feeds them
> into a checker.

...or (this time) we could just link to <http://safecurves.cr.yp.to/>,
as the source of these?

- -- 
/akr

---

From: Stephen Farrell <[email-masked]>
Date: Wed, 08 Jan 2014 23:23:37 +0000

On 01/08/2014 11:21 PM, Alyssa Rowan wrote:
>> from time to time is to include a shell script as an appendix to
>> a draft/RFC so that when you extract the script and run it with
>> the draft/RFC as input it pulls out the examples/numbers and
>> feeds them into a checker.
> 
> ...or (this time) we could just link to
> <http://safecurves.cr.yp.to/>, as the source of these?

Probably not - the RFC editor doesn't like recent URLs like that
for anything normative. Its fine for a draft but RFCs last a looong
time.

But my suggestion was more about ensuring that you don't get
errors when copying stuff into the draft and not about referencing.

S.

---

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

I asked Tanja about the two curves. The answer is that (A-2)/4 should
be small, but this is an efficiency problem with one of them, not
a security issue. My elligator belief was based on a misreading of a table.
I'll take out the bad one in the next version.
I'll add E521 and copy the formatting in the 01 draft, which I'll post
as soon as a few days go by the fix
Thanks for spotting the typos.

I don't want to rename curves because that induces consistency issues.
Removing dashes is a good idea.

The EFD formulas will go in appendix to address the URL problem, and
to address some people's desire for explicit formulas.
For validation I give you a point on the curve and a claimed order:
the Hasse-Weil bound plus a quick multiply does the rest. Validation
isn't normative, so I think we can refer people to safecurves.

On Wed, Jan 8, 2014 at 3:10 PM, Alyssa Rowan <[email-masked]> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA512
>
> -----BEGIN PGP SIGNATURE-----
>
> iQIcBAEBCgAGBQJSzdriAAoJEOyEjtkWi2t6WIwP/0U70JKAV3WOnbZcMB58rtSM
> Ru7loFhn9TvU3jw/p+H2tvmeUs08hKYDUUWavp7/x1B9TX3t+j3rADsWkoN/pQQd
> obr8AMdOF6QiupCjSbeZoq+wLMIiZKX3IV0pSzaO8FpTdBrIzjXTHgPy1We8H7eC
> Wkc2VC6f6eX/qyjKm6Fh3CdySJZ2dPy0X96HBqcwOMd5/hmR7VQ4DNxMEOHEfCVA
> Z2WwwYl2xNxOQ1Dn9kb4FU6CVRCc4/7DENZ+2FrCWUp1zG/3d8mUGzpGVunOv9ed
> rKKHnR9fhYjhfNSmGuTfLHTXc5mVqmEjZzmX0u1UR1CEktEKN/Nu2DMbPHToNVAA
> D7znHER4JZ8eMf3zLTslp8Uw0QkOhJiYZpDm24qb5urBLmlu55s6tYerCFEH4hDn
> R5DUPVURTgCbnpSGolKwJ2lBz8zQxzKCi9QoWV/VDNasg0L/ADIJeJUfpqdByWAz
> jFaFSVAgmf8df7X9WflV8ZCPkuoMszNZ9iGJn7AQTqUbjsMDfvqmOLfvFHD4Srzt
> tJtmDEL62O8Wml2zHN5hG/6ltfj9EZC+hl/EBSSCG1+nMqVodic5v4+E/lLU23/x
> db+l3PCsREZIURuT7o0YxukolV+93zbNlfOtd93HgB018rSeS+PBJ3yljN25h1Aa
> 5GNONjspxg93Z219jaNX
> =FUIv
> -----END PGP SIGNATURE-----

---

From: Paul Lambert <[email-masked]>
Date: Wed, 8 Jan 2014 16:30:07 -0800

> First, is this advising me on next steps, or is it an objection to the
Next steps.  I'm very supportive of the inclusion of these curves into the main stream.

> It's readily available. If you want to reformat it as an I-D, go right
Academic papers are not appropriate directly.  Clear and concise algorithm 
descriptions and guidelines are required.

> 
> Is it really that bad to have the EFD get cited for the formulas, or to
> advise implementers to read Handbook of Elliptic and Hyperelliptic
> Curve Cryptography?
Yes.  They are not standards.  They are not always precise and subject to
Interpretation and bad implementation.  
They are not complete ... Dan's point about OIDs and the like required
to actually use the curves.

Paul

---

From: Watson Ladd <[email-masked]>
Date: Wed, 8 Jan 2014 16:58:24 -0800

> descriptions and guidelines are required.

But the explicit formulas aren't actually required for intereop. I'll
put them as informational because it took me a few minutes to
write them down in the draft, and I don't mind that much.
 We don't define how TCP clients should maintain the buffer of sent
information efficiently, or how
routers should maintain the routing tables. OSPF doesn't explain how
to maintain a binomial heap.
This sort of information might belong in an RFC. But its lack doesn't
make a standard insufficient.

Anyway, this is totally immaterial: the next version, which fixes some
typos, adds E-521, and removes a badly designed
curve (secure but slow), adds in a section explaining the formulas
will hit the RFC editor some time next week: I want to collect
more comments and resolve them.

Take a good look for typos: that's what can really mess this whole thing up.

Anyway, once I get the next version up, I think we'll pretty much be
ready on this, assuming no major dealbreakers appear.

> to actually use the curves.

One of the big obstacles to the curves you mentioned was the lack of
vetting. That's gone now: you can point to it in an RFC when this gets
published. As a result when it comes to designing or revising old
standards, it won't be harder than putting any other curve now.

I'm very much against protocol design that involves lots of options: I
like these curves because they have great implementations with
liberal licensing available now. You can use these curves today with
just a choice of big or little endian, and software that sets speed
records.

Adding in the apparatus in each protocol is obviously going to take
longer, depending on how bad the protocol is to work with. But
I don't think CFRG is the right place for that.

---

From: Paul Lambert <[email-masked]>
Date: Wed, 8 Jan 2014 17:32:54 -0800

>>> The group is [l]Jac(E(F_q)). There, done. In fact, this is in the

?? 
>more comments and resolve them.
Comment: 
 -too terse
 - no clear mapping of numbers to variables
 - no documentation of Edwards point addition
   Which is different from durrent ECC drafts
 - no indication of security concerns and
  need or lack of checking public key values

Here¹s how I¹d document curve parameters:

class Curve3617(EdwardsCurveFp):
    curveId  = 'curve3716'
    strength = 207
    oid = None
    p  = 2**414 - 17
    d  = 3617
    xG = 0x1a334905141443300218c0631c326e5fcd46369f44c03ec7f5\
         7ff35498a4ab4d6d6ba111301a73faa8537c64c4fd3812f3cbc595
    yG = 0x22
    n  = 2**411 - 
33364140863755142520810177694098385178984727200411208589594759

Paul

PS - above parameters are directly executable Python code
     Why use pseudo code when you can use real code :-)

---

From: "Isaac Chua" <[email-masked]>
Date: Thu, 9 Jan 2014 09:55:15 +0800

Dear Watson,

Great initiative. I think the doc should include a summary on the criteria
DJB and Lange use (the parameter and security requirements) similar to the
Brainpool one (RFC5639).

I do wonder, should this doc comment/make recommendations on the use of
unsafe curves according to these criteria?

Regards,
Isaac

-----Original Message-----
From: Cfrg [mailto:[email-masked]] On Behalf Of Stephen Farrell
Sent: Thursday, 9 January, 2014 01:22
To: Watson Ladd; [email-masked]
Subject: Re: [Cfrg] Safecurves draft

> body use/typos/general nastiness?

No objection, but there's maybe some checking to be done before we're ready
to push the button.

One thing though is that rfc 3526 [1] is standards track so if there's a
reason for that (and there may or may not
be;-) then we might want these to be the same which'd mean not doing 'em in
cfrg. That can be figured out later though.

S.

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Thu, 09 Jan 2014 09:08:25 +0100

> to address some people's desire for explicit formulas.

When copying the EFD formulas in the appendix, please don't forget to define the
meaning of the variables. For example, for Montgomery curves [1] use X1, X2, ...
X5 without mentioning explicitly (unless I missed something) that the formulas give

	(X4, Z4) = 2 (X2, Z2)
	(X5, Z5) = (X2, Z2) + (X3, Z3)

for inputs such that (X1, 1) = (X2, Z2) - (X3, Z3). Reminding readers about
Montgomery ladders (so that this last condition makes sense) cannot hurt. By the
way, it might be worth pointing out that the formulas in the EFD use (A+2)/4, as
opposed to the formulas in the Curve25519 paper, that use (A-2)/4. (I may be
dense, but I got bitten by this.)

[1]: http://www.hyperelliptic.org/EFD/g1p/auto-montgom-xz.html#ladder-mladd-1987-m

This was for Montgomery curves since that's the kind I'm the most familiar with
right now, but similar remarks probably apply for twisted Edwards curves.

By the way, it might be good to insert a word of warning about the fact that the
design of the curves themselves doesn't automatically protect from all
side-channels, and some points are still the responsibility of implementers:
avoid branches and data-dependant memory accesses in the ladder, and either use
constant-time field arithmetic or randomize projective coordinates.

Manuel.