5 ms·

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 occu

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?

aaomidi 6y ago
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.
- dataflow 6y ago
  > 1. We kinda knew RSA has an expiration date due to quantum computers. Only if you somehow "know" quantum computing is ever going to be practically realized. It may never be.
  - deleted 6y ago
    [deleted]
  - freeone3000 6y ago
    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.
    - Laakeri 6y ago
      >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.)
      - coliveira 6y ago
        > it should be noted that quantum mechanics predicts that this will not happen There is a possibility that QM will break somewhere, but I wouldn't consider this very probable...
    - deleted 6y ago
      [deleted]
    - deleted 6y ago
      [deleted]
    - ouid 6y ago
      >There's no real big theoretical problems in the quantum computer building space. I don't think this is true...
    - core-questions 6y ago
      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.
  - akvadrako 6y ago
    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.
- chrisco255 6y ago
  Does this technique for factorization by Schnorr have any implications for any other cryptographic methods as well (if confirmed)?
anonisko 6y ago
"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".
- bawolff 6y ago
  Well that's generally true, sometimes breakthroughs do happen overnight. Its not impossible.
  - anonisko 6y ago
    Yup. That's why I say generally. Even if the paper is correct it seems to fall into the 'moving down the continuum' category.
- jMyles 6y ago
  > "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.
- mekster 6y ago
  > 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.
bawolff 6y ago
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.
- teraflop 6y ago
  There is no such thing as "elliptic-curve RSA".
- jMyles 6y ago
  > 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.
- SuchAnonMuchWow 6y ago
  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 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).
sillysaurusx 6y ago
There are lots of alternative constructions. ECC, for example. 1024-bit and higher RSA is still unfactorable, so I don't think anyone will be attacking RSA directly any time soon.
- akvadrako 6y ago
  ECC is considered even less quantum resistant than RSA because the key lengths are so short.
  - DennisP 6y ago
    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.
tgsovlerkhgsel 6y ago
If RSA-2048 is practically broken or breakable: 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.
- the8472 6y ago
  Also any proprietary/ancient SSH implementation only supporting RSA that you'll find in all kinds of boxes.
- bigiain 6y ago
  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?"
  - secfirstmd 6y ago
    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.
rurban 6y ago
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.
- TacticalCoder 6y ago
  > He didn't claim it is broken. But then there's that line: "This destroys the RSA cryptosystem" in the abstract of the paper.
  - rurban 6y ago
    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.
kadoban 6y ago
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.
Accujack 6y ago
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.

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?

aaomidi 6y ago

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.

dataflow 6y ago
> 1. We kinda knew RSA has an expiration date due to quantum computers. Only if you somehow "know" quantum computing is ever going to be practically realized. It may never be.
- deleted 6y ago
  [deleted]
- freeone3000 6y ago
  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.
  - Laakeri 6y ago
    >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.)
    - coliveira 6y ago
      > it should be noted that quantum mechanics predicts that this will not happen There is a possibility that QM will break somewhere, but I wouldn't consider this very probable...
  - deleted 6y ago
    [deleted]
  - deleted 6y ago
    [deleted]
  - ouid 6y ago
    >There's no real big theoretical problems in the quantum computer building space. I don't think this is true...
  - core-questions 6y ago
    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.
- akvadrako 6y ago
  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.
chrisco255 6y ago
Does this technique for factorization by Schnorr have any implications for any other cryptographic methods as well (if confirmed)?

anonisko 6y ago

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

bawolff 6y ago
Well that's generally true, sometimes breakthroughs do happen overnight. Its not impossible.
- anonisko 6y ago
  Yup. That's why I say generally. Even if the paper is correct it seems to fall into the 'moving down the continuum' category.
jMyles 6y ago
> "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.
mekster 6y ago
> 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.

bawolff 6y ago

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.

teraflop 6y ago
There is no such thing as "elliptic-curve RSA".
jMyles 6y ago
> 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.
SuchAnonMuchWow 6y ago
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 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).

sillysaurusx 6y ago

There are lots of alternative constructions. ECC, for example. 1024-bit and higher RSA is still unfactorable, so I don't think anyone will be attacking RSA directly any time soon.

akvadrako 6y ago
ECC is considered even less quantum resistant than RSA because the key lengths are so short.
- DennisP 6y ago
  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.

tgsovlerkhgsel 6y ago

If RSA-2048 is practically broken or breakable: 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.

the8472 6y ago
Also any proprietary/ancient SSH implementation only supporting RSA that you'll find in all kinds of boxes.
bigiain 6y ago
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?"
- secfirstmd 6y ago
  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.

rurban 6y ago

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.

TacticalCoder 6y ago
> He didn't claim it is broken. But then there's that line: "This destroys the RSA cryptosystem" in the abstract of the paper.
- rurban 6y ago
  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.

kadoban 6y ago

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.

Accujack 6y ago

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.