Current encryption is safe and here’s how it will stay that way
If there is a boogey man for encryption it’s quantum computing. The prospect of a computer so powerful it could work out all the possible permutations for the secret key and decrypt a message in minutes or hours or even days is pretty frightening. The era of quantum computing is here and there is no turning back, no escaping the fact we only have decades before current encryption is as good as the Caesar Cypher.
Yes, I said decades. Google announced quantum supremacy in 2019 and published a paper in Nature explaining the feat and although it’s an amazing computing achievement, the fastest quantum computers aren’t capable of foiling today’s encryption. This is the most important part to remember about quantum computing—we know quantum computers will eventually be fast and powerful enough to decrypt messages, but they aren’t there yet.
Not that scientists and cryptographers aren’t planning ahead. The U.S. National Institute of Standards and Technology (NIST) started a competition in 2016 to start looking for new quantum-proof encryption methods. And recently the field has gone from 69 contenders to just 15. And it looks like the quantum savior will be lattice-based cryptography:
While quantum machines are still a long way from being able to break modern encryption, NIST launched a competition in 2016 to develop new standards for cryptography that will be more quantum-proof. The race is long, with the winners set to be announced in 2022, but last week the organization announced that it had narrowed the initial field of 69 contenders down to just 15.
And so far a single approach to “post-quantum cryptography” accounts for the majority of the finalists: lattice-based cryptography. Via: The quest for quantum-proof encryption just made a leap forward | MIT Technology Review
Unlike traditional cryptography, including elliptic curve cryptography (ECC), which uses just regular math, lattice-based cryptography uses a path through a lattice of billions of points to create keys. If you don’t know the path, you can’t get the answer. Even the NSA thinks lattice-based cryptography is a good direction to head in our post-quantum world. It’s the shear complexity of a multidimensional grid of points that makes it hard for quantum computers to solve the puzzle.
But there’s a catch.
The need for speed in a small package
One of the reasons ECC is used by us and other mobile-based encryption solutions is it needs small key sizes (measured in bits) to achieve strong encryption. The larger the key size, the larger the encrypted text becomes, the more processing power and memory is needed, and the harder it is for mobile devices to handle all the overhead quickly. For something like a smartphone-based secure messaging app, you need an efficient system so there isn’t a lag between typing a message, encrypting the message, sending the message, receiving a message, and decrypting a message. Imagine how annoying it would be if you typed a message and it took 5 seconds to encrypt it, another 5 seconds to send it, and when the return message came back the same extra 10 seconds receive and decrypt the message.
ECC is perfect for mobile devices because you get strong encryption with small key sizes and lower computational overhead. We use this table to explain the scale we’re talking about here:
With 521-bit ECC you have the equivalent of 15360 bit RSA key in a package mobile devices and handle. And this is the additional challenge to finding quantum-proof encryption—it must be practical for mobile devices. Oh and not just mobile device, but also tiny devices like medical equipment that have only tiny amounts of memory, processing power, and storage space to work with:
However, it’s not just how impenetrable or complex the math is that counts. Post-quantum approaches will only work if they can be used in all the places that high-level cryptography will be needed. For example, the size of the key required to decrypt data is important: imagine what will be possible inside a piece of medical equipment that has little memory and severely limited bandwidth. If the math is so complex that opening the lock requires a massive key, the solution may not pass the usability test.
We have time to get it right
While quantum computing is here, even the best machines can’t solve “useful” problems yet. Problems that could push medical research and drug trials along faster, those aren’t feasible yet. What needs to happen now is the heat and pressure need to stay on the industry so we don’t lose track and forget the reality is looming.
“The next step is quantum computers solving a useful problem, which they haven’t done yet,” says Vadim Lyubashevsky, a cryptographer at IBM who worked on the CRYSTALS algorithm that is now a finalist with NIST. “If that doesn’t happen for a long time, I think companies will forget the hype and implement the weakest thing that comes out of NIST until they are suddenly reminded of the problem in 30 years.”
The work led by the NIST is essential to our future security, even if the threat seems a long way off. Don’t forget the internet itself is only 50 years old, and the web not even 30, and in this time we’ve increased what we considered “good enough encryption for banking” a couple times (128 bit used to be okay, now 256 bit is the minimum standard). We can’t afford to ignore the issue and as the quote above says, take the first thing out of the gate and figure it’s good enough.
ECC and quantum computing
A quick Google search on ECC and quantum resistance turns up results that sound ominous, but aren’t really. By pure math Shor’s algorthirm can be used by a quantum computer to find the right key to decrypt the message, but… as from Wikipedia:
Shor’s algorithm can be used to break elliptic curve cryptography by computing discrete logarithms on a hypothetical quantum computer . The latest quantum resource estimates for breaking a curve with a 256-bit modulus (128-bit security level) are 2330 qubits and 126 billion Toffoli gates . In comparison, using Shor’s algorithm to break the algorithm requires 4098 qubits and 5.2 trillion Toffoli gates for a 2048-bit RSA key, suggesting that ECC is an easier target for quantum computers than RSA. All of these figures vastly exceed any quantum computer that has ever been built, and estimates place the creation of such computers as a decade or more away. Elliptic-curve cryptography – Wikipedia
There’s a big difference between possible, probably, and practical. Right now we know how it’s possible, but we’re a long way off from probable or practical because the largest quantum computer right now is only 53 qubits far short of the 2330 qubits needed.
Last word: it’s not the encryption that’s broken, it’s finding the key
One misconception is when we talk about computers “breaking encryption” we’re not talking about any computer looking at a stream of cypher text and figuring out what the message is by guesswork. No, what computers try to do is find the private key used to encrypt the message. A computer is finding the single, extremely long, number that when punched into the equation to encrypt/decrypt the right result is returned. It’s the discrete logarithm problem that the computer is trying to solve for, not break the encryption itself.
Even cracking the Enigma code wasn’t about breaking the encryption by brute force guessing—that was then and still is today nearly impossible—it was finding the settings used on the Enigma machines that day to encrypt the messages. And that was only possible because they knew a certain message, sent nearly every day, started with the same text. Turing and the team at Bletchley Park knew they had the right settings when they could decrypt that morning weather report correctly.
And the better your password, the larger the encryption key, the harder it is for any computer to make that guess and find the right number.
And by the way all strong encryption used—including SKY ECC—would need a supercomputer cranking away at a message for several billion years to find the right answer.
By that time, I don’t think anything we’ve said today will be of interest to anyone.
