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>