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

[Dan Brown <[e-mail]>]

Hi Mike,

Further to your suggestion below, why not consider a modified version of Curve25519, with same underlying field, (Montgomery) equation y^2 = x^3 + Zx^2 + x, where

Z = PRF("Chicago"||counter)

Where PRF is some reasonable pseudorandom function mapping into the field of definition of Curve25519, and counter is some unambiguously encoded bit string representation of an integer is value is the minimal among these meeting as many as possible of the various criteria used for selection of the A coefficient in Curve25519, in particular resistance to known attacks, e.g. twist security, MOV resistance, and SASS.  (Hey, why not throw in other criteria too, strong DHP safety, high discriminant, and that other thing related to isogenies that Brainpool considers (is it endomorphism class number or something?).)

Given that Z would be larger than A, the resulting curve would certainly be slower than Curve25519.  But how much slower?  Surely it would be almost as easy to implement, and have similar side channel resistance, unless I have a severe misunderstanding.

I think one could then make a formal (if heuristic) argument that if an adversary knows of a secret weak class of some small, but non-negligible density subset of curves (over the given field), that this curve is drawn from a sample space of sufficient size such that it inherits the small fraction property.  My algebraic geometry is a little weak, but I assume that varying this single coefficient in the equation walks through a good fraction of the isomorphism classes (J-invariants).  This security argument may assume the attack works across birational equivalence, if one is concerned about an attack specifically on NIST P256.

Just to be clear, the gain here would only to be not rely on the plausible presumption a secret attack is independent of coefficient size.

Just to be extra clear, the claim is not the some particular size of Z resists attacks better, but the fact that Z is random is pseudorandomly selected.

Best regards,

Dan


From: Michael Hamburg [mailto:[e-mail]]
Sent: Monday, January 13, 2014 7:57 PM
To: Watson Ladd
Cc: Dan Brown; [e-mail]
Subject: Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid v Pseudorandom


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


On Mon, Jan 13, 2014 at 3:07 PM, Dan Brown <[e-mail]<mailto:[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
---------------------------------------------------------------------
This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.