7 ms·
No, RSA Is Not Broken
- aborsy 6y agoHow could someone write in the abstract of a supposedly scientific paper, “This destroys RSA cryptosystem“? Weird!
- eru 6y agoIt's a pre-print. Anyone can upload those.
- iso8859-1 6y agoIt'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.
- anoonmoose 6y agook then reformulate that to "even renowned professors can occasionally get high on their own supply and make wild claims"
- est31 6y agoNot anyone. For untrusted people, arxiv needs someone trusted to vouch for you.
- tom_mellior 6y agoHuh? 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.
- est31 6y agohttps://arxiv.org/help/endorsement https://arxiv.org/help/endorsement
- tom_mellior 6y agoAh. "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."
- deleted 6y ago[deleted]
- eru 6y agoThanks! I didn't know that. Getting endorsement seems a relatively low bar, but it's still a bar.
- tom_mellior 6y agoFor whatever it's worth, the preprint in question was not on arXiv but on https://eprint.iacr.org/index.html https://eprint.iacr.org/index.html which looks like it's even more laid back regarding submissions.
- MaxBarraclough 6y agoAn 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-broken.html/#comment-370288 https://www.schneier.com/blog/archives/2021/03/no-rsa-is-not...
- RcouF1uZ4gsC 6y agoThat 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.
- amelius 6y agoWhat kind of reasoning is this? Not all mathematicians are interested in or capable of computer programming.
- darig 6y agoWhen the "computer programming" in question is pure mathematics, the reasoning is called "logic".
- chrismeller 6y agoYou 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.
- not2b 6y agoHe 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".
- vlovich123 6y agoThe crypto stackexchange post leads to this Twitter thread discussing some of the math details: https://twitter.com/inf_0_/status/1367376959055962112 https://twitter.com/inf_0_/status/1367376959055962112
- muizelaar 6y agoSee also: https://github.com/lducas/SchnorrGate https://github.com/lducas/SchnorrGate an implementation in Sage Math.
- mzs 6y ago> 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 https://twitter.com/inf_0_/status/1367377462582079489
- mzs 6y ago> 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 https://twitter.com/DucasLeo/status/1367367057055109125
- sigzero 6y ago"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.
- tom_mellior 6y agoWhere is this quote from?
- theandrewbailey 6y agoWe'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 https://en.wikipedia.org/wiki/Shor%27s_algorithm
- aceon48 6y agoRSA is broken, but likely from Quantum computers held by a nation state
- waynesonfire 6y agoAre you referring to this https://www.wired.com/story/microsoft-retracts-disputed-quantum-computing-paper/ https://www.wired.com/story/microsoft-retracts-disputed-quan... quantum computer whose breakthrough was retracted?
- GuB-42 6y agoI 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.
- kzrdude 6y agoWhat's the consensus on RSA, that it's fine to use still with 4096-bit keys? Why are we not moving off of it?
- ralph84 6y agoNSA 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.
- jlgaddis 6y ago> 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).
- upofadown 6y agoI 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.
- tialaramex 6y agoYou 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.
- aarchi 6y agoHere are some notes on the paper's authenticity (in German): https://blog.fefe.de/?ts=9ec00c82 https://blog.fefe.de/?ts=9ec00c82 Amusingly, at the bottom of the page, it states “Proudly made without PHP, Java, Perl, MySQL and Postgres”.