Comment by elmo2you | Hacker News Reader

Comment by elmo2you | Hacker News Reader

Parent Full thread

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.

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

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

> 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

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

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?

> If I'm Evil Social Media Company and I want to leak your secrets to someone ..

Apparently I failed to be clear. The companies in question might not (and probably don't) have evil intentions. They could either be forced (and equally forced to shut up about it), or might not even be aware of it (or not to full extend).

As business PR/politics go, a business would likely present itself safe and promoting how it cares about user privacy (bla, bla, etc). It could even publicly voice opposition to any government's wishes to extend control over them. What happens in PR/politics can be very different (and involve very different people) from what can simultaneously be dictated behind close doors in the name of compliance, national security, or whatever.

You are correct. You are indeed trusting the creator/owner of a private key with your data. It's also true that there are plenty of ways in which this trust can be violated. But to me, neither of those are what I have a gripe with.

What bugs me particularly, is that RSA intrinsically has an ability to put in a backdoor that is just as difficult to detect/determine for an outsider/user, as it is to actually break that key. What bugs me even more, is that I pretty much never hear anyone talk about that, or people countering with how there are easier (but harder to hide) ways to "break" RSA cryptography.

Maybe, in particular after Snowden, the premise of trusting the creators/owners of private keys just isn't good enough anymore (if it ever was in the first place).

The point is not that a bad actor may have six other ways till Sunday to be evil, but that the ability to add an undetectable backdoor is something I don't like for a public key scheme that still underpins the security of a majority part of the Internet today.

I guess time will tell if that was a mistake or not.

Is there an alternative public key cryptography scheme where you can be sure that there's only a single private key?

Again, no matter how secure you make the cryptography, the weakpoint is the key. Why would someone "tweak" a key, provide it to a "big commercial company" (who for some reason doesn't generate their own key?), instead of just keeping a copy of the key?

> Why would someone "tweak" a key

To make it look, at least to outsiders (be that users or researchers) like you are providing actually strong crypto. Leaking a key might not be as trivial as some people would imagine, with proper security policies in place.

You are indeed right, in that the key is usually the weak point. But there are several ways in which that can be true, with rather different consequences. If a private key of big company show up in a place where should certainly not be, pandemonium would quickly ensue.

On the other hand, a "tweaked" (intentionally weakened) key is a very different story. It will provide easy plausible deniability. It's also much easier to manage breaking larger collections of such keys (with a similar "flaw") without ever any hard evidence linking such keys together.

Is it really that hard to understand/imagine? (sincere question)

With proper security policies in place, creating a flawed key would also "not be as trivial as some people would imagine". The issue which you claimed is that one can not determine whether or not the other party is following proper security policies - which is true no matter what.

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

Reply on news.ycombinator.com