Subject: [Cfrg] draft-ladd-safecurves-02

From: Watson Ladd <[email-masked]>
Date: Fri, 10 Jan 2014 11:11:19 -0800

Added: explicit formulas and a point format (big endian with a bit for
the missing coordinate).
The name is now the Chicago curves.

I'ld like the conversation to focus on moving this through the
process, rather than on bikeshedding names or formats. Ambiguity and
errors should be the focus, as well as complaints that "well, there is
this paper of Diem..."

Sincerely,
Watson

---

From: Trevor Perrin <[email-masked]>
Date: Fri, 10 Jan 2014 11:20:35 -0800

> Added: explicit formulas and a point format (big endian with a bit for

I don't see the draft yet, but if you're including point formats, any
thoughts on Jivsov's trick?

http://tools.ietf.org/html/draft-jivsov-ecc-compact-03

Trevor

---

From: Watson Ladd <[email-masked]>
Date: Fri, 10 Jan 2014 11:25:31 -0800

> http://tools.ietf.org/html/draft-jivsov-ecc-compact-03

Assumes short Weierstrass form. I did put in x coordinate only for
Montgomery, but it's not the same thing.

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

---

From: Alyssa Rowan <[email-masked]>
Date: Fri, 10 Jan 2014 19:48:25 +0000

On 10/01/2014 19:11, Watson Ladd wrote:

> Added: explicit formulas and a point format (big endian with a bit
> for the missing coordinate).

Fair enough. (Cofactors were also added, by the way.)

> The name is now the Chicago curves.

As good as any other.

Comments:
• Typo in end of section one: Weierstrass, not Weierstrauss.
• I think it'd be a little more helpful if section 2 were split into
  two sections: the Montgomery curves, and the Edwards curves. That'd
  make it much more apparent which curves are applicable to which
  sections in 3 and 4.
• Pretty please can we have Curve1174 as well?

Other than that, no more comments.

E-521's passed all tests, by the way, as expected (and it seems was
obviously rigid enough that three groups actually came up with the
exact same curve!).

I see no particular reason to hold this up.

- -- 
/akr

---

From: Michael Hamburg <[email-masked]>
Date: Fri, 10 Jan 2014 11:50:16 -0800

> Montgomery, but it's not the same thing.

Well, you can do it in any coordinate system where negating one coordinate negates the point.  You just have to change section 4.3 to use the curve’s formula instead of the short Weierstrass formula.  For example, you can do it with Edwards curves and negate x instead of y.

This trick is neat, but it saves only one bit, and restricts to a subset of EC points.  You can do the same thing with some other subset, particularly with Edwards curves.  For example, you could restrict to only q-torsion or only 2q-torsion points, or only Elligator-encodable points.

I think the fastest way to do this is the one I posted with the inverse square root on the isomorphic Montgomery curve, but there are other options which basically accomplish the same thing.

— Mike

---

From: Watson Ladd <[email-masked]>
Date: Fri, 10 Jan 2014 15:31:15 -0800

On Fri, Jan 10, 2014 at 11:48 AM, Alyssa Rowan <[email-masked]> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA512
>

Fixed

>   make it much more apparent which curves are applicable to which

I'll think about a clean way to do this. Of course, you can use
isogenies to convert
between all of these forms.

> • Pretty please can we have Curve1174 as well?

Included.

Anymore suggestions? This next one it would be nice to get Last Call on.
> -----BEGIN PGP SIGNATURE-----
>
> iQIcBAEBCgAGBQJS0E6JAAoJEOyEjtkWi2t6V3wP/0CHxxQtWozhfilM5BY+6Ffw
> PosRUsiRAA6V5UCeAiQUWzBUjIhV8kgyQSYTSuxgFNOASFMVIs24sSs48nLcUYjR
> ER+Hmtl8La6OJ/cR0iAaP92PY9UScbUFzWPAJXOljGTPYH7D7dykdAUSnfN5vfy4
> IeBdkJm66C/JYRwq20y3noSlQfJfclJYDOJIscUco6TYGV3/eLjiMFVFQfzAjJlz
> RHDwYbr8Quc2lr4Hjl4mm+NRHFdUskhD4i7lA0DfcjohILxC4dw71f5wlmDehuMI
> /MGccPbcPfQ0lEJpq5E3cY3jNtPU+EonY4TNnBA9mg2a2wVm2iIGOatptEzo+R7Q
> fsjw+i2MXML+gNqpspGcA5RPU3x0DHSSzu5DDhpRH5V+So51mVdXFjGeLrLK1gJk
> CZnOdDGgwc1tmOaphWMZZdcCYZosm8UMqh/J5tHCqUooknWxzVEKUs7eyn3TG6+I
> +gdtbOdZhQf0K8iIXtwc874+G+e2c0MiU64GkNN3UT/7QFQY5zVxcgDLXwzUHcZk
> PXx55n5IFz7iTwjTZd859grGRubHHjqDnnE/gNeWp7iGq2UezYMiRcLJUCehglYi
> 72bAdbRc/bLOBoIHzJSuqEDR0TKRFmmrIN0pfSJe7PO9iun3b/rLIYavDfwH8dLN
> NfKGARVJurKm1aW7wFk5
> =PsP0
> -----END PGP SIGNATURE-----
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: Robert Ransom <[email-masked]>
Date: Sat, 11 Jan 2014 08:17:18 -0800

On 1/10/14, Michael Hamburg <[email-masked]> wrote:

> Well, you can do it in any coordinate system where negating one coordinate
> negates the point.  You just have to change section 4.3 to use the curve’s
> formula instead of the short Weierstrass formula.  For example, you can do
> it with Edwards curves and negate x instead of y.

Or, in any application where (a) points should be transmitted or
stored in Edwards form, and (b) points can or will be doubled at least
once before use, one can negate the Edwards y coordinate iff the
Edwards x coordinate is ‘negative’.  (This corresponds to adding (0,
-1) (the point of order 2) in order to fix the sign of x.)

If one can also discard the point's sign or modify the secret key, one
can combine the above trick with Jivsov's suggestion: negate the
Edwards y coordinate to fix its sign bit, and discard it.  (This could
be useful for applications where public keys must be transmitted in
base 32 or base 64 and the coordinate field has one extra bit, e.g.
using points on the minimal-Edwards-parameter curve mod 2^206 - 5 as
DHT addresses.)

Robert Ransom

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Sat, 11 Jan 2014 17:45:04 +0100

Hi,

Notes taken while reading -02 (in order of reading, so mixing typos with more
important comments).

- abstract: why mention the Jacobian rather than say "elliptic curves" (as you
do in the intro)? Maybe say that DDH is *believed* to be hard, too.

- end of the intro: "then short Weierstrass curves": then -> than

- section 2 "Validation information is given at [SAFECURVES]." What do you mean
exactly? Is it a repeat of "Proofs of all properties claimed exist in
[SAFECURVES]." in the intro, or do you mean something else?

- as an implementer, I'd have a preference for constants in hex. Also, I don't
like the formatting very much. Starting each constant on a new line might help.

- I second Alyssa's suggestion to split the content in two sections, too.

- formulas for Montgomery curves: I think "P_i = [i] P_1" is not what you want
to say. Also, I'm not sure the reference to the Kummer curve is of any help.

- why give the formulas for Edwards with common sub-expressions already
eliminated, but not for Montgomery?

- point encoding "GF_p point on E(GF_p)" isn't that a bit redundant?

- "Formulas for decompression are left as an exercise to the reader." You can't
be serious. The goal should be to actually help people write correct
implementations, which this kind of funny (?) non-reference does not.

- security considerations: "some checks in some protocols": which and which?
"certain attacks": which ones? Again, please, this should be a technical
document giving precise, actionable information.

- IANA: sorry if this is a dumb question, but I'm not sure I see the need for a
IANA register here (an would it be only for the "chicago" curves or all known
curves)? So far, there are protocol-specific registries (eg, TLS Named Curves)
and it seems to me it has been enough.

- OTOH, it would probably be good to have OIDs for the curves here, since they
could be used by many protocols.

Manuel.

---

From: Robert Ransom <[email-masked]>
Date: Sat, 11 Jan 2014 10:06:38 -0800

> like the formatting very much. Starting each constant on a new line might

The basepoints should be specified by the value of the primary
coordinate and the sign bit of the other coordinate, not specified as
a pair of integers where one is too huge to be useful.

> - I second Alyssa's suggestion to split the content in two sections, too.

I strongly oppose separating the curves which happen to have been
first specified in Montgomery form from the curves first specified in
Edwards form.  Every Edwards curve is isomorphic to a corresponding
Montgomery curve and vice versa.  (That is the reason (the *only*
reason) that Dr. Bernstein advocates twist security for Edwards curves
-- twist security is only important for curves used in Montgomery
form.)

The document should also specify the equivalences.

> to say.

I don't currently remember how the inputs and outputs for those
formulas are arranged, but it's possible that “P_i = [i] P_1” may be a
useful mnemonic to give *after* explaining that the inputs are P, Q,
P-Q (in some order) and the outputs are 2P and P+Q (in some order).

> Also, I'm not sure the reference to the Kummer curve is of any
> help.

I agree that that reference in the current draft (-02) is not helpful,
but the fact that a Montgomery line is something other than a group is
absolutely critical, and it needs to be both stated and clearly
explained.  The fact that such a near-group for a genus-1 curve is
called a “Kummer line” should be part of the explanation.

> eliminated, but not for Montgomery?

Presumably because the formulas he copied from EFD happened to be that way.

More importantly:

* The addition formula given for Edwards curves uses the additional
curve parameter c, but with no indication of what that parameter is.

* The addition formula given for Edwards curves uses ‘inverted’
coordinates.  No one should use those in any new implementation --
they cannot represent the point at identity, and so cannot be used in
constant-time multiplication procedures.

* The document gives one addition formula, but no guidance as to how
to use it in a multiplication routine that achieves the ‘security and
performance advantages’ mentioned in the introduction.

> implementations, which this kind of funny (?) non-reference does not.

Indeed.  Dr. Bernstein had the good sense and decency to give the
exact algorithm for Edwards-form point decompression in coordinate
fields where q \in 5 + 8\ZZ in his Ed25519 signature scheme paper.

> document giving precise, actionable information.

I agree.  But I think Watson Ladd really believes that a good standard
should not specify how to implement it.

> and it seems to me it has been enough.

I see no reason to have IANA try to maintain an out-of-date copy of
the list on the SafeCurves web site.  (If there is a good reason to
create an IANA registry for these, the draft will need to specify how
the registry should be managed.)

> could be used by many protocols.

I strongly oppose publication of this draft as an RFC.  In its current
state, it will lead readers to produce defective implementations with
most of the security flaws that ‘SafeCurves’ are meant to avoid.

I also do not believe that Watson Ladd is willing to make the changes
needed to make this document useful.  I am not willing to contribute
to this document further.

Robert Ransom