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

From: David McGrew <[email-masked]>
Date: Tue, 29 Apr 2014 10:37:27 -0400

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]

    R9.  Required: resist twist attacks [2]

    R10.  Required: curve parameters should have good provenance;
    random curves should be provably pseudorandom [5]

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

    R12.  Required for PAKE: indistinguishability of curve points from
    random strings [2]

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.

---

From: Rene Struik <[email-masked]>
Date: Tue, 29 Apr 2014 13:10:34 -0400

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:
> 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
>
> ----
>
RS>>
The more general requirement is that constructs should allow secure 
implementations, which stretches much further than constant-time operations.
<<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
>    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
>    (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). 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). 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?)
<<RS

> R12.  Required for PAKE: indistinguishability of curve points from
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

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

-- 
email: [email-masked] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363

---

From: Michael Hamburg <[email-masked]>
Date: Tue, 29 Apr 2014 10:38:48 -0700

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 <[email-masked]> 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
> 
> 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.

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

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

> 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

---

From: David McGrew <[email-masked]>
Date: Tue, 29 Apr 2014 14:21:22 -0400

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.

>> about what the important goals are, and a good discussion about how 
>> to meet our common goals.  Comments are welcome, especially when they 

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?

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

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

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

> 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

---

From: David McGrew <[email-masked]>
Date: Tue, 29 Apr 2014 14:35:31 -0400

Hi Michael,

On 04/29/2014 01:38 PM, Michael Hamburg wrote:
> Hello,
>
> I agree that some of these requirements look like a presort.  More 
> comments inline.

thanks for the quick feedback.

>  I will probably not be in the meeting this afternoon, because my 
> employer is hesitant to agree to IP disclosure rules :-(

sorry to hear that.  The rules should not stop you from listening though :-)

>
> On Apr 29, 2014, at 10:10 AM, Rene Struik <[email-masked] 
> <mailto:[email-masked]>> 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
>>
> 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.
>

Agreed.   I think this is already captured in the requirements; I would 
put it this way: a construct that meets R8 but is slow or complicated 
would not meet R1 or R2.

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

Got it; it sounds like you are Rene are both in the "desired" not 
"required" category on this one.

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

Thanks for reminding me about rigidity, I'll add that text.   It might 
be up to debate, but it is good to at least raise the topic.

>> While intuitively perhaps a nice feature, not sure why this would be 
>> a requirement. Besides, this again seems to presort on solution 
> PAKE support shouldn’t be a requirement,

Agreed, which is why I separated out PAKE considerations.

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

OK, so "required for some PAKE protocols"?   Any suggestions on 
requirements language around anti-censorship applications?

thanks and regards,

David

>>> [email-masked] <mailto:[email-masked]>
>> email:[email-masked] <mailto:[email-masked]>| Skype: 
>> rstruik
>> [email-masked] <mailto:[email-masked]>

---

From: Rene Struik <[email-masked]>
Date: Tue, 29 Apr 2014 14:43:07 -0400

On 4/29/2014 2:21 PM, David McGrew wrote:
> 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
>>> to meet our common goals.  Comments are welcome, especially when 
>>> they come with suggested text and a reference, where appropriate.
>>>
>>> David
>>>
>>> ----
>>>
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
> 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
> 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.
>
>>>
RS>>
The paper I referenced above (HOST 2010) would be a good start, as do 
proceedings of FDTC/CHES/COSADE/CARDES, etc.
<<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

---

From: Michael Hamburg <[email-masked]>
Date: Tue, 29 Apr 2014 11:44:54 -0700

On Apr 29, 2014, at 11:35 AM, David McGrew <[email-masked]> wrote:

>>  I will probably not be in the meeting this afternoon, because my employer is hesitant to agree to IP disclosure rules :-(
> 

Ah, then perhaps I will listen.

>> 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.
> 
> OK, so "required for some PAKE protocols"?   Any suggestions on requirements language around anti-censorship applications?

"Required for some PAKE protocols" is probably good enough.  But at least any elliptic curve can do this with acceptable efficiency loss.  I don’t know about hyperelliptic curves, though.

Cheers,
— Mike

---

From: David McGrew <[email-masked]>
Date: Tue, 29 Apr 2014 14:51:17 -0400

Hi Rene,

On 04/29/2014 02:43 PM, Rene Struik wrote:
>> 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>>

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

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

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

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 will leave this point up to the PAKE devotees.

thanks,

David

---

From: Michael Hamburg <[email-masked]>
Date: Tue, 29 Apr 2014 11:55:39 -0700

On Apr 29, 2014, at 11:43 AM, Rene Struik <[email-masked]> wrote:
> 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

EKE requires indistinguishability.  You do a DH key exchange, but encrypt the ephemerals with the password.  This requires that the ephemerals are encoded in a way that cannot be distinguished from random.  If the adversary starts guessing passwords, then wrong guesses will result in random-looking data (in the ideal cipher model or under assumptions about the KDF).  If the adversary could distinguish the real encoded point from these random points, it would leak information about the password, and over many connections the password would be revealed by a passive attack.

But you can get indistinguishability for any elliptic curve using Tibouchi/BCIMRT’s Elligator Squared.

— Mike

---

From: "Dan Harkins" <[email-masked]>
Date: Tue, 29 Apr 2014 12:02:00 -0700 (PDT)

On Tue, April 29, 2014 11:43 am, Rene Struik wrote:
[snip]
> "requires" indistinguishability, so as to have a proof point?

  EKE.

  Dan.

---

From: Rene Struik <[email-masked]>
Date: Tue, 29 Apr 2014 15:09:42 -0400

Okay, with EKE indeed this would be the case.

Rene

On 4/29/2014 2:55 PM, Michael Hamburg wrote:
>
> On Apr 29, 2014, at 11:43 AM, Rene Struik <[email-masked] 
>> 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
>
> EKE requires indistinguishability.  You do a DH key exchange, but 
> encrypt the ephemerals with the password.  This requires that the 
> ephemerals are encoded in a way that cannot be distinguished from 
> random.  If the adversary starts guessing passwords, then wrong 
> guesses will result in random-looking data (in the ideal cipher model 
> or under assumptions about the KDF).  If the adversary could 
> distinguish the real encoded point from these random points, it would 
> leak information about the password, and over many connections the 
> password would be revealed by a passive attack.
>

---

From: Paul Lambert <[email-masked]>
Date: Tue, 29 Apr 2014 12:32:31 -0700

David,

Great list of criteria.

>can discuss more during the virtual call this afternoon.

I¹d disagree, but see that a few of the criteria could be tuned
slightly to more clearly not imply a specific class of solution.

For example - the criteria that appear to favor Edwards curves
(like twist secure) might be addressed by NIST curves using
other mechanisms.  These mechanisms are not currently documented
and I suggest any curve should be clearly describing ways to mitigate
attacks.

>implementations, which stretches much further than constant-time

Ok.  Please add another criteria.
This one, constant time,  is important. None of the NIST
specifications and recommendations describe side channel resistance
techniques. These could and should be created since we will be
required to use Suite B for some applications.

I¹d suggest a small improvement for R8

R8.  Required: specification must include a constant-time
implementations, to avoid side channel attacks [2]

Amenable is not enough Š someone needs to write it down.

Paul

>many ways to skin a cat or here and providing secure implementations.

Yes Š so the other mitigating techniques (e.g for NIST curves) need
to be documented.

>statement is up to debate.
No.  Random should be clearly random and have traceable provenance.
It might only be debatable because the NIST curves used a very old
process that did not fully show that there was nothing up anyones
sleeves.  NIST curve will fail this requirement, but we should document
this and move on.  FIPS standards will still mandate Suite B even
if the curves fail this criteria.

>If one wishes to go this way, shouldn't one
No.  But if generated randomly, the primes should have clear provenance.

Random primes are a nice to have and could be included if we consider
that having all parameters ³random² might be a desirable criteria.

>points (for which there is an extremely easy and low-cost check).
Yes, if you have other attacks, we should list them all not remove this
one.

> BTW -

---

From: Johannes Merkle <[email-masked]>
Date: Wed, 30 Apr 2014 16:14:02 +0200

Rene Struik wrote on 29.04.2014 20:43:
>> 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
>>>>
>>> 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>>
> Side Channel Resistance - State-of-Art of Secure ECC Implementations, Attacks and Countermeasures (Junfeng Fan, Guo, De
> Mulder, Schaumont, Preneel, Verbauwhede, HOST 2010)
> <<RS

Another good starting point could be the following recommendations (targeted at CC certifications but applicable to
other implementations as well), which have been co-authored by Tanja Lange
https://www.bsi.bund.de/SharedDocs/Downloads/DE/BSI/Zertifizierung/Interpretationen/AIS_46_ECCGuide_e_pdf.pdf

Johannes