Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

“This destroys the RSA cryptosystem”

eprint.iacr.org

Post reply on HN
Print view View original

111–120 of 152 posts

Re: “This destroys the RSA cryptosystem”

#111

Post by owenmarshall »

erincandescent wrote: post #102
elmo2you wrote: post #96

Earlier quoted context omitted.

> 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 rando…

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

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

Re: “This destroys the RSA cryptosystem”

#112

Post by _dps »

schoen wrote: post #109
_dps wrote: post #94

Earlier quoted context omitted.

There's a very amusing epilogue in Steven Levy's "Crypto" [0] about the fact that either RSA or Diffie-Hellman (I've forgotten which) was in fact known to the intelligence services for 10+ years prior to its re-discovery among public researchers. These are people who are very good at keeping secrets. [0] https://www.amazon.com/Crypto-Rebels-Government-Privacy-Digi...

https://en.wikipedia.org/wiki/Public-key_cryptography#Classi... Both, but neither for as long a period of time beforehand as you remember.

Aha! Good correction, thank you. I must have been remembering how long the discovery remained classified, not how long it predated the public discovery.

Re: “This destroys the RSA cryptosystem”

#113

Post by balupton »

I've gone ahead and updated the following wiki pages to get the right eyeballs on this: https://en.wikipedia.org/wiki/Integer_factorization https://en.wikipedia.org/wiki/RSA_(cryptosystem) https://en.wikipedia.org/wiki/Claus_P._Schnorr

Also cross-shared with Cloudflare's forum, as I believe they would be interested: https://community.cloudflare.com/t/this-destroys-the-rsa-cry...

Re: “This destroys the RSA cryptosystem”

#116

Post by hedora »

LeegleechN wrote: post #69
dleslie wrote: post #52

Earlier quoted context omitted.

If true... Hot damn! There's NP-Hard problems that if we had polynomial time solutions for we could vastly improve the quality of life on earth.

Integer factoring is in a fairly sparse in-between zone between polynomial and NP Hard problems. This is why quantum computers can have a near exponential speedup from them (disregarding this claimed result) and only a polynomial speedup for NP Hard problems. So even if this result holds it can't be converted into a fast solution for all NP Hard problems.

Though, if conventional computers can factor in polynomial time after all, I wonder if that would suggest quantum computing is no better than a polynomial speedup.

Re: “This destroys the RSA cryptosystem”

#117

Post by ralph84 »

tveita wrote: post #83
Centigonal wrote: post #13

The author of this paper is Claus P. Schnorr[1], of Schnorr signature fame. The paper has almost the same title as a 2017 draft paper[2] of his. The “This destroyes the RSA cryptosystem” quote is not in the linked paper abstract. This seems fishy. [1] https://en.wikipedia.org/wiki/Claus_P._Schnorr [2] https://www.math.uni-frankfurt.de/~dmst/research/papers/SVP9...

So are you saying I shouldn't run out and short the RSA stock? :) I was curious about the submission process for ePrint, it looks like there is supposed to be some vetting, even though it is explicitly not fact checked or peer reviewed. You do get papers from cranks and blockchainers but presumably Schnorr doesn't fall into those categories. https://eprint.iacr.org/about.html

RSA is owned by private equity so there's nothing to short. In any case, the patent on RSA is long-expired and OpenSSL drove the price of crypto libraries to $0, so any revenue RSA the company gets from RSA the cryptosystem is negligible.

Re: “This destroys the RSA cryptosystem”

#118

Post by stjohnswarts »

hn_throwaway_99 wrote: post #114

If this did actually "destroy the RSA cryptosystem", seems like a proof of concept would actually be trivial to demonstrate. Given that, my bet is on this (or, rather, at least that particular sentence) being BS.

Yeah I highly doubt the author of the paper would miss out on a chance like that. I think this is probably a lot of pearl clutching.

Re: “This destroys the RSA cryptosystem”

#119

Post by tialaramex »

erincandescent wrote: post #102
elmo2you wrote: post #96

Earlier quoted context omitted.

> 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 rando…

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

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?

Re: “This destroys the RSA cryptosystem”

#120

Post by sundbry »

7800 wrote: post #106
hyper_reality wrote: post #77

This is being discussed in CryptoHack Discord. We are struggling to understand the paper, it is written in a very dense style and the difficulty is compounded by the fact that lattice problems can be a challenging topic even for cryptographers. Either way, we think that the title "this destroys the RSA cryptosystem" is sensationalistic and probably incorrect. It is presumably based on the fact that the paper claims t…

It actually states, “This destroyes the RSA cryptosystem.” Seems a bit like the way an old pirate might speak, or at least someone hundreds of years old.

Its a meme. "This kills the crab."
Post reply on HN