What you’ll learn:
- Why today’s public-key cryptography is no match for quantum computers.
- How industry-standard cryptography has kept us safe thus far.
- What’s behind the new post-quantum secure algorithms selected by NIST.
- What you can do to prepare.
Feeling happy about the security of your systems, data, and online banking? That’s good because, today, we don’t have the computing performance available to break the cryptography that protects it. Well, to clarify, not in a reasonable amount of time orat an affordable price. But change is on the way.
Thanks to intense research into quantum computing, machines could be available in as little as 10 years that are able to extract your cryptographic keys in the blink of an eye—at least in comparison to the efforts required with today’s technology. Luckily, the security community has been working to find new algorithms that will be secure in a post-quantum computing age.
What’s Been Keeping Our Digital Systems Safe?
Cryptography relies on mathematical functions that are easy to compute in one direction (e.g., the multiplication of two large numbers) but exceptionally challenging to reverse (given a large number, find the two numbers that were multiplied to get this result). This means that website visits, bank payments, and access to encrypted data are easy for you, but hard for those looking to break into those systems.
In fact, because today’s cryptography is so good, hackers frequently resort to social engineering to acquire passwords and two-factor authentication pins rather than brute force the keys that protect data.
However, the core premise of this security is that it’s too costly to build a machine that could break it and/or it would take far too long to execute. Consequently, we no longer use the symmetric key cipher DES, the Data Encryption Standard, standardized in the late 1970s.
At the time, Whitfield Diffie and Martin Hellman determined a machine costing $20M would be needed to brute force the standard in around 12 hours. By the late 1990s, a custom DES-cracker costing $250k broke a DES key in two days, with another $10k machine repeating the feat in 24 hours in 2006.
Now, in 2022, researchers from IBM and Google to D-Wave and TU Delft (Delft University of Technology, Netherlands) regularly announce improvements to their quantum computers. While these machines will deliver significant advances to society, their ability to rapidly perform integer factorization is a concern since this is the math that underpins much of today’s public-key infrastructure. In a nutshell, today’s public-key cryptography can be considered broken when facing the computational power of a quantum computer.
Searching for Post-Quantum Cryptographic Algorithms
After it became clear that DES was no longer fit for purpose, the National Institute of Standards and Technology (NIST), a physical sciences laboratory and non-regulatory agency of the U.S. Department of Commerce, set out to find alternatives. In response to a contest organized by NIST, the Advanced Encryption Standard (AES) was selected as the replacement in 2001.
With the security of current cryptography again at risk, NIST started a new contest to find suitable public-key post-quantum cryptographic (PQC) algorithms in 2016 to replace the existing RSA and elliptic-curve cryptography (ECC) standards.
When AES was selected, the internet was new and massive connectivity, such as the Internet of Things (IoT), didn’t exist. Today, the systems demanding security are much more diverse, causing significant challenges for today’s algorithm developers.
Not only must protection against quantum-computer attacks be assured, but it also must be possible to execute the encryption algorithm on today’s small, performance-limited, low-power microcontrollers. Key size is another important way through which security can be improved. However, smart cards and IoT nodes may only provide kilobytes of storage, so this had to be considered.
Four PQC algorithms have been selected in the following six years, with more expected to be announced in the upcoming years. The first algorithm selected is CRYSTALS-Kyber, supporting comparatively small keys (compared to the other PQC candidates) and good operational speed. This is earmarked for the general key exchange used to protect data shared over public networks.
The other three are CRYSTALS-Dilithium, FALCON, and SPHINCS+, targeting the digital signatures used in authentication. Entries were submitted by teams from around the world, often combining industry and academia knowledge.
How PQC Algorithms Differ from Today’s Cryptography
The CRYSTALS and FALCON algorithms rely on the hardness in solving the learning-with-errors (LWE) problem over module lattices. By comparison, SPHINCS+ is based on problems from the realm of cryptographic hash functions. While this algorithm is slower and results in larger code, its inclusion in the winning group of algorithms provides some mathematical diversification, should a weakness be found in the others.
Those who developed these algorithms believe that they will be secure against cyberattacks supported by quantum computers once machines with enough qubits exist.
For software developers, especially in the area of embedded systems, it must be noted that PQC algorithms are much slower due to the different math involved. NIST has considered algorithm execution as part of the selection process, and these algorithms are among the fastest and most secure options submitted.
Another aspect is key size. Using RSA, highest security is attained with keys of 3,000 to 4,000 bits, while ECC requires much less at 32 to 64 bytes. Our new PQC algorithms will need keys of several kilobytes, placing semiconductor vendors under pressure as they build the next generation of security hardware. However, it should be noted that some submissions demanded keys requiring well over 1 MB, so, again, we’ve got the best of the bunch.
Another concern is execution performance on embedded processors and the associated runtime memory requirements. Thanks to years of development and optimization, RSA and ECC are well understood and have a small footprint. Work has already started to evaluate PQC on processors such as the Arm Cortex-M4, a workhorse of embedded systems, with the open project “pqm4” available on GitHub.
CRYSTALS-Kyber proves to be amongst the fastest and most memory efficient. New accelerators and dedicated devices, such as secure elements (SE) and trusted platform modules (TPM), will undoubtedly be developed to further improve performance and keep power consumption under control.
The final concern is implementation. Those following the topic of embedded security will be aware of the extremes that researchers go to to discover design weaknesses. Power monitoring and RF analysis are just some approaches for finding side channels through which cryptographic implementations can be compromised.
Developers have learned much from these efforts and believe that the methods employed to protect ECC and AES hardware can be reused. However, to hedge their bets, new countermeasures also are being explored.
Transitioning to a Post-Quantum World
So, what can be done to prepare your security for a post-quantum world? Although the new PQC algorithms will not be standardized before 2024, there’s plenty of preparatory work for businesses and organizations.
First, it makes sense to continue promoting good security practices amongst users of IT systems and mobile devices. Even PQC algorithms won’t protect against phishing attacks. Today’s most significant risk is that hackers go on a data-collection spree, stealing encrypted files and communication exchanges to deploy post-quantum computing to crack them in the years to come.
The second step is to clarify what security is implemented and where, especially for encrypted databases and files. One particular concern is the threat of store-now, decrypt later: Sensitive encrypted data could be stolen now and only decrypted when quantum computing becomes available.
Finally, developers can kick off exploratory conversations on PQC with vendors and suppliers to understand what will be available and when. Semiconductor vendors such as NXP, one of the contributors to CRYSTALS-Kyber, expect to have PQC-capable silicon available in the next few years, which will support the rollout and migration to this new worldwide security standard.
Cybersecure for the Years Ahead
Quantum computing is a real danger to the integrity of the security upon which we rely. While not yet advanced enough, it’s clear that the math behind today’s ECC and RSA algorithms will be no match for quantum computers.
Although it will take roughly two more years before we can see the new NIST PQC standards, those involved in cybersecurity, from cloud services and IT systems down to tiny IoT nodes, have concrete tasks to undertake. For some, just staying on top of developments will be enough so that, once solutions are available, they’re ready to integrate them.
One thing is clear—we’re ready for the post-quantum era. Thanks to the efforts of industry and researchers, our system and data security are assured.
Whitfield Diffie and Martin E. Hellmann, “Exhaustive Cryptanalysis of the NBS Data Encryption Standard,” Computer, June 1977.
Matthew Nelson, “Cracking DES code all in a day’s work for security experts,” CNN, January 1999.
Matthias J. Kannwischer et al., pqm4 project, GitHub.