[Cryptography] Fwd: Many curves versus one curve

[David Leon Gil]

As Mike isn't on this list, he asked me to forward this.

---------- Forwarded message ----------
From: *Mike Hamburg* <mike at shiftleft.org>
Date: Saturday, August 9, 2014
Subject: Many curves versus one curve

On 8/9/2014 7:26 PM, David Leon Gil wrote:

Cc: "cryptography at metzdowd.com" <cryptography at metzdowd.com>
> Subject: Re: [Cryptography] IETF discussion on new ECC curves.
> Message-ID: <683EFDEB-06A0-4248-8579-CDCF17CAEF34 at gmail.com>
>
> Does it make sense to have a small set of curves that everyone uses?  Or
> would it be better to have every application or even every user generate
> their own curve, using some process that would convince skeptics that the
> curves had been generated randomly?
>
> --John


 I think that Mike Hamburg has been working on a Sage(?) script to select a
curve satisfying the SafeCurves criteria deterministically from a random
seed. (He mentioned this on another list.)

"Working on" is a bit strong.  I hacked something together, but I haven't
polished it at all.

The main search part is actually a slightly patched pari/gp with a python
driver to divide the work between cores.  The modification is to make gp
bail out of SEA as soon as it finds a small prime dividing |E| or |~E|, and
to return that prime.  The built-in SEA has a bail-out condition but it's
not as flexible.

The biggest problem is that it takes a few core days to generate a curve at
the 512-bit level.  Then it takes another couple core-days to process the
logs to make a certificate that this was indeed the first one.  It's a
Poisson process, so it could take more or less time than that.  This could
probably be shortened by someone with better SEA skills than mine,
particularly for the cert generation.

It makes most sense on a per-application basis -- the computational cost of
verifying these conditions is fairly high.[*]

Yeah, the cert takes like an amd64-core-minute to verify in Python.  Not
something you want to run alongside your 150 microsecond DH.  Also it
doesn't check all the Safecurves criteria right now, just low cofactor, so
the others would probably add to the cost unless there's an easy way to
certify them.

However. Some EC primitives lose some of their nice properties if users can
select arbitrary curves (even over a single prime field). E.g., ECDSA is
not subject to key-share attacks if all users use the same curve; it is, if
arbitrary curves are permitted. (Koblitz and Menezes discuss this in their
'Another look' papers.)

You'd need to hash in the curve being used.

So current uses of EC might need reëxamination.

 -dlg

 PS, or, taking the other side: There is, by the way, a good
counter-argument to the 'just increase the bit-length' argument djb uses
for single curves:

 Suppose that an unknown fraction of elliptic curves has some undesirable
property. By using a large number of curves, we decrease the variance of
our risk in expectation. Under a minimax cost model, this is a big gain. (A
certainty of small loss, rather than a small chance of catastrophe.)

I kind of like this argument, though having lots of curves is really
inconvenient.

[*] For applications that are extremely length-constrained -- e.g., some
embedded devices -- provisioning with a per-device curve is the most
feasible way of increasing security. I, personally, would like a
standardized process for this.

I can post my GP patches if you want, though actually the important thing
to standardize is the verification.

Cheers,
-- Mike
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20140811/ee372c80/attachment.html>