Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid v Pseudorandom
Watson Ladd <watsonbladd@gmail.com> Mon, 13 January 2014 21:26 UTC
Return-Path: <watsonbladd@gmail.com>
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 B5C5D1AE1CC for <cfrg@ietfa.amsl.com>; Mon, 13 Jan 2014 13:26:24 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Level:
X-Spam-Status: No, score=-2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, SPF_PASS=-0.001] 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 zvDEtwdEG0dg for <cfrg@ietfa.amsl.com>; Mon, 13 Jan 2014 13:26:22 -0800 (PST)
Received: from mail-wg0-x22d.google.com (mail-wg0-x22d.google.com [IPv6:2a00:1450:400c:c00::22d]) by ietfa.amsl.com (Postfix) with ESMTP id 2F1551AE1C7 for <cfrg@irtf.org>; Mon, 13 Jan 2014 13:26:22 -0800 (PST)
Received: by mail-wg0-f45.google.com with SMTP id n12so3594195wgh.12 for <cfrg@irtf.org>; Mon, 13 Jan 2014 13:26:10 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; bh=zaH3lv6lpBRvd9ZpL1xnOXLeZ+Dpl4t4MX0IfljENDU=; b=mkelnDDkRSnknqoHiXKMsZceJXkFEXjgijZe7s5fcoBHw4IZooKoHVhFxCWVOUaeJD BfnZ/Kdre4eOQONipygVY6LCrZHH8NtTb6d/44NifI+z2vGfMCLuwWgZIU2iUMS4+QJK bC9ZBNsULBLUsJCZTnpWOc85iZ9/Hj8GIUqnbR3cpJONppdYTklbIqFyrZeIOK94qasI BksUSPLftZNxV6kLhOKm7RhJrfntPlJ+C+hSGIalnrs0v4+J0F2xLJDqV69n61bktc48 9blq/kJjS0EdTuTMv0cqUhjuegTitMAzwqRozYPStEPrP0TlW8UjJPL+WrSL5d+JDuuQ dOvg==
MIME-Version: 1.0
X-Received: by 10.194.189.132 with SMTP id gi4mr23890057wjc.5.1389648370481; Mon, 13 Jan 2014 13:26:10 -0800 (PST)
Received: by 10.194.242.131 with HTTP; Mon, 13 Jan 2014 13:26:10 -0800 (PST)
In-Reply-To: <810C31990B57ED40B2062BA10D43FBF5C1EA1B@XMB116CNC.rim.net>
References: <810C31990B57ED40B2062BA10D43FBF5C1EA1B@XMB116CNC.rim.net>
Date: Mon, 13 Jan 2014 13:26:10 -0800
Message-ID: <CACsn0ck7tEKVqaxyXJ+0T2oeJf=jz7go1cpptrntADtLyWbaaw@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: Dan Brown <dbrown@certicom.com>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
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: Mon, 13 Jan 2014 21:26:24 -0000
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
- [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