Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid v Pseudorandom

[Michael Hamburg <[e-mail]>]

On Jan 13, 2014, at 4:36 PM, Watson Ladd <[e-mail]> wrote:

> On Mon, Jan 13, 2014 at 3:07 PM, Dan Brown <[e-mail]> wrote:
>> Watson,
>> 
>> I had requested to keep this thread focused, specifically in the impact pseudorandom v rigid on security, but you declined to engage. Is it that you think this security issue unimportant, even though you concede with my narrow point?
> 
> I think it's completely bogus. People aren't primarily interested in
> the Chicago curves because of unknown attacks, but NSA cookery over
> NIST+the efficiency and security benefits they offer.

Speak for yourself.  I’m interested in a standard which has a better chance of resisting unknown attacks, and I’m not as concerned about NSA cookery as you are.

I agree that random (or pseudorandom) curves are preferable to rigid ones, so long as they are generated with the rest of the Safecurves properties.  The problem is, they are much harder to generate.  Maybe shake up some dice or Boggle boards at the CRYPTO rump session?  Or make a Bitcoin donation to EFF annotated with the hash of your software, and use the hash of its block?  Dunno.  The Brainpool method has too many degrees of freedom to convince everyone.

Either way, I feel that the highest practical ECC security level would come from a verifiably pseudorandom curve over a verifiably pseudorandom field.  This is because it will take either a significant mathematical breakthrough or a quantum computer to break existing 120s-ish-bit-secure curves such as Curve25519, anytime in the foreseeable future.  If it’s a quantum computer or a breakthrough that kills all curves, we’re screwed.

So that leaves a breakthrough which kills only curves with special properties, or only improves speed somewhat (eg, p^1/4 instead of p^1/2).  Given that, should we choose curves with known special properties that aren’t required for security?  (Small d, special fields?)  Or should we try to be as random as possible, constrained only by properties that have a good security argument?

The downsides are difficulty of generation, and speed: a random field would be at least twice as slow.  So if I had to take 3 next-gen curves to a desert island, I’d go for:

* Ed25519.  It’s deployed, it’s implemented, it’s significantly faster and easier to make secure than NIST P256.  There are other options, but this one works.  Once again, probably nobody is going to break this with a rho attack in the next couple of decades.

* Something with a bigger fast field.  Ed448-Goldilocks is my entry for that, but the others are also fine.  A pseudorandom $d$ value would probably improve things, if you could get confidence that it’s not rigged.  Whichever way this goes, ops on such a curve will take about 4x as long as Ed25519 in software.

* A pseudorandom curve over a pseudorandom 512-bit field.  Operations on such a curve will probably take at least 12x as long as Ed25519, and at least 16x if it’s a short Weierstrass curve.

In any case, if we list any pseudorandom curves, they should have most of the Safecurves properties except rigidity.  Some of the properties really aren’t necessary (eg, Elligator), and basically end up just requiring Edwards curves.  There’s a decent case that Edwards is a better shape than short Weierstrass anyway though, and in that case we should go for all the properties except rigidity.

Cheers,
— Mike