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

Paul Lambert <paul@marvell.com> Tue, 14 January 2014 02:38 UTC

Return-Path: <paul@marvell.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 1452B1AE1C8 for <cfrg@ietfa.amsl.com>; Mon, 13 Jan 2014 18:38:15 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.567
X-Spam-Level:
X-Spam-Status: No, score=-1.567 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, IP_NOT_FRIENDLY=0.334, SPF_PASS=-0.001] autolearn=no
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 SSSgK9Co_t4i for <cfrg@ietfa.amsl.com>; Mon, 13 Jan 2014 18:38:12 -0800 (PST)
Received: from mx0a-0016f401.pphosted.com (mx0a-0016f401.pphosted.com [67.231.148.174]) by ietfa.amsl.com (Postfix) with ESMTP id 0F5AD1ADFE4 for <cfrg@irtf.org>; Mon, 13 Jan 2014 18:38:12 -0800 (PST)
Received: from pps.filterd (m0045849.ppops.net [127.0.0.1]) by mx0a-0016f401.pphosted.com (8.14.5/8.14.5) with SMTP id s0E2c0Ih003624; Mon, 13 Jan 2014 18:38:00 -0800
Received: from pps.reinject (localhost [127.0.0.1]) by mx0a-0016f401.pphosted.com with ESMTP id 1hb0qa08eb-1 (version=TLSv1/SSLv3 cipher=AES256-SHA bits=256 verify=NOT); Mon, 13 Jan 2014 18:37:59 -0800
Received: from m0045849.ppops.net (m0045849.ppops.net [127.0.0.1]) by pps.reinject (8.14.5/8.14.5) with SMTP id s0E2bx6R003619; Mon, 13 Jan 2014 18:37:59 -0800
Received: from sc-owa.marvell.com ([199.233.58.135]) by mx0a-0016f401.pphosted.com with ESMTP id 1hb0qa08e5-13 (version=TLSv1/SSLv3 cipher=AES128-SHA bits=128 verify=NOT); Mon, 13 Jan 2014 18:37:59 -0800
Received: from SC-vEXCH2.marvell.com ([10.93.76.134]) by SC-OWA.marvell.com ([::1]) with mapi; Mon, 13 Jan 2014 18:37:57 -0800
From: Paul Lambert <paul@marvell.com>
To: Watson Ladd <watsonbladd@gmail.com>
Date: Mon, 13 Jan 2014 18:37:56 -0800
Thread-Topic: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid v Pseudorandom
Thread-Index: Ac8QyUaM3NrzVOH3TRC9Hirsc8CyyQAB1J7A
Message-ID: <7BAC95F5A7E67643AAFB2C31BEE662D018B7ED78AF@SC-VEXCH2.marvell.com>
References: <20140113230750.6111382.6841.8590@certicom.com> <CACsn0cmNSU3mmLfPnee-1w9k7p_ypTDYiu2hkAvzU0Pxvudt0w@mail.gmail.com> <7BAC95F5A7E67643AAFB2C31BEE662D018B7ED786D@SC-VEXCH2.marvell.com> <CACsn0cnzxj9+S5MR71Wdj9oic+m64aXENWWfCQs2M83r+zEo8A@mail.gmail.com>
In-Reply-To: <CACsn0cnzxj9+S5MR71Wdj9oic+m64aXENWWfCQs2M83r+zEo8A@mail.gmail.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
acceptlanguage: en-US
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: base64
MIME-Version: 1.0
X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10432:5.11.87, 1.0.14, 0.0.0000 definitions=2014-01-14_01:2014-01-14, 2014-01-14, 1970-01-01 signatures=0
X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 spamscore=0 suspectscore=0 phishscore=0 adultscore=0 bulkscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=7.0.1-1305240000 definitions=main-1401130211
Cc: Dan Brown <dbrown@certicom.com>, "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 02:38:15 -0000

> >
> > Curves based on 'new ECC math' for Edwards curves shows significant
> > potential for more efficient and easier implementations (I include
> > side channel protection under easier implementations).  A major
> > challenge we have is to provide clarity that we are introducing new
> > math ways to make calculations on elliptic curves.  The Small
> > Weierstrass curves have been so dominate in literature and standards
> > that they are described as 'the' elliptic curve.
> 
> 'New'. I'm sorry, but Montgomery form is from 1985.
> Granted that's a century after Weierstrass form, but it actually is
> contemporaneous with ECC being invented.

Not intended to be disparaging ... just true that they are new in standards.
I agree that the math has some history, but the standards
have been completely inbred with just Small Weierstrass equations.
Only point is that it's not the same jump of NIST to Brainpool 
(only tweaking a few domain parameters in an implementation).

There is a extra effort and diligence required to fill in the
gaps in our recommendations.

> 
> If the fact that the equations look different doesn't tip someone off
> to the difference, I'm not sure what will. Do we need great big
> flashing lights *this is not in short Weierstrass form*? And what does
> it say about our implementors that they do not know the basics of the
> algorithms they are asked to implement?
> 
> >
> > I am very supportive of our introduction of these families of new
> > curves.  Speed and ease of correct/secure implementation are
> > significant benefits of the 'new math'.
> >
> > So ... on choices, we can strongly recommend based on the benefits.
> > Suite B will live on for a long time based on the slow pace of
> > Government initiatives.
> >
> > Brainpool, the previous fashionable alternative seems less
> fashionable today.
> >
> > Edwards based curves seem an optimal choice where new curves are able
> > to be introduced. They are both fashionable (not NIST) and have
> > demonstrable benefits.
> >
> >
> > Now ... the current draft does seem confusing to me in this context
> on
> > benefits and clear curve recommendations.  There are a few too many
> > and we could trim or clarify when each would be used.
> 
> Feel free to make suggestions offlist. In fact, you can even submit
> diffs.
Perhaps ... after I get my implementation to work.

I'm having trouble understanding the literatures recommendations for multiplying ...


Paul

> 
> Sincerely,
> Watson Ladd
> >
> > Paul
> >
> >> >
> >> > 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.
> >
> >
> >>
> >> What about the known attacks which Brainpool implementations suffer
> >> from? There still isn't a side-channel clean one that gets correct
> >> answers all the time. Contrast with NIST and the new curves. (Yes,
> we
> >> need to churn out some code, but it's clear it can be done). I
> admire
> >> your persistence in necroequoflagellation,  but as DJB observed the
> >> previous time this came up, you've simply declared 486662 special,
> >> with no evidence that the curve is actually special.
> >> If you noticed a particularly unusual endomorphism, or an
> interesting
> >> map to some other scheme, or the Q-lift having unusually large rank,
> >> or an infinite Tate-Sharavich group, that would be reason to worry
> or
> >> consider it special. But the coefficient being small?
> >> What's so special about that?
> >>
> >> >
> >> > 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.
> >>
> >> These people should not be listened to: the world does not need more
> >> short Weierstrass curves. Pick rigid Edwards curves over the same
> >> field, and make a small for speed. I understand the field
> >> proliferation concern, particularly for hardware, but that's where a
> >> lot of speed comes from: ask AGL or Rich Salz how much speed they
> want to give up.
> >> We have Rich Salz on record as saying that Akamai is held back from
> >> PFS by the CPU demand, and with Curve25519 that will be solved. In
> >> software additional fields cost little.
> >>
> >> >
> >> > 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.
> >>
> >> Interop solution: MTI. Odds are people will pick a hardness, and the
> >> fastest thing that delivers that hardness will win out. Also, make
> >> clear standards can exclude curves, even to the extent of picking
> one
> >> and saying "This is it!". I think the majority of protocols where
> >> performance in software is a concern and correctness of
> >> implementation an issue should consider Curve25519 carefully, but I
> >> am not going to argue that I know better than the communities around
> >> these protocols what is appropriate for the hardware they are
> looking
> >> at running on and the constraints they face. Some protocols will
> need
> >> to dispense with choices because of these limitations I am going to
> >> argue that I know cryptography better than they do in most cases,
> and
> >> that's how I see this question: making a catalog of curves, where
> you
> >> can reach in and go "Oh, this one has high software performance,
> >> acceptable hardware performance, good security, useful for ECDH" or
> >> "This one is great in hardware, ok in software, moderate security
> >> (and some gotchas), all protocols" and make a choice easily.
> >>
> >> Sincerely,
> >> Watson Ladd
> >>
> >> >
> >> >
> >> > 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.
> >>
> >>
> >>
> >> --
> >> "Those who would give up Essential Liberty to purchase a little
> >> Temporary Safety deserve neither  Liberty nor Safety."
> >> -- Benjamin Franklin
> >> _______________________________________________
> >> Cfrg mailing list
> >> Cfrg@irtf.org
> >> http://www.irtf.org/mailman/listinfo/cfrg
> 
> 
> 
> --
> "Those who would give up Essential Liberty to purchase a little
> Temporary Safety deserve neither  Liberty nor Safety."
> -- Benjamin Franklin