Re: [Cfrg] Curve manipulation, revisited

[Alyssa Rowan <[e-mail]>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

On 29/12/2014 07:57, Benjamin Black wrote:

> The view voiced by several people that the 128-bit security level 
> curve in the draft is Curve25519 is a bit off base.

Thanks; I'd missed that.

My tentative support for the draft was strictly conditional on the
resultant 128-bit curve being (birationally) equivalent to Curve25519,
because I feel that would resolve our disagreement on curve choice.

As I said before, your draft is so close to it that any remaining
discrepancy is poorly justified, and simply gratuitously incompatible.

> First, the draft describes generation of (twisted) Edwards curves 
> and the 128-bit curve has minimal d (given the addition of the
> newly manufactured cofactor constraint), while Ed25519 does not.
> This is an advantage for both performance and rigidity with a tiny
> reduction in simplicity of implementation, achieving a better
> balance between security, performance, and simplicity.

Rigidity is largely qualitative. Rigidity means clearly and soundly
explaining, documenting and justifying all of your choices; quantifiably
eliminating them is impractical: as the BADA55 paper points out, there
are always choices.

And I don't think your curve _not_ being Curve25519 is a justifiable
choice now. Even one of your co-authors very clearly prefers Curve25519
(and will move without you if he absolutely has to), and the other wants
a different curve with random primes for his RSA multiplier anyway.

> Second, the specified base point is not the same and can't be the 
> same without forcing the (arbitrary) choice.

Correct me if I'm wrong, as it's before breakfast (and I'm notoriously
unreliable before breakfast!) - but given the cleared cofactors, is the
base point x=9 the smallest point on Curve25519 in Montgomery form?

> The result is that it is straightforward to modify existing 
> Curve25519 implementations to use the new curve, but modification
> is likely required.

My position is that modification _of the draft_ is likely required to
resolve the remaining discrepancies.

In fact, it appears to me at this point that _only you_ at Microsoft
Research want this as it stands; almost everyone else choosing a new
128-bit curve has considered the alternatives and chosen Curve25519 or
(for the hardware-with-an-RSA-multiplier people) a random-prime curve
analogue; and everyone on the group (including the chairs, I think!)
would just like this whole thing over with. (Missing #31c3 was just
embarrassing.)

My strong impression is that our clear preference as a group for a
128-bit non-NIST elliptic curve is Curve25519, and (although I wasn't
there) has been so even before the TLS WG's request, at the meeting in
Hawaii. Maybe we should wait until January before asking the chairs to
call for consensus, due to holidays. But please let's get something out
of the door - and, well, you know what we can agree on. Do we need to
resurrect the Turner draft instead?

That would at least give us a solid base for methodology for the
larger curve; then I feel we're largely discussing the choice of
primes and the relatively poor security::performance ratio of primes
in the ~2^384 region.


As we're already pretty late now, if you don't mind, I'm probably just
going to go ahead and use Curve25519/X25519/Ed25519 now - like the
running code in Tor, I2P, GNUnet, TextSecure, iOS, GnuPG, OpenSSH,
OpenBSD and a whole bunch of other things. They are not merely good
enough, they're great. I see no good reason to arbitrarily change that
just because CFRG said otherwise - and I suspect, neither will they.

- -- 
/akr
-----BEGIN PGP SIGNATURE-----

iQIcBAEBCgAGBQJUoS/kAAoJEOyEjtkWi2t6k6EP+QGo/6fWVWpmBJ0O+wA+P+pB
Jv5pfstHROhZZGwyAwWN8axUXB1DsIG3a7DwzNdxn/EEQMlbFgDMqEV0RGC/Ohji
hKPFK6wcSTbo3j/biAQqpue/7ChMwZCKzjJBySJUtACc40zivVQjCM2IH1EukG28
gEycuL66wmWHXI/1Fnazw9NBwV1JgltPurwY58MOsJXYFv19msmSQPiGd+9vzGk1
oxbYDELhe/u1XnQTEbTG7i7VGT2wqQpsb0wxO9rMIgUk7bLkEAvqeFoRalSlMSFj
N8HevIJt0+sD0XC7ccfm3NAgOUfAPRYM4vd4rmrTZwWDrQtlQGlME92lvGrxnRRg
0hWIb0XtilXSEnZngbs/yJQi32IHjFqa8iJxyUTJ92cE12bDxkFjegP0DhpPbSBw
oJeNnwn2NVoXsCP1Q6imhYfMTDnE+QXdvks7L0NUzKmeIjKqE8t92rdS3O1h+M86
hDwaGFZnQAT7PtR9tXNcMbf2thOPTHow4SjBzAjq10yfuQ7Q1M6t6qe/VOV1jaxL
FnTy6KXlkp59DxcdlL5OZpTpm3t7bXdONFejwb66kUVGzfKkQYv67CJy56lGMoJw
qPFV+rj2zs5n5T+Cjq2Ak1cpbzZazA56B98X8UAS4ptpBtaoP/9EbSfIfnn17r3+
8bd+eLrsRvHwep1lZNG1
=cPHX
-----END PGP SIGNATURE-----