The Universe Believes in Encryption

Our universe is built out of mathematics. Humans have been learning, discovering, and using mathematics for thousands of years because it’s the only thing that can accurately describe what happens around us. The laws of physics are written in mathematics, and they cannot be broken.

One year ago today the Snowden revelations began. Since then there has been a flood of calls for reform. A federal judge called the NSA “almost Orwellian”. Congress and President Obama have admitted that bulk surveillance of Americans is wrong and should end. But so far we haven’t seen real reform in the US, and we might never see it. Even if the US does pass meaningful surveillance reforms the problem won’t be solved. There are billions of people all over the world that rely on the Internet, and their privacy will continue to get violated by governments around the world.

On the eve of the Reset the Net day of action, Edward Snowden wrote:

Today, we can begin the work of effectively shutting down the collection of our online communications, even if the US Congress fails to do the same. That’s why I’m asking you to join me on June 5th for Reset the Net, when people and companies all over the world will come together to implement the technological solutions that can put an end to the mass surveillance programs of any government. This is the beginning of a moment where we the people begin to protect our universal human rights with the laws of nature rather than the laws of nations.

Like the laws of physics, encryption is also written in mathematics. All information can be expressed in bits: a series of ones and zeros. Through decades of pain-staking research brilliant cryptographers have figured out how to take a random number (called a key) and a collection of organized bits (such as an email, or a video, or a PowerPoint slideshow) and scramble them, using mathematics, to end up with another set of bits that’s indistinguishable from random.

(Bits that make up encrypted data have no pattern at all. If you point an antenna into space to collect radiation left over from the Big Bang and store that in the form of bits, you won’t be able to tell the difference between that and encrypted data.)

If you have this indistinguishable-from-random set of bits, and you also have the original key, you can use another series of mathematical operations to get back to the original plaintext — the email, video, or PowerPoint document.

As long as the key remains a secret, and as long as the math that scrambles the bits is sound, then encryption works. Let me phrase that another way: as long as the key itself isn’t stolen or surveilled, and as long as the math works like it’s supposed to and doesn’t have any flaws, then encryption is impossible to break*. As impossible as it is for a photon to escape the event horizon of a black hole. As impossible as it is to travel faster than the speed of light.

It’s mind-blowing that encryption is even possible, but thanks to computers it’s easy, and thanks to the free and open source software movement it costs nothing, is built-in to all major operating systems and web browsers, and is available for all humanity to use.

In the introduction to Cypherpunks: Freedom and the Future of the Internet, Julian Assange wrote:

We discovered something. Our one hope against total domination. A hope that with courage, insight and solidarity we could use to resist. A strange property of the physical universe that we live in.

The universe believes in encryption.

It is easier to encrypt information than it is to decrypt it.

The fact that encryption is possible is one of the marvels of our universe and of mathematics, the language that our universe is written in.

We’re living at a technological crossroads. The Internet could still yet wind up being the greatest tool for human liberation or the greatest tool for ubiquitous surveillance and oppression that civilization has ever seen. But if we’re clever enough we can win. The laws of physics are on our side, if only we accept their help.

* The adversary can try to guess the key, which is just a random number, but there are quite a few numbers to choose from in the set of all possible keys. The trick is making the set of possible keys big enough that, even devoting all of the computational resources on Earth towards guessing the key, our sun will go supernova before it’s found. With modern crypto, key-guessing is unfeasible.

Finding flaws in the math might be possible. Whenever flaws are found and published, they get fixed (this is why you see so many WPA wifi networks but barely any WEP networks, because WEP flaws have been published about and fixed). Spy agencies might be holding onto secret flaws in crypto that aren’t publicly known, but for the most part they wouldn’t even have to use them since most people and servers are either using known-weak crypto or not using crypto at all. (This is why we need to Reset the Net.) If we want to restore privacy to humanity, we want to force our adversaries to use up their secret flaws.

8 thoughts on “The Universe Believes in Encryption

  1. Seth Schoen

    There are clearly some math problems that take more computation to solve than human beings will ever be able to perform. In fact, it’s pretty easy to state math problems like that.

    A concern for me is that we don’t have proof than any of our cryptographic primitives are inherently that difficult to break. We don’t have a proof that a block cipher like AES-256 inherently requires 2²⁵⁶ computational steps (or even 2²⁵⁰ or 2¹²⁸ or 2⁶⁴ steps) to distinguish its output from random data. We don’t have a proof that a hash function like SHA-256 requires a particular number of computational steps to compute preimages or second preimages. We don’t have a proof of what exactly the inherent difficulty is of the tasks whose difficulty we rely on for public-key cryptography (DHP and RSA problem, or their naïve solutions via discrete logarithm and integer factorization).

    Most of the research in cryptography that does involve formal proofs is in the form of reductions that transform the ability to solve one problem into the ability to solve another (which has been assumed to be hard to solve), or conversely that transform the resistance of one system to a class of attacks into the resistance of another system to another class of attacks. (We assume that problem X is hard to solve and we show that if you could solve problem Y, you could solve problem X; therefore we must conclude that problem Y is also hard to solve.) This is the same general strategy of lots of computational complexity research, which is interested in the relative difficulty of problems, which can be established by exhibiting reductions.

    In the cryptographic case, though, there’s usually just an assumption at the bottom, which is that the underlying thing seems pretty difficult to break and no very powerful attacks against it have been published. It seems that many of the problems that we would like to be easy (because we want to do computations using them) are proven to be hard, while many of the problems that we would like to be hard (because we want to rely on their difficulty for cryptographic purposes) are not proven to be hard.

    So although the universe clearly does allow us to have secure cryptography, we’re still unable to demonstrate that any of the cryptography that we regularly use is actually secure cryptography.

    Reply
    1. Micah Lee Post author

      These are excellent points. None of the crypto we use is provably secure, which is why we have to worry about unknown flaws at all. I think this will change though in the future (maybe very near future?) when quantum crypto becomes more feasible. We can only hope that NSA/GCHQ doesn’t have secret mathematic knowledge about certain ciphers that the civilian cryptographers don’t know about it.

      I’m by no means a physcist, but my understanding is because eavesdropping on quantum operations causes superpositions to collapse, eavesdroppers can always be detected. Because of this fact, many quantum crypto tasks could/will have “unconditional security”, meaning they’ve been proven to be secure. Here’s the paper on it: http://arxiv.org/abs/0906.1030

      Reply
      1. Chad

        Micah are you poking fun of this poster?
        Not that I mind, everyone deserves a good poking now and then and some people deserve a good roasting.
        Just that, as I’m not an expert (except to all the people who understand less than I and trust me to secure them and their systems) it’s difficult to understand if this is something on the order of “Oh shit, “they” could have broken all encryption and they’re just waiting till all the bears are sufficiently sticky and logy from the honeypots before they swoop them up” . . . or more along the computational lines of “Difficult to conclude that life only exists on Earth given the immense vastness of the universe, but since we haven’t met E.T. … a million white crows does not no black crows make.”

        You’re one of the few voices I trust on the net, and this response almost seems to undermine your usual firm”You can trust encryption with your life” stance.

        Reply
        1. Micah Lee Post author

          Hey Chad, no I’m not poking fun at Seth. He made some very good points: none of the crypto we rely on has been mathematically proven to be secure. But I don’t think this is a reason to panic or anything.

          For example, public key crypto works by picking two very large prime numbers and multiplying them together to get an enormous number that isn’t prime, but only has two factors. The security relies on the fact that if you just have that enormous number, it’s a “hard problem” to factor it and figure out what the two prime factors are (such a hard problem that we’ll all be long dead before an RSA key is broken using the most efficient solution to factor numbers that exists right now). Mathemeticians have been trying to figure out how to do this efficiently for hundreds of years and have so far failed.

          However, no one has ever proved, mathemetically, that it’s impossible. (In math people prove things all the time.) So even though it’s a hard problem that has stumped geniuses for centuries, it’s still possible, as far as we know, that someone could figure out a breakthrough in mathematics: a way to efficiently factor huge numbers.

          So while I personally believe that it’s impossible to efficiently factor large numbers, I could be wrong, because it hasn’t been proven. Just because something “might not be impossible” doesn’t mean that NSA can do it — on the contrary, they really almost certainly cannot. Be we just don’t know that for sure.

          Reply
  2. ASmith

    There are multiple signs the NSA had their fingers and goons in the AES competition which picked the weakest finalist and as Bruce Almighty has pointed out, 14 rounds does not entirely disperse a 256 AES key. However Russia’s stronger alternative GOST added double the number of key rounds plus added 2 reverse rounds and a customized S box scheme which wasn’t static for all groups using it. Still Russia abandoned its GOST about the same time the US Military stopped using AES 256 to safeguard its secrets. Effective attacks on AES chain block cipher also proved effective on GOST as well being a chain block cipher. However and most importantly to the point, USA citizens, business’s and those shackled to openssl are constrained to continue using AES while it appears Serpent, Three-Fish 512/1024 and Seine hashing has been deliberately kept out even thou those encryption algorithms have a far larger security margin than AES ever did.
    I recall a episode of NCIS naval inspection crime series where the cyber techs immediately defeated AES and bragged about NSA breaking it. That episode was never repeated and NCIS further episodes acted quite contrary in its further episodes. The point being, there certainly are growing signs the rather old AES256 is in no fashion as secure as the PoliceState appears to portray it as and as pointed out by Bruce Almighty, AES wasn’t offering much of a safety margin to begin with way back in the 1990’s. Its 12 rounds for a 16 character 128bit key while 14 rounds for a 32 character 256bit key appears to be deliberately crippled ON PURPOSE. With Russia bailing on its 32 round Gost, you know there’s a very good chance AES256 is not remotely as safe from State Sponsored goons as those same goons and thugs would have you and anyone else they can fool into believing.

    Reply
  3. mm-hmm

    you are by far not the only person to suggest this, but to think that universal encryption protects human rights is to see the world from one point of view–your, end-user’s, tech-centric point of view.

    how are the human rights of the victims of criminal attacks, war crimes, and other direct acts of violence protected when the perpetrators have easy access to systems that are by stipulation or design opaque to law enforcement?

    how are the human rights of the family of a murder victim less important than the human rights of the murderer to use encrypted communication?

    a world of total encryption is a world of no law enforcement, or next to no law enforcement. I know of not one argument so far that has persuasively shown how this cannot be the case, especially if we were to be able to root out human infiltration of technical systems of the kind you deride here.

    however much you dislike the current political system and the current ways in which laws are enforced, a world where law enforcement is impossible is a world where “human rights” means almost nothing.

    you are welcome to promote your political vision as much as you see fit, but I’d appreciate some more clarity about exactly what it is you are promoting. look at the basic list of human rights agreed to by the UN and others, and look at how many of them would be difficult if not impossible to guarantee if people NOT like you–the “bad guys,” not “good guys” like you understand yourself to be–can put themselves entirely or almost entirely beyond the reach of law.

    lawlessness is already the #1 challenge to human rights in this world. you owe it to yourself and others to think carefully about how massively decreasing the ability for laws to be enforced leads to better realization of human rights.

    Reply
    1. Micah Lee Post author

      a world of total encryption is a world of no law enforcement, or next to no law enforcement.

      I think you’ll have to explain this one a bit more. I don’t see how a world where people on the internet have privacy means that the rule of law will no longer exist.

      One of the reasons why I’m such a supporter of freely available crypto for everyone is preciesly because the rule of law isn’t enforced at all when the people commiting the crimes are part of the Intelligence Community or law enforcement. If they completely disregard laws and the Constitution, then at least we can use technology to keep ourselves safe.

      Reply
  4. gki

    Hi, it’s not directly related, but I thought you might know an answer this doubt on TLS.
    I know if i load without TLS, http://abc.com/some/thing/here , then ISP can see /some/thing/here and all content and that if i load with TLS, ISP will know i loaded abc.com but not “/some/thing/here” or contents.
    … but what if I load with TLS, https://something.abc.com , then will ISP see that I loaded something.abc.com or will it just see “abc.com” ?

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *