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