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

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

Return-Path: <mcgrew@cisco.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 731AB1A0953 for <cfrg@ietfa.amsl.com>; Tue, 29 Apr 2014 11:51:27 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -9.552
X-Spam-Level:
X-Spam-Status: No, score=-9.552 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, J_CHICKENPOX_21=0.6, RP_MATCHES_RCVD=-0.651, SPF_PASS=-0.001, USER_IN_DEF_DKIM_WL=-7.5] 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 qVNzyEB_YUOM for <cfrg@ietfa.amsl.com>; Tue, 29 Apr 2014 11:51:25 -0700 (PDT)
Received: from alln-iport-3.cisco.com (alln-iport-3.cisco.com [173.37.142.90]) by ietfa.amsl.com (Postfix) with ESMTP id 135A71A094C for <cfrg@irtf.org>; Tue, 29 Apr 2014 11:51:25 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=@cisco.com; l=10448; q=dns/txt; s=iport; t=1398797484; x=1400007084; h=message-id:date:from:mime-version:to:cc:subject: references:in-reply-to:content-transfer-encoding; bh=8jeqLCPRRbGoYsAng7lXrqw18vFijRADFzCpIM0D1Lk=; b=lpLB5CK3oGlHrxF+BR7Lal0hkAV82eI6ZBH2yMlwe2q5xjCT5aJ5Z0sN zQnAuqiSzTecDz9ifOSxmQK3dIjs+kxAQDBoH/EZi9SMGxvKs/oNiGrVE xBuytBZ2Qp6HY1fTWNNovnAKxNM7u1BQFxQNtEGHQVD2FOR54AZy64okW c=;
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AiAFAKvzX1OtJV2d/2dsb2JhbABZgwZPviuHOYElFnSCJQEBAQMBAQEBNTYKAQULCw4KCQ8HDwkDAgECARUwBg0BBQICBRKIHggNyS8XiS+CeiuBGREBUAcYhCEBA5Ueg3KBPIUjjAODTSGBNQ
X-IronPort-AV: E=Sophos;i="4.97,952,1389744000"; d="scan'208";a="39744058"
Received: from rcdn-core-6.cisco.com ([173.37.93.157]) by alln-iport-3.cisco.com with ESMTP; 29 Apr 2014 18:51:23 +0000
Received: from [10.0.2.15] (rtp-mcgrew-8913.cisco.com [10.117.10.228]) by rcdn-core-6.cisco.com (8.14.5/8.14.5) with ESMTP id s3TIpMQ3030935; Tue, 29 Apr 2014 18:51:22 GMT
Message-ID: <535FF4A5.7060502@cisco.com>
Date: Tue, 29 Apr 2014 14:51:17 -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: Rene Struik <rstruik.ext@gmail.com>
References: <535FB927.8080909@cisco.com> <535FDD0A.7070206@gmail.com> <535FEDA2.4090502@cisco.com> <535FF2BB.3050703@gmail.com>
In-Reply-To: <535FF2BB.3050703@gmail.com>
Content-Type: text/plain; charset="ISO-8859-1"; format="flowed"
Content-Transfer-Encoding: 7bit
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/y7FyZC1lXsRL_yIIE2tWIxQKCkg
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
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 18:51:27 -0000

Hi Rene,

On 04/29/2014 02:43 PM, Rene Struik wrote:
> On 4/29/2014 2:21 PM, David McGrew wrote:
>> Hi Rene,
>>
>> On 04/29/2014 01:10 PM, Rene Struik wrote:
>>> Hi David:
>>>
>>> Some preliminary comments below. 
>>
>> great, thanks.
>>
>>> 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.
>>
>> OK.   Note that I took the approach of describing the criteria for 
>> new ECC mechanisms, instead of the criteria for ECC mechanisms 
>> overall.  So I am presupposing that we are interested in something 
>> different than short Weierstrass form ECC as in IEEE P1363.    Not 
>> saying that existing ECC is bad, just that we are investigating 
>> alternatives.
> RS>>
> There is nothing wrong with also considering short-Weierstrass curves. 
> In fact, the Microsoft paper (IACR ePrint 2014-130) explicitly does so. 

Right, and I agree that seems like a worthwhile approach.  Maybe I 
should have said "something different from RFC6090".

> One should wish to engage into new developments not because it is 
> different (there are so many interesting things under the sun...), but 
> because one believes it really buys us something in a substantiated 
> and clearly articulated way. 

Agreed.

> Hence, my preliminary feedback, where I tried to evaluate whether we 
> do not cut off branches from the solution tree without clear support 
> for this.
> <<RS
>>
>>>
>>> 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
>>
>> Just for clarity: you are not disagreeing with R8, just saying that 
>> it doesn't go far enough in expressing the requirements of avoiding 
>> side channels, right?
> RS>>
> In theory, I can imagine that one could have non-constant time 
> implementations that nevertheless do not leak any meaningful info, 
> although, admittedly, I do not recall having seen public papers in 
> that direction. Stipulating point solution requirements re 
> implementation security (constant-time, avoids twisted curve attacks, 
> invalid points, etc.) does not capture the real requirement that we 
> simply want good real-world implementation security. (This is a huge 
> area with many pitfalls and something most CFRG people probably do not 
> closely follow that much (CHES, FDTC, COSADE, CARDES, etc.), but 
> nevertheless, in my mind, present a much higher threat than any 
> algorithmic consideration (besides the obvious), esp. with highly 
> constrained devices deployed in critical infrastructure (internet of 
> things type, sensors, etc.).)

I agree about the scale of the threat, and I think that the more detail 
we can provide around this requirement, the better.

> <<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
>>
>> So, would you be comfortable moving R9 to "desired"?   Are there 
>> other attacks that we should enumerate?
> RS>>
> This is still an area in lots of flux. Well, a good read would be
> Side Channel Resistance - State-of-Art of Secure ECC Implementations, 
> Attacks and Countermeasures (Junfeng Fan, Guo, De Mulder, Schaumont, 
> Preneel, Verbauwhede, HOST 2010)
> <<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
>>
>> I think R10 is a reasonable requirement from the point of view that, 
>> if someone were generating new curves up to our criteria, we would 
>> want that requirement to be met.   Or maybe I am missing some demerit 
>> of randomly generated curves?    I realize that there are nuances 
>> here that I am not capturing, and I look forward to hearing from 
>> others how they think R10 should be rewritten.
>>
>>>>
>>>>    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). 
>>
>> Fair enough; could you help to enumerate those attacks?
> RS>>
> The paper I referenced above (HOST 2010) would be a good start, as do 
> proceedings of FDTC/CHES/COSADE/CARDES, etc.
> <<RS

Agreed.

>>
>>> 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). 
>>
>> I think you are right about ECIES, because the receiver is using a 
>> static (not ephemeral) key.   At least that's the sense I meant for 
>> "ephemeral".
>>
>>> 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?)
>>
>> I meant for R11 to cover implementation attacks in general, not just 
>> invalid curve attacks.  Sorry for the confusion.
>>
>>> <<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
>>
>> Maybe I should say here "required for some PAKE protocols"?
> RS>>
> I think Michael Hamburg also concurred with my note. I fail to see why 
> one cannot possibly get a good PAKE protocol that relies, e.g., on 
> GLV/GLS-friendly curves. Can you give an example of a PAKE scheme that 
> "requires" indistinguishability, so as to have a proof point?
> <<RS

I will leave this point up to the PAKE devotees.

thanks,

David

>>
>> thanks and regards,
>>
>> David
>>
>>>
>>>
>>>
>>> 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
>>>
>>>
>>
>
>