Re: [Cfrg] New names for draft-ladd-safecurves

[Watson Ladd <[e-mail]>]

On Tue, Jan 21, 2014 at 6:16 PM, Jon Callas <[e-mail]> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> My concern is essentially this:

Let me reduce the number of hands you have to deal with.

>
> Assume a curve that we'll call 1234-56 for some reason. If it's a nominally Edwards curve (like 414-19, fka Curve3617), it can (and will) appear in Edwards, twisted Edwards, and Montgomery forms. There are lots of good reasons for flopping it around and doing arcane things with it.

Not our problem: if an implementation does something arcane, and it
gets the right answer, it isn't a problem if our standard doesn't
explain what it does. The issue would be if protocols were likely to
do arcane things, and it was useful to put them in this draft as well.

>
> On the one hand, one might want to transport the curve in any of those formats. The primary purpose of a standard is for interoperability. Thus, having a way to know what form a curve is transported in is a good idea.
>
> On the other hand, having many names for things causes questions and confusion because you then have to explain why the different names are really the same thing. Elliptic curves are hard enough as it is.

Not the same, isomorphic. Ed25519 isn't the same as Curve25519, they
are isomorphic curves. Does it matter to implementors if they are
isomorphic or not? Not really: the formulas work, and those who get it
can take advantage of that fact.

>
> On the third hand, it might even be good to have a single *transport* format and just pick one. Force people to transport in one format.

Currently my idea is each curve name has a specified format. How is
this confusing?

>
> On the fourth hand, is that *really* going to cause less confusion than having a name for each format?
>
> See -- I don't have an answer here. With my standards hat on, I tend towards the third hand. Define *a* transport format and have just one. With my crypto hat on, some crypto people would cheer that, and others wouldn't. Either way, there's chance for error.

Here is the problem in a nutshell: some protocols can get away with
transporting only an x-coordinate, and some cannot. For those that
can,
Montgomery ladders naturally work on the twist as well as on the
original curve, so there is no issue with a missing check causing
problems.

However, if the transport format requires a y coordinate, than
Montgomery ladder implementations have to do some extra work to
transmit. The extra work isn't prohibitive, but given that we aren't
adding points, it seems a bit useless to do that work.

We've already crossed the Rubicon when we decided not everything was a
short Weierstrass curve. The zero, one, many rule still seems good to
me.

When an implementation uses an Edwards curve, it needs to reconstruct
points correctly. This is involves a check of being a quadratic
residue or the correct answer to a square root, which if missing isn't
an interop problem but a potential security issue for ECDH. However,
the extra bit for exact reconstruction is free when packing.

With signature schemes the natural approach is to use Edwards curves
and take full advantage of batching. This can't be done with
Montgomery ladder, and as the exponents (except for the signature
creation exponent) are public (well, random, but revealing them after
you start can't hurt you) Edwards curves can use Bos-Coster algorithm
for very high verification speed. Forcing an Edwards curve to pack to
Montgomery form is a waste of time, given that the receiver is going
to be using Edwards form anyway.

I've not seen a strong argument for using a unique form per
isomorphism class. ECDH can work on Edwards curves if implementation
size is an issue. Robert Ransom argues that as small Edwards d leads
to fast Montgomery arithmetic, we should specify only Edwards curves,
and the equivalent Montgomery form, but he wants a single point format
that requires reconstructing y for a Montgomery ladder and turning
points into Montgomery points. (Ask him why it makes sense: I
disagree).

For a protocol like MQV, Edwards form would still make sense.
Implementations could use the Montgomery ladder and reconstruction for
the single-exponents, and take full advantage of Shamir's trick on an
Edwards curve for the final key. But MQV isn't used because of
patents, and it isn't that useful. I don't see a reason to expand the
draft's scope to support this niche case with an implementation
strategy that isn't strictly necessary.

Hopefully this explains my position and the issues more clearly then
my prior emails.
Sincerely,
Watson Ladd
>
>         Jon
>
>
> -----BEGIN PGP SIGNATURE-----
> Version: PGP Universal 3.2.0 (Build 1672)
> Charset: us-ascii
>
> wj8DBQFS3yn0sTedWZOD3gYRAnx2AJ4q3SrQ7/eeTUYgwAYnZNLfncOg6wCfWRy5
> EvQ+uaBNA2SjnJFLcasiYlg=
> =XuJM
> -----END PGP SIGNATURE-----
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg



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