Re: [Cfrg] ECC desiderata

["Paterson, Kenny" <[e-mail]>]

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" <[e-mail]> 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.
>