News for hackers. Stuff that matters.
Re:No, RSA Is Not Broken by mzs on Tuesday March 09, 2021 @12:06PM (#26400849)
> Instead of performing 96 lattice reductions with a near guarantee of recovering 96 smooth values, a very rough approximation with the correct determinant indicates that we would need to perform 2^200 reductions of enormous lattices to find enough smooth values.

> This is well beyond any plausible computation. It strongly suggests that this particular approach does not scale to the point of practically breaking RSA.

> However, there are many open questions. Would a different lattice construction avoid this problem? Can the bound be established in another way? What are the concrete performance numbers and asymptotic complexity?

- Keegan Ryan

https://twitter.com/inf_0_/status/1367377462582079489

Re:No, RSA Is Not Broken by mzs on Tuesday March 09, 2021 @12:07PM (#26400867)
> update: the new version of March 3rd is much easier to test, requiring SVP in dimension as low as 47 (down from 1800 !).

> Out of 1000 trials, no factoring relations was found.

- Léo Ducas

https://twitter.com/DucasLeo/status/1367367057055109125

Re:No, RSA Is Not Broken by MaxBarraclough on Tuesday March 09, 2021 @11:17AM (#26400269)
An interesting point at [0]:

> if Schnorr could “destroy RSA”, he would have destroyed one of the RSA Challenge problems to prove it. He did not.

[0] https://www.schneier.com/blog/archives/2021/03/no-rsa-is-not...

Re:No, RSA Is Not Broken by amelius on Tuesday March 09, 2021 @12:13PM (#26400938)
What kind of reasoning is this? Not all mathematicians are interested in or capable of computer programming.
Re:No, RSA Is Not Broken by chrismeller on Tuesday March 09, 2021 @12:43PM (#26401304)
You are correct, but I think it’s still a valid point. The way to demonstrate to the world that it is broken would have been to break it, and if you even skim over his bonafides it seems like something he is 1) an expert in and 2) would have the resources to demonstrate, even if not programmed by himself (grad students, perhaps?).

He’s also older and retired and could simply have the attitude of “F it, I’ll leave this here, mic drop”, so who the hell really knows.

Re:No, RSA Is Not Broken by not2b on Tuesday March 09, 2021 @01:01PM (#26401525)
He could find any number of grad students who would be happy to code up his algorithm for him, so they can be co-authors on the paper that "destroyed RSA".
Re:No, RSA Is Not Broken by lisper on Tuesday March 09, 2021 @01:25PM (#26401845)
Or any number of hackers who would be happy to do it so they could be the first to break into people's bank accounts. If RSA were broken as a result of a public announcement with no warning, there would be no doubt in anyone's mind because chaos would ensue in very short order.
Re:No, RSA Is Not Broken by Someone on Tuesday March 09, 2021 @04:52PM (#26404835)
I’m not claiming anything about the correctness of this proof, but if it isn’t correct, writing a program that implements the algorithm would be a waste of time.

So, if the proof is hard to follow and describes a complex algorithm, grad students who don’t fully grok the supposed proof might not be that happy to work on that program. They might end up looking for a nonexistent bug in their program for months.

I also think it’s illustrative to mention the Grothendieck prime (https://en.wikipedia.org/wiki/57_(number)) here, as an example of how little concern some mathematicians have for applications of their results. That _could_ explain why Schnorr didn’t bother to even ask his students to write that program.

Re:No, RSA Is Not Broken by RcouF1uZ4gsC on Tuesday March 09, 2021 @12:06PM (#26400852)
That isn't as reassuring as it seems. It may be that Schnorr could "destroy RSA", but that the computing requirements are still beyond what a researcher could have access to, but are within the abilities of a large corporation or nation-state. An example is SHA-1. We have known it was broken for some time, but it took Google's massive compute power to actually produce a real world collision.
Re:No, RSA Is Not Broken by sigzero on Tuesday March 09, 2021 @12:20PM (#26401016)
"Schnorr has been making presentations on his concept since at least 2009. In my personal opinion, 11+ years is enough time for a small group to make some kind of significant demonstration software, if people believed that the idea is likely to work.

Because this proposed factoring technique has been public for more than a decade, both specialists in lattice algorithms, and other mathematicians who focus on factoring algorithms in general, have had plenty of opportunity to study Schnorr’s ideas. I don’t see evidence that even one mathematician with relevant expertise has yet been persuaded."

It's been out there for a long time and...nada.

Re:No, RSA Is Not Broken by tom_mellior on Tuesday March 09, 2021 @03:03PM (#26403400)
Where is this quote from?
Re:No, RSA Is Not Broken by muizelaar on Tuesday March 09, 2021 @11:36AM (#26400491)
See also: https://github.com/lducas/SchnorrGate an implementation in Sage Math.
Re:No, RSA Is Not Broken by aarchi on Tuesday March 09, 2021 @01:38PM (#26402021)
Here are some notes on the paper's authenticity (in German): https://blog.fefe.de/?ts=9ec00c82

Amusingly, at the bottom of the page, it states “Proudly made without PHP, Java, Perl, MySQL and Postgres”.

Re:No, RSA Is Not Broken by vlovich123 on Tuesday March 09, 2021 @11:35AM (#26400473)
The crypto stackexchange post leads to this Twitter thread discussing some of the math details: https://twitter.com/inf_0_/status/1367376959055962112
Re:No, RSA Is Not Broken by kzrdude on Tuesday March 09, 2021 @12:45PM (#26401332)
What's the consensus on RSA, that it's fine to use still with 4096-bit keys? Why are we not moving off of it?
Re:No, RSA Is Not Broken by ralph84 on Tuesday March 09, 2021 @01:59PM (#26402369)
NSA used to push pretty hard for moving to elliptic curve from RSA. There was some speculation they already knew better factoring methods that worked for breaking RSA.

But then the Dual_EC_DRBG backdoor came to light, so maybe they were just pushing elliptic curve to get their backdoors out there.

These days NSA pushes for post-quantum crypto, but it's not practical yet.

Re:No, RSA Is Not Broken by jlgaddis on Tuesday March 09, 2021 @07:47PM (#26406464)
> NSA used to push pretty hard for moving to elliptic curve from RSA. There was some speculation they already knew better factoring methods that worked for breaking RSA.

Just to add a bit more detail...

NSA was pushing EC pretty hard for a bit. Then, after a while, they switched gears and said (and I'm paraphrasing here, obviously), "Actually, don't worry about it. If you've already switched to EC, that's fine, just stick with it. If you're still on RSA, though, just stick with that. There's no need to switch, both are fine (for the time being)."

So who knows WTF they were thinking. Unfortunately, it's impossible to get any real "signal" from their statements since they can no longer be trusted. They could be legitimately looking out for our best interests or they could be trying to get everyone to use less secure algorithms -- and we have no way to know which it is!

(Personally, I've just carried on normally and pretended like they never said anything at all).

Re:No, RSA Is Not Broken by tialaramex on Tuesday March 09, 2021 @07:28PM (#26406332)
You should avoid attempting RSA key exchange because it's too hard to safely do this correctly and even if you do that loses forward secrecy in protocols where that means something.

If you're just doing signatures (so e.g. modern TLS or SSH) then any of the elliptic curve signature schemes are nicer than RSA. However, whether that's practical for you to rely on will depend on whether it's important to let random peers from the public Internet connect with whatever mouldy garbage they're running which may only do RSA.

Re:No, RSA Is Not Broken by upofadown on Tuesday March 09, 2021 @02:42PM (#26403086)
I still need to be convinced that more than 2048 bit RSA keys are required. There seems to be no rational reason to use longer keys.

There have been no real breakthroughs in breaking RSA for 15-20 years. So if you were playing the odds you would actually prefer RSA over systems invented more recently.

Re:No, RSA Is Not Broken by aborsy on Tuesday March 09, 2021 @11:10AM (#26400194)
How could someone write in the abstract of a supposedly scientific paper, “This destroys RSA cryptosystem“?

Weird!

Re:No, RSA Is Not Broken by eru on Tuesday March 09, 2021 @11:19AM (#26400290)
It's a pre-print. Anyone can upload those.
Re:No, RSA Is Not Broken by iso8859-1 on Tuesday March 09, 2021 @11:30AM (#26400423)
It's not anyone though, it is a renowned professor called Claus Peter Schnorr. And he has claimed through other channels that it is his paper.
Re:No, RSA Is Not Broken by anoonmoose on Tuesday March 09, 2021 @12:14PM (#26400957)
ok then reformulate that to "even renowned professors can occasionally get high on their own supply and make wild claims"
Re:No, RSA Is Not Broken by est31 on Tuesday March 09, 2021 @12:35PM (#26401212)
Not anyone. For untrusted people, arxiv needs someone trusted to vouch for you.
Re:No, RSA Is Not Broken by tom_mellior on Wednesday March 10, 2021 @02:02AM (#26408647)
For whatever it's worth, the preprint in question was not on arXiv but on https://eprint.iacr.org/index.html which looks like it's even more laid back regarding submissions.
Re:No, RSA Is Not Broken by eru on Tuesday March 09, 2021 @10:48PM (#26407531)
Thanks! I didn't know that.

Getting endorsement seems a relatively low bar, but it's still a bar.

Re:No, RSA Is Not Broken by tom_mellior on Tuesday March 09, 2021 @03:04PM (#26403426)
Huh? The way I remember it, registering at arXiv is the same as registering anywhere else. I certainly don't recall needing someone to vouch for me.
Re:No, RSA Is Not Broken by est31 on Tuesday March 09, 2021 @03:41PM (#26403897)
Re:No, RSA Is Not Broken by tom_mellior on Tuesday March 09, 2021 @04:09PM (#26404298)
Ah. "In most cases, automatic endorsement is given to authors from known academic institutions and research facilities." So the ancestor's "Anyone can upload those." should have been "Anyone with an academic email address can upload those."
Re:No, RSA Is Not Broken by aceon48 on Tuesday March 09, 2021 @12:32PM (#26401164)
RSA is broken, but likely from Quantum computers held by a nation state
Re:No, RSA Is Not Broken by waynesonfire on Tuesday March 09, 2021 @12:37PM (#26401230)
Are you referring to this https://www.wired.com/story/microsoft-retracts-disputed-quan... quantum computer whose breakthrough was retracted?
Re:No, RSA Is Not Broken by GuB-42 on Tuesday March 09, 2021 @02:22PM (#26402735)
I don't believe it. The state of the art in quantum computing is far from it. In fact, we are not even sure if it is possible at all due to the extremely low temperatures required for a significant number of entangled qubits.

In general, secret tech is only more advanced than what is available in the open when it has no real application outside defense. But a lot of people want quantum computers more simple than the ones that can crack RSA, and they don't have them. So I find it unlikely that any nation state has a quantum computer able to break current crypto.

The focus on post-quantum cryptography is mostly preventive.

Re:No, RSA Is Not Broken by theandrewbailey on Tuesday March 09, 2021 @12:26PM (#26401100)
We've already used and proven Shor's algorithm[0]; we just need a machine with enough quantum bits to defeat conventional encryption.

[0] https://en.wikipedia.org/wiki/Shor%27s_algorithm