3 ms·

Yes, that's what I meant with dated. So the linked paper is a work in progress from half a year ago, but presented today on ePrint and with an abstract that has

Yes, that's what I meant with dated. So the linked paper is a work in progress from half a year ago, but presented today on ePrint and with an abstract that has extra text added. I can not determine if this "discovery" could actually break any practically operating RSA systems. Considering how that is probably true for most people, that could even be the intent here. The claim that this will destroy RSA cryptosystems, so all of them categorically, just feels like a big red flag to me. If it said it could break RSA under certain circumstances .. then maybe. Don't get me wrong, I think there are plenty of things wrong with RSA. Not least of all that determining if a key pair has a backdoor (when only having access to a public key), is essentially just as hard as deriving a private key from a public key (both require you to factor the product of two primes). It still puzzles me that apparently only cryptographic strength has been an argument for the adoption of RSA, but not the ability to detect any (trivially simple to add) backdoor. Apparently we are all supposed to trust whoever generated an RSA key pair (and only supplies a public key). Something I'd rather not do in this day and age.

phkahler 6y ago
You're supposed to generate your own key pair. Keep the private one and publish the public one.
jfrunyon 6y ago
Why would someone backdoor their own key when they could instead just mirror the data or something? Yes, the person you are encrypting something towards is responsible for ensuring that encryption is secure. No matter how secure you make the cryptography, the other party could still just leak the key...
- elmo2you 6y ago
  > Why would someone backdoor their own key when they could instead just mirror the data or something? Ever thought about .. let say big commercial companies (e.g. social media platforms), using keys that are either knowingly or unknowingly tweaked? A backdoor might not be trivially simple (one of the primes being fixes), but e.g. one prime be somehow part of any collection that is smaller than the pool of truly random primes. The problem then changes into "just" a list of division on the product of primes, with all potential candidates. A third party with the right information would have the practical ability to circumvent the encryption. Still, at the same time, the companies can (maybe even sincerely) claim they use strong cryptography that "can't be broken" (when it has no backdoor). Luckily, no government would ever consider either demanding such things, or covertly implement them through a compromised supply chains (or standard bodies?), even without the knowledge of their targets. [/sarcasm] To be clear, I'm not saying this actually happens. I honestly don't know. There is also something to say that this would already have leaked if it did happen. Maybe. On the other hand, some rather nasty secrets have successfully been kept for a long time. Sometimes decades, or still denied after as much as a century. I'm only saying that it is practically impossible to independently determine if such things are happening, while the technically possibility actually exists. Those involved might themselves not even be aware of it, which makes it even more problematic. Which makes me wonder, why RSA was ever adopted in the first place. I know it all made more sense when it was introduced, in a world with a lot more trust (maybe always naively, considering some historical revelations). But with everything that has happened ever since, the world has changed a lot. > No matter how secure you make the cryptography, the other party could still just leak the key. That's a whole different topic and not what I was pointing at.
  - erincandescent 6y ago
    > That's a whole different topic and not what I was pointing at. No, fundamentally it is If I'm Evil Social Media Company and I want to leak your secrets to someone (the NSA, KGB, whatever), I could 1. Send your plaintext to them (easy) 2. Send them the private key (arguably even easier - I don't have to mirror the traffic, and only my key security officers need to be aware of the fact that we are doing this) 3. Figure out some complex method to make a backdoored key which is backdoored in a way that _only they_ can exploit. You'll pick 1 or 2 every time. Fundamentally, you trust the owner(s) of the private key with your data, since they can just decrypt it and share it and preventing them from dooming you with "weak keys" is more about protecting them from themselves (i.e. accidentally generating weak keys) than anything else
    - owenmarshall 6y ago
      > Figure out some complex method to make a backdoored key which is backdoored in a way that _only they_ can exploit. I don’t disagree with your conclusion, but we are pretty sure the NSA has engaged in these attacks before: launching and pushing to standardize a patently bad RNG with very suspicious constructs and then bribing RSA Labs $10m to make it the default in their products. So option three isn’t just good in theory, the NSA very likely put it into practice with Dual_EC_DRBG.
    - tialaramex 6y ago
      If you use a modern protocol, doing (2) doesn't make any difference for this purpose on its own. The server's long term private key for say, TLS 1.3 (and the popular modes of TLS 1.2 but we'll sidestep discussing that) doesn't help you decrypt the messages. Its purpose is only to produce proof (by signing the transcript) that you're really you. There are two plausible choices you could make to achieve the goal you've described other than your suggestion (1) The first option is you send the ephemeral session secrets, if the hypothetical Bad Guys you want to help are only interested in retrospectively decrypting transmissions you could even batch these secrets up and send them over periodically, one flash drive full of secrets at a time for example. The other alternative is that you choose one (or a few) value for your supposedly ephemeral random choice in ECDH and communicate this value to the Bad Guys. This is of course detectable by your peers, some systems may in fact detect this already. By knowing what your choice will be in ECDH they can figure out the agreed session secrets each time. Unlike your option (2) this is not very subtle. Why are flash drives full of secret data sent to the KGB every morning? Or why does your "secure" server always pick 7 as its random number?

phkahler 6y ago

You're supposed to generate your own key pair. Keep the private one and publish the public one.

jfrunyon 6y ago

Why would someone backdoor their own key when they could instead just mirror the data or something? Yes, the person you are encrypting something towards is responsible for ensuring that encryption is secure. No matter how secure you make the cryptography, the other party could still just leak the key...

elmo2you 6y ago
> Why would someone backdoor their own key when they could instead just mirror the data or something? Ever thought about .. let say big commercial companies (e.g. social media platforms), using keys that are either knowingly or unknowingly tweaked? A backdoor might not be trivially simple (one of the primes being fixes), but e.g. one prime be somehow part of any collection that is smaller than the pool of truly random primes. The problem then changes into "just" a list of division on the product of primes, with all potential candidates. A third party with the right information would have the practical ability to circumvent the encryption. Still, at the same time, the companies can (maybe even sincerely) claim they use strong cryptography that "can't be broken" (when it has no backdoor). Luckily, no government would ever consider either demanding such things, or covertly implement them through a compromised supply chains (or standard bodies?), even without the knowledge of their targets. [/sarcasm] To be clear, I'm not saying this actually happens. I honestly don't know. There is also something to say that this would already have leaked if it did happen. Maybe. On the other hand, some rather nasty secrets have successfully been kept for a long time. Sometimes decades, or still denied after as much as a century. I'm only saying that it is practically impossible to independently determine if such things are happening, while the technically possibility actually exists. Those involved might themselves not even be aware of it, which makes it even more problematic. Which makes me wonder, why RSA was ever adopted in the first place. I know it all made more sense when it was introduced, in a world with a lot more trust (maybe always naively, considering some historical revelations). But with everything that has happened ever since, the world has changed a lot. > No matter how secure you make the cryptography, the other party could still just leak the key. That's a whole different topic and not what I was pointing at.
- erincandescent 6y ago
  > That's a whole different topic and not what I was pointing at. No, fundamentally it is If I'm Evil Social Media Company and I want to leak your secrets to someone (the NSA, KGB, whatever), I could 1. Send your plaintext to them (easy) 2. Send them the private key (arguably even easier - I don't have to mirror the traffic, and only my key security officers need to be aware of the fact that we are doing this) 3. Figure out some complex method to make a backdoored key which is backdoored in a way that _only they_ can exploit. You'll pick 1 or 2 every time. Fundamentally, you trust the owner(s) of the private key with your data, since they can just decrypt it and share it and preventing them from dooming you with "weak keys" is more about protecting them from themselves (i.e. accidentally generating weak keys) than anything else
  - owenmarshall 6y ago
    > Figure out some complex method to make a backdoored key which is backdoored in a way that _only they_ can exploit. I don’t disagree with your conclusion, but we are pretty sure the NSA has engaged in these attacks before: launching and pushing to standardize a patently bad RNG with very suspicious constructs and then bribing RSA Labs $10m to make it the default in their products. So option three isn’t just good in theory, the NSA very likely put it into practice with Dual_EC_DRBG.
  - tialaramex 6y ago
    If you use a modern protocol, doing (2) doesn't make any difference for this purpose on its own. The server's long term private key for say, TLS 1.3 (and the popular modes of TLS 1.2 but we'll sidestep discussing that) doesn't help you decrypt the messages. Its purpose is only to produce proof (by signing the transcript) that you're really you. There are two plausible choices you could make to achieve the goal you've described other than your suggestion (1) The first option is you send the ephemeral session secrets, if the hypothetical Bad Guys you want to help are only interested in retrospectively decrypting transmissions you could even batch these secrets up and send them over periodically, one flash drive full of secrets at a time for example. The other alternative is that you choose one (or a few) value for your supposedly ephemeral random choice in ECDH and communicate this value to the Bad Guys. This is of course detectable by your peers, some systems may in fact detect this already. By knowing what your choice will be in ECDH they can figure out the agreed session secrets each time. Unlike your option (2) this is not very subtle. Why are flash drives full of secret data sent to the KGB every morning? Or why does your "secure" server always pick 7 as its random number?