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
- [Cfrg] [CFRG] Safecurves v Brainpool / Rigid v Ps… Dan Brown
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … Watson Ladd
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … Dan Brown
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … Alyssa Rowan
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … Watson Ladd
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … Michael Hamburg
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … Paul Lambert
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … Watson Ladd
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … Paul Lambert
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … Manuel Pégourié-Gonnard
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … Dan Brown
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … Igoe, Kevin M.
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … Mike Hamburg
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … Dan Brown
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … David McGrew
- [Cfrg] publishing drafts (was: Re: [CFRG] Safecur… David McGrew
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … Alyssa Rowan
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … Paul Lambert
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … Watson Ladd
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … David McGrew
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … Watson Ladd
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … Igoe, Kevin M.
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … Dan Brown
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … Manuel Pégourié-Gonnard
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … David McGrew
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … Johannes Merkle
- [Cfrg] NUMs/rigidity security (Re: [CFRG] Safecur… Adam Back
- Re: [Cfrg] NUMs/rigidity security (Re: [CFRG] Saf… David McGrew
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … David McGrew
- Re: [Cfrg] NUMs/rigidity security (Re: [CFRG] Saf… Adam Back