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

From: Dan Brown <[email-masked]>
Date: Mon, 13 Jan 2014 16:55:21 +0000

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.

Today, I checked that

http://safecurves.cr.yp.to/rigid.html

characterizes Curve25519 as "fully rigid", and brainpoolP256t1 as "somewhat
rigid", and more critically, implies the latter to be at greater risk to a
secret attack on the ECLDP.  (Am I misinterpreting?)

On November 4, 2013, I wrote the following email to the TLS list

http://www.ietf.org/mail-archive/web/tls/current/msg10393.html

which claims that BrainpoolP256t1 has a lower risk than Curve25519 of resist
a hypothetical secret attack on a maliciously generated NIST P256.  These
seems to an opposite conclusion from that implied by the safecurves.  Hence
my disagreement.

The gist of my argument was that pseudorandomness can avoid a class of
unknown weak curves, with a certain probability related to the density of
the weak class from the pool of curves which it is drawn.  

Yes, rigidity helps more to prevent malicious generation of the curve.  I am
not disagreeing with the safecurves site on that point.  

I am saying that for an honest generator of a new curve, who is thoroughly
worried about some secret attack that could affect a maliciously-generated
P256, using a random curve is her best recourse, followed by pseudorandom
curve (as in brainpool). Rigidity is on par with arbitrary regeneration for
convincing oneself that one's chosen curve resists this secret attack, but
rigidity is better for convincing other parties.

In the terms of the safecurves site, I'd say that, first, it omits this
important argument, that is okay in the sense that the site serves to put
the best foot forward. Second it implies wrong conclusions, which is a
slight mistake and ought to be corrected. Anyway, I hope that CFRG and IETF
will consider a more balanced argument, and the users of Curve25519 are
adequately informed.  That is, I hope that CFRG can provide peer review.

Is it fair to say that the possibility of P256 being malicious is one of the
main reasons for the recent rise in popularity of Curve25519?  Or is the
pattern between recent news and standards adoption just a coincidence?  If
this is the main reason, then we should look into it carefully.

Not to lose focus: I hope to start other emails threads on other less
important issues, e.g. how much risk is there that P256 is weak and the
impact on the rest of ECC, random v special, how special are safecurves,
relative importance of side-channel resistance v DLP, risks of parameters v
keys, do attacks target curves, random v pseudorandom, and so on.  So, I
hope that that this thread can be kept focussed on this one issue.  

To summarize my position, and divide into candidate pieces for discusssion: 

1.      Pseudorandomness protects effectively (as possible for ECC) against
the spectral weakness necessary to hypothesize a malicious NIST P256.

2.      Rigidity protects against the spectral weakness only by invoking
assumptions about spectral weakness (*).

3.      Protecting against attacks, such as the hypothetical spectral
weakness, is more important than (subsumes?) protecting against malicious
generation.

Regarding (*), the assumptions about the spectral weakness, I may wish to
start a separate thread to discuss.  It seems that the safecurves site does
not say too much about it, but there was some pertinent email discussion on
the TLS list, that I think merits some consideration for the CFRG.

Best regards,

Daniel Brown

Research In Motion Limited 

	

---------------------------------------------------------------------
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.

---

From: Watson Ladd <[email-masked]>
Date: Mon, 13 Jan 2014 13:26:10 -0800

On Mon, Jan 13, 2014 at 8:55 AM, Dan Brown <[email-masked]> wrote:
>
> Last week I wrote that I would soon write up my disagreements with the safe curves site.
>
>
>
> -        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).

>  <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

---

From: David McGrew <[email-masked]>
Date: Tue, 14 Jan 2014 15:56:37 -0500

Hi Dan,

thanks for sharing your thoughts, more inline:

On 01/13/2014 11:55 AM, Dan Brown wrote:
> -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.
>

This is an important question, so let me take a step back before I 
answer it.

You and others are welcome as individuals to contribute individual 
submission Internet drafts and call them to the attention of CFRG. If 
you want to provide a more formal document, then an I-D seems more 
appropriate, but I am personally fine with an email such as this one, 
when there is no need for a permanent record.

Technically, I-Ds are not permanent documents; they expire by design.  
Some I-Ds progress to become RFCs.   Progressing an I-D to an RFC takes 
a bit of work and patience, so ideally, we should minimize the number of 
documents we progress to RFC.

The research group can choose to take on an I-D, because it wants to 
endorse the work and make sure that it gets published.   However, it is 
not necessary to do that.   Alternatively, I-Ds that are individual 
submissions can get progressed to RFC, and can be reviewed in CFRG.    
This has been done before with CFRG, with RFCs 5116 and 6090 for 
instance.  The process for progressing drafts to RFCs is described in 
http://tools.ietf.org/search/rfc5742    If CFRG takes on a draft, then 
the CFRG chairs are responsible for performing or orchestrating the work 
that needs to be done to get it published as an RFC.   If someone wants 
to publish a draft as an individual submission RFC, rather than going 
through the CFRG process, then they will need to convince a Security 
Area Director (Sean or Stephen) to publish their draft.  Of course, one 
of the differences of authoring an individual submission instead of an 
RG draft is that, in the latter case, the author is accountable for a 
work product of the entire group (that is, the draft needs to reflect 
input from other RG members).

We need to be conscious of the limited resources that we have for 
reviewing and shepherding documents within CFRG, and make sure that we 
take on work that we can complete.   We are fortunate to have the 
participation of a lot of very talented people (including you), but we 
all have a finite amount of time.   So I think CFRG needs to figure out 
what topics to prioritize, and get people to volunteer as authors and 
reviewers (which could include implementers, in the case of specifications).

There clearly is interest, within IETF and CFRG, regarding ECC 
alternatives.  It would be good to have a discussion on what sort of 
RFCs would be most useful, which could include security analysis or 
separate recommendations as well as specifications.   Speaking as an RG 
member, not a chair, I personally like the idea of an RFC describing 
Montgomery or Edwards curves that provides the same sort of information 
as RFC6090: definitions, implementation guidance, references on 
security, and so forth.

I hope that this makes sense - I took a detailed question and gave a 
broad answer :-)

regards,

David