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

[Rene Struik <[e-mail]>]

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. 
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. 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.).)
<<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
>
>> 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
>
> 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
>>> [e-mail]
>>> http://www.irtf.org/mailman/listinfo/cfrg
>>
>>
>


-- 
email: [e-mail] | Skype: rstruik
cell: [phone] | US: [phone]