Remember quantum computing and the quantum computers that make it possible?
Along with superstrings, dark matter, graviton, and controlled nuclear fusion (hot or cold), quantum computing is a concept many of you have heard of, even if you know very little about these topics beyond their names.
Some of us have vague information or think we do. Because we know why they matter, and we can recite short but inconclusive paragraphs about their basic underlying concepts, and how they were proven, discovered, or invented. can be roughly assumed. Of course.
Of course, practice can lag far behind theory. As the old joke says, controlled nuclear fusion as used to generate clean (ish) electrical energy will be within 20 years of him from the 1930s.
The same is true for quantum computing, which promises to challenge cryptographers with new and faster techniques for parallel password cracking.
In fact, enthusiasts of quantum computing will appreciate that the performance gains are so dramatic that even the world’s wealthiest and most hostile governments were once able to comfortably hold out for decades. It claims to be the encryption key…
… can be suddenly broken in half an afternoon by a modest group of enthusiastic enthusiasts who thrive in your local makerspace.
Superimposition of all answers at once
A quantum computer is a single computation that simultaneously “evaluates” all possible collections of a given computation (usually an algorithm that must be computed over and over with constantly changing inputs until it yields the correct output). It claims that it can be done in iterations. Output in parallel internally.
This probably creates what is known as Superpositionthe correct answer is displayed immediately, and many incorrect answers are displayed.
Of course, we know that at least one of the possible answers is correct, but we don’t know which one is correct, which in itself isn’t all that exciting.
In fact, we are not much better off than Schrödinger’s famous cat. dead AND alive It’s over quickly until someone decides to look into it alive XOR dead.
But quantum computing enthusiasts argue that if constructed with due care, quantum devices can reliably extract the correct answer from the superposition of all answers. Perhaps even a sufficient amount of computation to crunch the cryptanalysis puzzle currently considered computationally infeasible.
incalculable “You get there eventually, but you, maybe the Earth, and – who knows? – the universe will last long enough for the answers to serve a useful purpose.
Schrödinger’s computer
Some cryptographers and some physicists doubt that a quantum computer of this size and computing power might actually be possible, but Schrödinger’s cat in an unopened box is a good example. At present, no one is convinced by either method.
As I wrote when I covered this topic earlier this year:
Some experts believe that quantum computers [be used against] Real-world cryptographic keys.
They suggest that quantum computers baked into physics have operating limits that forever limit the maximum number of answers that can be reliably computed simultaneously. Any use for solving toy problems.
Some say, “It’s a matter of time and money.”
Two major quantum algorithms are known that, if implemented reliably, could pose risks to some of the cryptographic standards we rely on today.
- Grover’s quantum search algorithm. Usually, if you want to search through a set of randomly ordered answers to see if your answer is on the list, at worst you’ll have to go through the entire list before you can get a definitive answer. .But Grover’s algorithm, given a large and sufficiently powerful quantum computer, does the same feat about square root Do a lookup that normally takes 2 hours2N will try (think using 2128 operation to forge a 16-byte hash) in just twoN. Try instead (imagine cracking that hash with 264 to go).
- Shor’s quantum decomposition algorithm. Some modern cryptographic algorithms rely on the fact that they can quickly multiply two large prime numbers together, but it’s nearly impossible to undo the product back to the original two numbers. Roughly speaking, he’s stuck trying to divide a 2N-digit number by every possible N-digit prime until he either hits the jackpot or finds no answer.However, Shore’s algorithm surprisingly solves this problem by logarithm of usual effort. Therefore, factoring a binary number of 2048 digits takes twice as long as factoring a 1024-bit number instead of factoring a 2047-bit number, which represents a significant speedup.
When the future collides with the present
Obviously, part of the risk here isn’t just that we might need new algorithms (or larger keys, or longer hashes) in the future…
…but the digital secrets and certificates we create today and expect to be secure for years and decades may suddenly become crackable within the lifetime of the associated password or hash. there is.
So in 2016, the US National Institute of Standards and Technology (NIST) launched a long-running search for a patent-free, open-source, and freely available cryptographic algorithm that could be considered “post-quantum.” Started a public competition. This means that quantum computing tricks like the ones above are not going to give you any useful speedups.
The first algorithm accepted as a standard in post-quantum cryptography (PQC) will emerge in mid-2022, with four secondary candidates lining up for possible official approval in the future.
(Sadly, one of the four was cracked by a Belgian cryptographer not long after its announcement, but it is a great reminder of the importance of allowing global, long-term, public scrutiny of the standardization process. )
parliament on this matter
Well, last week, December 21, 2022, US President Joe Biden said, HR 7535: Cybersecurity Readiness for Quantum Computing.
The law does not yet mandate new standards, nor does it give a set time frame for switching from the algorithms currently in use, so it is more of a cautionary tale than a regulation.
In particular, the law serves as a reminder that cybersecurity in general, and cryptography in particular, should never be allowed to stand still.
Congress found that:
(1) Cryptography is essential to US national security and the functioning of the US economy.
(2) Today’s most popular cryptographic protocols rely on the computational limits of traditional computers to provide cybersecurity.
(3) Quantum computers may one day have the ability to push the boundaries of computation, solving hitherto difficult problems such as integer factorization, which is important for cryptography.
(4) Rapid advances in quantum computing will allow US adversaries to now use classical computers to steal encrypted sensitive data that a sufficiently powerful quantum system can decipher. suggests that you may wait until
It’s a parliamentary sense –
(1) A strategy is needed to transition federal information technology to post-quantum cryptography.When
(2) A government-wide and industry-wide approach to post-quantum cryptography should prioritize the development of applications, hardware intellectual property, and software that can be easily updated to support cryptographic agility. .
what to do?
The last two words above are the ones to remember. crypto agility.
That means you don’t just need to can Switch algorithms, change key sizes, quickly adjust algorithm parameters…
…but gladly To do so, and to do so safely, perhaps in the short term.
As an example of what not to do, consider the recent LastPass announcement. LastPass customers’ backed-up password vaults had been stolen.
LastPass claims to use 100,100 iterations of the HMAC-SHA256 algorithm in the PBKDF2 password generation process (currently recommends 200,000, OWASP apparently recommends 310,000, but not exemplary. But let’s accept “over 100,000” as satisfying)…
…but only for master passwords created after 2018.
The company informed users with previously created master passwords that their master passwords had been processed in just 5000 iterations, not to mention requiring them to change their passwords to adopt the new iteration strength. didn’t seem to do it.
This makes old passwords much more exposed to attackers using modern cracking tools.
In other words, Maintain cryptographic agilityeven if the sudden quantum computing breakthrough never happened.
When Keep your customers agile too – You don’t have to wait for them to find the hard way they could have been safe if you kept them moving in the right direction.
You probably guessed what we were going to say at the end at the beginning of this article, so it doesn’t disappoint.
Cybersecurity is a journey, not a destination.
