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

[Tony Arcieri <[e-mail]>]

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