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

James Bottomley describes the use of the trusted platform module with elliptic-curve cryptography, with a substantial digression into how the elliptic-curve algorithm itself works. "The initial attraction is the same as for RSA keys: making it impossible to extract your private key from the system. However, the mathematical calculations for EC keys are much simpler than for RSA keys and don’t involve finding strong primes, so it’s much simpler for the TPM (being a fairly weak calculation machine) to derive private and public EC keys."

to post comments

Bottomley: Using Elliptic Curve Cryptography with TPM2

Posted Oct 15, 2017 17:14 UTC (Sun) by flussence (guest, #85566) [Link] (11 responses)

IIRC there was some software patent FUD surrounding ECC a while ago, which is the only reason I can think of (in the rest of the non-legacy world) why we haven't started replacing RSA en-masse. Does anyone know if that's over now?

Bottomley: Using Elliptic Curve Cryptography with TPM2

Posted Oct 15, 2017 20:36 UTC (Sun) by Wol (subscriber, #4433) [Link] (8 responses)

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:33 UTC (Mon) by Otus (subscriber, #67685) [Link]

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

No, the RSA problem is not the same as discrete log. It is linked to integer factorization, but does not necessarily imply that either, so it could be easier.

https://en.m.wikipedia.org/wiki/RSA_problem

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...

Bottomley: Using Elliptic Curve Cryptography with TPM2

Posted Oct 16, 2017 2:24 UTC (Mon) by njs (subscriber, #40338) [Link]

We have started replacing RSA with ECC en masse -- ECC is very common in new applications, e.g. Bitcoin and Signal both use it exclusively. Migrating existing protocols like TLS is slower because everyone has to interoperate with legacy stuff, but here are some stats from Mozilla last year that show something like 95% of incoming connections using some variant of ECDHE (= elliptic curve Diffie-Hellman): https://jve.linuxwall.info/blog/index.php?post/2016/08/04...

RSA is still very common for TLS certificates, but even that's starting to shift.

Bottomley: Using Elliptic Curve Cryptography with TPM2

Posted Oct 16, 2017 12:35 UTC (Mon) by cesarb (subscriber, #6266) [Link]

For the most common curves (secp256r1, secp384r1, secp521r1, and Curve25519), it does seem to be over now; even the conservative RedHat has enabled these curves.

Bottomley: Using Elliptic Curve Cryptography with TPM2

Posted Oct 16, 2017 1:14 UTC (Mon) by rbd (guest, #73313) [Link]

James seems to be a bit confused about what discrete logarithms are. The post says:

In fact, it can be demonstrated mathematically that trying to compute n is equivalent to the discrete logarithm problem….

but as the linked Wikipedia article says

Popular choices for the group G in discrete logarithm cryptography are […] cyclic subgroups of elliptic curves over finite fields….

so in fact reversing multiplication in the group of an elliptic curve is not just equivalent to the discrete log problem, it is the discrete log problem in a certain class of finite group. As is pointed out in the post, there are elliptic curves where an adversary may have information that makes the discrete log problem unexpectedly easy, but the adversary is still solving the discrete log problem.