NSA Announces Update to Commercial National Security Algorithm Suite 2.0 and Quantum Computing FAQ

In October 2022, Entrust published the article, NSA Announces New Post-Quantum Resistant Algorithm Suite 2.0 and Transition Timetable. At that time the National Security Agency was one of the first to put a firm line in the sand, publishing an aggressive timeline for the recommended adoption of post-quantum-resistant algorithms. It was a bit of a wake-up call to the digital security industry. Fast forward 18 months and we have a new updated version of the paper: The Commercial National Security Algorithm Suite 2.0 and Quantum Computing FAQ. Algorithm specifications, recommendations, and guidance are slowly starting to crystallize. The eagerly anticipated NIST standardized PQC (post-quantum cryptography) algorithms are set to be approved in summer 2024. You can check for updates here.

At first glance, the algorithm suite looks unchanged:

Table: Commercial National Security Algorithm Suite 2.0

The newly assigned NIST names are now included in the table (see highlighted rows above) as we prepare to let go of the names CRYSTALS-Kyber and CRYSTALS-Dilithium, chosen originally by the cryptographers who designed the algorithms. These are now replaced by the more formal ML-DSA (Digital Signature Algorithm) and ML-KEM (Key Encapsulation Mechanism), a set of algorithms that can be used to establish a shared secret key between two parties communicating over a public channel. These algorithms now have FIPS Publications, FIPS PUB 203 and 204 respectively, assigned to them. The paper also includes an informative FAQ section and some guidance on which PQC algorithms can be used in which situation. Some key areas to note include:

NIST SP 800-208

Regarding stateful hash-based signature schemes, published in 2020, the NSA has only approved LMS and XMSS for use in National Security Systems (NSS). The multi-tree algorithms HSS and XMSSMT are not allowed, although no explanation has been given for this decision.

Stateless Hash-Based Digital Signature Standard (SLH-DSA)

Known to many as SPHINCS+, despite being hash-based, it cannot be used to sign software. It’s not part of the CNSA and is not approved for use.

FIPS Approval of LMS and XMSS Signing Algorithms

Hardware security modules (HSMs) are discussed in relation to certification/FIPS approval of LMS and XMSS signing algorithms. For validating signatures, they must have passed NIST’s Cryptographic Algorithm Validation Program (CAVP).

Hardware Security Modules and the Use of LMS and XMSS

Code signing applications using HSMs will need to be validated to NIST’s Cryptographic Module Validation Program (CMVP). LMS and XMSS algorithms are stateful, meaning they use one-time signatures and when deployed can only produce a finite number of signatures before a new public/private key needs to be generated. See the illustration below for a visual of the stateful key generation process.

Figure 1: Illustration of the stateful generation of derived keys

The private key is a random seed that derives a new private key for each signature. To maintain their security properties, the private key must be used in conjunction with a counter. This is what limits derived private keys to only generate a single signature. The CNSA 2.0 paper further highlights the concern that these private keys, if backed up or migrated to multiple devices, could break the “one-signature-per-derived-private-key” rule. The NSA’s opening position was to forbid export of keys created using these algorithms regardless of whether they’re encrypted or not. While some vendors still believe in the doctrine of storing keys in the box, in the physical memory of the HSM, most vendors have followed Entrust’s long-standing approach: Store keys as encrypted fragments, tokens, or key blobs – whichever terminology you prefer – outside of the physical HSM. The HSM-vendor community, including Entrust, have raised strong objections with the NSA proposal since that would create a single point of failure and severely limit the lifespan of an HSM. Deployments of HSMs are typically configured in pairs where resilience, availability, and backing up keys is standard practice. The NSA has agreed to look at supporting exports without the detrimental impact on the integrity of the algorithm’s security. We’ll continue to keep you updated on the outcome on their review.

Firmware Signatures – Begin Transitioning Immediately

The updated CNSA 2.0 paper also explains the rationale for the prioritization of firmware signatures in their timeline, recognizing that in this use case, the validation algorithm is not easily updated.

• “Software- and firmware-signing: begin transitioning immediately, support and prefer CNSA 2.0 by 2025 where available, exclusively use CNSA 2.0 by 2030.”

Further, the paper explains, “even in systems that are designed for extensibility and cryptographic agility, a quantum-resistant root of trust may be required in the firmware years before the rest of the system upgrades to quantum-resistance. NSA prioritizes this in our timelines to avoid unexpected costs and security issues later in our transition.”

The NSA is recognizing the role that HSMs as a root of trust play in signing firmware, which then acts as the foundation layer of an organization’s cryptographic stack. With 2025 only months away, Entrust is already working on firmware that is safe from a cryptographically relevant quantum computer (CRQC).

ML-DSA for Firmware or Software Signing

The paper recognizes that firmware roots of trust are long-term and, “are a critical component to upgrade…expected to be implemented for some long-lived signatures in 2025, before validated ML-DSA is widely available.” This is impactful for Entrust and our customer base.

Deployment of CNSA 2.0 Algorithms in Mission Systems

The paper encourages algorithm deployment as soon as available and recommends, “testing in vendor and government research environments now to understand the effects of deployment of the new algorithms on particular systems given the increased sizes used in these algorithms.”

Hybrid Solutions

The FAQ section covers the NSA’s position on hybrid cryptographic solutions, using a combination of both classic and post-quantum cryptography. The idea is that until PQC algorithms are standardized and proven in the field, hybrid covers both bases – if the classic algorithms are compromised by a CRQC, the PQC algorithm will protect the data. Equally, if the PQC algorithm was found to be weak, the classic algorithm will still provide some level of protection. According to the paper, “the NSA has confidence in CNSA 2.0 algorithms and will not require NSS developers to use hybrid certified products for security purposes.” They further state in the paper that, “NSA recognizes that some standards may require using hybrid-like constructions to accommodate the larger sizes of CRQC algorithms and will work with industries on the best options for implementation.”

The NSA explained their reservations about hybrid deployments are due to concerns on complexity, compatibility, and the fact that hybrid deployments are an interim solution and will need to be migrated in the future to solely PQC algorithms.

However, the hybrid approach has support in the industry. Some highlight the ill-fated SIKE algorithm, which made it to the 4^th round of the NIST competition only to falter and be broken on a laptop, as an example of what can happen to emerging post-quantum cryptography. Hybrid adds an extra layer of protection in case the PQC algorithm turns out to be vulnerable. I’ve published blog posts about my colleagues at Entrust actively involved in the specification of composite signatures in conjunction with the Internet Engineering Task Force.

In summary, in the space of 18 months the PQC position has moved forward. We can anticipate some of the NIST PQC short-listed algorithms to be standardized in summer 2024. What was theoretical and fuzzy a couple of years ago is starting to take shape. Timelines are firming up and the NIST and NSA are being prescriptive on which algorithms should be adopted in which particular use case, and by when.

For organizations who are following NSA recommendations and want to experiment now, Entrust offers a PQC Option Pack for use in conjunction with our nShield HSMs. It supports the NIST’s PQC algorithms identified for standardization. Customers with an nShield FIPS Level 3 HSM and the nShield Post-Quantum Option Pack can generate quantum-resistant keys inside the HSM, protected by FIPS 140-2 Level 3 Security World standard mechanisms, and carry out key signing, digital signature, encryption, decryption, and key exchange. Learn more about our post-quantum cryptography solutions.