Re: [Cfrg] Criteria for the selection of new ECC mechanisms

Rene Struik <rstruik.ext@gmail.com> Tue, 29 April 2014 17:10 UTC

Return-Path: <rstruik.ext@gmail.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 EE8EE1A0776 for <cfrg@ietfa.amsl.com>; Tue, 29 Apr 2014 10:10:46 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.4
X-Spam-Level:
X-Spam-Status: No, score=-1.4 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, J_CHICKENPOX_21=0.6, 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 ZeHJBb-cPUdv for <cfrg@ietfa.amsl.com>; Tue, 29 Apr 2014 10:10:45 -0700 (PDT)
Received: from mail-ie0-x22b.google.com (mail-ie0-x22b.google.com [IPv6:2607:f8b0:4001:c03::22b]) by ietfa.amsl.com (Postfix) with ESMTP id 895E11A0663 for <cfrg@irtf.org>; Tue, 29 Apr 2014 10:10:45 -0700 (PDT)
Received: by mail-ie0-f171.google.com with SMTP id to1so560515ieb.16 for <cfrg@irtf.org>; Tue, 29 Apr 2014 10:10:41 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=message-id:date:from:user-agent:mime-version:to:subject:references :in-reply-to:content-type:content-transfer-encoding; bh=WBUbK2tFnCtofYulRBboJHdJ0yGfq38n459R4Z4pKlw=; b=iPEFCZgp60uCACAM+IVJ5CSGzqkOF4n7vDM7W71z5quYdYFbS6mkvCU6di7dng0sBc Yfxu/sAYPgScPClcX7C4OhOUIUiu3C1V3Y8ukKsJ+DOoJmKAHiIxguC4UyEA68UYHrNO 0mRJtY1NV7IQsHbr0pFCBzHirfRuCa4T7KHIznRVtayY+MaNyNc4KLrkwe0+zNjS/3MO kXn7v6794gPS1z0HVRcedTLl60mfpAGFxjkBS7upvUVoTwehLYLTc9+ttYXAPsnsH0Xa PGb3aXg+Wq6YwQGi+Hyb5pUL3+1t4ipG0woKUpfq6UmVs7gONCSG6ZBqUzVmtnCggWho KPmA==
X-Received: by 10.42.232.206 with SMTP id jv14mr24426028icb.52.1398791439940; Tue, 29 Apr 2014 10:10:39 -0700 (PDT)
Received: from [192.168.1.103] (CPE0013100e2c51-CM001cea35caa6.cpe.net.cable.rogers.com. [99.231.3.110]) by mx.google.com with ESMTPSA id p4sm9278119igy.7.2014.04.29.10.10.37 for <multiple recipients> (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Tue, 29 Apr 2014 10:10:39 -0700 (PDT)
Message-ID: <535FDD0A.7070206@gmail.com>
Date: Tue, 29 Apr 2014 13:10:34 -0400
From: Rene Struik <rstruik.ext@gmail.com>
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:24.0) Gecko/20100101 Thunderbird/24.4.0
MIME-Version: 1.0
To: David McGrew <mcgrew@cisco.com>, "cfrg@irtf.org" <cfrg@irtf.org>
References: <535FB927.8080909@cisco.com>
In-Reply-To: <535FB927.8080909@cisco.com>
Content-Type: text/plain; charset="ISO-8859-1"; format="flowed"
Content-Transfer-Encoding: 7bit
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/-2VGmBHygbIddjoD9uJTt7_9FFM
Subject: Re: [Cfrg] Criteria for the selection of new ECC mechanisms
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, 29 Apr 2014 17:10:47 -0000

Hi David:

Some preliminary comments below. Summary: some of the "requirements" you 
state below seem to effectively pre-sort on solution directions, rather 
than stipulating real requirements, which in my mind is undesirable. We 
can discuss more during the virtual call this afternoon.

Rene

On 4/29/2014 10:37 AM, David McGrew wrote:
> 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]
RS>>
The more general requirement is that constructs should allow secure 
implementations, which stretches much further than constant-time operations.
<<RS
>
>    R9.  Required: resist twist attacks [2]
RS>>
This is just and example of a particular implementation attack in a very 
wide spectrum. It would be a shame if this were supposed to rule out any 
non "twist-secure" curves, just because of this stipulation. There are 
many ways to skin a cat or here and providing secure implementations.
<<RS
>
>    R10.  Required: curve parameters should have good provenance;
>    random curves should be provably pseudorandom [5]
RS>>
Indeed, curve parameters should have good provenance. The second 
statement is up to debate. If one wishes to go this way, shouldn't one 
also stipulate that the prime fields underlying a prime curve should be 
generated randomly?
<<RS
>
>    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.)
RS>>
Again, the more general requirement should be that this should resist 
implementation attacks over a very wide spectrum, not just invalid curve 
points (for which there is an extremely easy and low-cost check). BTW - 
Use of ephemeral keys does not necessarily resist invalid curve attacks, 
e.g., in context of ECIES (where one does not check the ephemeral point 
to be valid). Perhaps I am missing something here, but not sure how 
complete addition laws help in thwarting invalid curve attacks. (Do you 
mean that one can keep computing if, e.g., hQ=O, where h is the 
co-factor and Q a received point? For small h=1,2,4, why would this be a 
major design criterium?)
<<RS

> R12.  Required for PAKE: indistinguishability of curve points from
>    random strings [2]
RS>>
While intuitively perhaps a nice feature, not sure why this would be a 
requirement. Besides, this again seems to presort on solution 
directions, since this would prohibit use of, e.g., affine curve points 
(as, e.g., Dragonfly uses). The world is bigger than x-coordinate only 
arithmetic.
<<RS



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.
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg


-- 
email: rstruik.ext@gmail.com | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363