[Cryptography] NIST Workshop on Elliptic Curve Cryptography Standards

Ryan Carboni ryacko at gmail.com
Fri May 15 22:09:09 EDT 2015

On Fri, May 15, 2015 at 6:20 PM, Tony Arcieri <bascule at gmail.com> wrote:

> On Sat, May 16, 2015 at 7:52 AM, Ryan Carboni <ryacko at gmail.com> wrote:
>> Look now I'm really confused. Before differential cryptanalysis, DES
>> s-boxes were viewed with suspicion.
>> But now people are saying, "we don't completely understand ECC, but we
>> have devised means of creating EC and hope we get lucky and it ends up
>> secure twenty years down the road."
> That's not what I'm saying at all.
> BADA55 is a demonstration of why a "verifiably random" process, i.e.
> trying to pick curve parameters via the output of a, shall we say,
> "something potentially up my sleeve" number run through a hash function
> like SHA1, is a bad idea.
> That's not how rigid curve generation works, however. Instead, we pick a
> set of constraints which generate curves that are not known to be
> susceptible to any attacks today. Instead of mystery constants, we encode
> our best knowledge about fast, secure ECC today into a constraint solver,
> and have that pick the curves for us.

No. I think you're arguing that it's possible to secretly create a curve
vulnerable to attack, so it's better to make our own curve based on what we
think is secure, even though it's not easy to discover how a curve was
backdoored after a decade even when you have all the math right in front of

And AFAIK, the NSA curves (besides Dual_EC_DRBG) have not been proven to be
backdoored, they've only been proven to be suspicious. How would you know
that the NSA didn't choose the constants for additional security, like the
DES s-boxes?

> I suppose the most important takeaway I'm getting is that ECC is secure
>> enough for obfuscation-grade cryptography.
>> Otherwise one should should stick with 2048-bit RSA?
> Six of one, half dozen of another. Pollard's rho algorithms are still the
> best general case attack against both ECC and RSA. ECC and RSA are both
> special cases of the hidden subgroup problem.
> You can worry about special case attacks against ECC which we can't
> foresee based on present knowledge, but why are those more likely than
> novel methods of factoring numbers, or improvements in index calculus
> attacks, both of which would affect only RSA but not ECC?
> Hypothetical attacks aside, RSA has a lot of real problems in practice.
> Due to its susceptibility to index calculus attacks, large key sizes are
> used. We now have the uncomfortable tradeoff between amplification attacks
> (i.e. DDoS) in e.g. the DNSSEC case where the response includes an RSA
> public key or signature, or reducing the key size and thus the security
> margin (DNSSEC chose the latter... the root zone uses a 1024-bit ZSK)
> Likewise, use of unpadded RSA is an exceedingly common error in
> cryptographic programs.
> I would consider the use of RSA for anything other than legacy
> interoperability to be a code smell at this point. If you're creating a new
> pubkey protocol without legacy interop requirements today, you should
> probably be using ECC.

I don't know. How many key bytes are leaked using RSA? How many key bytes
could be leaked using ECC? Although it is clear that AES leaks key bytes
according to a paper entitled "Transposition of AES Key Schedule," but I'm
fuzzy on the math involved.

The performance difference between RSA and ECC is about 20x. So it
ultimately depends on how much you're willing to pay for additional
/provable/ security.

TBF, the Rabin cryptosystem is more secure than RSA, as the RSA problem is
unique to RSA.

I suppose this all ultimately depends on your threat model. If your threat
model requires protection against agencies capable of manipulating devices
in transit, global passive surveillance, backdooring firmware, hacking
servers that contain crypto keys, a war chest of dozens of zero days, and a
general need for security theater, then perhaps one should not use a NSA
ECC. Afterall. At least your key exchange algorithm /might/ be more than
the NSA's versus the NSA.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150515/377453ca/attachment.html>

More information about the cryptography mailing list