“This destroys the RSA cryptosystem”
eprint.iacr.org
eprint.iacr.org
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...
He also apparently misspelled(?) his own name. It's "Claus-Peter" (also on other publications), not "Claus Peter". agreed, seems odd.
https://link.springer.com/chapter/10.1007/978-3-642-42001-6_...
Not quite the same title. He has papers with similar titles since at least 2010.
I wanted to say thanks - this document linked to on his wikipedia page was unexpectedly fascinating! NSA, patents, conspiracies..
https://www.orbooks.com/catalog/cypherpunks/
Or this:
https://cryptoanarchy.wiki/getting-started/what-is-the-cyphe...
"What is a Cypherpunk?
Cypherpunks advocate for the use of cryptography and similar methods as ways to achieve societal and political change. Founded in the early 1990s, the movement has been most active during the 1990s “cryptowars” and following the 2011 internet spring. The term cypherpunk, derived from (cryptographic) cipher and punk, was added to the Oxford English Dictionary in 2006"
So I thought, hmm that sounds like the crypto-anarchy that was discussed on HN the other day. And your 2nd link has a page on that[1]. Indeed they sound like the same idea – one is the people, the other is the system they want. Cyber-equality. Defined, rather, by the system they don't want: the powerful able to read the communications of the less powerful, but not vice versa.
Is there anyone (openly) arguing this would be a bad thing? (Also I'm wondering why I've heard about bitcoin/blockchain a million times but didn't even know what these words meant!)
[1] https://cryptoanarchy.wiki/getting-started/what-is-a-cypherp...
Examples:
https://nakedsecurity.sophos.com/2017/10/12/us-government-ca...
https://www.npr.org/2020/02/21/805032627/trump-administratio...
I guess you missed the EARN IT bill last year? It happens so often I've lost track of it. The EFF and various organizations have to push for it every year, it's disheartening. At this point I think we need a constitutional amendment for encryption, but I'm not sure if the public sentiment is right for that now.
Also, I guess I meant, is there anyone aside from those in power arguing for it!
> Actually, I don't think of the NSA's plots to deny everyone but themselves (and those they dub worthy) access to strong un-GAKed commercial cryptography as a conspiracy, per se. NSA officials acted upon a fairly open if Byzantine strategy. It was hatched by men who obviously believe that Western liberal society is best safeguarded if the US can continue to gleen the benefits of the huge passive eavesdropping net that has for decades sustained America's geo-political dominance.
Here's a current output from `M-x spook` on my machine:
> Europol BATF bluebird secure Narco banners Blister agent BVD fraud SADMS UKUSA mania weapons of mass destruction Virii EDI Bin Laden
[1] https://www.gnu.org/software/emacs/manual/html_node/emacs/Ma...
Wow - so quaint!
Exactly. But before the Snowden leaks hardly anyone in the mainstream believed or listened to these "conspiracist" hacker/cypherpunk dudes.
Money quotes:
>The government's been in bed with the entire telecommunications industry since the forties. They've infected everything. They get into your bank statements, computer files, email, listen to your phone calls... Every wire, every airwave. The more technology used, the easier it is for them to keep tabs on you. It's a brave new world out there.
>Fort Meade has 18 acres of mainframe computers underground. You're talking to your wife on the phone and you use the word "bomb", "president", "Allah", any of a hundred keywords, the computer recognizes it, automatically records it, red-flags it for analysis. That was 20 years ago.
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://twitter.com/ManishEarth/status/1366906561486983171 https://www.math.uni-frankfurt.de/~dmst/teaching/WS2019/SVP9...
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 to reduce some forms of integer factorisation to a lattice problem which can be solved in polynomial time. However, whether this technique applies in the general case to RSA moduli is not argued here and the claim seems to be premature.
Seems a bit like the way an old pirate might speak, or at least someone hundreds of years old.
This is discussed here, at Hacker News. It's also discussed at many other places on the internet. :-)
Why is this chat room you mention relevant? And who are "we" you speak of? You are presenting yourself as some kind of authority, but you need to back that claim up.
That’s not to be dismissive of their opinion, but I don’t think it’s accurate to call it a claim to authority. It’s the same as saying “a channel on IRC” or “a group on WhatsApp.”
"Factoring Integers by CVP and SVP Algorithms"
It would hardly be getting such attention with the original title, and that attention is either what it needs, or what it needs to promptly dispell it.
EDIT: deleting claim about name, matches other places
seems somewhat fishy, I'll wait what experts say in the next few days...
How does it destroy RSA? Under what conditions? That claim sounds rather broad and definitely bold, to say the least.
^ Date on the pdf
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.
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...
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.
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
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.
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?
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.
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)
P.S. Please don't bring Cooty.
Which is mostly a good thing, to be clear.
I would consider 1024 bits risky in the following 10 years. 2048 bits probably won't ever be broken without significant algorithmic breakthrough or quantum computers.
[0] https://en.wikipedia.org/wiki/RSA_Factoring_Challenge
[1] https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/202...
But RSA is about a thousand times slower than double-SHA256, yet it still needs such large keys for security. That's because nobody is going to brute-force RSA, there are far better options. Like the General Number Field Sieve. Of course that's still exponential, this paper claims to be polynomial time for the vector-finding portion, not sure about overall. I've only skimmed it, and it's rather dense.
I factored a 2^65.4 bit semi-prime using Sagemath on an M1 in milliseconds.
// get two random primes (pretend P, Q)
sage: random_prime(2^34)
12697300267
sage: random_prime(2^33)
3962800609
// make a semi-prime (pretend N)
sage: 12697300267*3962800609
50316869230723462603
// check length of semi-prime (65-bits)
sage: log(50316869230723462603,2).n()
65.4476759618453
// factor it in 18milliseconds.
sage: time factor(50316869230723462603)
CPU times: user 9.78 ms, sys: 9.07 ms, total: 18.8 ms
Wall time: 23.2 ms
This example was 2^65 bit RSA, which is negligible in bit-strength.
bash$ time factor 50316869230723462603
50316869230723462603: 3962800609 12697300267
real 0m0.009s
user 0m0.009s
sys 0m0.000s[0] https://www.amazon.com/Crypto-Rebels-Government-Privacy-Digi...
Both, but neither for as long a period of time beforehand as you remember.
(You can also use it for digital signatures, where you provide a copy of the message and also "encrypt" the message with the private key; anyone can publicly decrypt it. If the "decrypted" message matches the original, then the signature proves that the message was signed by someone who has the private key.)
RSA works by starting with two large random prime numbers P and Q. You multiply P and Q to get a number M, and that number becomes part of the public key. An attacker who knows P and Q can compute your private key and decrypt your messages.
RSA assumes that it's computationally infeasible to factor M back into P and Q. It's supposed to be something like O(2^n), where n is the length of M.
A fast factorization algorithm breaks that assumption, allowing attackers to decrypt messages and forge digital signatures.
If Schorr has found an algorithm that does this, I would say it "destroyes the RSA cryptosystem."
(My guess: it probably doesn't work, because drafts of this paper have been out for a few years and the sky hasn't fallen yet.)
The final theorem in the paper is where the polynomial time claim is states. Can't quote it here because it would make no sense in isolation, but the math is readable and the claims should be independently verifiable.
* 2011, retires from work at RSA foundation
* 2015, publishes first version of this paper, stating, "This is a WIP".
* 2017, 2018, 2019: Publishes updates of this paper, still stating "This is a WIP". Paper mostly ignorred.
* 2021: Publishes this final update. Removes "WIP" marking. Adds sentence (verifiable in original paper), "This destroys RSA cryptosystems".
Whether or not it's true, the level of dismissal here is kinda insane. This guy has credibility up the wazoo. The paper is dense and beyond my understanding. But this guy ain't some crackpot, this isn't some out-of-nowhere change: He's been clear about his intent and goals for nearly a decade, and now he says it's achieved.
The linked one is: received 1 Mar 2021
The PDF is: work in progress 31.10.2019
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.
I don't know what that means for this paper, just happened to have those two key lengths off the top of my head.
Moreover, a 768 bit product was factored over 11 years ago, though it took two years to compute! https://en.wikipedia.org/wiki/RSA_Factoring_Challenge
That discussion is from 2010. The download link for the paper does not seem to work.
[1] https://www.math.uni-frankfurt.de/~dmst/teaching/WS2019/SVP9...
Let's say you have an algorithm that can solve NP-hard problems in polynomial time with an N% success rate.
What value of N makes the algorithm useful in practice depends on the practicality of its use as an attack against the NP-hard problem; there is an inflection point whereat the speed of the attack outstrips the speed at which the cypher can change secrets.
Also cross-shared with Cloudflare's forum, as I believe they would be interested: https://community.cloudflare.com/t/this-destroys-the-rsa-cry...
There's NP-Hard problems that if we had polynomial time solutions for we could vastly improve the quality of life on earth.
On page 14 they seem to claim a factor 2 improvement in the exponent of the quadratic number field sieve, which might be better that the general sieve for some N, but is still worse asymptotically.
(Not saying that the above has anything to do with this paper in particular.)
1. Is the 'n' small enough in the SVP problems to pay out the transform?
2. Is there inverse for this transform? It would be the way to solve NP-hard problems with a quantum computer.
What is the factorization of RSA-1024?
Extra credit:
What is the factorization of RSA-2048?