NIST names new post-quantum cryptography standards

The path to a secure future in a world with quantum computers just became a bit clearer. The U.S. National Institute of Standards and Technology (NIST) announced the algorithms that were chosen in the third round of its competition to create a new post-quantum cryptography (PQC) standard built upon encryption algorithms that can resist the powers of quantum processors.

NIST made an announcement with several layers. At the core were the choices for the main algorithms: CRYSTALS-Kyber for establishing a key and CRYSTALS-Dilithium for digital signatures. Both share the same theoretical approach which could make it simpler to implement both concurrently. 

NIST also announced that the digital signatures algorithms Falcon and SPHINCS+ would be standardised. It will also continue to study several other algorithms and perhaps standardise them during the fourth round of the competition.

NIST initially promised that the results would be available in early 2022 but later put out a statement saying that the results were delayed but not for technical reasons. The contest began in 2016 and is evolving slowly. 

The mathematics is complex and sometimes it can take years to begin to understand the algorithms well enough to spot weaknesses. Sometimes potential problems don’t emerge for decades. This trepidation shows in the way that NIST chose two winners but many runners up or alternates.

In 2020 at the end of the second round of the contest, NIST chose seven algorithms as finalists and designated eight others as alternates for further study. Since then, academics and experts have examined algorithms, probed weaknesses, and searched for potential attacks. NIST also asked government employees from agencies like the NSA for classified assessments.

The contest was motivated by the fact that some of the most common algorithms in broad use are also the ones that may be most threatened by the emergence of a successful 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 cryptographic systems using elliptic curves may also be threatened.

This broad class of algorithms includes many of the most commonly used standards for digital signatures or key negotiation. Federal Information Processing Standard (FIPS) 186-4, Digital Signature Standard (DSS), for instance, includes three NIST-approved digital signature algorithms: DSA, RSA and ECDSA. All could be broken by an effective quantum machine.

Some of the symmetric algorithms like AES or SHA256 may be as vulnerable to Shor’s algorithm because they use a different technique. Still, other algorithms like Grover’s algorithm may support partial attacks. The field of quantum computing is still young. Yet-to-be-discovered algorithms that may provide entirely different types of attacks.

What are the CRYSTALS algorithms?

The two CRYSTALS (Cryptographic Suite for Algorithmic Lattices) algorithms that won the crown rely upon the hardness of what’s often called the module learning with errors (MLWE) problem. 

The challenge is to take several sample points, some of which might be distractors, and determine or “learn” the function that generates them. This is a relatively new foundation for cryptographic algorithms, but it appears to be strong and, most importantly, different enough that there aren’t any known quantum algorithms that might solve it quickly.

The CRYSTALS algorithms also use a form of points from what is known to algebraists as a “power-of-two cyclotomic ring,” which makes computation with standard CPUs straightforward and fast. The evaluations of the algorithms praised the speed of its implementation.

What are the Falcon and SPHINCS+ algorithms?

NIST also committed to standardising two other algorithms known as Falcon and SPHINCS+ to complement the main choices. Falcon could offer smaller digital signatures which may be essential for some applications where size is important.

SPHINCS+ is a stateless, hash-based algorithm that uses a very different approach relying on leveraging one of the many standard hash algorithms already available. NIST imagines that it might be a good back-up in case a broad weakness appears. It doesn’t rely upon arithmetic in a lattice like the other algorithms.

Four encryption algorithms remain under study

As Steve Jobs might say, there’s one more thing. Four other algorithms are advancing to the fourth round. They won’t 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 rely on different mathematical problems and so any attack on, say, MLWE, might not affect them.

The plans for these four algorithms vary. In the announcement, NIST suggests it will choose either BIKE or HQC, two algorithms built upon the problem of structured codes, 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 keep around but not attractive enough to commit to making a full standard. SIKE, for example, is said to offer small keys and ciphertexts. NIST suggests that they may choose to turn either into a full standard at the end of the fourth round.

NIST will distribute more details in the NIST Interagency or Internal Report (NISTIR) 8413, Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process that will be released at its Computer Security Resource Center. They are also planning the 4th NIST PQC Standardization Conference for November 29 to December 1, 2022.

The fourth round of the process should be similar to the first three rounds in that NIST will solicit comments and then use these insights to refine the algorithms. At the same time, they will work on writing more concrete standards for implementing the algorithms. One focus will be choosing the best parameters that control, say, the number of rounds or the size of the keys.

It’s also clear that the process is far from over. In the announcement, NIST suggested that they will ask for new proposals for algorithms to “diversify its signature portfolio, so signature schemes that are not based on structured lattices are of greatest interest.”

Practical security implications

The good news is that security teams will now have new standards to choose among. The main CRYSTALS standards will surely be the focus, but the most cautious developers with the deepest time horizons will want to explore supporting some or all the alternates. If the code must run for a long time, it’s hard to know which algorithms may fall prey.

Those who are actively defending systems don’t need to do anything but sketch out future plans. The results aren’t like the discovery of a flaw in a common code base like, say, the one found in the Log4J library. 

The process began because people started to openly speculate what might happen to security on the internet if any quantum computer with significant power were to appear. The goal of the contest is to produce alternatives in case such a machine were to magically appear.

Still, the announcement means that developers of cryptography libraries can begin to offer the new standard in the future. It may take several years before developers will have an option to use CRYSTALS algorithms in place of other more traditional standards.

Architects and engineers can begin to add these new algorithms to their specifications as alternatives to the current standards. This would give their new designs more resilience in the future.

Security professionals can take solace in the slow pace of development of working quantum hardware. While there have been high-profile projects run by well-funded companies, few announcements have been made about machines that directly affect security.

Google, for example, proudly broadcast the news of what they called “quantum supremacy,” but it involves another type of calculation that doesn’t represent the state of the art executing Shor’s algorithm. Researchers trying to factor numbers to attack RSA, though, often focus on integers with known structure that can be exploited to greatly simplify the process. 

As a result, some detractors refer to the attempts as “stunts” that rely upon knowing the answer before starting the computation. They acknowledge that they’re useful events and valuable experiments, but they may not be the kind of progress that would threaten current security. That would require the ability to attack arbitrary large numbers without the special structure.

John Mattsson, a security specialist at Ericsson, suggests that progress in quantum hardware development didn’t seem to follow the promises. 

“My personal experience is that researchers personally involved in quantum computing are much more optimistic,” said Mattsson. “It might, of course, be that researchers working on quantum computing make correct estimates, but history has shown that researchers are often too optimistic on when their research will have commercial implications.”

Even if the quantum computers are not anywhere close to being as dangerous as wolves baying at the door, the contest offers an opportunity for CISOs and other security professionals to revisit their plans for the future. 

The process offers a chance to nurture new algorithms and new techniques. These can refresh existing protocols and provide a back-up in case any of the existing standard develop a weakness that doesn’t depend upon quantum computing.