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

91–100 of 152 posts

Re: “This destroys the RSA cryptosystem”

#91

Post by setpatchaddress »

hardwaregeek wrote: post #43
smolder wrote: post #18

Earlier quoted context omitted.

If that's the case it's funny to think... NSA could have sat on this for years. Though that would be a really hard secret to keep.

I've held the theory that if anybody found something like fast prime factoring or a P = NP proof, they'd get assassinated pretty quickly. It'd be in basically every government's interest to get the knowledge, then make sure nobody else has it.

The Trump presidency forever cured me of the last vestiges of the idea that government would be capable of recognizing the importance of something like this and authorizing something like an assassination as a remedy.

Which is mostly a good thing, to be clear.

Re: “This destroys the RSA cryptosystem”

#94

Post by _dps »

smolder wrote: post #18
pkulak wrote: post #6

Earlier quoted context omitted.

Yeah, if this really is fast prime factoring, we're all in a lot of trouble.

If that's the case it's funny to think... NSA could have sat on this for years. Though that would be a really hard secret to keep.

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

Re: “This destroys the RSA cryptosystem”

#95

Post by rincebrain »

eternalny1 wrote: post #85
muricula wrote: post #36

The website is being hugged to death, but archive.org has scraped the PDF: https://web.archive.org/web/20210302215033/https://eprint.ia...

This is a different paper. The linked one is: received 1 Mar 2021 The PDF is: work in progress 31.10.2019

No, that archive.org link is a valid link for the PDF of the linked paper - if you click through to the PDF from the HN link, it's identical, including the "work in progress 31.10.2019" stamp on the first page.

Why "work in progress 31.10.2019" appears on something supposedly submitted 1 Mar 2021 is an open question, but they do point to the same thing.

Re: “This destroys the RSA cryptosystem”

#96

Post by elmo2you »

jfrunyon wrote: post #89
elmo2you wrote: post #72

Earlier quoted context omitted.

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…

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.

Re: “This destroys the RSA cryptosystem”

#97

Post by szc »

SAI_Peregrinus wrote: post #86
londons_explore wrote: post #45

Earlier quoted context omitted.

RSA has always been a lot weaker than it seems at first... I mean, people have been moving from 1024 to 2048 bit primes... The biggest number I could conceivably brute force is probably about 2^50. Maybe 2^60 with a big budget, or 2^65 with a team of ASIC designers. The mere fact that 2^1024 is considered risky tells you how far from ideal RSA is!!

Bitcoin last peaked at a hash rate of 170EH/s[1]. That's about 2^61 double SHA256 hashes per second. There are about 31.6E6 seconds per year. So around 72.5E24 hashes/year, or 2^86. VERY expensive, but 2^80 is well within brute-force range. I'd consider any symmetric system with less than 112 bits of security to be potentially breakable within the next few years. For anything over 50 years, I'd want a 256-bit securit…

Comparing these two sets of O() estimates is a bit dubious. SHA256 uses almost no memory and hashing can effectively be distributed across machines at no cost. All of the current factorization mechanisms build vast sparse matrices and then perform reduction operations. At some threshold point the memory needed exceeds the capacity of a single machine. This means the O() estimates will hit a speed wall as it is necessary to distribute the computation. Single machine size / memory availability is of course a moving target! O() complexity bounds are great, but unless you've got a machine that can perform every one of the operations at a cost multiplier of effectively 1 it is not always possible scale things up or make this sort of algorithm comparison.

Re: “This destroys the RSA cryptosystem”

#98

Post by SAI_Peregrinus »

szc wrote: post #97
SAI_Peregrinus wrote: post #86

Earlier quoted context omitted.

Bitcoin last peaked at a hash rate of 170EH/s[1]. That's about 2^61 double SHA256 hashes per second. There are about 31.6E6 seconds per year. So around 72.5E24 hashes/year, or 2^86. VERY expensive, but 2^80 is well within brute-force range. I'd consider any symmetric system with less than 112 bits of security to be potentially breakable within the next few years. For anything over 50 years, I'd want a 256-bit securit…

Comparing these two sets of O() estimates is a bit dubious. SHA256 uses almost no memory and hashing can effectively be distributed across machines at no cost. All of the current factorization mechanisms build vast sparse matrices and then perform reduction operations. At some threshold point the memory needed exceeds the capacity of a single machine. This means the O() estimates will hit a speed wall as it is necess…

True! Comparing symmetric speeds for SHA256 to the operations needed in RSA is iffy at best. But for illustrating the point that brute-forcing the keys used in current RSA is a braindead way to attack things that doesn't really matter. It just further enhances the point. Brute force just isn't the attack to use for comparisons.

Re: “This destroys the RSA cryptosystem”

#100

Post by zelon88 »

setpatchaddress wrote: post #91
hardwaregeek wrote: post #43

Earlier quoted context omitted.

I've held the theory that if anybody found something like fast prime factoring or a P = NP proof, they'd get assassinated pretty quickly. It'd be in basically every government's interest to get the knowledge, then make sure nobody else has it.

The Trump presidency forever cured me of the last vestiges of the idea that government would be capable of recognizing the importance of something like this and authorizing something like an assassination as a remedy. Which is mostly a good thing, to be clear.

The American government isn't the only one you have to worry about.
Post reply on HN