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

[Michael Hamburg <[e-mail]>]

Hello,

I agree that some of these requirements look like a presort.  More comments inline.  I will probably not be in the meeting this afternoon, because my employer is hesitant to agree to IP disclosure rules :-(

On Apr 29, 2014, at 10:10 AM, Rene Struik <[e-mail]> wrote:

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

What’s more, it’s important that the constructs should allow relatively simple and efficient secure implementations.  A curve that has straightforward constant-time complete addition formulas is preferable to one where the complete addition formulas are much slower or more complicated.

Likewise, if a curve is designed for GLS/GLV, it should be possible to exploit this in constant time without losing the GLS/GLV advantages.

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

I agree that we shouldn’t state twist-security as a hard requirement, as there are other defenses.  That said, twist-security isn’t terribly hard to come by even at high security levels, costing perhaps $20 of EC2 compute time for both a curve and a certificate that it’s the first one.  So I don’t see a particularly good reason to use curves without this property unless everyone is generating their own for some reason.

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

This is only a requirement for curves with claimed random parameters.  If the underlying prime is claimed to be random, there should be strong evidence that it was indeed generated at random.  Likewise, if it is non-random, there must be strong evidence of rigidity (it’s the curve with the lowest-in-absolute-value d, mod the first prime in this family of implementation-friendly primes, which satisfies the safety properties).

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

PAKE support shouldn’t be a requirement, and this feature is not even required for PAKE.  SPEKE, SPAKE2EE and Dragonfly don’t even use indistinguishability, just an inverse-samplable map to a large subset of the curve (eg, SWU/BCIMRT or Elligator).  SPAKE2 and JPAKE don’t even use that.  It’s only EKE and anti-censorship applications that use this, and you can use Tibouchi’s “Elligator Squared” (which is actually the same as BCIMRT) on any curve with a small overhead in ciphertext size.

Cheers,
— Mike

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