Quantum computing will have the ability to break most existing encryption methods. People and, in particular, governments are collecting encrypted messages/files/etc. for decryption in the future.
These saved “messages” will include traffic to websites. This will include commerce (think gun and ammo purchases), blogs (this one is not encrypted), forums, etc.
A reliable source recently told me to expect RSA encryption to be broken in three years and government entities are preparing for that.
My guess is that all encryption is already broken using the old-fashioned methods of coercing or suborning an insider.
That’s the primary reason why most current implementations of encryption went to Diffie-Helman Ephemeral (with or without Ellipical Curves) and deprecated RSA key exchange some time ago, because the secret for any one conversation is generated fresh by both sides and only exists as long as both sides have it cached in memory (or an idiot logs it). The weakness of RSA type encryption/key exchange is that they rely on a permanent secret (the private key of the server’s certificate), and once you crack that, you can easily crack everything ever communicated with that server as long as you have a complete copy of the traffic. With ephemeral cyphers, the most you can do is crack one conversation at a time.
The advantage of ephemeral cyphers is that there is nothing for an insider to reveal, either willingly, or under rubber-hose cryptanalysis. It doesn’t matter if the cops have a court order or a water board; you simply don’t have what they are asking for.
TLS 1.3, which came out a few years ago, takes this a step further and has separate secrets for the client and server for both the handshaking process and the bulk crypto, and the protocol only supports ephemeral cyphers (and pre-shared keys, but that’s not for anonymous TLS). No RSA encryption even possible in TLS 1.3. So, if you want to crack that, you have to simultaneously break two secrets per conversation.
Doesn’t help if you’re Chinese, in China. The only encryption there is SN1, SN2, and SN3, their legally required national ciphers, and they are optimized for wiretapping. You can’t even (legally) generate your own private keys in China. If you want to do encryption, you go to the government, they generate a private key and give you a copy, then you go to a certificate authority to get your server certificates. That’s the kind of garbage that authoritarian governments want to do, but they’re not going to get there without crushing the knowledge of cryptographic methods, free exchange of ideas and installing a bunch of monitoring gear in the ISPs to monitor for illegal crypto, then arresting a lot of grandmas who don’t know what they did wrong.
Essentially a cyber one-time pad, then. Those work if the production isn’t compromised in some way. I have to assume that TPTB are working non-stop to do exactly that. I would not trust any one-time pad that I did not produce myself.
Distribution can be tough.
Indeed. And as an amateur I would worry about accidently producing one with some sort of pattern that could be exploited. But what are you going to do when all the institutions have been corrupted.
Simple commands like “Climb Mt. Niigata” could be prearranged and memorized but flexibility is severely limited.
One thing to keep in mind when it comes to using advanced encryption techniques, is that it’s not entirely impossible to use them, even when you have to use Official Keys, and still do it without the Authorities being able to find it.
Just take up an interest in photographs and art, for example. Then take a message, encrypt it using RSA, elliptical curves, or even AES, and then put it in the least significant bits of each pixel of the photograph. If done correctly, it will be indistinguishable from random variations of color from photos.
This is called “steganography”, and just like any other encryption and secret-passing technique, there remains a certain art to it, in no small part due tho the “arms race” of those trying to hide things vs those trying to find them, but it certainly is an option to keep in mind!
Quantum computing is the subject of a vast amount of hype and very little reality.
The way it looks to me is that it is a lovely subject for basic research, and a laboratory curiosity that allows one to spend vast amounts of money. But the state of the art is roughly where conventional computers were in 1945, or perhaps even 1939.
It’s not accurate that quantum computing can break “most encryption methods”. A sufficiently large quantum computer can certainly break RSA, using Shor’s algorithm. It can also apparently break Diffie-Hellman, since there apparently exists a similar algorithm to do discrete logarithms fast. But block ciphers like AES are an entirely different beast and not subject to those algorithms.
The world of Internet crypto has already spent a lot of energy on “post quantum encryption”. I haven’t followed it in detail but I believe it amounts to replacing DH and RSA in the keying algorithms, leaving the block ciphers (AES) alone since they weren’t affected.
A key phrase in the above is “sufficiently large”. Shor’s algorithm requires two qubits per bit of the number to be factored (the RSA key). So a typical RSA key (2k bits) would require 4k qubits, and 4k RSA keys are already not too unusual. But it’s not simply a matter of physically implemented qubits, because quantum computers require error correction. It’s hard to get good information on how much that affects the answer. One source I’ve seen describes an error correcting code that requires a factor of 9; other discussions I’ve seen mentioned numbers as high as a factor of 100. So, taking the smallest number, breaking a typical 2k RSA key would take 36k qubits. That’s two orders of magnitude higher than the state of the art.
One more question is whether quantum computers scale well. It’s not just a matter of building more qubits; they need to be coherent to perform the computation. Can that many qubits remain coherent in a real world device, long enough to execute an interesting computation?
So it looks like the solutions are available and the problem may never even materialize in the first place.
Pingback: State of the art in quantum computing | The View From North Central Idaho
RSA encryption was broken decades ago. Just saying.
“Citation needed”.
If you mean that a 512 bit RSA key was factored, well, sure, exactly as expected. Which is why 2k bit keys are now routine and 2x-4x that is certainly reasonable.
I thought RSA had already been cracked.
I also don’t expect any of my electronic communications to stay secure, at least not from the 3 letter agencies…
I’m with the others, the current quantum computers are not big enough to matter yet; some day they may.