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

"Igoe, Kevin M." <kmigoe@nsa.gov> Tue, 14 January 2014 17:24 UTC

Return-Path: <kmigoe@nsa.gov>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 56EAB1AE143 for <cfrg@ietfa.amsl.com>; Tue, 14 Jan 2014 09:24:29 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -7.438
X-Spam-Level:
X-Spam-Status: No, score=-7.438 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_HI=-5, RP_MATCHES_RCVD=-0.538] autolearn=ham
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id EfT0lMHKYyV9 for <cfrg@ietfa.amsl.com>; Tue, 14 Jan 2014 09:24:25 -0800 (PST)
Received: from nsa.gov (emvm-gh1-uea08.nsa.gov [63.239.67.9]) by ietfa.amsl.com (Postfix) with ESMTP id CC1B81AE155 for <cfrg@irtf.org>; Tue, 14 Jan 2014 09:24:24 -0800 (PST)
X-TM-IMSS-Message-ID: <0ddf31e10001907c@nsa.gov>
Received: from MSHT-GH1-UEA01.corp.nsa.gov ([10.215.227.18]) by nsa.gov ([63.239.67.9]) with ESMTP (TREND IMSS SMTP Service 7.1; TLSv1/SSLv3 AES128-SHA (128/128)) id 0ddf31e10001907c ; Tue, 14 Jan 2014 12:23:30 -0500
Received: from MSMR-GH1-UEA03.corp.nsa.gov ([10.215.224.3]) by MSHT-GH1-UEA01.corp.nsa.gov ([10.215.227.18]) with mapi id 14.02.0342.003; Tue, 14 Jan 2014 12:24:11 -0500
From: "Igoe, Kevin M." <kmigoe@nsa.gov>
To: 'Dan Brown' <dbrown@certicom.com>, Watson Ladd <watsonbladd@gmail.com>
Thread-Topic: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid v Pseudorandom
Thread-Index: Ac8QtEhLa4qQ887tT6aHk4eH+te9FQAjD+Ng
Date: Tue, 14 Jan 2014 17:24:10 +0000
Message-ID: <3C4AAD4B5304AB44A6BA85173B4675CABA9A20E7@MSMR-GH1-UEA03.corp.nsa.gov>
References: <20140113230750.6111382.6841.8590@certicom.com>
In-Reply-To: <20140113230750.6111382.6841.8590@certicom.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-originating-ip: [10.215.225.46]
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: base64
MIME-Version: 1.0
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid v Pseudorandom
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Tue, 14 Jan 2014 17:24:29 -0000

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:cfrg-bounces@irtf.org] On Behalf Of Dan Brown
> Sent: Monday, January 13, 2014 6:08 PM
> To: Watson Ladd
> Cc: cfrg@irtf.org
> 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: cfrg@irtf.org
> Subject: Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid v
> Pseudorandom
> 
> 
> On Mon, Jan 13, 2014 at 8:55 AM, Dan Brown <dbrown@certicom.com>; 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
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg