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

[David McGrew <[e-mail]>]

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.

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

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

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

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

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