Subject: [Cfrg] "Abandoning ECC" — Any replies to "A riddle wrapped in a curve"?

From: Tao Effect <[email-masked]>
Date: Thu, 22 Oct 2015 19:16:55 -0700

Matthew Green references [cfrg] and this email specifically: https://www.ietf.org/mail-archive/web/cfrg/current/msg06426.html <https://www.ietf.org/mail-archive/web/cfrg/current/msg06426.html>

From this blog post: http://blog.cryptographyengineering.com/2015/10/a-riddle-wrapped-in-curve.html <http://blog.cryptographyengineering.com/2015/10/a-riddle-wrapped-in-curve.html>

In it he says there’s an argument for abandoning all of ECC, including curve25519.

<BEGIN>

By calculating the number of possible curve families, Koblitz and Menezes show that a vast proportion of curves (for P-256, around 2^{209} out of 2^{257}) would have to be weak in order for the NSA to succeed in this attack. The implications of such a large class of vulnerable curves is very bad for the field of ECC. It dwarfs every previous known weak curve class and would call into question the decision to use ECC at all.

In other words, Koblitz and Menezes are saying that if you accept the weak curve hypothesis into your heart, the solution is not to replace the NIST elliptic curves <https://www.ietf.org/mail-archive/web/cfrg/current/msg06426.html> with anything at all, but rather, to leave the building as rapidly as possible and perhaps not shut the door on the way out. No joke.

On the gripping hand, this sounds very much like the plan NSA is currently implementing. Perhaps we should be worried.

</END>

So, I’m not a cryptographer, but ya’ll (supposedly) are. What say the list?

- Greg

---

From: Tony Arcieri <[email-masked]>
Date: Thu, 22 Oct 2015 21:06:54 -0700

Hi Greg,

I think some context and basic fact-checking is in order.

I read the Koblitz paper[1] before Matt Green blogged about it and have
been discussing it with several people found it rather interesting, however
much of what it describes is about the early history of ECC (particularly
in the 1990s) and the "verifiably random" process used by NIST for
generating their curves. I'd say Brainpool used a similar process, but it
turns out if you actually tried to verify their curves they screwed up[2].

I am not sure why you are quoting the phrase "Abandoning ECC" in the
subject line of your email as it appears in neither the Matt Green blog
post or the Koblitz paper, and if you actually read the Koblitz paper,
hypothetical claims we should "abandon ECC altogether" (actually in the
paper) are countered by phrasing like "This scenario is highly implausible
for several reasons" and claims that it is "preferable to use other curves
(either the Edwards curves recommended by Bernstein-Lange [5, 6], or the
curves being promoted by the Microsoft group [10], or perhaps some others)"
which is exactly what the CFRG is doing. The "rigid" curve generation
guidelines described in draft-irtf-cfrg-curves were the subject of a
painful, rather long bikeshedding debate, however I think the result is a
foundation for trust in next-generation ECC standards which are not
susceptible to the sorts of attacks discussed in the Koblitz paper, and in
fact the paper specifically calls out curves generated in this fashion as
being such.

The larger concern cited by both the Koblitz paper and Matt Green's blog
post is that the NSA feels it is urgent to move to post-quantum
cryptography. I'll quote Matt Green:

"despite the fact that quantum computers seem to be a long ways off and
reasonable quantum-resistant replacement algorithms are nowhere to be seen,
NSA decided to make this announcement publicly and not quietly behind the
scenes. Weirder still, if you haven’t yet upgraded to Suite B, you are now
being urged not to. In practice, that means some firms will stay with
algorithms like RSA rather than transitioning to ECC at all. And RSA is
also vulnerable to quantum attacks."

This is a legitimate concern, and perhaps ECC is not long for this world,
but if the threat is large quantum computers which can break the ECC
algorithms we use today, RSA and all other "pre-quantum" algorithms will be
affected too. And per Matt Green: the post-quantum algorithms are not only
slow but we are still not certain of their security properties.

If anything, I hope the takeaway for the CFRG is after the current ECC
standardization work is done, perhaps it would be prudent to move onto
evaluating post-quantum algorithms and standardizing them for use in e.g.
TLS. I suspect this is probably already on the chairs' roadmap.

[1]: https://eprint.iacr.org/2015/1018.pdf
[2]: http://bada55.cr.yp.to/brainpool.html

---

From: Tao Effect <[email-masked]>
Date: Thu, 22 Oct 2015 21:17:51 -0700

Hey Tony,

Thanks very much, that was very well written.

> I am not sure why you are quoting the phrase "Abandoning ECC" in the subject line of your email as it appears in neither the Matt Green blog post or the Koblitz paper

I didn’t mean it as a direct quote, but rather I quoted it to … quote the idea, the concept. To indicate, in other words, that I was not personally advocating that such a thing be done.

Cheers,
Greg

> On Oct 22, 2015, at 9:06 PM, Tony Arcieri <[email-masked]> wrote:
> 
> Hi Greg,
> 
> I read the Koblitz paper[1] before Matt Green blogged about it and have been discussing it with several people found it rather interesting, however much of what it describes is about the early history of ECC (particularly in the 1990s) and the "verifiably random" process used by NIST for generating their curves. I'd say Brainpool used a similar process, but it turns out if you actually tried to verify their curves they screwed up[2].
> 
> I am not sure why you are quoting the phrase "Abandoning ECC" in the subject line of your email as it appears in neither the Matt Green blog post or the Koblitz paper, and if you actually read the Koblitz paper, hypothetical claims we should "abandon ECC altogether" (actually in the paper) are countered by phrasing like "This scenario is highly implausible for several reasons" and claims that it is "preferable to use other curves (either the Edwards curves recommended by Bernstein-Lange [5, 6], or the curves being promoted by the Microsoft group [10], or perhaps some others)" which is exactly what the CFRG is doing. The "rigid" curve generation guidelines described in draft-irtf-cfrg-curves were the subject of a painful, rather long bikeshedding debate, however I think the result is a foundation for trust in next-generation ECC standards which are not susceptible to the sorts of attacks discussed in the Koblitz paper, and in fact the paper specifically calls out curves generated in this fashion as being such.
> 
> The larger concern cited by both the Koblitz paper and Matt Green's blog post is that the NSA feels it is urgent to move to post-quantum cryptography. I'll quote Matt Green:
> 
> "despite the fact that quantum computers seem to be a long ways off and reasonable quantum-resistant replacement algorithms are nowhere to be seen, NSA decided to make this announcement publicly and not quietly behind the scenes. Weirder still, if you haven’t yet upgraded to Suite B, you are now being urged not to. In practice, that means some firms will stay with algorithms like RSA rather than transitioning to ECC at all. And RSA is also vulnerable to quantum attacks."
> 
> This is a legitimate concern, and perhaps ECC is not long for this world, but if the threat is large quantum computers which can break the ECC algorithms we use today, RSA and all other "pre-quantum" algorithms will be affected too. And per Matt Green: the post-quantum algorithms are not only slow but we are still not certain of their security properties.
> 
> If anything, I hope the takeaway for the CFRG is after the current ECC standardization work is done, perhaps it would be prudent to move onto evaluating post-quantum algorithms and standardizing them for use in e.g. TLS. I suspect this is probably already on the chairs' roadmap.
> 
> [1]: https://eprint.iacr.org/2015/1018.pdf <https://eprint.iacr.org/2015/1018.pdf>
> [2]: http://bada55.cr.yp.to/brainpool.html <http://bada55.cr.yp.to/brainpool.html>

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Fri, 23 Oct 2015 00:27:25 -0400

On Fri, Oct 23, 2015 at 12:17 AM, Tao Effect <[email-masked]> wrote:
> I am not sure why you are quoting the phrase "Abandoning ECC" in the subject
> line of your email as it appears in neither the Matt Green blog post or the
> Koblitz paper
>
>
> I didn’t mean it as a direct quote, but rather I quoted it to … quote the
> idea, the concept. To indicate, in other words, that I was not personally
> advocating that such a thing be done.

The original premise looks bogus to me.

First off we have seen attacks that involve quite large numbers of
weak keys. 1/2^48 is much smaller.

More importantly, there might well be something about the enumeration
attack that allows someone to construct a curve from a set of
parameters that guarantee the desired property. Alternatively, they
might be able to perform the attack on more than one candidate at
once.

Finally, don't make too many assumptions about 1990s computing
capabilities available to the NSA and GCHQ.

---

From: Peter Gutmann <[email-masked]>
Date: Fri, 23 Oct 2015 04:38:16 +0000

Tony Arcieri <[email-masked]> writes:

>The larger concern cited by both the Koblitz paper and Matt Green's blog post
>is that the NSA feels it is urgent to move to post-quantum cryptography

It's not really that.  There are two things, the move off Suite B and the
attempt to find a replacement.  The move off Suite B is no surprise, the NSA
are simply admitting that after a decade of fruitless attempts to get anyone
interested in it (outside of organisations with a government gun pointed at
their heads, who had no choice), no-one wanted it.  They were in the same
position they were in before Suite B in terms of people not being able to take
advantage of COTS products, it still didn't solve the Type-1-algorithm product
problem.

The second issue is what to replace Suite B with.  They could have said "AES,
'25519, and SHA2, and we're done".  Instead, they're pushing yet another white
elephant to follow on from their previous herd.  After all this time they
still don't understand how COTS actually works.

Peter.

---

From: "Paterson, Kenny" <[email-masked]>
Date: Fri, 23 Oct 2015 10:04:41 +0000

Tony, all,

On 23/10/2015 05:06, "Cfrg on behalf of Tony Arcieri"
<[email-masked] on behalf of [email-masked]> wrote:

>TLS. I suspect this
> is probably already on the chairs' roadmap.

It is. 

However my perception is that the science and technology here are less
mature than we'd like them to be. This is going to be a difficult
challenge for CFRG (and everyone else).

Cheers,

Kenny 

><https://eprint.iacr.org/2015/1018.pdf>