For those of us less familiar with cryptography and RSA in general: what are the implications if RSA is broken? What are the mitigations that would need to occur in its place?
The public web and code signing PKIs collapse overnight. Most certificate authorities use RSA-2048 either for the roots or intermediates. The HN site not only uses a RSA-2048 key in its own certificate, the CA issuing that certificate and the root CA issuing the intermediate also do.
All data transmitted without forward secrecy on most web sites is compromised. Most websites nowadays use forward secrecy and/or ECDSA, but data sent years ago may still be of value (e.g. passwords) and become decryptable now.
Any data (e.g. backups, past e-mails) encrypted using RSA keys is at risk.
Any authentication system relying on RSA keys has a problem. This can include systems like smartcards or HSMs that are hard to update, software or firmware updates, etc. Banking too.
Edit to add - if RSA-1024 is practically breakable but RSA-2048 is not: some systems that relied on RSA-1024 have a problem. These should be rare, but sometimes legacy doesn't get updated until it becomes an absolute emergency. Everyone realizes that RSA-2048 is only a matter of time, that time is running out quicker than expected, and starts upgrading to ECDSA with more urgency. This will likely take a long time due to legacy hardware.
Surely I'm not the only one who read this and thought "I wonder how long the NSA have known this result, and how much better their internal attacks are than public academic results? I wonder how much of their 'full take' internet backbone archive has been decrypted and keyword mined?"
There was a quote in a newspaper I unfortunately forget the location of about four years ago about a massive break through in encryption by the NSA post Snowden. Enough subtle hints about it. My working assumption had been it was RSA related. I noticed for example some interesting organisations changed their guidelines about its usage in past three years or so.
If it is what I think it is, then it's commonly believed that they broke commonly used Diffie-Hellman parameters, allowing them to break any connection encrypted using those.
The parameters can, in theory, be safely used by everyone, and generating them is relatively expensive. But because a few of these parameters were extremely widely used, and they were only 1024 bits strong, it is believed that a gargantuan effort to break them was worth it and the NSA did it.
>All data transmitted without forward secrecy on most web sites is compromised.
Forward secrecy does not protect against broken cryptography, so this is more about what methods were used and how much an new technique like this affects them.
Nope. Whilst that's how TLS_RSA_WITH_AES_128_CBC_SHA works, this not how Forward Secrecy enabled suites like TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 work. Most sites (and certainly any sites that think they're "secure") thus are not affected in this way.
In TLS 1.3 all suites (such as TLS_AES_128_GCM_SHA256) have forward secrecy so it isn't even explicitly called out.
In these modern modes (and in other modern protocols like SSH) the two peers agree random ephemeral keys (these days with Elliptic Curve Diffie Hellman) and long term private keys are only used to sign things to prove who you're talking to over the resulting securely encrypted connection.
So if you break RSA you can forge those signatures but you can't decrypt messages sent to and from the legitimate owner of the keys, those were, as your parent explained, secured with AES and not RSA. You would need to perform a live active attack, a MitM to interpose between the real server and its clients so as to decrypt all messages in transit.
The point of forward secrecy is that past key are not recoverable from future communications. You need to store the whole communication history to have any chance.
Unless you break the encryption. Then you get the past keys.
Forward secrecy only protects against the exposure of private key material. It does not protect against broken cryptography as it depends on the cryptography to keep old messages private. That's because it works by forgetting the session keys. If you can derive those session keys again then it is of no value.
Nope. A session key is normally not created by one party and sent to another, it's generated by something like Diffie-Hellman in which the long-living RSA keys are only used for authenticity verification.
Diffie-Hellman requires discrete logarithms rather than factorization (and then there are more modern methods).
"Broken" generally isn't a binary event in cryptography.
It's a continuum from "impossible to do with all the time and energy of the universe and the most advanced computers we have" to "my commodity hardware can crack it in a few minutes".
The same goes for fears of quantum computing breaking current cryptography. It goes from effectively impossible to "yeah, we could break it with a few years of constant computation, which is plenty of time to switch to quantum resistant schemes".
> "Broken" generally isn't a binary event in cryptography.
If there were, for example, a way to glean a private key without factoring the modulus, I think we'd all agree that this amounts to "breaking" the system insofar as that it changes the applicability of the hardness assumption.
On the other hand, simply achieving a faster way to factor the modulus is, at best, part of a continuum as you say.
> which is plenty of time to switch to quantum resistant schemes
That's not how you treat broken cryptography. If your data is already collected and stored encrypted by a third party which still holds value after several years, you're already in bad shape.
Depending on exactly how broken, a large portion of traffic on the internet would lose almost all of its security guarantees (privacy, resistance to forgery). It would also be a huge effort, and take forever to get everyone to fix it. That's about as close to "movie disaster" level as it gets.
1. We kinda knew RSA has an expiration date due to quantum computers. Assuming the paper is true, this just brought the expiration date far closer to us.
2. Major issue is going to be webpki and replaying govt captured encrypted communications.
3. There are a lot of abandoned servers out there that use RSA. There is a lot of code signing that uses RSA. There is just a lot of identity proven on the web that uses RSA to prove the identity. It's going to be a clusterfuck of identity. Again, assuming the paper means RSA is just completely broken.
There's no real big theoretical problems in the quantum computer building space. There's problems of scale, and funding, and usual growing pains of a new industry, but scale went from 7 to 24 fairly quickly and all it took was more money. If I gave IBM $10T dollars, they could build me a 1024-qbit computer. Once it gets cheaper, which is the current problem, I don't see any reason why Azure Quantum (ex) wouldn't simply decrease in price to where it can be used practically.
>There's no real big theoretical problems in the quantum computer building space
The current quantum computers are just on the edge of what we can simulate classically, so we can't yet rule out the possibility that realizing a quantum computation requires an exponential amount of energy in the number of qubits. (Though it should be noted that quantum mechanics predicts that this will not happen.)
This couldn't be further from the truth. If more money could get IBM to more qubits, they would be doing it. Fundamental problems with scaling have held them back for ages. The only people making any progress on scaling is D-Wave and their model is never going to have any impact on factoring anyway.
This is true - in general each bit you add to a quantum computer means the noise floor needs to be twice as low, so difficulty scales exponentially. That is unless a threshold is reached where error correction scales faster.
But for now, it's more important to ask whether ECC is vulnerable to some variant of Schnorr's attack, which uses conventional computers. We already had an algorithm to break RSA on quantum.
Well, the most obvious problem for the average lay person is that the movie "Sneakers" would suddenly gain relevance again, and most of the cast are too old (or too dead) to make a sequel.
Also, that whole thing about lots of computer encryption tech suddenly being effectively insecure.
He didn't claim it is broken. Only that it can be broken 2x faster than before. RSA 4096 as recommended by the FSF is still secure. RSA 2048 might be breakable by the NSA. But so far we are at 800-1000 at risk.
Yes, because RSA 2048 is broken, not RSA 4096. Almost everything uses 2k, nobody uses 4k. The cryptosystem infrastructure would be broken. Not talking about the possible backdoors in the ECC NIST curves. Thanksfully we have the djb curves there.
This would massively break basically all traditional public key crypto i think (depends a bit on if it extends to eliptic-curve or just integer based RSA [edit: meant to say whether the algorithm can be adapted to solving discrete logrithms over eliptic curves]). It would be the biggest crypto thing to happen in the last 30 years at least.
The mitigation would be to move to experimental post-quantum crypto systems immediately (quantum computers have all the fuss because they can break rsa).
This is basically an unbelievable result. Without actually providing some factored numbers i am very doubtful.
[I have not read paper]
Edit: as pointed out below, i may have gotten overexcited. Still an incredible result if true.
> This would massively break basically all traditional public key crypto i think (depends a bit on if it extends to eliptic-curve or just integer based RSA).
"A bit"? A lot more than a bit. A world.
And on the surface, since it appears to be a factoring system, rather than a general purpose discrete log solver, the consequences, while incredible, are far more limited than the picture you paint. If this is even true; a matter over which I'm skeptical.
As stated in your comment, eliptic curve cryptography relies on discrete logarithm but this algorithm is a method for factoring integers, with ideas similar to the Quadratic Sieve algorithm (https://en.wikipedia.org/wiki/Quadratic_sieve).
It does not extend to breaking eliptic-curve cryptography, for the same reason that the Quadratic Sieve does not extend to eliptic-curve crypto: the underling math problem is different (factorisation vs discrete logarithm).
