NIST Prepares For Quantum Cryptography Attacks
Quantum computers could totally break all current encryption someday. Thankfully we're getting prepared.
Quantum computers are not a 100% replacement for current so-called "classical" computers. But they're far superior at some things. One of those things is math. And math is used to make sure encryption is secure.
Here's a short lesson on encryption and apologies to those who really study encryption for the shortcuts here.
The product of two large prime numbers is really hard to figure out. The larger the number the more difficult it is to figure out what primes were used to make it. But if you know the primes, then you can decrypt the data and use it with ease. Suffice to say it's really hard math.
Another way to protect encryption is something called an integer discrete logarithm. That is also very hard math.
Humans can't do it in lifetimes, computers can do it but it's really hard.
The largest key ever solved was a 795-bit RSA key in 2019. The same team that did that also computed a discrete logarithm from a key of the same size. Both those efforts took the equivalent of 4,000 core-years using Intel Xeon Gold 6130 CPUs.
Suffice to say you need a lot of machines, using a lot of power to spend a lot of time to crack that. It's pretty secure.
A quantum computer could do both pretty much instantly. You could make the keys even bigger but that won't help. Quantum computing uses the superposition of bits to try lots of possible solutions at once, rather than cranking through attempts.
Thankfully quantum computers are still in the experimental stage and can't practically do this. Yet.
And so even more thanks should go to the US National Institute of Standards and Technology which Tuesday announced the first four candidates for post-quantum cryptography - or PQC - algorithms that cannot be easily broken by quantum or classical computers. For more will be announced at a later date.
Let's walk you though the four candidates.
CRYSTALS-Kyber is used to establish digital keys for two computers that have never interacted before to be able to encrypt their communications.
CRYSTALS-Dilithium is for digital signatures and identity verification. Like what's used in email encryption. It's the companion to CRYSTALS-Kyber and both are considered to be strong enough with excellent performance for most uses. Dilithium is also the easiest of the digital signatures algorithms to implement.
FALCON is harder to implement and may not work on all devices but it's included for use where CRYSTALS-dilitium signatures are too large.
SPHINCS+ is larger and slower but is based on different math, which is good to have as a backup in case a weakness is someday discovered in the lattice approach. Specifically it uses hash functions instead of structured lattices. It's just good policy to have a diverse number of ways to encrypt.
To that point, NIST has four other algorithms under consideration that don't use lattices or hash functions. They will announce one or two of those as additional candidate standards within the next year.
This is a huge step for multiple reasons. One is that while companies can use whatever they want, NIST is seen as a guidepost around the world and may companies want to know their choices before they hop on board.
And second, while quantum computers can't break current encryption yet, malicious actors are capturing encrypted data and holding it for the day when they can decrypt it using Quantum computers. So the faster new encryption goes into place the better protected data is for the future.
Still, NIST advises organizations not to bake these into their systems quite yet as they may change slightly before the standards are finalized which is expected to happen in 2024.