As Mike isn't on this list, he asked me to forward this.<div><br>---------- Forwarded message ----------<br>From: <b>Mike Hamburg</b> <<a href="mailto:mike@shiftleft.org">mike@shiftleft.org</a>><br>Date: Saturday, August 9, 2014<br>
Subject: Many curves versus one curve<br>
<div bgcolor="#FFFFFF" text="#000000">
<br>
<div>On 8/9/2014 7:26 PM, David Leon Gil
wrote:<br>
</div>
<blockquote type="cite">
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Cc: "<a>cryptography@metzdowd.com</a>"
<<a>cryptography@metzdowd.com</a>><br>
Subject: Re: [Cryptography] IETF discussion on new ECC curves.<br>
Message-ID: <<a>683EFDEB-06A0-4248-8579-CDCF17CAEF34@gmail.com</a>><br>
<br>
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?<br>
<br>
--John</blockquote>
<div><br>
</div>
<div>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.)</div>
</blockquote>
"Working on" is a bit strong. I hacked something together, but I
haven't polished it at all.<br>
<br>
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.<br>
<br>
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.<br>
<blockquote type="cite">It makes most sense on a per-application basis -- the
computational cost of verifying these conditions is fairly
high.[*] </blockquote>
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.<br>
<blockquote type="cite">
<div>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.)</div>
</blockquote>
You'd need to hash in the curve being used.<br>
<blockquote type="cite">
<div>So current uses of EC might need reëxamination.</div>
<div><br>
</div>
<div>-dlg</div>
<div><br>
</div>
<div>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:</div>
<div><br>
</div>
<div>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.)</div>
</blockquote>
I kind of like this argument, though having lots of curves is really
inconvenient.<br>
<blockquote type="cite">
<div>[*] 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. <br>
</div>
</blockquote>
I can post my GP patches if you want, though actually the important
thing to standardize is the verification.<br>
<br>
Cheers,<br>
-- Mike<br>
</div>
<br></div>