The National Institute of Standards and Technology has lifted the veil on the latest post-quantum cryptographic standards for keys and signature algorithms. Namely CRYSTALS Kyber and Dilithium as well as Falcon and SPHINCS+.
Will the future of a world with quantum systems also be more secure? This week, the US National Institute of Standards and Technology (NIST) announced the algorithms that were chosen in the third round of their competition to create a post-quantum cryptography (PQC) standard based on cryptographic algorithms. able to withstand the capabilities of quantum processors. NIST made an announcement with multiple layers. At its heart are two main algorithms: CRYSTALS-Kyber for establishing a key and CRYSTALS-Dilithium for digital signatures. Both share the same theoretical approach, which could simplify the simultaneous implementation of both. NIST also announced that the Falcon and SPHINCS+ digital signature algorithms would be standardized. It will also continue to study several other algorithms and possibly standardize them in the fourth round of the contest. NIST originally promised the results would be available in early 2022, but later released a statement saying the results had been delayed, but not for technical reasons. The competition started in 2016 and is slowly evolving. The math is complex, and it sometimes takes years to begin to understand the algorithms well enough to spot weaknesses, knowing that potential problems don’t show up so much for decades. This apprehension shows how the NIST proceeded with its choice.
In 2020, at the end of the second round of the competition, NIST chose seven algorithms as finalists and designated eight others as alternates for further study. Since then, academics and experts have examined algorithms, probed for weaknesses, and researched potential attacks. NIST also asked government employees of agencies like the NSA for classified assessments. The competition was motivated by the fact that some of the most commonly used algorithms are also those that could be most threatened by the emergence of a capable quantum computer. Algorithms like RSA or Diffie-Hellman rely on repeated exponentiation in a finite field or ring, and these are easily attacked with Shor’s algorithm. Other common encryption systems use elliptical curves which can also be at risk. This broad class of algorithms includes many of the most commonly used standards for digital signatures or key negotiation. For example, FIPS (Federal Information Processing Standard) 186-4, Digital Signature Standard (DSS) includes three NIST-approved digital signature algorithms: DSA, RSA, and ECDSA… which could be broken by an efficient quantum system. Some of the symmetric algorithms like AES or SHA256 may also be vulnerable to Shor’s algorithm because they use a different technique. Yet other algorithms like Grover’s can support partial attacks. The field of quantum computing is still young. Yet-to-be-discovered algorithms that can deliver entirely different types of attacks.
What are CRYSTALS algorithms?
The two CRYSTALS (Cryptographic Suite for Algorithmic Lattices) algorithms that won the crown rely on the hardness of what is often referred to as the modulus-with-error (MLWE) learning problem. The challenge is to take multiple sample points, some of which might be distractors, and determine or “learn” the function that generates them. This is a relatively new basis for encryption algorithms, but it seems to be solid and, importantly, different enough that no known quantum algorithm can solve it quickly. CRYSTALS algorithms also use what algebraists call a “power-of-two cyclotomic ring”, which makes computation simple and fast with standard processors. Algorithm reviews have praised the speed of its implementation.
NIST has also committed to standardizing two other algorithms known as Falcon and SPHINCS+ to complement the top picks. Falcon could offer smaller digital signatures, which can be essential for some size-critical applications. SPHINCS+ is a stateless hash-based algorithm that uses a very different approach based on leveraging one of the many standard hashing algorithms already available. NIST imagines this could be a good backup in case a broad weakness emerges. It does not rely on lattice arithmetic like other algorithms.
Four encryption algorithms remain under study
As Steve Jobs might say: just one last thing. Four other algorithms pass to the fourth round. They will not be the main standard or even the first alternative, but the committee wants to encourage experimentation and testing, no doubt in case weaknesses in the first choice appear. The four are: BIKE, Classic McEliece, HQC and SIKE. All are based on different mathematical problems and so any attack on, say, MLWE, might not affect them. Plans for these four algorithms vary. In the announcement, NIST suggests that it will choose BIKE or HQC, two algorithms based on the Structured Codes Problem, as an additional standard at the end of the fourth round of the process. Both SIKE and McEliece are in a more nebulous position of being attractive enough to stay, but not attractive enough to commit to creating a full standard. SIKE, for example, would offer small keys and ciphertexts. NIST suggests they can choose to turn either into a full standard at the end of the fourth round.
NIST will provide more details in its upcoming Third Round of the NIST Post-Quantum Cryptography Standardization Process report to be published in its Computer Security Resource Center. They are also planning the 4th NIST PQC Standards Conference for November 29-December 1, 2022. The fourth round of the process is expected to be similar to the first three rounds in that NIST will solicit feedback and then use that information to refine the algorithms. At the same time, they will work on writing more concrete standards for the implementation of algorithms. One of the objectives will be to choose the best parameters that control, for example, the number of revolutions or the size of the keys. It is also clear that the process is far from over. In the announcement, NIST suggested that it will seek new algorithm proposals to “diversify its signature portfolio, such that signature schemes that are not based on structured networks are of greatest interest.”
Practical Security Implications
The good news is that security teams will now have multiple standards to choose from. The main CRYSTALS standards will surely be the focus, but the more cautious developers with the deepest time horizons will want to explore support for some or all of the alternatives. If the code is to run for a long time, it is difficult to know which algorithms may fall prey. Those who actively defend the systems have nothing to do but sketch out future plans. The results do not resemble the discovery of a flaw in a common codebase such as, for example, that found in the Log4J library. The process started because people started speculating openly about what might happen to internet security if a quantum computer with significant power were to appear. The purpose of the contest is to produce alternatives in case such a machine magically appears. Nevertheless, the announcement means that crypto library developers can start offering the new standard in the future. It may take several years before developers have the ability to use CRYSTALS algorithms in place of other more traditional standards. Architects and engineers can start adding these new algorithms to their specifications as alternatives to current standards. This would give their new designs more resilience in the future.
Security professionals can take comfort in the slow development of working quantum hardware. Although there have been high-profile projects run by well-funded companies, few announcements have been made regarding machines that directly affect safety. Google, for example, proudly spread the news of what they called “quantum supremacy,” but it involves a different kind of computation that doesn’t represent the state of the art running Shor’s algorithm. However, researchers attempting to factor numbers to attack RSA often focus on integers with a known structure that can be exploited to greatly simplify the process. As a result, some critics refer to the attempts as “cascades” which rely on knowing the answer before starting the calculation. They recognize that these are useful events and valuable experiences, but they may not be the kind of progress that would threaten current security. This would require the ability to attack arbitrary large numbers without the special structure. John Mattsson, security specialist at Ericsson, suggests that progress in the development of quantum hardware did not seem to keep up with promises. “My personal experience is that researchers personally involved in quantum computing are much more optimistic,” Mattsson said. “Researchers working on quantum computing may, of course, make correct estimates, but history has shown that researchers are often overly optimistic about when their research will have commercial implications.” Even though quantum computers are nowhere near as dangerous as wolves howling at the door, the contest offers an opportunity for CISOs and other security professionals to review their plans for the future. The process offers a chance to develop new algorithms and techniques. These can update existing protocols and provide a backup in case one of the existing standards develops a weakness that does not depend on quantum computing.