Re: [Cfrg] ECC desiderata

"Paterson, Kenny" <> Fri, 08 August 2014 18:08 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id E440F1B2CAC for <>; Fri, 8 Aug 2014 11:08:46 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2.602
X-Spam-Status: No, score=-2.602 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_LOW=-0.7, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=ham
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id 7Vw88mPuGFav for <>; Fri, 8 Aug 2014 11:08:40 -0700 (PDT)
Received: from ( []) (using TLSv1 with cipher ECDHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id EC7E81A0021 for <>; Fri, 8 Aug 2014 11:08:39 -0700 (PDT)
Received: from ( by ( with Microsoft SMTP Server (TLS) id 15.0.1005.10; Fri, 8 Aug 2014 18:08:37 +0000
Received: from ([]) by ([]) with mapi id 15.00.1005.008; Fri, 8 Aug 2014 18:08:37 +0000
From: "Paterson, Kenny" <>
To: "D. J. Bernstein" <>, "" <>
Thread-Topic: [Cfrg] ECC desiderata
Thread-Index: AQHPsyL4KE0zW1XBXkWO7nNCXXVftZvHEgOA
Date: Fri, 08 Aug 2014 18:08:37 +0000
Message-ID: <>
References: <>
In-Reply-To: <>
Accept-Language: en-GB, en-US
Content-Language: en-US
user-agent: Microsoft-MacOutlook/
x-originating-ip: []
x-microsoft-antispam: BCL:0;PCL:0;RULEID:;UriScan:;
x-forefront-prvs: 02973C87BC
x-forefront-antispam-report: SFV:NSPM; SFS:(6009001)(66654002)(479174003)(52604005)(51704005)(189002)(199002)(24454002)(83506001)(105586002)(107046002)(19580405001)(19580395003)(83322001)(15975445006)(20776003)(95666004)(99396002)(106116001)(64706001)(50986999)(21056001)(81342001)(76176999)(54356999)(85306004)(36756003)(81542001)(66066001)(80022001)(4396001)(2656002)(87936001)(83072002)(85852003)(86362001)(92726001)(92566001)(74662001)(77982001)(15202345003)(561944003)(101416001)(107886001)(74482001)(79102001)(74502001)(106356001)(76482001)(46102001)(31966008)(2501001); DIR:OUT; SFP:; SCL:1; SRVR:DBXPR03MB381;; FPR:; MLV:sfv; PTR:InfoNoRecords; MX:1; LANG:en;
Content-Type: text/plain; charset="utf-8"
Content-ID: <>
Content-Transfer-Encoding: base64
MIME-Version: 1.0
Subject: Re: [Cfrg] ECC desiderata
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: Fri, 08 Aug 2014 18:08:47 -0000


Many thanks for providing this detailed view of requirements as part of
the ongoing discussion - it's very helpful as our "requirements" phase
draws to a close.

We will wait a couple more days for comment on this and the other recent
messages on the list - including your forthcoming message about Brian
LaMacchia's post from yesterday



On 08/08/2014 17:07, "D. J. Bernstein" <> wrote:

>Suggestions are summarized at the bottom. These are mainly tweaks to the
>list suggested by David McGrew and discussed by quite a few people. I'll
>send a separate message to comment on Brian's new list from yesterday.
>Benjamin Black writes:
>> Performance must be measured using "production-quality"
>> implementations. By this I mean implementations which employ the sort
>> of techniques/optimizations appropriate for large scale deployment.
>Surely everyone would agree that we want crypto implementations to be
>secure, and in particular to
>   * work correctly for all valid inputs, and
>   * avoid compromising security when inputs are invalid, and
>   * avoid all data flow from secrets to timing.
>Would anyone argue that an implementation flunking these requirements
>is "production-quality" or "appropriate for large scale deployment"?
>On the other hand, there clearly isn't agreement that crypto should
>   * be written in JavaScript, or
>   * trust typical compilers, or
>   * avoid vector intrinsics, or
>   * avoid assembly language, or
>   * be written as "completely portable" code,
>even though for each of these items I've seen people in various venues
>vociferously arguing that the item is critical for "production" or
>"deployment" or some similar phrase. As an example of the subtlety of
>these issues, the strongest formally verified guarantees available today
>for ECC software are for software written in assembly language, and this
>situation is likely to persist.
>I think it's perfectly legitimate to ask how much simplicity is
>sacrificed from, e.g., having F_p arithmetic tuned separately for Intel
>chips and for ARM chips. However, for many people the resulting speedups
>are more important than the loss of simplicity, and it would be crazy to
>demand that those people ignore those speedups just because someone else
>refers to multiple implementations as not being "appropriate for large
>scale deployment".
>I conclude that the concept of "production-quality" should not appear in
>a list of ECC requirements (or desiderata): it includes some items that
>are uncontroversial but other items that compromise security and speed.
>David McGrew writes:
>> R8.  Required: amenable to constant-time implementations, to avoid
>> side channel attacks [2]
>I don't think that "amenable" works as a yes/no requirement: every
>cryptographic function _can_ be implemented in constant time. What we
>care about is how simple and fast the resulting implementations are---
>and the extent to which non-constant-time implementations would have
>been simpler or faster, creating bad incentives for implementors.
>I'd suggest stating the core desiderata as follows (where "secure"
>includes the first three items I listed above):
>   D1. Speed and simplicity (and speed-simplicity combinations) for
>   secure implementations.
>   D2. Avoiding speed incentives and simplicity incentives towards
>   insecure implementations.
>Curves with cofactor 1 obviously score so badly on these axes---without
>having any compensating advantages---that I think they should be taken
>off the table. Each new curve should have a unique point of order 2 and
>points of order 4, for compatibility with the Montgomery ladder and
>complete Edwards addition. Such curves should still be quantitatively
>evaluated against the same desiderata.
>> R2.  Required: amenable to compact implementations and fast
>> implementations, across both small and large processors [1]
>I again don't think that "amenable" works as a yes/no requirement. The
>processor comment applies to any mention of speed (e.g., both D1 and
>D2 above), so I'd suggest turning R2 into a modular statement:
>   "Speed" includes speed on many different platforms: e.g., speed on
>   64-bit desktop CPUs, speed on 32-bit smartphone CPUs, speed on
>   embedded microcontrollers, and speed of hardware implementations.
>As for "compact": Obviously small implementations can contribute to
>speed (avoiding cache misses, fitting into available chip area for a
>hardware accelerator, etc.), and there's a huge correlation between
>compactness and simplicity. Is there an argument to identify compactness
>per se as a separate desideratum---something where compactness will help
>select ECC mechanisms in ways that simplicity and speed won't?
>> R3.  Desired: re-use components between signatures and key exchange
>> algorithms [3]
>I would suggest naming more of the important operations:
>   "Speed" includes speed of many important ECC operations inside TLS,
>   PKIX, SSH, IKE, and other protocols: e.g., key generation, signing,
>   verification, and DH shared-secret computation. "Simplicity" includes
>   the simplicity of implementations supporting all of these operations,
>   the simplicity of implementations supporting only DH, the simplicity
>   of implementations supporting only signatures, etc.
>It's important for the metric to be simplicity rather than reuse. For
>example, it's obviously much better to have
>   * complexity 300 for DH implementation (keygen+sharedsecret)
>   * complexity 500 for signatures implementation (keygen+sign+verify)
>   * complexity 600 for combined implementation
>than to have
>   * complexity 10000 for DH implementation
>   * complexity 10000 for signatures implementation
>   * complexity 11000 for combined implementation
>even though the second option would score better on any "reuse" metric.
>> R1.  Desired: easy to understand and implement [1]
>This is one aspect of simplicity. Is there evidence that different types
>of ECC simplicity are in conflict? If not then I'd suggest simply saying
>"simplicity" and not getting caught up in weighing the details.
>> R9.  Required: resist twist attacks [2]
>The reason that this is important is that
>   * _with_ twist-security the simplest secure DH implementation is the
>     Montgomery ladder, while
>   * _without_ twist-security the simplest secure DH implementation is
>     the Montgomery ladder _plus_ checking that the input is on the
>     curve---omitting the check produces security problems.
>I think this is adequately covered by D2 ("Avoiding speed incentives and
>simplicity incentives towards insecure implementations"). Furthermore,
>if someone comes up with an argument that twist-security is outweighed
>by something else then D2 will handle the variation better than a
>separate requirement would.
>> R11.  Desired for key exchange: resist invalid curve attacks [2];
>> note that complete addition laws help and are thus desirable [2].
>> (Note that the use of ephemeral keys also resist such attacks.)
>This was later clarified as covering "implementation attacks in general,
>not just invalid curve attacks"; and again I think this is covered by D1
>and D2.
>> R12.  Required for PAKE: indistinguishability of curve points from
>> random strings [2]
>I see indistinguishability as being more important for simplifying
>anti-censorship protocols than for simplifying PAKE protocols. However,
>I would suggest that CFRG not bother making separate requirements along
>these lines, primarily because I don't see how it could actually end up
>making a difference in CFRG's selection of ECC mechanisms.
>> R6.  Desired: can be used with current software implementations
>> (using different curve parameters) of TLS, PKIX, SSH, and IKE [4]
>Suppose an implementation is limited to the NIST P-256 prime---including
>the ECDSA-specified NIST P-256 reduction procedure, which looks quite
>different from the reduction procedure for better primes. Does CFRG want
>this implementor objecting to any prime other than the NIST P-256 prime,
>on the basis of the code changes required?
>Obviously there is some value in being able to reuse existing code. For
>example, suppose
>   * a server wants the speed benefits of optimized code for a new
>     curve, or the security benefits of simple code for that new curve,
>     or both; and
>   * the client already has secure code, doesn't care about speed, and
>     can support the new curve with a very small code change, making the
>     server happy.
>This code reuse can allow faster deployment than demanding a more
>serious code change from the client. However, if the client's existing
>code is _not_ secure, then it's actually better for security to pressure
>the client to throw that code away.
>Let me suggest a different way to handle R6:
>   "Simplicity" includes the simplicity of new implementations, and the
>   simplicity of modifying preexisting implementations.
>This works nicely with both D1 and D2. For example, if it's simple to
>modify a preexisting implementation to obtain a secure implementation of
>a new ECC mechanism---for example, "using different curve parameters"
>without further effort---then that's positively valued under D1. If it's
>simpler to modify a preexisting implementation to obtain an _insecure_
>implementation, then that's negatively valued under D2.
>> R7.  Desired: can be used within current ECC standards of TLS,
>> PKIX, SSH, and IKE [4]
>As a desideratum for new _curves_ this is content-free: all of the
>proposed _curves_ can be used with the existing standards. See my
>"curves, coordinates, and computations" message.
>My understanding is that CFRG isn't considering replacement _algorithms_
>such as Schnorr signatures. However, there are strong reasons for CFRG
>to consider recommending better _coordinates_ on the wire, because this
>has clear benefits for simplicity of implementations. Obviously this has
>a transition cost---but the whole reason for CFRG to consider it is that
>it's desirable _despite_ this cost!
>Something to keep in mind is that the cost of redeploying software has
>very little to do with the amount of code changed. There isn't some
>magical dividing line between deploying a new curve with an old
>coordinate system and deploying a new curve with a new coordinate
>system. Both of these are code changes (including whatever protocol
>extensions are necessary) and incur very similar deployment costs.
>Something else to keep in mind is that only a small fraction of the
>Internet is cryptographically protected today. This suggests that CFRG
>should put a high value on simplifying new implementations that will do
>a better job at protecting the Internet than today's implementations.
>David Jacobson writes:
>> Performance needs to be measured with the defenses deployed.
>Right. D1 makes this explicit ("Speed ... for secure implementations").
>As I wrote earlier, there are two reasons to highlight timing attacks
>rather than power attacks, EM attacks, acoustic attacks, etc.: first,
>timing is naturally visible through the Internet; second, I highly doubt
>that considering side-channel attacks beyond timing will affect any
>curve decisions. All of the major sources of timing variation in
>software are documented in various attack papers and defense papers
>(despite the caveat in
>Simon Josefsson writes:
>> Instead of R8-R11, I suggest to summarize this more generally as:
>> R8'. Required: the solution should be secure against reasonable and
>> well-understood threats, including (but not limited to and necessarily
>> not all of) brute-force, side-channel, invalid-curve, twist attacks, or
>> maliciously chosen curve parameters.
>Every proposal will be resistant to brute-force attacks, side-channel
>attacks (with enough implementation effort), invalid-input attacks (with
>enough implementation effort), and twist attacks (with enough
>implementation effort). But this has a cost, in speed and in simplicity,
>and the variations in these costs are exactly what make some proposals
>better than others.
>Michael Hamburg writes:
>> complete addition laws should probably be on the list as nice-to-have
>The importance of a complete addition law is that it allows a simpler
>secure implementation of (e.g.) signature verification. This is
>analogous to twist-security and is similarly covered by D2.
>> it’s important that the constructs should allow relatively simple
>> and efficient secure implementations.
>Agreed (and David also indicated that he agrees). This is what I'm
>labelling D1.
>Putting all of this together, I'd suggest replacing R1+R2+R3,
>R6+R7+R8+R9, and R11+R12 with the statement of desiderata shown below.
>D1. Speed and simplicity (and speed-simplicity combinations) for
>secure implementations.
>D2. Avoiding speed incentives and simplicity incentives towards insecure
>"Secure" includes the following properties: an implementation works
>correctly for all valid inputs; avoids compromising security when
>inputs are invalid; and avoids all data flow from secrets to timing.
>"Speed" includes speed on many different platforms: e.g., speed on
>64-bit desktop CPUs, speed on 32-bit smartphone CPUs, speed on
>embedded microcontrollers, and speed of hardware implementations.
>"Speed" includes speed of many important ECC operations inside TLS,
>PKIX, SSH, IKE, and other protocols: e.g., key generation, signing,
>verification, and DH shared-secret computation. "Simplicity" includes
>the simplicity of implementations supporting all of these operations,
>the simplicity of implementations supporting only DH, the simplicity
>of implementations supporting only signatures, etc.
>"Simplicity" includes the simplicity of new implementations, and the
>simplicity of modifying preexisting implementations.