I'd always figured they'd have a (useful) quantum computer sitting in the basement of Ft. Meade at some point, and it's existence would be Top Secret with whatever codeword means "if this leaks, or we think it'll leak, we just assassinate you"
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.
I don't think it's too far a leap to suggest that knowledge like that could get you killed. Lets ask some Iranian nuclear scientists to see what they think...
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.
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!!
It's for various reasons, but one of them is that, from an attacker perspective, you don't have to strictly solve the factorization problem. You just need to be able to crack a tiny fraction of the keys in a reasonable amount of time in order for RSA at that key length to be considered unsafe to use. In that sense the attacker gets the benefit of best-case complexity.
According to RSA Factoring Challenge 829 bits were broken recently [0]. The total computation time was roughly 2700 core-years [1].
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.
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 security level since general purpose quantum computers might be made within that time.
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.
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.
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.
Don't confuse brute forcing 2^65 possibilities with factoring a 2^65 bit semi-prime (n in RSA).
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
2^1024 bit RSA is about 2^80 in bit strength.
This example was 2^65 bit RSA, which is negligible in bit-strength.
This reminds me of a story a professor told us in school. We were talking about all this and he explained that it’s an assumption that no fast algorithm exists, he sure couldn’t find one but added maybe the NSA could. He said there was this student in his class that was really bright, top 5. On an exam this student scored a 40 the next highest score was a 50, the top three scores were something like 70-90+. He was the student that scored a 40. He and the 50 are accomplished professors/researchers in their field—the top two scorers work for the NSA—so he says, “maybe the NSA can do it.”
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.
Aha! Good correction, thank you. I must have been remembering how long the discovery remained classified, not how long it predated the public discovery.
Dunno we have post quantum algorithms which don't rely on factoring prime numbers like RSA does, but it will be a lot of systems administration type work to make sure that nobody is using RSA keys anymore.
RSA is a "public key" cryptography system, where you have a public key that everyone's allowed to know, and a private key that you keep secret. Anyone can use the public key to encrypt messages, but you need the private key to decrypt messages.
(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.)
I would be very skeptical if there is indeed a poly time algorithm for integer factorization. If that's actually what the paper claims then it's a very big claim.
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.
It's hard to figure out what they are claiming, which makes the whole paper seem fishy.
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.
>This last sentence of the abstract, "This destroyes the RSA cryptosystem", does not appear on the abstract of the actual PDF (which also appear to be dated).
It appears on the linked page only, it is someone's assessment of the result. Whether that person is qualified to make that assessment is anyone's guess
It is a direct quote from the end of the abstract. The paper could hardly be titled that way. It is editorialising and thus against the guidelines.. but it's reasonable IMO.
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.
Can someone please correct me? We don't know polynomial CVP/SVP algorithms correct? In fact, isn't SVP an NP-Hard problem? Why would this "destroy" RSA?
I'm not sure if this is the claim in the paper; but I'll try to explain in plain terms.
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.
They only tested with numbers size of ~2^800, which is around 240 digits, but I believe (correct me if I'm wrong) there exists usages of RSA with over 600 digits, so it'll still take a massively long amount of time to factor those numbers...
It's worth noting that numbers of this size are already being factored with existing techniques. RSA-250, a 250 digit (829 binary digit) product of two primes was factored pretty recently: https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/202...
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.
Thanks, looks great. It's by Julian Assange and a few others. First words of the book:
"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!)
The American and Australian governments have both advocated strongly, recently, for the ability of law enforcement to decrypt civilian communications. Of course, there's plenty of other countries that would desire this imbalance of power, as well.
> Is there anyone (openly) arguing this would be a bad thing?
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.
I was surprised to see, in the 1999 email you linked, that NSA mass surveillance was already widely known, before the NSA ramp up from 9/11 and before the Snowden disclosures.
> 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.
At the time ECHELON was well-known among hacker and conspiracy circles, and it was making big news overseas due to major disclosures by partner governments.
> The idea is that if lots of people add suspicious words to their messages, the agencies will get so busy with spurious input that they will have to give up reading it all.
>
I was surprised to see, in the 1999 email you linked, that NSA mass surveillance was already widely known, before the NSA ramp up from 9/11 and before the Snowden disclosures.
Exactly. But before the Snowden leaks hardly anyone in the mainstream believed or listened to these "conspiracist" hacker/cypherpunk dudes.
I recently rewatched the movie "Enemy of the State" from 1998.
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.
it was widely known that they were At It, but things like "they undetectably tap fibres" or "AT&T would allow mass tee-ing of traffic" were considered a bit fringe-y, in my recollection. and of course turned out to be true and not even in the most extreme of their operations.
Here is a little background on one of those fringe theories that turned out to be true. Not pre-9/11, but pre-Snowden. https://en.wikipedia.org/wiki/Room_641A
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.
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.
This last sentence of the abstract, "This destroyes the RSA cryptosystem", does not appear on the abstract of the actual PDF (which also appears to be dated).
How does it destroy RSA? Under what conditions? That claim sounds rather broad and definitely bold, to say the least.
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, 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.
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.
> 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
> 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.
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?
> If I'm Evil Social Media Company and I want to leak your secrets to someone ..
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.
Again, no matter how secure you make the cryptography, the weakpoint is the key. Why would someone "tweak" a key, provide it to a "big commercial company" (who for some reason doesn't generate their own key?), instead of just keeping a copy of the key?
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)
With proper security policies in place, creating a flawed key would also "not be as trivial as some people would imagine". The issue which you claimed is that one can not determine whether or not the other party is following proper security policies - which is true no matter what.
There's a difference between cryptography broken in "theory" and broken in "practice". Couldn't find anything relevant to that point in the paper. Who here is qualified to make that assessment?
The linked page links to the full article as a PDF, though I'll be honest and say it still doesn't help me fully understand the ramifications of that statement.
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.
It looks like someone read the paper and came to the conclusion that this shortens the expected lifespan of RSA and submitted the paper to IACR. I doubt it was Schnorr himself who decided to make the sensationalist claim.
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.
If you've been following Schnorr's work, his pathway for the last decade can be summed up as thus:
* 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.
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 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.
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.
I assume “we” refers to the aforementioned community on Discord. I would hardly call that a claim to authority; it’s closer to, “my friends and I think this is bunk.”
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.”
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.
That's not necessarily the case in general. If you had an algorithm which, given a billion dollars' worth of specialized lattice reduction ASICs, could break 2048-bit RSA in a few months' time, then for all practical purposes this would mean that 2048-bit RSA was broken -- there are plenty of state actors who would drop that kind of money in a heartbeat -- but that doesn't mean that some guy who came up with it would be able to do a demo on his laptop.
(Not saying that the above has anything to do with this paper in particular.)
But still it would be trivial to write a program that could demonstrate this, no? Something that you could show that perhaps broke an unreasonably short RSA key in a shorter time than expected.
151 comments
[ 3.9 ms ] story [ 219 ms ] threadP.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.
[1] https://charts.bitcoin.com/btc/chart/hash-rate#5ma4
I factored a 2^65.4 bit semi-prime using Sagemath on an M1 in milliseconds.
2^1024 bit RSA is about 2^80 in bit strength.This example was 2^65 bit RSA, which is negligible in bit-strength.
[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.)
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.
[1] https://www.math.uni-frankfurt.de/~dmst/teaching/WS2019/SVP9...
https://news.ycombinator.com/item?id=26322289
"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...
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.
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
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://eprint.iacr.org/2021/232.pdf
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://marc.info/?l=cypherpunks&m=95280154624588&w=2
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.
https://en.wikipedia.org/wiki/Crypto_Wars
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.
https://en.wikipedia.org/wiki/ECHELON
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://eprint.iacr.org/about.html
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)
https://eprint.iacr.org/2021/232.pdf
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.
That discussion is from 2010. The download link for the paper does not seem to work.
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.
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.”
There is also: https://simons.berkeley.edu/sites/default/files/docs/14975/c...
Also cross-shared with Cloudflare's forum, as I believe they would be interested: https://community.cloudflare.com/t/this-destroys-the-rsa-cry...
(Not saying that the above has anything to do with this paper in particular.)