Bottomley: Using Elliptic Curve Cryptography with TPM2 [LWN.net]

Bottomley: Using Elliptic Curve Cryptography with TPM2

Posted Oct 15, 2017 20:36 UTC (Sun) by Wol (subscriber, #4433)
In reply to: Bottomley: Using Elliptic Curve Cryptography with TPM2 by flussence
Parent article: Bottomley: Using Elliptic Curve Cryptography with TPM2

As the article points out, there is another big reason why we're not replacing RSA.

In order to crack RSA, we need to solve the discrete logarithm problem. If this is done, it will be a PhD-worthy advance in mathematics, and hard to keep secret.

But individual elliptic curves can be solved, and that is not a particularly noteworthy achievement. So (a) you might pick a curve to which the solution is known - and hence all your keys can be trivially broken, or (b) even if you choose a currently strong curve, cracking your curve is unlikely to be widely broadcast and again all your keys will be trivially broken.

In other words, Elliptic Curve Cryptography is both solveable and partially solved, ie pick the wrong curve and your encryption is useless. While RSA is still completely unbroken, and any solution will almost certainly be widely broadcast shortly after it is discovered.

Cheers,
Wol

Bottomley: Using Elliptic Curve Cryptography with TPM2

Posted Oct 16, 2017 3:43 UTC (Mon) by luto (subscriber, #39314) [Link] (5 responses)

> But individual elliptic curves can be solved, and that is not a particularly noteworthy achievement.

Please clarify. There are certainly insecure curves, but I've never heard that you can take an otherwise-okay curve, compute something, and thus "solve" the curve.

In contrast, one can use a number field sieve to do a massive pre-computation that makes DLP easier mod any given prime. IIRC djb has run the numbers, and 1024-bit DH is likely economically breakable this way by an NSA-style attacker as long as enough users are using the same prime.

Bottomley: Using Elliptic Curve Cryptography with TPM2

Posted Oct 16, 2017 6:55 UTC (Mon) by wahern (subscriber, #37304) [Link] (1 responses)

All existing ECC standards rely on shared, fixed domain parameters. So ECC is susceptible to the same fundamental issue as most DH implementations. In a real sense it's even more susceptible as nobody is suggesting _not_ to use shared parameters, whereas best practice for DH for over 15 years has been to dynamically generate unique prime groups.

Don't think of the NSA attacks on DH as people using key sizes that were too small. Rather, the salient lesson is that when enough people are using shared parameters the economic calculus applied for choosing key sizes can be substantially impacted if you don't take account of that fact. Anybody who looked at the increase of DH usage on the Internet and the fact that almost everybody was using shared primes could have easily calculated that we were approaching (or had already passed) a point where the old cost models were outdated. But nobody thought to look; at least, nobody both looked at the evolving situation and reacted to it except the NSA and, perhaps, other secret actors.

Precomputing solutions to ECC domain parameters of popular curves may be more difficult relative to DH in terms of specific known techniques (e.g. Weil decent attacks). But there are still many unknowns. We're always going to push the envelope and risk being too optimistic when choosing key sizes because it's never free; there's always a cost+benefit tradeoff. While the highest-end processors are ridiculously powerful, the biggest growth may come from IoT devices with 1990s or 2000s era computation power.

The researcher behind Ed448 has said it's probably too conservative, so while Ed448 might be perfectly safe until the age of ubiquitous quantum computing, the vast majority of people are likely to continue using shorter keys. The margin of safety is going to be smaller than what we could theoretically accomplish, meaning we can't be as lax when it comes to understanding and continually tracking the cost+benefit model in light of real-world deployments. That's the takeaway--the NSA program showed that we were lacking in our ability to clearly and honestly reassess the economic calculus of real-world usage, and in particular identifying the systemically weak links.

Bottomley: Using Elliptic Curve Cryptography with TPM2

Posted Oct 16, 2017 9:00 UTC (Mon) by Otus (subscriber, #67685) [Link]

> Don't think of the NSA attacks on DH as people using key sizes that were too small. Rather, the salient lesson is that when enough people are using shared parameters the economic calculus applied for choosing key sizes can be substantially impacted if you don't take account of that fact.

That has to be taken into account for sure, but I disagree that using non-shared parameters is the way to go. If you have to rely on multiple targets taking longer to attack it means the choices are already broken since attacking one target is possible (or close to so).

This is also the case in many symmetric algorithms. Multi-target attacks are cheaper than attacking each individually, and breaking someone's key is faster than breaking a particular key.

The solution is to choose parameters such that without advances in theory any amount of computational power will be insufficient to break any key. The same should be possible with ECC.

Bottomley: Using Elliptic Curve Cryptography with TPM2

Posted Oct 16, 2017 12:40 UTC (Mon) by Wol (subscriber, #4433) [Link] (2 responses)

> Please clarify. There are certainly insecure curves, but I've never heard that you can take an otherwise-okay curve, compute something, and thus "solve" the curve.

Bear in mind I'm not a cryptography expert but ...

I believe that with RSA you publish PQ (the product of your two big primes) as part of your public key. Crack that PQ, and EVERYBODY who is using that PQ has had their key broken. Which is why most people calculate their own PQ.

On the other hand, while there are very many elliptic curves (an infinite number?) for the most part we only use a few of them, so very many people share the same elliptic curve. Crack one person using a curve, and again everyone else using the same curve has been cracked.

That's really my point - cracking an individual PQ doesn't get you very far as the chances of many people using it is slim, cracking an elliptic curve will probably get you major crack as each curve is widely used.

Cheers,
Wol

Bottomley: Using Elliptic Curve Cryptography with TPM2

Posted Oct 16, 2017 15:17 UTC (Mon) by MattJD (subscriber, #91390) [Link] (1 responses)

> I believe that with RSA you publish PQ (the product of your two big primes) as part of your public key. Crack that PQ, and EVERYBODY who is using that PQ has had their key broken. Which is why most people calculate their own PQ.

To be clear, P and Q are basically the secret of an RSA key (technically there is a third value, d, but that can be easily computed from the P, Q, and the e value in the public certificate). People use a different P and Q (and thus PQ value) as otherwise they would be basically sharing keys.

Note that actual RSA keys are described slightly differently, but doesn't change the fact people can't share a P and Q.

Bottomley: Using Elliptic Curve Cryptography with TPM2

Posted Oct 20, 2017 0:31 UTC (Fri) by Wol (subscriber, #4433) [Link]

Or if, as is theoretically possible, two people come up with the same PQ by chance, they can solve the other person's encrypted communications ...

Cheers,
Wol

Bottomley: Using Elliptic Curve Cryptography with TPM2

Posted Oct 16, 2017 12:57 UTC (Mon) by excors (subscriber, #95769) [Link]

> In order to crack RSA, we need to solve the discrete logarithm problem.

Or find a bug in an RSA implementation that's widely used in TPMs, YubiKeys, ID cards, etc: https://crocs.fi.muni.cz/public/papers/rsa_ccs17, https://arstechnica.com/information-technology/2017/10/cr...