CNSA 2.0 and Quantum Resistant Encryption Algorithms

by King Ables

The National Security Agency (NSA) has released the Commercial National Security Algorithm (CNSA) Suite 2.0 and Frequently Asked Questions detailing future quantum resistant (QR) algorithm requirements for National Security Systems (NSS). CNSA 1.0 was published in 2016 to replace NSA Suite B and standardized the use of the AES, SHA, RSA, DH, ECDH, and ECDSA algorithms and mandated minimum key/curve sizes and uses. CSNA 2.0 adds quantum resistant algorithms with an eye to deprecating the algorithms under threat from practical quantum computing before such platforms are generally available.

These new QR algorithms will replace the RSA and ECC-based algorithms currently used by most products in Common Criteria evaluations. When Automated Cryptography Validation Test System (ACVTS) tests are implemented for these new algorithms, they will be added as selections in NIAP-approved Protection Profiles. Products to be evaluated must implement these new algorithms by the time they are made mandatory, and their counterparts deprecated.

Symmetric algorithms are not considered to be at risk, so they are largely unchanged from CNSA 1.0. CNSA 2.0 specifies AES-256, SHA-384, and adds SHA-512.

Asymmetric algorithms specified in CNSA 1.0 are threatened by quantum computing, and therefore are replaced by new QR asymmetric algorithms in CNSA 2.0.

The first additions will be algorithms used exclusively to digitally sign firmware and software. Leighton-Micali Signatures (LMS) and eXtended Merkle Signature Scheme (XMSS) are signature algorithms specified by NIST SP 800-208. These algorithms will be added to NIAP PPs as selections but will not be mandatory immediately. Note that NIST SP 800-208 requires the key generation and signature generation algorithms to be implemented in hardware and FIPS 140-3 Level 3 validated. It is currently unknown how this requirement will relate to CNSA 2.0. However, a Common Criteria Target of Evaluation (TOE) typically only performs signature validation, which can obtain a Cryptographic Algorithm Validation Program (CAVP) certificate for a software or firmware implementation. ACVTS tests for LMS and XMSS are currently in development and are estimated to be completed in the second half of 2023. NSA encourages vendors to begin implementing these algorithms immediately and recommends new software and firmware use them by 2025, and all software and firmware use them exclusively by 2030.

Future additions will be the asymmetric algorithms CRYSTALS-Kyber for key establishment and CRYSTALS-Dilithium for digital signatures. Both have yet to be standardized by NIST, so there is currently no definite timeline for these additions.

The general plan for each new algorithm is:

1. Approve and publish (LMS, XMSS done, CRYSTALS in progress),
2. Add tests to ACVTS (LMS, XMSS in progress, CRYSTALS TBD),
3. Define CC evaluation activities (LMS, XMSS in progress), and
4. Add requirement as selections to PPs.

Vendors should move to using LMS and XMSS for all software and firmware signing. Products subject to CC evaluation should implement verification of signatures created using LMS and XMSS as soon as possible so the functionality can be claimed and evaluated once the appropriate PP or Module has been updated. Changes to PPs and Modules will be made by updated versions or Technical Decisions. NIAP hopes to make all PP and Module updates by 2027. A public comment period is planned prior to each update.

NIST and NIAP acknowledge the proposed schedule is aggressive which is why vendors are encouraged to begin adoption of the new algorithms immediately. While the proposed schedule is not set in stone, it is hoped the CNSA 2.0 algorithms can be made mandatory and CNSA 1.0 algorithms can be deprecated by 2030.