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

[Mike Hamburg <[e-mail]>]

My two cents:

The goal of rigidity is to constrain the curves without giving them any extra properties that might be relevant to an attacker.  It seems to me that for this purpose, CM is worse than small coefficients.  As a result, Bernstein's Safecurves criteria ban curves with small CM discriminant, despite no attacks being known.

However, the endomorphisms on such curves can speed up implementation, and I could definitely see a use for CM curves or GF(p^2) curves with a 256-ish-bit prime, a la GLS/GLV.  It reduces the computation required for perfect forward secrecy, right?  But in terms of protecting against hypothetical unknown attacks, I don't think it makes sense to use CM curves at high security levels.

I'd be very interested to hear the opinion of someone who is more versed in the subject.

Cheers,
-- Mike

On Jan 14, 2014, at 9:24 AM, Igoe, Kevin M. <[e-mail]> wrote:

> It has been a long time since I've looked at the complex multiplication 
> method for generating elliptic curve, but I believe that with some care
> the CM method might satisfy your criterion for being rigid.
> 
> Should use of the CM method be encouraged, tolerated, or prohibited?
> 
>> -----Original Message-----
>> From: Cfrg [mailto:[e-mail]] On Behalf Of Dan Brown
>> Sent: Monday, January 13, 2014 6:08 PM
>> To: Watson Ladd
>> Cc: [e-mail]
>> Subject: Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid v
>> Pseudorandom
>> 
>> 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?
>> 
>> Instead, you mostly repeated the general speed and side channel
>> benefits of Chicago, which I was not yet disputing.
>> 
>> Also, you suggested that I was referring to the field choices. I did
>> not intend to, but I should clarify.
>> 
>> For a given field, pseudorandom curve better resists secret attacks
>> than rigidity.
>> 
>> Field size would on my list of issues, but way, way down on my ranking
>> of importance.
>> 
>> A couple people have suggested to me (off list) to generate new curves
>> with explainable seeds but the same fields as NIST curves.
>> 
>> The result would seem to be intermediate between Brainpool and Chicago.
>> 
>> My main reluctance with that would further babble, and yet more
>> difficulty with interoperability.
>> 
>> 
>> From: Watson Ladd
>> Sent: Monday, January 13, 2014 4:26 PM
>> To: Dan Brown
>> Cc: [e-mail]
>> Subject: Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid v
>> Pseudorandom
>> 
>> 
>> On Mon, Jan 13, 2014 at 8:55 AM, Dan Brown <[e-mail]> wrote:
>>> 
>>> Last week I wrote that I would soon write up my disagreements with
>> the safe curves site.
>>> 
>>> 
>>> 
>>> My first disagreement is written up below, but first two editorial
>> issues:
>>> 
>>> 
>>> 
>>> - My last email was in the context of Watson’s draft spec for the
>> Chicago (Bernstein?) curves, but I would like to detach the issue from
>> the I-D. My comment about the reference in Watson’s I-D to a website
>> was just an editorial comment.
>>> 
>>> 
>>> 
>>> - These technical issues that I hope CFRG discusses just might be
>> resolved and written into a CFRG I-D cataloging of elliptic curves and
>> their relative merits and so on, which should be independent of
>> Watson’s spec for the Chicago curves. For now, I opted to discuss via
>> email list, rather than placing these arguments into my own one-sided
>> individual I-D. Please advise me if such an I-D is preferred to email.
>> 
>> 
>> I think this is an excellent idea (the catalogue of good curves).
>> 
>>> 
>>> 
>>> 
>>> Today, I checked that
>>> 
>>> 
>>> 
>>> http://safecurves.cr.yp.to/rigid.html
>>> 
>>> <snip>
>> 
>> Rather then engage a peripheral argument, let me lay out the case for
>> the Chicago curves (named after the city in which Bernstein resides,
>> and in a long IETF tradition starting with TCP Reno, Oakley key
>> agreement protocol, and fundamentally of no import: see Shakespeare,
>> Romeo and Juliet, Act 2, Scene 2, or Wittgenstein, Philosophical
>> Investigations for more information) in the fairest light.
>> 
>> First efficiency: point addition on an Edwards curve costs 11
>> multiplications, doubling 7 multiplications. This is for a complete,
>> strongly unified addition formula, which requires no work for special
>> cases. By contrast on a short Weierstrass curve addition costs 16
>> multiplications, doubling 8.
>> This is with no assumptions on Z, which if we impose reduce the cost of
>> addition on a short Weierstrass curve to 11 multiplications. But if we
>> impose the same condition on the Edwards curve, the cost is 10
>> multiplications.
>> 
>> However, I've forced the Edwards curve to represent the identity, which
>> if we are willing to drop, slices off two more multiplications.
>> By contrast the
>> Weierstrass curve has special cases that need additional work to handle
>> in a secure manner. Most people just don't bother. I also let the
>> Weierstrass form be special with a=-3, while keeping the Edwards curve
>> fully general.
>> 
>> So given the same prime Edwards has short Weierstrass beat. This is
>> true no matter what algorithm for exponentiation is used. And I even
>> gave short Weierstrass curves a handicap by letting them avoid
>> representing the entire curve and having exceptional cases, and fix
>> some parameters.
>> 
>> Montgomery form is even better: differential addition costs 10M, and
>> calculates a doubling for free. Sadly the differential part makes
>> radix-k algorithms tough, but in memory constrained environments (like
>> hardware) Montgomery form can't be beat. (And we haven't even used
>> nonuniform differential addition chains yet.. I'm still hopeful).
>> 
>> Then there is the prime shape: Brainpool uses a random prime, which is
>> a terrible idea from an efficiency perspective. NIST primes are sized
>> for 32 bit machines, and have some hiccups on 64 bit machines. But the
>> Chicago primes are primes for all seasons: 2^k-c with small c is nice
>> no matter what radix you adopt. Unsaturated arithmetic makes addition
>> faster because reductions aren't necessary at all times, and the
>> Chicago primes are good from that perspective.
>> 
>> Now security: having an efficient complete addition formula makes
>> writing timing, cache, and branch side channel free code a piece of
>> cake. By contrast short Weierstrass curves have all sorts of wrong
>> curve, or invalid point, or somewhere the calculation messes up issues.
>> Usually the defense is a final check on the result being on the code,
>> but that isn't the same as knowing that no attack is possible because
>> your code always generates the right answer.
>> 
>> Lastly, many websites want to deploy PFS ciphersuites but are deterred
>> by the computation expense involved. Minimizing that expense is
>> essential. In the wider IETF context we are catering to devices from
>> the lowly MSP430, to the latest and greatest supercomputer. What does
>> Brainpool let us do? We should stick to the NIST and Chicago curves:
>> NIST for those who require it, and Chicago for those who require the
>> extra speed.
>> 
>> I would like to hear good arguments against this position. Robert
>> Ransom I understand wants twisted Edwards curves for an extra bit of
>> speed, using isogenies to keep them the same as the Chicago curves, but
>> selecting only those with small parameters and particularly nice prime
>> shapes.
>> Dan Brown believes that the Brainpool primes are less special in a way
>> that has to do with ECC security, despite this never affecting ECC
>> before.
>> 
>> Sincerely,
>> Watson Ladd
>> ---------------------------------------------------------------------
>> 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.
>> _______________________________________________
>> Cfrg mailing list
>> [e-mail]
>> http://www.irtf.org/mailman/listinfo/cfrg
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg