[Cfrg] Criteria for the selection of new ECC mechanisms

David McGrew <mcgrew@cisco.com> Tue, 29 April 2014 14:37 UTC

Message-ID: <535FB927.8080909@cisco.com>
Date: Tue, 29 Apr 2014 10:37:27 -0400
From: David McGrew <mcgrew@cisco.com>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/20131103 Icedove/17.0.10
MIME-Version: 1.0
To: "cfrg@irtf.org" <cfrg@irtf.org>
Content-Type: text/plain; charset="ISO-8859-1"; format="flowed"
Content-Transfer-Encoding: 7bit
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/5HqjPeqU0pFoU7P8QWiIC6X4LEc
Subject: [Cfrg] Criteria for the selection of new ECC mechanisms
Precedence: list

Hi CFRG,

in order to frame the discussion in today's meeting, I wrote up criteria 
for new ECC mechanisms.  I will go over this briefly in today's 
meeting.   Hopefully, this will foster good understanding about what the 
important goals are, and a good discussion about how to meet our common 
goals.  Comments are welcome, especially when they come with suggested 
text and a reference, where appropriate.

David

----

Criteria for the selection of new ECC mechanisms
David McGrew
April 28, 2014

This short note summaries the criteria that have been put forward for
new ECC mechanisms, using the requirements language typical of
standards processes.  Each criterion is identified as either required
(strictly necessary) or desired (not strictly necessary, but strongly
appealing).  Some criteria apply only to key exchange methods (and not
to signatures) or Password Authenticated Key Exchange (PAKE), and are
labeled as such.  The Safecurves web page is an outstanding resource
for security criteria, though it does not distinguish between
properties that are essential for key exchange and those for
signatures.  Sources are described in footnotes; this note aims to be
objective, but the author's opinion is reflected in some choices.

The following criteria have been identified:

Simplicity

    R1.  Desired: easy to understand and implement [1]

Efficiency

    R2.  Required: amenable to compact implementations and fast
    implementations, across both small and large processors [1]

    R3.  Desired: re-use components between signatures and key exchange
    algorithms [3]

Intellectual Property

    R4.  Required: available worldwide under reasonable and well
    understood licensing terms [1]

    R5.  Desired: available worldwide under royalty-free licensing
    terms [1]

Interoperability

    R6.  Desired: can be used with current software implementations
    (using different curve parameters) of TLS, PKIX, SSH, and IKE [4]

    R7.  Desired: can be used within current ECC standards of TLS,
    PKIX, SSH, and IKE [4]

Security

    R8.  Required: amenable to constant-time implementations, to avoid
    side channel attacks [2]

    R9.  Required: resist twist attacks [2]

    R10.  Required: curve parameters should have good provenance;
    random curves should be provably pseudorandom [5]

    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.)

    R12.  Required for PAKE: indistinguishability of curve points from
    random strings [2]

Footnotes:

    [1] Original criteria set out for the Advanced Encryption Standard,
        which is equally applicable to ECC.  National Institute of
        Standards and Technology (NIST) of the United States, 1998.

    [2] Daniel J. Bernstein and Tanja Lange. SafeCurves: choosing safe
        curves for elliptic-curve cryptography.
        http://safecurves.cr.yp.to, accessed April 2014.

    [3] Criteria identified by David McGrew, 2014.

    [4] Criteria identified by Russ Housley, TLS WG meeting at IETF89.

    [5] Criteria widely acknowledged on CFRG email list during 2014.

Re: [Cfrg] Criteria for the selection of new ECC … Rene Struik
Re: [Cfrg] Criteria for the selection of new ECC … Michael Hamburg
[Cfrg] Criteria for the selection of new ECC mech… David McGrew
Re: [Cfrg] Criteria for the selection of new ECC … David McGrew
Re: [Cfrg] Criteria for the selection of new ECC … David McGrew
Re: [Cfrg] Criteria for the selection of new ECC … Rene Struik
Re: [Cfrg] Criteria for the selection of new ECC … Michael Hamburg
Re: [Cfrg] Criteria for the selection of new ECC … David McGrew
Re: [Cfrg] Criteria for the selection of new ECC … Michael Hamburg
Re: [Cfrg] Criteria for the selection of new ECC … Dan Harkins
Re: [Cfrg] Criteria for the selection of new ECC … Rene Struik
Re: [Cfrg] Criteria for the selection of new ECC … Paul Lambert
Re: [Cfrg] Criteria for the selection of new ECC … Johannes Merkle