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

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

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 56EAB1AE143 for <>; Tue, 14 Jan 2014 09:24:29 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -7.438
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 ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id EfT0lMHKYyV9 for <>; Tue, 14 Jan 2014 09:24:25 -0800 (PST)
Received: from ( []) by (Postfix) with ESMTP id CC1B81AE155 for <>; Tue, 14 Jan 2014 09:24:24 -0800 (PST)
X-TM-IMSS-Message-ID: <>
Received: from ([]) by ([]) 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 ([]) by ([]) with mapi id 14.02.0342.003; Tue, 14 Jan 2014 12:24:11 -0500
From: "Igoe, Kevin M." <>
To: 'Dan Brown' <>, Watson Ladd <>
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: <>
References: <>
In-Reply-To: <>
Accept-Language: en-US
Content-Language: en-US
x-originating-ip: []
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: base64
MIME-Version: 1.0
Cc: "" <>
Subject: Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid v Pseudorandom
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-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 [] On Behalf Of Dan Brown
> Sent: Monday, January 13, 2014 6:08 PM
> To: Watson Ladd
> Cc:
> 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:
> Subject: Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid v
> Pseudorandom
> On Mon, Jan 13, 2014 at 8:55 AM, Dan Brown <> 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
> >
> >
> >
> >
> >
> > <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