Crypto-agility: The Gold at the End of the Rainbow for NIST PQC

Cryptography is the backbone of data security technology. In this article, Jo Lintzen, MD at Cryptomathic Inc. explains the preparations for post-quantum cryptography standards and the importance of future-proofing how we use cryptography to protect data in the advent of quantum computing and beyond.

Recently, Ward Beullens, a PostDoc at IBM Research, made headlines for publishing a practical key recovery attack against the Rainbow signature scheme. While this didn’t garner much media attention, the news did cause many in the cryptography community to sit up and take note. What’s more, the ramifications of this event spread far beyond cryptographers to anyone who cares about data security (hint: that should be just about everyone).

To fully understand the significance of these events, it’s important to know the background.

The NIST Post-Quantum Cryptography Standardization Process

In 2016, The US National Institute of Standards and Technology (NIST) announced that it would take a proactive approach to addressing the threat of quantum computing to public-key cryptography. If quantum computing continues to develop at pace, it’s inevitable that these incredibly powerful computers will eventually be capable of breaking essentially all public-key cryptographic algorithms currently in use. In response to this threat, NIST started a multi-year project with the goal of standardizing one or more quantum-resistant public-key cryptographic algorithms, for public-key encryption, key establishment, and digital signature algorithms.

Research teams from around the world responded with over 70 submissions of cryptographic schemes, along with parameters to meet three increasing security levels, SL1, SL3, and SL5. Then NIST and the crypto community began their cryptanalysis. Of the 19 digital signature algorithms accepted for Round 1, nine advanced to Round 2 (January 2019). In July of 2020, three finalists were announced: Dilithium, Falcon, and Rainbow. 

Why does this even matter? Because cryptography plays a foundational role in pretty much all cybersecurity efforts. Cryptography is the backbone of data encryption technology and provides a fast, economical, and secure method to protect data and verify its integrity. As we place more personal and sensitive data online—and as cyberthreats increase in both frequency and sophistication—it becomes more imperative than ever to have encryption tools that are immediately trustworthy and also futureproof.

The End of the Rainbow

Rainbow, one of the three schemes to make it to the NIST competition finals, is based on the so-called Unbalanced Oil and Vinegar scheme. This multivariate signature scheme relies on the difficulty of solving a large system of multivariate quadratic equations over a finite field and includes a trapdoor function. The cryptographers who created Rainbow believed that the algorithm could stand up to the power of large-scale quantum computers. It looked promising.

But people are still smarter than computers and Rainbow’s advancement within the NIST standardization process created a great deal of interest among cryptographers.

Enter Ward Beullens. His most recent work seems to break Rainbow wide open at the most basic level—and here’s the kicker—without even using quantum computing. He used good old-fashioned reverse engineering techniques to crack the code. So, while Rainbow may still technically be considered quantum proof, it's not human proof.

What next? 

Fortunately, the attack methods used by Beullens on Rainbow do not apply to Dilithium and Falcon, as their security relies on an entirely different mathematical concept (hard lattice problems). NIST will announce which algorithm will be standardized soon. After a period for public comment the first set of standards should be finalized by 2024.

Who knows what the continued cryptanalysis of these schemes will bring? Whatever algorithms NIST will choose, they might be broken in the future. As the French ANSSI cautions, “the maturity level of the post-quantum algorithms presented to the NIST process should not be overestimated.”

So where do we go from here?

The need for crypto-agility

If nothing else, the NIST post quantum signature standardization process in general, and the cryptanalysis of the Rainbow signature scheme in particular, serve as a critical reminder of the importance of future-proofing how we use cryptography to protect data. This must be done by embracing the concept of crypto-agility and building systems that facilitate fast and easy switching between cryptographic algorithms. Nothing lasts forever, including cryptographic algorithms, and even the most sophisticated schemes may have to be replaced over time. Finding a single platform from which to manage and scale cryptography solutions across your entire enterprise is the first step toward becoming crypto-agile and creating a truly resilient architecture.

This article was first published in Cloud Computing Magazine on May 03, 2022.