9 ms·
This got me thinking. Imagine this discovery led to a larger breakthrough on prime numbers that allowed easy factorization of large integers and effectively re
by EMIRELADERO 2y ago
This got me thinking.
Imagine this discovery led to a larger breakthrough on prime numbers that allowed easy factorization of large integers and effectively rendered public key cryptography such as RSA ineffective overnight, by allowing anyone with a consumer-grade CPU to crack any production-size key.
Does the industry have DR plans for this scenario? Can the big players quickly switch to a different, unbroken encryption system? While it would probably be a heavenly day for jailbreakers, console modders and other "device freedom" types generally, the overall impact would be disastrous and incalculable.
Does the industry simply not consider "sudden number theory breakthrough" a possible event?
- apples_oranges 2y agoWe could always switch to symmeric keys (but key exchange would be somewhat problematic). Also elliptic curves crypto doesn't use primes, so even public key/private key crypto would still be around and secure.
- shinycode 2y agoFrom what I remember in my math class where we made those cryptography calculations by hand, the teacher many years ago said that the day we could guess prime numbers it will be a disaster because many cryptographic calculations are based on the premise that we can’t guess prime numbers. I don’t know if that changed ?
- PeeMcGee 2y agoIt's easy to find primes of a given bit length, and it's easy to multiply them together. It's hard to un-multiply a given number (public key) into its unique prime factors (private key).
- mbreese 2y agoBut if we could more easily find primes, the search space for finding those prime factors would be significantly smaller. In my mind, it’s not a question of easy vs hard… it’s a question of fast vs slow. The default algorithm for finding primes is pretty simple, but it takes a lot of math and time. If you reduce the time requirements, then we start to get into trouble.
- JackSlateur 2y agoThe world has moved away from RSA etc to elliptic curves. Not everybody did, through. RSA is no longer the standard, and has not been for many years.
- opyate 2y agoStill, plenty of old stuff was scraped/sniffed under the "store now, decrypt later" methodology.
- milansuk 2y agoTrue. The only solution is to keep your data outside cloud(aka someone else's computer) no matter what encryption you use.
- K0balt 2y agoAlso means it can’t transit the internet. So actually, only on airgapped networks.
- 8372049 2y agoIf we're going to extremes like that, airgapped networks aren't truly safe either
- barelyauser 2y agoAlso, the safest data is the one never sampled into digital format and stored in computer systems.
- mckn1ght 2y agoCould you explain why that is? If I have an airgapped smart home network, someone has to come physically sniff the packets. If it’s only over ethernet, they have to physically plug in. That’s not a scalable attack strategy.
- tommiegannert 2y agoI think this is where the move to elliptic curve comes in, and that seems well on its way. Both in signatures and handshakes (Diffie-Hellman). Perhaps it's not a one minute operation to DR, but I doubt everything would be open if RSA/DH was rendered insecure overnight. I know my SSH keys are a mixed bag right now.
- exe34 2y agodoes the move to elliptic crypto suggest that the people in the know expect prime factorisation to be broken soon?
- staunton 2y agoIt's to do with "if we ever have big/good quantum computers, prime factorization is doable" and with "let's use the new shiny things". On a related note, someone might discover some elliptic curve math tomorrow and your CPU can break all that stuff just as well...
- exe34 2y agoso with my cynic hat on, maybe a bunch of people already have that and that's why we're being moved off the hard stuff.
- staunton 2y agoThe NSA had the option to do something like that when they (via NIST) standardized DES. They chose to standardize a version that's secure against attacks that only they knew at the time, shorten the key length so they can still brute-force it if they really need to, and successfully kept the attack secret until researchers at a foreign university independently discovered it decades later.
- alphager 2y agoYup, that was the older generation. The newer generation used NIST to propagate a backdoored RNG and to weaken several ECC-curves.
- scrapheap 2y agoIf someone found a way to easily factorize large integers easily on consumer grade hardware then it would be very painful as RSA is one of the big public key algorithms. Before you start worrying about it though consider that RSA has held up for 47 years of active cryptanalysis so far - during which time many alternative algorithms have been suggested as being superior, only to be broken a short time later. Also the push to switch to Elliptic-Curve algorithms has been more down to them being easier for computers to use to encrypt/decrypt data. Personally if I had to bet on which public key algorithm will still be around in 10 years time then I'd put my money on RSA.
- raverbashing 2y agoActually RSA has several "gotchas", so it is not that it has held up but people have managed to work around those gotchas into a working encryption system (Basically your data is not encrypted with RSA, you encrypt a secondary key, send it with RSA but the main encryption is AES see https://en.wikipedia.org/wiki/Transport_Layer_Security#Key_exchange_or_key_agreement https://en.wikipedia.org/wiki/Transport_Layer_Security#Key_e... )
- fharding 2y agoKey exchange is done for speed (symmetric key crypto is way faster than public key) and forward secrecy. It’s not done because RSA is flawed per se. We use DH instead of e.g. ElGamal encryption for the same reasons.
- raverbashing 2y agoYeah it's not so much of a flaw of RSA, but encrypting pure text with it for example is more complicated (and has more caveats with padding, etc) than just encrypting a fixed amount of bytes
- sk5t 2y agoDon’t think this merits an “actually” - using a session key et al. is basic usage and does not bear on the strength of RSA itself.
- keepamovin 2y agoI guess one perspective is finding fast factoring is considered super rare. The story is so many smart people have looked at it, it's probably impossible...for now. But that story may be its own weakness. Anyway, the risk, while just as real as something like the grid being downed by a massive solar storm with multiyear recovery period from stone age due to transformer manufacturing delays and no stockpiles, just seems too minuscule/theoretical to spend much time on - from that point of view. Regarding any plan, I don't know if it's so easy to just switch to ECC, because actual asymmetric encryption with ECC depends on shared secret, which (if you're assuming an unsecured exchange channel due to RSA being broken), is more vulnerable to MITM than RSA. I don't think it's an easy swap out. All that aside, another point of view is RSA is probably already broken, the break is just secret to the codebreaking agencies. It would be very desirable for them to keep their breakthrough secret. That might even involve trying to find ways to suppress any "sudden number theory breakthroughs" hahaha! :)
- atemerev 2y agoThe industry couldn’t even prepare for a bad Crowdstrike update. And yet, it figured things out in a few days or so. The ability to prepare for catastrophic scenarios is overestimated. The ability to survive them is underestimated.
- robertlagrant 2y agoThis would be a lot worse than that. Crowdstrike was bad because everyone lets relatively untested code straight into the Windows kernel - i.e. known incompetence of approach. This would be bad despite massive care taken to have the right approach.
- atemerev 2y agoYes, except there is no “massive care”. If people are OK to install other companies’ rootkits to their critical infrastructure, they will not care about anything else, too.
- digging 2y ago"Some people did X" !== "All people do X"
- robertlagrant 2y agoThe massive care is the algorithm selection process, the careful implementations, and the long-term observation and correction of the performance of the algorithm implementations.
- HeatrayEnjoyer 2y agoCS was a software update. RSA is baked into many silicon circuits and firmware ROMs.
- atemerev 2y agoWell, hardware is replaceable, too.
- golol 2y agoI think someone working in cryptography will worry about a sudden number theory breakthrough that allows for breaking of cryptography as much as a someone working in the energy sector will worry about a sudden physics breakthrough that allows for practically free energy cold fusion energy.
- ertgbnm 2y agoPretty sure that it would require that P=NP if such an event happened. So if factorization was cracked, everything else would be too.
- amelius 2y agoAre you sure about that? And even if problems can be solved in polynomial time, the constants involved can be prohibitively large.
- cvoss 2y agoInteger factorization is an NP problem but is not known to be NP-complete. Therefore, we do not know how to solve all NP problems in P time using a hypothetical P time factorization. P =? NP would remain open.
- zitterbewegung 2y agoMany people in the industry does not think that RSA is crackable due to the assumptions that the Riemann Hypothesis and also the distribution of prime numbers is such a hard problem with a long time of being unsolvable. A possible mitigation for things like websites would be either ECC or even using the quantum resistant encryption systems (the industry would more likely avoid this due to the systems being very prototypical since we have just started researching this). Since old bitcoin wallets can’t be moved off of RSA you can transfer the coins to your wallet and there is no mitigation.
- red_trumpet 2y agoI don't see how proving the Riemann Hypothesis would help cracking RSA? If it helps, couldn't you just assume it is true and start cracking RSA today? If you ever hit a point where it doesn't work then BOOOM: Riemann Hypothesis disproven!
- tzs 2y agoI think it is the other way around--disproving the RH might break some things. Most mathematicians believe RH is true, and generally when doing industrial number theory people operate under the assumption that RH is indeed true and so if they need to use X to justify something and there is a theorem of the form "if RH is true then X" they use X. Thus a proof of RH is not a problem. It just confirms that what people applying number theory already assumed was correct. A disproof means that those X's might not be true and their use would need to be reassessed.
- AnotherGoodName 2y agoRSA was once 128bits and today has to be 2048bits minimum to be secure because it was essentially broken multiple times. There used to be 128bit rsa encrypting hardware that now doesn’t work at all to protect data due to previous mathematical breakthroughs. The congruence of squares equivalence to factorization demonstrated we need at least 500 bits and then the special number field seive that built on this push it to 1024. The general number field seive pushed it again to 2048. Sure it’s not a log(n) break but it’s been broken. If you look at the complexity analysis of the special vs general number field seive the portion of the exponent going from 1/2 to 1/3 should give you thought. Can it be moved to 1/4? Could it be moved indefinitely to 1/x? The general number field seive is relatively recent. If someone comes up with a similar breakthrough again (and this has happened many times over with rsa) your 2048bit keys won’t be secure just as your 128bit rsa keys from the past are no longer secure.
- neets 2y agoI always assumed in the Anime “Ghost in the Shell Stand Alone Complex” they used, “Barrier Mazes” rather than cryptography for a reason
- dhosek 2y agoI remember telling my high school students that if they found an efficient way to factor large numbers, they would destroy capitalism and a large number of them got very excited about number theory after that.
- jaystraw 2y agoi'm glad they got excited about number theory, but how would improved factoring algorithms destroy capitalism??
- thedangler 2y agoIf someone did find out how to do it, do you think they would make it public?
- devnull3 2y agoIf there is a such a breakthrough then the hackers or even spy agencies will not reveal it. They will instead silently make use of it. It will be essentially a backdoor for them.
- heyoni 2y agoWouldn’t it likely originate from academia? If so you can bet that the work will be published just like this one.
- Retr0id 2y agoIt's hard to know where things are today, but historically, public academia has often been behind the true cutting edge of cryptanalysis. For example, take a look at the history of Differential Cryptanalysis https://en.wikipedia.org/wiki/Differential_cryptanalysis https://en.wikipedia.org/wiki/Differential_cryptanalysis > The discovery of differential cryptanalysis is generally attributed to Eli Biham and Adi Shamir in the late 1980s, who published a number of attacks against various block ciphers and hash functions, including a theoretical weakness in the Data Encryption Standard (DES). It was noted by Biham and Shamir that DES was surprisingly resistant to differential cryptanalysis, but small modifications to the algorithm would make it much more susceptible. > In 1994, a member of the original IBM DES team, Don Coppersmith, published a paper stating that differential cryptanalysis was known to IBM as early as 1974, and that defending against differential cryptanalysis had been a design goal. According to author Steven Levy, IBM had discovered differential cryptanalysis on its own, and the NSA was apparently well aware of the technique.
- heyoni 2y agoThat is both impressive and disappointing. I'm so used to seeing large corporations publishing AI models and other techniques (like Ghidra) that I assumed a finding like that would be disseminated to the public. But you're right, something that could be used to decrypt modern ciphers could very well be kept secret for as long as possible.
- nobodyandproud 2y agoIIRC, Elliptic curve cryptography doesn’t rely on factorization, so there’s already an interim PKC solution in place. I also recall there were many problems with the ECC based algorithms or at least the implementations—something about discrete approximations weakening security? Far beyond my comprehension
- k__ 2y agoThere is also lattice-based cryptography.
- AnotherGoodName 2y agoECC is very closely related though (hidden abelian subgroup problem is the category they both fall under). It’s actually concerning because rsa was broken. The reason we’re not using 128bit rsa keys anymore and instead using 2048bit keys is because rsa was broken by the general number field sieve. We’re now all using ecc to avoid working with very large keys but there’s no mathematical proofs that ecc is anymore difficult. In fact it’s widely believed to be the same problem underneath. That may surprise people. ECC, the thing we rely on, is not proven except by the fact that no one has broken it yet just like rsa was until someone broke it.
- dakiol 2y agoIsn’t this the same as zero-day vulnerabilities? Typically only a bunch of people out there know how to take advantage of such holes, and eventually they get fixed. I guess if public key cryptography gets broken, only a bunch of people would know how to take advantage of it, and eventually it would get fixed.
- deleted 2y ago[deleted]
- deleted 2y ago[deleted]
- AnotherGoodName 2y agoThat happened many many times over with rsa! The us government used to restrict export of long rsa keys. At one point much of the world was using 128bit rsa keys but Dixon method had everyone scrambling to use 512bit keys. Then the special number field drive had us all scrambling to use 1024bit keys and the general number field seive again had us scrambling to get to 2048bit keys.l and that really wasn’t that long ago relatively speaking. Check out rsa encryption hardware from the 80s. They are really proud of some of the hardware that can do 512bits! (Useless today) https://people.csail.mit.edu/rivest/pubs/pubs/Riv84.pdf https://people.csail.mit.edu/rivest/pubs/pubs/Riv84.pdf The special and general number field seize complexity statements are a few constants in difference. Look at those constants. Do they seem to be some root limit to you? Is it really that unlikely that there’s not a way to reduce those further making even 2048bit keys useless? You don’t need to ask “what would happen if RSA broke” because those of us who have been through this many times now can straight up tell you. You’ll be scrambling to once more bump up the key size and you’ll be auditing all the potential data leaked.
- simpaticoder 2y agoRSA failures with bit-depth were a matter of degree; a prime number factorization break-through would be a matter of kind.
- AnotherGoodName 2y agoIt’s not log(n) but still a break since we were literally using lower bit strength than was trivially factorable thanks to mathematical advances and to the point of thinking RSA 2048 is safe, well we once thought that about 128bit RSA. If the above pans out like the general number field seive did we may yet need to move the goal posts further. And we really really shouldn’t be surprised if it happens since it’s happened so many times already.
- MobiusHorizons 2y agoI believe this was one of the reasons for the broad adoption of elliptic curve based cryptography. The mechanism is not based on prime numbers, so smaller keys were adequate, and it was hoped that they might avoid future degradation due to prime factorization research. Of course they could still be vulnerable to their own attacks, but it still requires an attacker to expend more resources.
- rainbowzootsuit 2y agoSince Setec Astronomy closed operation, we've been okay.
- BigParm 2y agoDo the mathematicians not prove that this is impossible before we all adopt a cryptosystem? Like I don't think everyone started using RSA on a prayer
- tomtomastom 2y agoNo it's quite hard to prove that