Score:3

Crypto

How brittle is the current public key encryption infrastructure

kodlu

8/14/24, 12:32 AM

Edit: One half of the answer to this question also applies to a recently asked and now deleted question regarding the impact of an algorithm which breaks DLP over integers but has no impact on factoring. It would be tricky to go pure RSA.

This is a question based on hypothetical scenarios, please bear with me.

Consider the two widely implemented (in the real world) public key cryptosystems (PKC), RSA and Elliptic Curve Cryptography.

What is the relative penetration of the two approaches to PKC [I am being vague, and it is enough for the answer to be based on rough estimates]. I guess I am asking for a high level statistical summary of real world cryptography from the point of view of PKC.

Scenario 1:

If there was a non-Quantum break of RSA tomorrow with a practical (choose whatever population you wish that are able to implement the attack but do not include just nation states, so maybe large industrial companies as well) attack, what estimated percentage of systems would be affected?

What estimated percentage of such systems already have Elliptic Curve based PKC built in? What estimated percentage of such systems could be converted into Elliptic Curve based PKC?

Note 0: A quantum computing breakthrough would impact both, that's not what I am asking about.

Note 1: I don't really know but have a hunch that there are quite a few places where RSA is used but Elliptic Curve based crypto is not implemented.

Scenario 2:

If there was a non-Quantum break of Elliptic Curve Cryptography tomorrow with a practical (choose whatever population you wish that are able to factor but do not include just nation states, so maybe large industrial giants as well) attack, what estimated percentage of systems would be affected?

What estimated percentage of such systems already have RSA based PKC built in? What estimated percentage of such systems could be converted into RSA based PKC?

Note 2: I estimate that for constrained systems, there are scenarios where RSA is not practical.

Generic Question:

In both cases, for significant systems without the post-break secure PKC, how long do you estimate it would take for such PKC to be rolled out?

Any comments, pointers to resources appreciated.

has no impact on factoring.

522

1 + 3

elliptic-curves

fgrieu

8/14/24, 9:54 AM

Our current TLS PKIs are brittle for non-cryptographic reasons. Actors including nation states already have means to attack it for many practical purposes, by having control on a single of the thousands certification authorities most browsers/OSes trust (directly or indirectly), and having it issue a certificate that allows a MitM attack to succeed. The hardest part for said actors is routing the traffic in a way that allows MitM (but they find ways to do it). Apparently, few people care: I'm not aware of much effort to build detection of rogue certificates into or on top of TLS.

aiootp

8/14/24, 12:35 PM

@fgrieu There are some notable examples. The once popular HTTPS Everywhere browser plugin ran an observatory (https://www.eff.org/observatory) in the background to correlate domains with keys for all users, checking for rogue issuances. I think with TLS being enforced by default in browsers now, & with RFC-9162 (https://developer.mozilla.org/en-US/docs/Web/Security/Certificate_Transparency), the project has found mainstream successors in the "Certificate Transparency" movement. There's also dark-web hosting using public keys as routable addresses, which many clear-web sites now offer.

kodlu

8/14/24, 6:04 PM

Thanks to you both for the interesting comments

Score:4

Crypto

Daniel S

8/14/24, 8:15 AM

Probably the most prevalent form of PKI usage today is the Transport Layer Security (TLS protocol), and I'll omit discussion of Network layer usage (such as IPsec) and Application layer usage (such as Signal/WhatsApp).

Current usage of TLS is frequently dependent on both elliptic curve and RSA. Take this site for example, if we go to the Settings -> More Tools -. Developer Tools -> Security information in our browser, we se that the connection is secured using TLS1.2, ECDHE_RSA with X25519 and AES_128_GCM. Even in websites where TLS1.3 is used so that RSA is not permitted to be used as a key establishment mechanism, RSA is still commonly in use as a signature algorithm. Thus an EC break would allow passive decryption of the traffic and an RSA break would allow an active man-in-the-middle attack. Even where websites are using ECDSA signatures, there is usually a point in the certification chain where RSA is used.

An up-to-date snapshot of website usage is provided daily by the crawler.ninja site. Here you can see the most popular ciphersuites (note TLS1.3 does not include key establishment and signatures in the suite name) as well as the most common key exchange methods and key sizes.

This puts most modern PKC in the position where there is support for both, but also reliance on both.

It would likely be quite hard to transition to a monoculture of either RSA or EC. If we wanted to rely solely on RSA, then there is no method for public key establishment in TLS1.3 (we could use finite field Diffie-Hellman in place of elliptic curve if that is acceptable). If we wanted to rely solely on EC, there will be an immense number of long-lived certificates to be revoked (not to mention the even trickier proposition of universally removing certificates from root stores on all computers).

Modern TLS implementations should include implementations of both forms, so at the transport layer at least the problem is not so much software as standards and infrastructure. This is fortunate: adoption of EC cryptography took decades to fully roll out and estimates of the migration time for new public key algorithms are on the decades scale.

+ 2

kodlu

8/14/24, 6:02 PM

Thanks! Very interesting details in your answer

dave_thompson_085

8/15/24, 12:16 AM

ECC was slow, but I think it was because there was no clear need (nothing broken) plus it was seen as a US-government thing, especially during the period NSA was pushing it, as well as possibly risking patent litigation. In contrast the responses to Apache-renegotiation (RFC5746) and BEAST (fragmentation in 1.0 or below) -- and POODLE (drop SSL3) -- were widespread (though not universal) within one year. (Even though BEAST was adequately mitigated by a few browser fixes and AFAIK never demonstrated after that.)

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: How brittle is the current public key encryption infrastructure

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.