When reviewing the WireGuard VPN last fall, one of the things that came up was WireGuard’s support for an optional, additional PSK (Pre Shared Key) layer of security. Like most modern crypto, WireGuard’s basic encryption is asymmetrical, meaning you encrypt the data with one key and decrypt it with another. PSKs, by contrast, are symmetric cryptography—the same key used to encrypt the data is also used to decrypt it.

The fundamental problem with symmetric cryptography is practical, not mathematical: how do you get the key to your communication partner in the first place? The whole reason you want the encryption is because you don’t trust the medium in between you and your partner, so you can’t use that medium to share a key. The ever-present fear is that an MITM—Man In The Middle—will intercept the key, destroying your secrecy.

That pitfall is what makes asymmetrical cryptography—the kind used for everything from SSH keys to SSL/TLS for websites to you name it—so attractive. With asymmetric cryptography, you send your public key to your communication partner in the clear. Your partner encodes a message with your public key, which you can then read with your private key because that was never shared. You can do the same thing in reverse to send data the other way—get your partner’s public key, and use it to encrypt a message to send to them to be decrypted with their private key.

So in the US at least, companies are beginning to sprout up hoping to facilitate this kind of cryptography for others.

The quantum computing bogeyman

This basic concept—negotiate a connection and an ephemeral PSK using asymmetric cryptography—has been serving the world extremely well for a couple of decades now. The tech world would have trouble functioning without it, in fact. Secure modern communication is only possible because we don’t need to meet communication partners in person to furtively hand over a PSK like thieves in the night. But there’s a nasty spectre (no, not that Spectre) looming on the horizon: quantum computers.

Like quantum physics itself, quantum computers are weird beasties that relatively few people genuinely understand. Conventional computers are themselves digital but operate on essentially-analog principles. If there’s a sufficient amount of charge on one side of a gate, it qualifies as a one; if there isn’t, it qualifies as a zero. Presto, we have bits!

Quantum computers don’t operate with classical bits at all, they instead store and process data in the form of qubits. Instead of a relatively macro quality like “how many electrons are on the other side of this gate,” a qubit is measured by means of the state of a single quantum particle. For example, a quantum computer might store qubits in the spin of individual electrons, encoding a 0 as “spin down” and a 1 as “spin up.” Things only gets weirder from here—where a classical bit can only store a single 0/1 value, a qubit can store a coherent superposition of values. This means you can store two bits in a single qubit using superdense encoding, assuming you can make use of a pre-existing entangled state between Alice and Bob (the sender and the recipient of your qubit of data). It also means that you can’t actually know the value of your qubit without destroying your qubit (so I hope you’ve got a pen and pencil handy to write it down when you do read it).

Let’s return for a moment to that idea of storing a “coherent superposition of values.” Scientific American explained this pretty accessibly a few years ago, and Ars has been exploring the idea since 2008. Remember Schrödinger’s Cat, the poor beastie trapped in a box with no airholes, neither alive nor dead until some ghoulish researcher opened his box to find out? This turns out to be a pretty fair representation of a qubit. When you actually measure a qubit, you can only get a 0 or a 1 out—the cat is either alive, or dead. However, you can manipulate the likelihood of the cat’s survival directly. You can store a cat with a 75 percent likelihood of survival in the box; when you open it up, you still only get a 0 or a 1 (dead cat, or live cat). But the likelihood of that 0 or 1 is very real, and it’s actually stored in that qubit. (Trying to make practical use of probabilistic information storage is, frankly, beyond me. But it turns out nobody asked me to build a quantum computer.)

In strictly practical terms, quantum computers are somewhat analogous to GPUs—they’re not necessarily better at everything than conventional, general-purpose CPUs are, but they’re fantastically better at certain operations. In particular, quantum computers are really, really good and classical computers are really, really bad at factoring very large integers. Many of the most widely-used asymmetric crypto algorithms rely on this weakness of classical computers to keep the encryption asymmetric. Once quantum computers scale up to around 1,500 qubits, it becomes practical to use Shor’s Algorithm to attack modern RSA, Diffie-Hellman, and elliptic-curve schemes directly and in real time. (This means the eventual doom of Bitcoin, as well as current SSL/TLS schemes.) IBM made news a year ago with a 50-qubit version of their Q quantum computers, so this probably won’t happen tomorrow, or the day after… but it looks inevitable that it will happen.

Quantum computers are also better at attacking symmetric cryptography, but not enough to matter. You can cut the time to attack a symmetric algorithm in half using a quantum computer, but one bit of entropy isn’t anything to write home about. There are also some asymmetric crypto algorithms that don’t rely on factoring huge integers. As far as we know today, they aren’t especially vulnerable to attack by quantum computer, either. The end of mathematically-derived crypto isn’t here quite yet… but it’s definitely time to start thinking about new ways of achieving secrecy over long distances.

https://arstechnica.com/?p=1418385