Subject: [Cfrg] Task looming over the CFRG

From: "Igoe, Kevin M." <[email-masked]>
Date: Mon, 5 May 2014 17:58:48 +0000

As most the folks who read this list have noticed, a virtual interim meeting of the CFRG
was held on Tues 29 April to discuss the way forward for elliptic curve cryptography
in the IETF.  This was driven by an earnest plea from the TLS WG for firm guidance from
the CGRG on the selection of elliptic curves for use in TLS.  They need an answer  before
the Toronto IETF meeting in late July.  TLS needs curves for several levels of security (128,
192 and 256), suitable for use in both key agreement and in digital signatures.

*       The consensus of the attendees was that it would be best for TLS to have a single
      "mandatory to implement" curve for each of the three security levels.

*       Though the attendees were reluctant to make a formal commitment, there
      was clearly a great deal of support for the Montgomery curve curve25519 (FYI, the
      25519 refers to the fact that arithmetic is done modulo the prime 2**255 - 19 ).

*       curve25519 only fills one of the three required security levels.  We still need
      curves of size near 384 bits and 512 bits.

*       NIST curves: I doubt TLS will be willing to revisit the question of elliptic curves once the
      CFRG has made their recommendation.  Another option to consider is advising TLS to
      use of the NIST curves in the short term, buying time for the CFRG to do an unrushed
      exploration of the alternatives, drawing academia and other standards bodies into the
      discussion.

P.S.  It has been suggested that the CFRG hold a session at the Crypto conference in
Santa Barbara in an effort to draw in more participation from the academic community.
No guarantees we can pull this off, but it is worth the attempt. Thoughts? Volunteers?

P.P.S. We need to start lining up speakers for the CFRG session at IETF-90 (Toronto).

----------------+--------------------------------------------------
Kevin M. Igoe   | "We can't solve problems by using the same kind
[email-masked]  | of thinking we used when we created them."
                |              - Albert Einstein -
----------------+--------------------------------------------------

---

From: Michael Hamburg <[email-masked]>
Date: Mon, 5 May 2014 11:25:05 -0700

Hi Kevin,

As the designer of an ECC system which is aimed at 224-ish-bit security, I’m curious: is it a firm requirement that the curves be set at 128, 192 and 256 bits?  Or was there consensus in the meeting that the curves should be set at these security levels?  Patrick Longa aimed his talk at these security levels, but I don’t recall this being stated as a requirement.

Cheers,
— Mike

On May 5, 2014, at 10:58 AM, Igoe, Kevin M. <[email-masked]> wrote:

> The consensus of the attendees was that it would be best for TLS to have a single
> “mandatory to implement” curve for each of the three security levels.
>  
> Though the attendees were reluctant to make a formal commitment, there
> 25519 refers to the fact that arithmetic is done modulo the prime 2**255 – 19 ).
>  
> curve25519 only fills one of the three required security levels.  We still need
> NIST curves: I doubt TLS will be willing to revisit the question of elliptic curves once the 
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: Rene Struik <[email-masked]>
Date: Mon, 05 May 2014 14:35:53 -0400

Hi Kevin:

Just a few hours prior to the CFRG Interim, David McGrew suggested some 
criteria for elliptic curves, on which a few comments were received on 
the mailing list. This list was also - very briefly - discussed during 
the Virtual Interim. During the virtual interim, there were 
presentations by various people on curve picks. There was no discussion 
on schemes these curves should be used with (except for plain ECDH).

I think it would be premature to now already draw a conclusion here, 
since there has hardly been time to digest presentations and reflect 
upon this. Any presumed concensus by attendees during the call could 
hardly have been based on reflecting on presented material, since this 
was uploaded x-minutes prior to the meeting and there was no magical 
break during the interim to digest material further. So, what was the 
point of the curve selection criteria strawman and virtual interim 
presentations if the conclusions are already known now?

I would suspect (and raised this on the chat box at the end of the 
interim) that there should be a sequel to this during the IETF-90 
meeting in Toronto (assuming CFRG would indeed meet there).

Best regards, Rene

http://www.ietf.org/mail-archive/web/cfrg/current/msg04461.html

On 5/5/2014 1:58 PM, Igoe, Kevin M. wrote:
> in the IETF. */This /**/was/**/driven by an earnest plea from the TLS 
> WG for firm/**//**/guidance /**/from
> the CGRG /**/on the selection of elliptic curves/**//**/for use in 
> TLS. They need an answer /**/before
> /**/the /**/Toronto/**/IETF meeting i/**/n/**//**/late July/*.  TLS 
> needs curves for several*//*levels of security (128,
> 192 and 256), suitable for use in both key agreement and*//*in digital 
> signatures.
>
>     25519 refers to the fact that arithmetic is done modulo the prime
>     2**255 -- 19 ).
>

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

---

From: Paul Lambert <[email-masked]>
Date: Mon, 5 May 2014 12:09:42 -0700

Hi Rene,

From: Rene Struik <[email-masked]<mailto:[email-masked]>>
Date: Monday, May 5, 2014 at 11:35 AM
To: "Igoe, Kevin M." <[email-masked]<mailto:[email-masked]>>, "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>
Subject: Re: [Cfrg] Task looming over the CFRG

Hi Kevin:

Just a few hours prior to the CFRG Interim, David McGrew suggested some criteria for elliptic curves, on which a few comments were received on the mailing list. This list was also - very briefly - discussed during the Virtual Interim. During the virtual interim, there were presentations by various people on curve picks. There was no discussion on schemes these curves should be used with (except for plain ECDH).

I disagree.  The consensus in the ad hoc was clear.  Discussions on this list are consist with the ad hoc discussion.   The flurry of activity in other working groups also reflects the same consensus to recommend Curve25519.

since there has hardly been time to digest presentations and reflect upon this.

True, but none of the items were new information. Anyone participating in an informed discussion should be familiar will all of the criteria. The collection of the list is valuable and could be the basis of any final formal recommendation.  Expressing the criteria in neutral and fair language that captures the background and importance of each requirement is worthy of it’s own additional effort … but should not delay decisions we make based on our discussions.

We can move forward with a recommendation and continue to use David’s excellent list as the benchmark for rational of the selection.

There was also additional work we need to consider and the ad hoc ran out of time to summarize work items.  Specifically, there are supporting recommendations required to:
 - document the changes in ECDH for cofactors >1
    - this may impact a variety of specifications.

I’m also not clear yet what is the recommendation for digital signatures.   At a minimum, recommendations should be established to make ECDSA deterministic.   Other signature algorithms are possible, but the impact on PKI or alternatives of introducing a new signature algorithm needs some discussion (IMHO).

 I’d like to see a self consistent recommendations that define  key exchanges and signatures for the same curve (or related transformed curve).  PKI interworking to bridge to the new curves would fall out from this set of definitions.

Paul

Any presumed concensus by attendees during the call could hardly have been based on reflecting on presented material, since this was uploaded x-minutes prior to the meeting and there was no magical break during the interim to digest material further. So, what was the point of the curve selection criteria strawman and virtual interim presentations if the conclusions are already known now?

I would suspect (and raised this on the chat box at the end of the interim) that there should be a sequel to this during the IETF-90 meeting in Toronto (assuming CFRG would indeed meet there).

Best regards, Rene

On 5/5/2014 1:58 PM, Igoe, Kevin M. wrote:
As most the folks who read this list have noticed, a virtual interim meeting of the CFRG
was held on Tues 29 April to discuss the way forward for elliptic curve cryptography
in the IETF.  This was driven by an earnest plea from the TLS WG for firmguidance from
the CGRG on the selection of elliptic curves for use in TLS.  They need an answer before
the Toronto IETF meeting inlate July.  TLS needs curves for several levels of security (128,
192 and 256), suitable for use in both key agreement and in digital signatures.

----------------+--------------------------------------------------
Kevin M. Igoe   | "We can't solve problems by using the same kind
[email-masked]<mailto:[email-masked]>  | of thinking we used when we created them."
                |              - Albert Einstein -
----------------+--------------------------------------------------

_______________________________________________
Cfrg mailing list
[email-masked]<mailto:[email-masked]>http://www.irtf.org/mailman/listinfo/cfrg

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

---

From: Rene Struik <[email-masked]>
Date: Mon, 05 May 2014 15:28:59 -0400

Hi Paul:

I do not think there is reason to mute technical discussion, esp. since 
the criteria David McGrew put forward were just a strawman proposal and 
seemed to pre-sort solution directions (see, e.g., Mike Hamburg's 
response Wed last week, April 30th) and did not receive technical 
feedback before. This emphasizes that there may be different 
perspectives on what would be appropriate criteria ("the" criteria as 
you were paraphrasing was simply a set of potential criteria put forward).

FYI - You suggested that "At a minimum, recommendations should be 
established to make ECDSA deterministic". You may wish to have a look at 
RFC 6979 - Deterministic Usage of the Digital Signature Algorithm (DSA) 
and Elliptic Curve Digital Signature Algorithm (ECDSA) (August 2013).

Best regards, Rene

[excerpt of your email of May 5, 2014, 3:09pm EDT]
True, but none of the items were new information. Anyone participating 
in an informed discussion should be familiar will all of the criteria.

On 5/5/2014 3:09 PM, Paul Lambert wrote:
>
> Hi Rene,
>
> From: Rene Struik <[email-masked] <mailto:[email-masked]>>
> To: "Igoe, Kevin M." <[email-masked] <mailto:[email-masked]>>, 
> "[email-masked] <mailto:[email-masked]>" <[email-masked] 
> <mailto:[email-masked]>>
>     Just a few hours prior to the CFRG Interim, David McGrew suggested
>     some criteria for elliptic curves, on which a few comments were
>     received on the mailing list. This list was also - very briefly -
>     discussed during the Virtual Interim. During the virtual interim,
>     there were presentations by various people on curve picks. There
>     was no discussion on schemes these curves should be used with
>     (except for plain ECDH).
>
> I disagree.  The consensus in the ad hoc was clear.  Discussions on 
> this list are consist with the ad hoc discussion.   The flurry of 
> activity in other working groups also reflects the same consensus to 
> recommend Curve25519.
>
> True, but none of the items were new information. Anyone participating 
> in an informed discussion should be familiar will all of the criteria. 
> The collection of the list is valuable and could be the basis of any 
> final formal recommendation.  Expressing the criteria in neutral and 
> fair language that captures the background and importance of each 
> requirement is worthy of it’s own additional effort … but should not 
> delay decisions we make based on our discussions.
>
> We can move forward with a recommendation and continue to use David’s 
> excellent list as the benchmark for rational of the selection.
>
> There was also additional work we need to consider and the ad hoc ran 
> out of time to summarize work items.  Specifically, there are 
> supporting recommendations required to:
> I’m also not clear yet what is the recommendation for digital 
> signatures.   At a minimum, recommendations should be established to 
> make ECDSA deterministic.   Other signature algorithms are possible, 
> but the impact on PKI or alternatives of introducing a new signature 
> algorithm needs some discussion (IMHO).
>
>  I’d like to see a self consistent recommendations that define  key 
> exchanges and signatures for the same curve (or related transformed 
> curve).  PKI interworking to bridge to the new curves would fall out 
> from this set of definitions.
>
> Paul
>
>
>     Any presumed concensus by attendees during the call could hardly
>     have been based on reflecting on presented material, since this
>     was uploaded x-minutes prior to the meeting and there was no
>     magical break during the interim to digest material further. So,
>     what was the point of the curve selection criteria strawman and
>     virtual interim presentations if the conclusions are already known
>     now?
>
>>     in the IETF. */This /**/was/**/driven by an earnest plea from the
>>     TLS WG for firm/**/guidance /**/from
>>     the CGRG /**/on the selection of elliptic curves/**//**/for use
>>     in TLS.  They need an answer /**/before
>>     /**/the /**/Toronto/**/IETF meeting i/**/n/**/late July/*.  TLS
>>     192 and 256), suitable for use in both key agreement and*//*in
>>     digital signatures.
>>
>>     [email-masked]://www.irtf.org/mailman/listinfo/cfrg
>
>
>     -- 
>     email:[email-masked]  | Skype: rstruik

---

From: David McGrew <[email-masked]>
Date: Mon, 05 May 2014 15:37:03 -0400

Hi Michael,

On 05/05/2014 02:25 PM, Michael Hamburg wrote:
> Hi Kevin,
>
> As the designer of an ECC system which is aimed at 224-ish-bit 
> security, I'm curious: is it a firm requirement that the curves be set 
> at 128, 192 and 256 bits?

Eric Rescorla suggested that CFRG recommend a single family of curves, 
as opposed to recommending multiple curves at each security level.   The 
security levels that you mention were his examples, and are good ones in 
my opinion.   But there was no explicit discussion of whether or not 
there should be curves at other security levels.

David

> Or was there consensus in the meeting that the curves should be set at 
> these security levels?  Patrick Longa aimed his talk at these security 
> levels, but I don't recall this being stated as a requirement.
>
> Cheers,
> --- Mike
>
>
> On May 5, 2014, at 10:58 AM, Igoe, Kevin M. <[email-masked] 
> <mailto:[email-masked]>> wrote:
>
>> in the IETF. */This/**/was/**/driven by an earnest plea from the TLS 
>> WG for firm/**//**/guidance/**/from
>> the CGRG/**/on the selection of elliptic curves/**//**/for use in 
>> TLS.  They need an answer/**/before
>> /**/the/**/Toronto/**/IETF meeting i/**/n/**//**/late July/*.  TLS 
>> [email-masked] <mailto:[email-masked]> | of thinking we used when we 
>> created them."
>> |              - Albert Einstein -
>> [email-masked] <mailto:[email-masked]>

---

From: "Igoe, Kevin M." <[email-masked]>
Date: Mon, 5 May 2014 19:49:04 +0000

Mike:

  Being off by a few bits isn't a show stopper. but 32-bits is probably too
much.  The security levels echo the AES security levels of AES-128, AES-192
and AES-256.  Using a 224 bit curve with AES-128 only provides roughly 112-bits
of security versus the 128 bits ostensibly provided by AES-128.  I just want to ensure
that a user who thinks they are getting 128 bits of security gets 128 bits of
security.

                              Kevin

From: Michael Hamburg [mailto:[email-masked]]
Sent: Monday, May 05, 2014 2:25 PM
To: Igoe, Kevin M.
Cc: [email-masked]
Subject: Re: [Cfrg] Task looming over the CFRG

Hi Kevin,

As the designer of an ECC system which is aimed at 224-ish-bit security, I'm curious: is it a firm requirement that the curves be set at 128, 192 and 256 bits?  Or was there consensus in the meeting that the curves should be set at these security levels?  Patrick Longa aimed his talk at these security levels, but I don't recall this being stated as a requirement.

Cheers,
- Mike

On May 5, 2014, at 10:58 AM, Igoe, Kevin M. <[email-masked]<mailto:[email-masked]>> wrote:

_______________________________________________
Cfrg mailing list
[email-masked]<mailto:[email-masked]>
http://www.irtf.org/mailman/listinfo/cfrg

---

From: Paul Lambert <[email-masked]>
Date: Mon, 5 May 2014 13:52:40 -0700

From: Rene Struik <[email-masked]<mailto:[email-masked]>>
Date: Monday, May 5, 2014 at 12:28 PM
To: Paul Lambert <[email-masked]<mailto:[email-masked]>>, "Igoe, Kevin M." <[email-masked]<mailto:[email-masked]>>, "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>
Subject: Re: [Cfrg] Task looming over the CFRG

Hi Paul:

I do not think there is reason to mute technical discussion,
No such intent … just an observation that you hold a minority view point.

On your advocacy … are you proposing that the NIST curves be maintained as the primary recommendation, or do you have other preferences in your curves?

esp. since the criteria David McGrew put forward were just a strawman proposal and seemed to pre-sort solution directions (see, e.g., Mike Hamburg's response Wed last week, April 30th) and did not receive technical feedback before.

Yes … the criteria could be tuned to be more neutral and to have a ranking of importance.  Additional criteria could also be added to make NIST curves more favorable if we are simply creating a score card.  However, I’m not sure the consensus would change.

NIST curves were created over 15 years ago.  NIST has not kept pace in this period with recommendations to mitigate attacks documented by industry.  NIST has not considered the advancements in open cryptographic publications that have identified new curves and algorithms that provide improved performance and better “safety” of implementations.  Patents have expired since the publication of the original NIST recommendations that open new opportunities for license-free security based on elliptic curves.

This emphasizes that there may be different perspectives on what would be appropriate criteria ("the" criteria as you were paraphrasing was simply a set of potential criteria put forward).

Yes.  Like statistics, criteria can be abused to justify a particular result.  I do not see that that was the intent of the list published to this working group.   If you see ways that the criteria could be modified or extended to sway the group to your preferred curve choice, please do be specific and provide a compelling analysis.

FYI - You suggested that "At a minimum, recommendations should be established to make ECDSA deterministic". You may wish to have a look at RFC 6979 - Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA) (August 2013).6979.

Yes, I am very familiar with RFC 6979. This is an informational RFC and provides the procedures and test vectors for “Deterministic ECDSA”.  It is not a “recommendation” or requirement.  This is not a black box testable recommendation since you can not easily tell a truly random the use in ECDSA of: a truly random number, a deterministic number, a back-door predictable deterministic number, etc.   This is an area that NIST has completely failed industry.   Attacks and mistakes in implementations are possible with the NIST ECDSA recommendations.  RFC 6979 helps and “deterministic” techniques should be more strongly codified as a recommendation.

Paul

Best regards, Rene

[excerpt of your email of May 5, 2014, 3:09pm EDT]
True, but none of the items were new information. Anyone participating in an informed discussion should be familiar will all of the criteria.

Hi Rene,

Hi Kevin:

Paul

Best regards, Rene

the Toronto IETF meeting inlate July.  TLS needs curves for severallevels of security (128,

---

From: Michael Hamburg <[email-masked]>
Date: Mon, 5 May 2014 13:55:41 -0700

Kevin,

Sorry to be ambiguous: the curve I designed has a 448-bit field and a 446-bit prime-order subgroup, so a parallel rho attack should cost just under 2^223 point operations on average.  So it sits between the 192 and 256-bit security levels.

I’m not particularly invested in getting this curve into TLS, but I’d like to know whether there’s a point in submitting it for this purpose, or if it will be rejected for having the “wrong security level".

Matching the nominal security level of the asymmetric part to that of the symmetric part sounds obvious on its face, but in fact it is not usually done above the 128-bit level.  For example, Suite B doesn’t specify a direct matching of nominal security levels: it specifies AES-256 with SHA-384 and ECDSA-NIST-p384 for TOP SECRET communications.  Likewise, almost nobody pairs AES-256 with the matching RSA-15k, and even AES-128 is usually paired with the nominally weaker RSA-2048.

This actually makes sense.  Nobody is going to do a 128-bit exhaust for many decades.  Not Google, not the NSA, not the KGB, nobody.  With today’s most efficient supercomputers, the heat output from 2^128 operations would be far more than enough to boil the oceans dry [1].  So we’re talking about defenses against sub-128-bit attacks, and defense in depth against hypothetical advances in cryptography, and quantum resistance for primitives that can resist at all.  Stronger curves, ciphers and hashes will stand or fall on their own, not all together as computer power surpasses their nominal security level.

Also, nobody uses AES-192.

So I don’t think it’s obvious that matching the AES security levels is a requirement.  If the RG thinks it is, or if there’s some obscure legal requirement that the levels match, then fine.  Just describe why.

Cheers,
— Mike

[1] Lenstra, Kleinjung, Thomé.  “Universal security: from bits and mips to pools, lakes — and beyond”.  https://eprint.iacr.org/2013/635.pdf

On May 5, 2014, at 12:49 PM, Igoe, Kevin M. <[email-masked]> wrote:

> Mike:
>  
>   Being off by a few bits isn’t a show stopper. but 32-bits is probably too
> ·         The consensus of the attendees was that it would be best for TLS to have a single
> ·         Though the attendees were reluctant to make a formal commitment, there
> ·         curve25519 only fills one of the three required security levels.  We still need
> ·         NIST curves: I doubt TLS will be willing to revisit the question of elliptic curves once the

---

From: "Blumenthal, Uri - 0668 - MITLL" <[email-masked]>
Date: Mon, 5 May 2014 17:34:53 -0400

IMHO, the logic/reason of matching security levels of the cryptographic algorithms employed in a protocol suite is fairly obvious and does not need an explicit justification. There might be a reason to have the key-protecting/key-wrapping algorithm a bit (no pun intended! :) stronger than the one that uses that key. I can't think of a reason to protect a key with a weaker algorithm than the key-using one. 

You observed that strength-matching was not done with RSA (considering the key sizes involved, and where those keys may need to be stored and processed, one possible reason for that mismatch pops up automatically :).

More surprisingly, matching was not done with ECC either. We don't have an explanation for this design choice. Copying designs we don't understand (or do we?) does not sound like a good recipe.

Let me ask you: could you explain why you want to mix algorithms of different cryptographic strength? What benefit do you derive from including a stronger algorithm in a chain made of weaker algorithms? How big would your performance gain be?
--
Regards,
Uri               <[email-masked]>

---

From: Michael Hamburg <[email-masked]>
Date: Mon, 5 May 2014 16:10:16 -0700

Hi Uri,

Security levels aren’t comparable across primitives.  They technically represent resistance to brute force, but brute force past about 128 bits will not be possible in the foreseeable future.  So instead they represent design conservatism, including features like resistance against quantum attacks (obtainable for AES but not for ECC) or resistance to mathematical breakthroughs.

You should match security at lower levels because a chain isn’t stronger than its weakest link.  But the weakest link in a stronger-than-brute-force system is the one which falls to a math breakthrough, not the one with the fewest bits of security.  Extra bits in the security rating are just extra chances that the breakthrough won’t be big enough.  Since the threats against each system are different, and the math techniques they use are different, each system will stand or fall separately.  Instead of just matching security levels, the optimum will be about performance budgeting.

This is why people don’t use AES-192.  Some engineers are designing for performance- or memory-sensitive applications, or don’t like overengineering, and they pick AES-128.  Others would rather be more conservative, and they pay the extra 40% to go to AES-256.  The halfway solution of AES-192 isn’t used, because it isn’t the optimum for anyone’s performance budget.

So it makes sense that people commonly use AES-256 and sometimes use p384, but rarely p521 and never AES-192.  Going from AES-192 to AES-256 costs 20% on a function which is hardware-accelerated and probably not the bottleneck anyway.  Going from p384 to p521 doubles an already expensive computation (and maybe also gets you sued for patent infringement, but hopefully we can avoid that this time around).

If you want an argument for my specific curve, it’s designed around what I suspect is an inflection point in the security/cost graph — near 448 bits on 32-bit platforms, and 480 bits on 64-bit platfoms.  So Longa et al’s ed-382-mers (their fastest 384-ish-bit curve) costs 590kcy for ECDH on Sandy Bridge.  My curve (Ed448-Goldilocks) costs 674kcy — 14% slower than ed-382-mers, and it includes point compression.  Longa et al’s ed-511-mers costs 1372Mcy — 132% slower than ed-382-mers.  A hypothetical Ed480-Goldeneye built on the same principles might cost 730kcy, but I think it would be worse on ARM.

Anyway, an engineer balancing performance and security might consider the 14% cost hit worthwhile to go from 382 bits to 448 bits (plus point compression), but might not want to pay the 132% cost hit to go all the way to 511 bits.  So perhaps just one curve is enough, particularly if that curve is 448 bits.

Anyway, this argument might not be convincing, but I hope it at least sounds reasonable and worth further discussion.

Cheers,
— Mike

---

From: Watson Ladd <[email-masked]>
Date: Mon, 5 May 2014 16:12:02 -0700

> 192 and 256), suitable for use in both key agreement and in digital

Digital signatures is a bit hairy because of the issue of certs: you
end up needing to support more curves than you would think you would
going in. But yes, we should discuss adopting more Schnorr-like
mechanisms then ECDSA: the patents that forced ECDSA to look the way
it did are long gone. However, that's not what the current TLS draft
is about: it's purely addressing key exchange. Certificate changes
will be a bit more work.

> curves of size near 384 bits and 512 bits.

My suggestion: we look at the safecurves website and find curves.
Right now Curve41417 and Ed448 are both contenders for the 384 size:
it will come down to efficiency, which requires some coding to be
done. I understand both have implementations, and it comes down to who
can optimize the best.

For the 512 size M-511 looks good to me. Maybe some prime shapes are
more optimized, etc, but 2^384 is in a dry spot for primes: the best I
got was 2^384-317, which is a large enough epsilon to cause problems
on small radix machines.

> exploration of the alternatives, drawing academia and other standards bodies

How much more time do we need? We can hold meetings ad nauseam, but I
don't think our alternatives will change that much, or the various
factors causing us to lean one way or the other. Put it another way:
do you foresee any information in the next 12 months that would change
the status of Curve25519? If not, why not make the decision now, or at
least plan to end Toronto with the decision made?

Sincerely,
Watson Ladd

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: Johannes Merkle <[email-masked]>
Date: Tue, 6 May 2014 14:05:55 +0200

Paul Lambert wrote on 05.05.2014 22:52:
> NIST curves were created over 15 years ago.  NIST has not kept pace in this period with recommendations to mitigate attacks documented by industry. NIST has not considered the advancements in open cryptographic publications that have identified new curves and algorithms that provide improved performance and better “safety” of implementations. 

We should not mix up curves with (possibly insufficient) recommendations for side-channel resistance. These are two
different things.

I do not mean to advocate the NIST curves, but lack of "safety" is a weak argument against them. It has been shown that
time-constant and exception-free implementations of Weierstrass curves are easily possible while still obtaining good
efficiency [1]. And invalid-point attacks are very easily (and cheaply) thwarted by point validation as recommended by
NIST and ANSI standards.

IMHO, lack of rigidity and slightly inferior performance are much better arguments against NIST curves.

Johannes

[1] Joppe W. Bos, Craig Costello, Patrick Longa, Michael Naehrig: Selecting Elliptic Curves for Cryptography: An
Efficiency and Security Analysis. Cryptology ePrint Archive, Report 2014/130.

---

From: "Igoe, Kevin M." <[email-masked]>
Date: Tue, 6 May 2014 12:32:37 +0000

In fact we had wanted to use AES -128 and AES-192, but a quick survey
of AES implementations (hardware centric, I believe) showed that there
were very few implemented AES-192, whence the decision to go
with AES-128 and AES-256 in Suite B, paired with P256 and P384.   All
of the crypt purists grumbled endlessly about the mismatch betwixt AES-256
and P384.

From: Michael Hamburg [mailto:[email-masked]]
Sent: Monday, May 05, 2014 4:56 PM
To: Igoe, Kevin M.
Cc: [email-masked]
Subject: Re: [Cfrg] Task looming over the CFRG

Kevin,

I'm not particularly invested in getting this curve into TLS, but I'd like to know whether there's a point in submitting it for this purpose, or if it will be rejected for having the "wrong security level".

Matching the nominal security level of the asymmetric part to that of the symmetric part sounds obvious on its face, but in fact it is not usually done above the 128-bit level.  For example, Suite B doesn't specify a direct matching of nominal security levels: it specifies AES-256 with SHA-384 and ECDSA-NIST-p384 for TOP SECRET communications.  Likewise, almost nobody pairs AES-256 with the matching RSA-15k, and even AES-128 is usually paired with the nominally weaker RSA-2048.

This actually makes sense.  Nobody is going to do a 128-bit exhaust for many decades.  Not Google, not the NSA, not the KGB, nobody.  With today's most efficient supercomputers, the heat output from 2^128 operations would be far more than enough to boil the oceans dry [1].  So we're talking about defenses against sub-128-bit attacks, and defense in depth against hypothetical advances in cryptography, and quantum resistance for primitives that can resist at all.  Stronger curves, ciphers and hashes will stand or fall on their own, not all together as computer power surpasses their nominal security level.

So I don't think it's obvious that matching the AES security levels is a requirement.  If the RG thinks it is, or if there's some obscure legal requirement that the levels match, then fine.  Just describe why.

Cheers,
- Mike

[1] Lenstra, Kleinjung, Thomé.  "Universal security: from bits and mips to pools, lakes - and beyond".  https://eprint.iacr.org/2013/635.pdf

On May 5, 2014, at 12:49 PM, Igoe, Kevin M. <[email-masked]<mailto:[email-masked]>> wrote:

Mike:

                              Kevin

From: Michael Hamburg [mailto:[email-masked]]
Sent: Monday, May 05, 2014 2:25 PM
To: Igoe, Kevin M.
Cc: [email-masked]<mailto:[email-masked]>
Subject: Re: [Cfrg] Task looming over the CFRG

Hi Kevin,

Cheers,
- Mike

---

From: Johannes Merkle <[email-masked]>
Date: Tue, 6 May 2014 14:47:39 +0200

Watson,

> is about: it's purely addressing key exchange. Certificate changes
While I agree that Schnorr-like signatures (potentially deterministic) have slight advantages over ECDSA, the discussion
on the signature scheme is a different topic, isn't it? Most ECDSA implementations could be easily adopted to twisted
Edwards curves (or any other elliptic curve representations for that matter) by exchanging the underlying curve
arithmetic, without any change in the code implementing the signature algorithm.

I am not even sure, if using ECDSA over twisted Edwards curves requires new signature algorithm OIDs and ASN1 syntax.
The signature consists of two integers r and s, only the public key and the curve parameters need to be re-interpreted.

-- 
Johannes

---

From: Paul Lambert <[email-masked]>
Date: Tue, 6 May 2014 13:44:30 -0700

Johannes,

On 5/6/14, 5:05 AM, "Johannes Merkle" <[email-masked]> wrote:

>> NIST curves were created over 15 years ago.  NIST has not kept pace in
>>this period with recommendations to mitigate attacks documented by
>>industry. NIST has not considered the advancements in open cryptographic
>>publications that have identified new curves and algorithms that provide
>>improved performance and better ³safety² of implementations.
>
>
>We should not mix up curves with (possibly insufficient) recommendations
>for side-channel resistance. These are two
>different things.
>
>I do not mean to advocate the NIST curves, but lack of "safety" is a weak
>argument against them.

Yes.  I agree, and normally avoid the term ³safe² for these comparisons.
However, after close reading of the last decade of NIST publications there
is no recomendations on such potential vulnerabilities.
Plus 
>It has been shown that
>time-constant and exception-free implementations of Weierstrass curves
>are easily possible while still obtaining good
>efficiency [1]. 
None of which are documented by NIST.

>And invalid-point attacks are very easily (and cheaply) thwarted by point
>validation as recommended by
>NIST and ANSI standards.
Yes.  ³Safe² has become a smoke cloud of several possible issues some more
important than others.  The point validation is well covered by NIST.
The comparable topic for Curve25519 is the special selection of the secret
key which is never mentioned as a issue/criteria.

>arguments against NIST curves.

Here¹s another attempt at ranking (from --- to +++ range)

               NIST   Twisted Edwards
Side Channel    +         +++
Performance     +         +++
Rigidity        -         +++

I¹m not sure it¹s possible to get this mailing list to agree on the
subjective value of some of the criteria.   My earlier rant was trying to
stress the time period that has passed without evaluation or improvements
on the NIST recommendations.  Progress has been made that should be
captured in recomendations for new curves.

Paul

>
>Johannes
>
>[1] Joppe W. Bos, Craig Costello, Patrick Longa, Michael Naehrig:
>Selecting Elliptic Curves for Cryptography: An

---

From: Watson Ladd <[email-masked]>
Date: Tue, 6 May 2014 15:19:51 -0700

On Mon, May 5, 2014 at 2:34 PM, Blumenthal, Uri - 0668 - MITLL
<[email-masked]> wrote:
> IMHO, the logic/reason of matching security levels of the cryptographic
> algorithms employed in a protocol suite is fairly obvious and does not need
> an explicit justification. There might be a reason to have the
> key-protecting/key-wrapping algorithm a bit (no pun intended! :) stronger
> than the one that uses that key. I can't think of a reason to protect a key
> with a weaker algorithm than the key-using one.
>
> You observed that strength-matching was not done with RSA (considering the
> key sizes involved, and where those keys may need to be stored and
> processed, one possible reason for that mismatch pops up automatically :).
>
> More surprisingly, matching was not done with ECC either. We don't have an
> explanation for this design choice. Copying designs we don't understand (or
> do we?) does not sound like a good recipe.

I'm not sure if everyone knows this, but given 2^64 AES-128
encryptions of say 0, under different keys, and 2^64 steps, I can
recover one of the keys with probability 1/2 by a trivial application
of the birthday bound.

There are variants of this attack that work with significantly less
data: http://cr.yp.to/snuffle/bruteforce-20050425.pdf explains this
well. The headline result is 2^10 input keys, 2^86 calculation, and
probability close to 1 of finding one of the keys. I can think of many
numbers to describe this situation, but 2^128 isn't one of them.

For discrete log based systems this phenomenon doesn't happen: I
cannot find one discrete log among many in time much faster than to
find a particular discrete log. That's why ChaCha (which uses 256 bit
keys) plus Curve25519 makes sense: an attacker who wants to break such
a combination has to take a discrete log over a group of size roughly
128 or do at least 2^128 trial encryptions, even if given a ludicrous
number of keys to pick from.

Sincerely,
Watson Ladd

---

From: "Blumenthal, Uri - 0558 - MITLL" <[email-masked]>
Date: Tue, 6 May 2014 20:17:05 +0000

> ….this argument might not be convincing, but I hope it at least sounds
> reasonable and worth further discussion.

Well, I asked not for an argument – but for a reason & explanation.  :-)
Your answer provided both, thank you!

> ……This is why people don’t use AES-192.  Some engineers are designing for
> performance- or memory-sensitive applications, or don’t like over-engineering,
> and they pick AES-128.  Others would rather be more conservative, and they pay
> the extra 40% to go to AES-256.  The halfway solution of AES-192 isn’t used,
> because it isn’t the optimum for anyone’s performance budget.

Interesting. So nobody ways "I want to be a little faster and cheaper than
AES-256, but I have to be more secure than AES-128"…? I'm surprised.

> So it makes sense that people commonly use AES-256 and sometimes use p384, but
> rarely p521 and never AES-192.  Going from AES-192 to AES-256 costs 20% on a
> function which is hardware-accelerated and probably not the bottleneck anyway.
> Going from p384 to p521 doubles an already expensive computation (and maybe
> also gets you sued for patent infringement, but hopefully we can avoid that
> this time around).

I understand your reasoning now. And I think you just gave a probable reason
why P521 wasn't used much so far. (Better to carry 15K-bit keys than being
sued for a 521-bit key :)

Again, thanks for explaining!

>> key sizes involved, and where those keys may need to be stored and processed,
>> one possible reason for that mismatch pops up automatically :).
>> 
>> Let me ask you: could you explain why you want to mix algorithms of different
>> cryptographic strength? What benefit do you derive from including a stronger
>> algorithm in a chain made of weaker algorithms? How big would your
>> performance gain be?
>> --
>> Regards,
>> Uri               <[email-masked]>
>> 
>> 
>>> Sorry to be ambiguous: the curve I designed has a 448-bit field and a
>>> 446-bit prime-order subgroup, so a parallel rho attack should cost just
>>> under 2^223 point operations on average.  So it sits between the 192 and
>>> 256-bit security levels.
>>> 
>>> I’m not particularly invested in getting this curve into TLS, but I’d like
>>> to know whether there’s a point in submitting it for this purpose, or if it
>>> will be rejected for having the “wrong security level".
>>> 
>>> Matching the nominal security level of the asymmetric part to that of the
>>> symmetric part sounds obvious on its face, but in fact it is not usually
>>> done above the 128-bit level.  For example, Suite B doesn’t specify a direct
>>> matching of nominal security levels: it specifies AES-256 with SHA-384 and
>>> ECDSA-NIST-p384 for TOP SECRET communications.  Likewise, almost nobody
>>> pairs AES-256 with the matching RSA-15k, and even AES-128 is usually paired
>>> with the nominally weaker RSA-2048.
>>> 
>>> This actually makes sense.  Nobody is going to do a 128-bit exhaust for many
>>> decades.  Not Google, not the NSA, not the KGB, nobody.  With today’s most
>>> efficient supercomputers, the heat output from 2^128 operations would be far
>>> more than enough to boil the oceans dry [1].  So we’re talking about
>>> defenses against sub-128-bit attacks, and defense in depth against
>>> hypothetical advances in cryptography, and quantum resistance for primitives
>>> that can resist at all.  Stronger curves, ciphers and hashes will stand or
>>> fall on their own, not all together as computer power surpasses their
>>> nominal security level.
>>> 
>>> So I don’t think it’s obvious that matching the AES security levels is a
>>> requirement.  If the RG thinks it is, or if there’s some obscure legal
>>> requirement that the levels match, then fine.  Just describe why.
>>> 
>>> Cheers,
>>> — Mike
>>> 
>>> [1] Lenstra, Kleinjung, Thomé.  “Universal security: from bits and mips to
>>> pools, lakes — and beyond”.  https://eprint.iacr.org/2013/635.pdf
>>> 
>>>> As the designer of an ECC system which is aimed at 224-ish-bit security,
>>>> I’m curious: is it a firm requirement that the curves be set at 128, 192
>>>> and 256 bits?  Or was there consensus in the meeting that the curves should
>>>> be set at these security levels?  Patrick Longa aimed his talk at these
>>>> security levels, but I don’t recall this being stated as a requirement.
>>>>  
>>>> Cheers,
>>>> — Mike
>>>>  
>>>>