Imagine no encryption, I wonder if you can...
January 16, 2010 7:51 AM   Subscribe

What if: RSA was just "cracked" due to a new discovery about prime numbers. What happens around the world on day 1? Total chaos? Or yawns?

"What if" scenario: yesterday a paper was published online revealing a new mathematical discovery about prime numbers; which rendered useless all methods of encryption based on the difficulty of obtaining the prime factors of very large numbers. What happens now? Does the world just hicup and switch back to using symmetric encryption algorithms and life goes on?

Would the entire Internet need to be shut off? All ISPs, the telecoms, hosting companies, Google, Akamai, etc could no longer secure traffic in and out of their networks, plus they would need to block their own core infrastructure from being hacked(all infrastructure using ssh & ssl to securely connect to servers and routers). Pull the plug?

Also, I presume all consumer facing e-commerce would halt because Visa and the banks would revoke all credit card & bank account processing until they could secure their systems? So down goes Amazon, Ebay & the Internet giants, along with tens of billions of dollars.

Would WWIII break out? Who knows what kinds of global military sabotage would become possible, given that they are routinely hacking into each other's networks, and have the capability to instantly apply the RSA crack to active operations. Would China take down the Pentagon from within? Or perhaps the converse? The Clancyesque catastrophic scenarios made possible are endless and suddenly practical to a well-funded and trained non-civilian organization.

Would Wall St. shut down? Given their reliance on electronic trading, I can't imagine they would continue with the risk of losing all their investments over now-insecure online networks. So now the total blowback could be in the trillions! And we all thought the housing bubble crash was worth panicking over!

Global shipping? I can't imagine places, boats and trains can move goods
around the world given the Internet and phone network outages, nor can they continue operations without securing their own networks and infrastructure.

I could keep going, but so far it sounds like it could end up being post-apocalyptic. Or am I blowing this way out of proportion, and there's some easy replacement for Public Key Encryption which the world could just swap in and keep going?
posted by archae to Computers & Internet (21 answers total) 8 users marked this as a favorite
Secure military applications usually do not asymmetric ciphers for exactly this reason. A symmetric cypher would not be affected by such a discovery.
posted by Brennus at 8:01 AM on January 16, 2010

We don't yet have the technological infrastructure to do widespread quantum cryptography. If we did, we could probably do one-time pads pretty safely, reducing the need for PKI. Presumably governments and larger business entities would have the financial means to deploy and use QC, but anything that relies on PKI for everyday commerce or other private communication for regular folks would more than likely come to a halt.
posted by Blazecock Pileon at 8:03 AM on January 16, 2010

You're blowing things out of proportion. The world got along without that kind of encryption for a long time, and it could do it again. Consider another scenario: all phones suddenly stopped working. Do you think the world would really end? That would be a much more global issue, but people get along alright without phones.

Would WWIII break out? Who knows what kinds of global military sabotage would become possible, given that they are routinely hacking into each other's networks, and have the capability to instantly apply the RSA crack to active operations. Would China take down the Pentagon from within? Or perhaps the converse? The Clancyesque catastrophic scenarios made possible are endless and suddenly practical to a well-funded and trained non-civilian organization.

Do you think the only thing that prevents war is the existence of this kind of strong encryption?
posted by OmieWise at 8:04 AM on January 16, 2010

I guess it depends what you mean by 'rendered useless'. Whatever the crack I assume there would still be a cost associated to breaking a code.
Depends how high this cost is I assume.

There are alternative crytography systems, I assume all military senstive stuff would use one-time pad stuff and the like.

What I find interesting is that all the internet traffic in history would become vunerable.

This link that came to my attention only yesterday might be of interest:

And this from a few weeks back:

I don't know if eliptical curve cryptography would also be cracked:
wikipedia link

Also in general people really don't care about protecting their own communications. Falls under the 'nothing to fear/hide'. See Facebook.
posted by 92_elements at 8:10 AM on January 16, 2010

What if integer factorization actually turns out to be an easy problem? Yeah, that would suck, but the reason it was chosen for cryptography in the first place is because all of our best efforts show it to be a very hard and tedious problem.

A lot of things would suck if incredibly unlikely things happen... we don't prepare for every possibility just in case.
posted by smackfu at 8:15 AM on January 16, 2010

The practical upshot would be like discovering a major security flaw in a browser or OS - RSA is used in the security layer of protocols like HTTPS, so would have to be replaced by something like elliptic curve cryptography. This would require a lot of e-commerce websites to switch over - this has, it seems, only recently been added to the Apache default build so many webservers would have to be patched. Firefox 2+ is capable of supporting ECC-based security by default, not sure about other browsers, so there might be rather less impact on the desktop. There could certainly be uncertainty and possibly media hype/panic (cf. the millennium bug) during the transition period.

One possibility of this happening for real is if a workable quantum computer was developed. One could then use Shor's algorithm to factor large numbers much more quickly than a classical computer could.
posted by Electric Dragon at 8:57 AM on January 16, 2010

You're blowing things out of proportion. The world got along without that kind of encryption for a long time, and it could do it again. Consider another scenario: all phones suddenly stopped working. Do you think the world would really end? That would be a much more global issue, but people get along alright without phones.

A while ago I read about a traffic light computer failure problem causing mass congestion.

The issue wasn't that the traffic lights stopped working - every individual set of lights worked exactly as designed - but the connections between traffic lights (which do things like make sure one set of lights turns green just before the cars from a previous set of traffic lights arrive at it) failed.

Because the function of this network was to increase traffic throughput, when it broke down traffic throughput dropped, leading to substantial congestion.

In other words, a communication network breakdown didn't stop each individual system from acting sensibly - but capacity problems still arose because of the sudden loss of the efficiency the communication network had made possible.
posted by Mike1024 at 9:40 AM on January 16, 2010 [1 favorite]

The world got along without that kind of encryption for a long time, and it could do it again

The world also got along fine for a long time without electricity, running water, the shipment of food via trucks, sewage systems etc. But if all that stuff stopped now, we wouldn't suddenly return to our agrarian lifestyle - we'd be in a position where we *depend* on all those things, but don't have them. That seems like it'd likely lead (in the near term) to a more catastrophic result, not just "going back to how things were before'?

So one version of the OP's question is: How much do we depend on encryption for some of the basic functions of how the world works? How much would it mess things up is that stopped working, not gradually (in a way where we could gradually use other technologies) but suddenly (in a way where all the things that depend on encryption suddenly break)...
posted by ManInSuit at 10:22 AM on January 16, 2010 [1 favorite]

RSA is used by almost everyone in the UNIX world to control remote access.

The question would be how quickly these systems could be locked down, and how quickly the script kiddies would start taking advantage of the vulnerability.

To give some perspective, for two whole years, Debian Linux, one of the most used varieties of Linux for servers, had a broken RNG that crippled ssl based security. Theoretically malicious hackers could have started trolling for Debian machines to exploit immediately after the security was compromised. This being open source software, anyone who understood the change in question would know that breaking in had become easy. At the very least, they could have started breaking in to unpatched machines as soon as the announcement. This would have been a race between how quickly people updated their security patches and how quickly the kiddies were exploiting the hole (a very familiar situation in the world of Microsoft Windows). Either the people breaking in were extremely subtle about it, or the security hole was not very widely taken advantage of.
posted by idiopath at 10:31 AM on January 16, 2010

RSA's security relies on the difficulty of two problems, one of which is integer factorization (the other involves taking the nth root of an integer modulo some prime). However there are other schemes that choose discrete logarithms as the hard problem instead. Diffie-Hellman key exchange is one, as are the ElGamal and Ecliptic Curve (ECC) encryption algorithms. ECC is an essentially an extension of ElGamal that avoids integer-based attacks and thus allows for a shorter key-length. We're all supposed to switch to ECC eventually, though there are still some patent issues.

However, Bruce Schneier claims that the quantum computers with the power to break RSA could break ECC as well (though a 256-bit symmetric cipher like AES-256 would probably be fine).

None of this addresses what would happen if our public key systems did suddenly become insecure. The NSA has endorsed public key algorithms, but I don't know if it's used for any important miltary work. (And some important communication links aren't encrypted at all, apparently.) Remember that public key crypto solves the problem of key distribution; it's not used for encrypting the messages themselves. And key distribution is less of a problem for governments than it is for the private sector. SSL relies on it, as does SSH for key-based authentication.

But remember that the first step to eavesdropping is access. Almost no one sends encrypted emails, but that's not a huge problem in practice since it's hard to access that data without physical access somewhere along the communications chain. Active attacks can be even harder, since you have to keep the parties from communicating directly. Even SSH authentication spoofing requires you at least have access to the user's public key, which may not be available anywhere outside the organization.

And as for the political ramifications it's important to remember that a world war is not in the economic interest of any world power. Nor is a breakdown in the global financial system.
posted by serathen at 10:57 AM on January 16, 2010

First off there is the cost angle as someone mentioned. Baring some unforeseen crazy discovery, the "breaking" of an algorithm means that attacking the algorithm is possible in less time than using brute force (i.e. trying every possible key). There will still be an expense to cracking each message, so one potential countermeasure would be to flood the system with more messages for the attacker to decode.

Secondly, there are alternative asymmetric crypto systems out there that don't rely on prime number factorization, such as the aforementioned Elliptical Curve Cryptography.

Thirdly, one-time pad solutions while unbreakable are impractical for the masses.
posted by mmascolino at 11:00 AM on January 16, 2010

There is a difference between what would happen in the short term, and what would happen in the long term. I take this question to be about the long term, as no one starts WWIII as a short-term undertaking. There would be chaos for a while, but only for a little while. We aren't talking about the internal combustion engine here, or even, as I pointed out, the phone. We're talking about a ubiquitous component of high level systems, most of which are replaceable.
posted by OmieWise at 11:49 AM on January 16, 2010

Although the text does say on day one. Still, I tend to think that just the cracking of the code would not lead to chaos on day one.
posted by OmieWise at 12:24 PM on January 16, 2010

Another thing to consider is the lag time between the new finding and it being made public. For a start papers can take up to a year to be published, then even when they are not a lot of people read them. So this finding would have to be first kept quiet until publication then suddenly picked up by the media in a big way for all these supposed hackers to find out about it quick enough to do damage before a fix is put into place.

Even then chances are high that the researchers would quietly tell at least their government, or the people they care about, so they can be protected before the info is made public. As an example I've read about new IE hacks being found but not made public until microsoft has a fix in place, generally when the person finding it is somehow funded by microsoft in the first pace. Scientists, on the whole, want to make the world a better place. Which makes sense when you see how much expensive education we need and how little we get paid, research is more likely done for passion than for profit.

Who get protected and who gets hit would depend on who makes the finding, so maybe some people are still targeted. If it was public good research done by an academic I wouldn't be surprised if they suppress the whole thing until the internet at least is sorted, if not everything else too. If it's someone making money from an alternative type of encryption then they'll make sure everyone buys their new version before doing anything about it. If it's black hat hackers they'll use it to their own ends and targets before they publicise it round the world. Etc.

You're also assuming someone will find one thing about prime numbers, publish it, then the encryption system will be broken pretty much straight away. But often science works in steps, each building on the ones before. So it's more likely that either we'll know this finding is coming because of the preliminary work being done (or even just because we know someone is working on it) or it will take time plus more work to go from the prime number thing to killing the encryption. In either scenario there is again time to switch to a different type of encryption.

The omg chaos scenario would require someone to basically stumble across the prime number something while looking for something else, and have that prime number something immediately and easily wipe out all encryption of this type and the info about it be immediately disseminated around the world so that it can be put to use really fast. There are a lot of unlikely steps in that chain.
posted by shelleycat at 12:34 PM on January 16, 2010 [1 favorite]

In the short term, like day 1? Nothing would happen. The crack would only be known to a few people, and even fewer would be able to actually implement it. Knowledge of a theoretical weakness doesn't suddenly make a real-world cryptosystem stop working. Things would keep ticking on just as they were the day before.

The problems would occur when that theoretical break got transformed into some sort of tool that even a moron could use. Or perhaps they would start before that, when criminal syndicates and their more-skilled-than-average hackers got their paws on it, but still it would take a while.

And even with transport encryption broken, it still requires the would-be interceptor to get into a place where they can intercept the traffic in the first place. You'd start to see a lot of corporate networks start to disconnect themselves from the public Internet; the ability to VPN into a secure network from an insecure location would disappear. It would be like the early 80s all over again; private, siloed networks that are "air gapped" from each other and from the public networks, and can only be accessed from within physically-secure premises.

The government wouldn't collapse, and WWIII wouldn't break out. That's ridiculous. Although the government has made increasing use of COTS products over the past decade or so, and is a heavy user of public-key crypto, the really secure stuff is done over networks that are totally isolated from the public Internet. (In some places the secure networks are tunneled over insecure networks, similar to a VPN, but these could be unplugged in a hurry.) Cf. SIPRNET, Highside.

There'd be a hell of a market for symmetric encryption products, especially ways of solving the key-distribution problem. You might still be able to use things like rolling-code tokens.

Also, depending on how your hypothetical RSA break works, other forms of public-key crypto might work. Not all PK crypto relies on the difficulty of factoring prime numbers. Elliptic curve systems, for instance, use the discrete logarithm problem as their "one way function", and are preferred by some people for new applications anyway. Some cryptosystems can be changed over to different algorithms with relative ease — the discovery that old algorithms were flawed and needed to be replaced isn't exactly unknown. It's happened before and the world didn't end, although the discoveries were made well in advance of any practical "in the wild" cracks.

You can be quite confident that there are people, deep in the bowels of certain agencies, who are paid to think about these things and have given some thought about what to do if some genius mathematician suddenly comes up with a really earth-shattering prime-factorization method. A lot of companies would have to suddenly spend a lot of money upgrading their IT systems, and if new PK algorithms didn't exist it might put a big crimp in Internet commerce and telecommuting and generally roll the progress of the last few years back somewhat, but it wouldn't be the end of civilization.

You can look back historically and find long periods when either cryptography prevailed (encryption methods existed that were stronger than decryption), or cryptanalysis prevailed; we're in one of the former periods now, but it wasn't that long ago when we were in the latter, and we'd survive if things changed. The difference is generally a much greater reliance on physical security, one-time-pads, and face-to-face rather than technologically-mediated communication when strong cryptography doesn't exist or isn't trusted.
posted by Kadin2048 at 12:38 PM on January 16, 2010 [2 favorites]

I love nerdy apocalypses that don't involve the singularity (which is too far away and abstract) or "THE MACHINES REBEL" hand-waviness. We really do need another Y2K, even if that was blown out of proportion. It was immediate, scary, and had a hint of truth.

My guess is that military installations would probably be okay, as they already have more levels of security.

Shops and banks would be messed up pretty awful, but common sense would take place (Online shops would stop shipments when they see all these orders with no cash to back them up), and they would attempt to revert to backups made pre-mass cracking. Yes, some money would be lost, but I expect it would be the economic level of damage of a massive hurricane. Some online businesses might stay offline for a week or two while updating security and making sure they were indeed bulletproof.
posted by mccarty.tim at 1:32 PM on January 16, 2010

Why would banking collapse? Before the internet credit card transactions were done via phone modems. Those sessions werent encypted and anyone with the ability to tap the line could collect those cards. Considering modern networks are switched, I think its feasible to have credit card transactions in the clear or with breakable encryption to keep the amatuers away. Sure, the Visa fraud department will have to up its game and banks will be a lot tougher when charges come in from odd locations, but the system should hold.

There are alternate systems of protecting credit card numbers and other sensitive information without a key exchange. Instead of sending 4100-0000-0000-0000, you would instead send a one way hash. Replay attacks are possible but you dont have the real number. Rotating different hash methods or hash methods that encode the time/date would limit liability.

Keys could be generated without any kind of handshake. Sure, it would be less secure than what we do now, but the key could be generated from static info like the credit card processor's ID number and tax ID, which Visa would know, but Joe Cracker would have a hard time figuring out. Or some kind of secondary communications like a POTS phone call to get the key to get the credit machine to work.

Youd probably also have a clear time for purchases. Maybe 24-hours to make sure its wasnt fraud. We do this with checks now so its not a real stretch for credit cards, although it would be inconvenient.

Not to mention, we live in a sea of broken protocols. SSL has some problems that allow MITM attacks. WEP and WPA-TKIP is broken. 56-bit DES is still used by many legacy applications. Im sure some of the infosec people can name some more examples.

I doubt the scenario you present is the end of the world. Its just a game changer. Also, historically we dont see discovieries like this. Most likely something like this falls into the category of "We discovered how to crack x better. Now it takes 1/4 of an acre of supercomputers as opposed to 10 acres."
posted by damn dirty ape at 9:39 PM on January 16, 2010

it still requires the would-be interceptor to get into a place where they can intercept the traffic in the first place.

This is where DNS attacks become seriously deadly. If you spoof a DNS response (or more likely, just install malware that changes the resolver to one under your control) then you don't have to intercept any traffic because you can just reroute it to a system you control. SSL certificates currently prevent this attack, as does DNSSEC, but both of those rely on asymmetric crypto (and the latter was designed in such a way as to present such serious barriers to implementation that it will probably remain a dream forever.)

SSL has some problems that allow MITM attacks.

No, it had a problem where if you could find an certificate authority that was still issuing MD5-hashed certificates you could craft a specially designed cert signing request that would result in the ability to forge any cert from that CA, but after the vulnerability was disclosed all the major CAs very quickly ceased issuing the antiquated MD5 certs (and browser vendors set timetables to disable the use of MD5 certs entirely), so that one is pretty much a non-issue now.
posted by Rhomboid at 2:45 AM on January 17, 2010

Even then chances are high that the researchers would quietly tell at least their government, or the people they care about, so they can be protected before the info is made public. As an example I've read about new IE hacks being found but not made public until microsoft has a fix in place, generally when the person finding it is somehow funded by microsoft in the first pace.

I think the term for what you're talking about is responsible disclosure.

A recent example was DNS cache poisoning - it was unusual because while a 'normal' bug might only effect one vendor's software, this bug affected about 150 vendors' software. Every vendor had to be given enough information to convince them the bug was real, and to allow them to check their fixes worked. And they all had to keep that information to themselves, for long enough for all the vendors to get patches ready and tested.

Then they all had to release their patches at the same time - because when the public see the patches, people can work out from the solution what the problem was. And if you want people to apply the patches as a matter of urgency, you may have to convince them the threat is real. For the DNS bug, patches were released on the 8th of July.

Then you have to wait for everyone to download and apply the patches. Some people will be very slow - some statistics say that 10% of people are still running Internet Explorer 6.

On about the 11th of July, 3 days after the patches came out, a 'is your server vulnerable' tool came out. On about the 21st of July, details of the bug were accidentally disclosed (then un-disclosed). On the 23rd of July, the first exploit for the bug was released. On the 30th, it was confirmed that sites were being compromised.

Anyway, what we can learn from this that's relevant to the discussion is:

* When software from 150 vendors was at risk, they still managed to keep the bug quiet for 14 weeks. An encryption vulnerability might effect more/different vendors, but this shows it's possible to keep things quiet long enough to develop a patch.
* Patches were released, and exploits weren't developed for 16 days (and only after more attack details were released). This shows that it seems possible to release patches without immediately giving the game away (obviously how much a patch gives away a bug depends on the details of the bug).
* Only 2 days after the (inadvertent) release of full attack details, exploits became available, and confirmed attacks were seen 7 days later. This shows that (a) details sometimes get leaked by accident; in principle such leaks could have happened during the 14-week patching period, especially if there were more vendors involved; and (b) Exploits become available very soon after attack details are released, and attacks start soon after that.
posted by Mike1024 at 5:53 AM on January 17, 2010 [2 favorites]

Response by poster: Thanks for some really great answers as well as taking the question into areas I had not thought of!
My question is definitely targeted towards the shortest time frame which causes the most public impact. And yes, I realize we got along fine before RSA, so I'm interested in exploring how we are now dependent on technology in ways which are too subtle for us to even notice.

Considering the importance of PK crypto, I don't think we'd see the scenario of an lone academic spilling the details in an obscure math journal; but nobody connects the dots until months later. So for my hypothetical scenario, let's say the lone genius publishes it to Arxiv and announces it on Twitter—the entire Internet will have seen it within 24 hours.

Also, I hadn't thought of the parallel to the recent DNS vulnerability and the issue of "responsible disclosure." Would a revelation like cracking RSA be too important in itself to warrant responsible disclosure?
posted by archae at 4:19 AM on January 18, 2010

Best answer: The question re "responsible disclosure" is if you had some sort of a prime-factorization algorithm that essentially breaks RSA, who would you disclose it to? The algorithm has been in the public domain for almost ten years, and the majority of the implementations in use are not created nor maintained by RSA Data Security. So disclosing to them really wouldn't protect that many 'good guys.'

Assuming the hypothetical break only affected RSA (and not Elgamal or DSA, which depend on Diffie-Hellman and discrete logarithms rather than prime-factorization), so that there were still workable PK algorithms, then it would seem responsible to disclose first to whatever organizations or individuals might be capable of quickly producing a patch to the most common or high-profile PK tools. Certain people active in the development of OpenSSL might make that list, as would the NSA and some major software vendors (IBM and Microsoft come to mind), probably. You'd have to carefully weigh each disclosure, balancing the entity's ability to keep a secret for the length of time required versus the help they might be able to provide.

But if you'd found some magical breakthrough that somehow affected all public-key systems (although I'm not sure what that would be, and I'm doubtful that there's any sort of algorithm or software that would do it — you'd have to have some advancement in quantum computing, perhaps), then the list might be different: since there's no hope of a patch or fix, the question is more of preparation and mitigation. In that case you might want to think of high-profile users of PK crypto who would become immediate targets, and find some way to inform them directly before the public announcement. You'd want to keep the disclosure/warning window short, but you could at least give major targets an opportunity to disconnect themselves from the outside world, shut down their VPNs, etc.

Although it's sort of fun to think about, I don't think the latter scenario bears that much consideration even as a hypothetical; I really can't come up with any plausible scenario that would totally destroy all PK crypto and not require the would-be interceptor to construct some sort of new machine (which would mean the day 0 effect would be nothing).
posted by Kadin2048 at 10:41 AM on January 18, 2010

« Older Why does white noise work?   |   public records of coop purchase Newer »
This thread is closed to new comments.