Re: [Cfrg] ECC desiderata

"Paterson, Kenny" <Kenny.Paterson@rhul.ac.uk> Fri, 08 August 2014 18:08 UTC

Return-Path: <Kenny.Paterson@rhul.ac.uk>
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 E440F1B2CAC for <cfrg@ietfa.amsl.com>; Fri, 8 Aug 2014 11:08:46 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.602
X-Spam-Level:
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 mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 7Vw88mPuGFav for <cfrg@ietfa.amsl.com>; Fri, 8 Aug 2014 11:08:40 -0700 (PDT)
Received: from emea01-db3-obe.outbound.protection.outlook.com (mail-db3lrp0078.outbound.protection.outlook.com [213.199.154.78]) (using TLSv1 with cipher ECDHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id EC7E81A0021 for <cfrg@irtf.org>; Fri, 8 Aug 2014 11:08:39 -0700 (PDT)
Received: from DBXPR03MB383.eurprd03.prod.outlook.com (10.141.10.15) by DBXPR03MB381.eurprd03.prod.outlook.com (10.141.10.11) with Microsoft SMTP Server (TLS) id 15.0.1005.10; Fri, 8 Aug 2014 18:08:37 +0000
Received: from DBXPR03MB383.eurprd03.prod.outlook.com ([10.141.10.15]) by DBXPR03MB383.eurprd03.prod.outlook.com ([10.141.10.15]) with mapi id 15.00.1005.008; Fri, 8 Aug 2014 18:08:37 +0000
From: "Paterson, Kenny" <Kenny.Paterson@rhul.ac.uk>
To: "D. J. Bernstein" <djb@cr.yp.to>, "cfrg@irtf.org" <cfrg@irtf.org>
Thread-Topic: [Cfrg] ECC desiderata
Thread-Index: AQHPsyL4KE0zW1XBXkWO7nNCXXVftZvHEgOA
Date: Fri, 8 Aug 2014 18:08:37 +0000
Message-ID: <D00AD023.29ACF%kenny.paterson@rhul.ac.uk>
References: <20140808160744.7250.qmail@cr.yp.to>
In-Reply-To: <20140808160744.7250.qmail@cr.yp.to>
Accept-Language: en-GB, en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
user-agent: Microsoft-MacOutlook/14.4.3.140616
x-originating-ip: [134.219.227.30]
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; H:DBXPR03MB383.eurprd03.prod.outlook.com; FPR:; MLV:sfv; PTR:InfoNoRecords; MX:1; LANG:en;
Content-Type: text/plain; charset="utf-8"
Content-ID: <83CFF9EB41596F41A19057E161A42A6D@eurprd03.prod.outlook.com>
Content-Transfer-Encoding: base64
MIME-Version: 1.0
X-OriginatorOrg: rhul.ac.uk
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/mrWuWmKlyXbO7yTBB7KhQ6DK14M
Subject: Re: [Cfrg] ECC desiderata
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: Fri, 08 Aug 2014 18:08:47 -0000

Dan,

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

Regards,

Kenny

On 08/08/2014 17:07, "D. J. Bernstein" <djb@cr.yp.to> 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 http://blog.cr.yp.to/20140517-insns.html).
>
>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.
>
>---Dan
>
>
>D1. Speed and simplicity (and speed-simplicity combinations) for
>secure implementations.
>
>D2. Avoiding speed incentives and simplicity incentives towards insecure
>implementations.
>
>"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.
>