Implementing PQC (Post-Quantum Cryptography) in FIPS 140-3 Modules

On August 13, NIST published the first post-quantum cryptography (PQC) standards, as announced in https://www.nist.gov/news-events/news/2024/08/nist-releases-first-3-finalized-post-quantum-encryption-standards.

In conjunction with this announcement, the CMVP also updated its standards and tooling. With the CMVP updates, these PQC algorithms can now be included in new FIPS 140-3 submissions!

What are the new PQC algorithms?

ML-KEM is a key-encapsulation mechanism. This algorithm can be used to establish a shared secret key over a public channel. It is intended as a replacement for key establishment algorithms (as specified in NIST SP 800-56A and NIST SP 800-56B) since those utilize asymmetric cryptography and are vulnerable to attacks from quantum computers. ML-KEM is based on CRYSTALS-Kyber, with differences as described in Appendix C of the new standard.

The ML-KEM standard is FIPS 203: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.203.pdf

ML-DSA is a digital signature algorithm. It can be used to detect modifications to data and to verify the signer’s identity. It is intended as a replacement for asymmetric digital signature algorithms (as specified in FIPS 186-5) since those utilize asymmetric cryptography and are vulnerable to attacks from quantum computers. ML-DSA is based on CRYSTALS-Dilithium, with differences as described in Appendix D of the new standard.

The ML-DSA standard is FIPS 204: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.204.pdf

SLH-DSA is also a digital signature algorithm. It is intended as an alternative to ML-DSA since ML-DSA relies on lattice cryptography and SLH-DSA is hash-based. SLH-DSA is based on SPHINCS⁺, with differences as described in Appendix A of the new standard.

The SLH-DSA standard is FIPS 205: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.205.pdf

NIST is continuing to develop standards for additional PQC algorithms for key encapsulation and digital signatures, but the standards above are intended to be the primary PQC algorithms.

Adding PQC Algorithms to FIPS 140-3

Publishing the FIPS standards for the PQC algorithms was a crucial step, but not sufficient for these algorithms to be included as approved algorithms in FIPS 140-3 modules. Fortunately, the CMVP took the remaining steps in record time!

The FIPS 140-3 Standards

Standards for algorithms used in FIPS 140-3 modules must be explicitly listed in the FIPS 140-3 standards.

The CMVP met this requirement by updating:

• SP 800-140C: Approved Security Functions to list FIPS 204 and FIPS 205 (ML-DSA and SLH-DSA) as approved digital signature standards
• SP 800-140D: Approved SSP Generation and Establishment Methods to list FIPS 203 (ML-KEM) as an approved key-encapsulation mechanism standard

CAVP Testing

Algorithms used in FIPS 140-3 modules must pass automated testing by the Cryptographic Algorithm Validation Program (CAVP). After successful testing, algorithm certificates are issued for the tested implementations. These algorithm certificates are a prerequisite to submitting a FIPS module to the CMVP for validation.

Testing is now available for these algorithms on both the CAVP’s demo server (accessible by vendors) and the validation server.

Details on the CAVP testing process and tested capabilities for each algorithm can be found at the following links:

• ML-KEM: https://pages.nist.gov/ACVP/draft-celi-acvp-ml-kem.html
• ML-DSA: https://pages.nist.gov/ACVP/draft-celi-acvp-ml-dsa.html
• SLH-DSA: https://pages.nist.gov/ACVP/draft-livelsberger-acvp-slh-dsa.html

Algorithm Self-Tests

Algorithms used in FIPS 140-3 modules must also have corresponding self-tests implemented. The latest version of the FIPS 140-3 Implementation Guidance includes an update to IG 10.3.A that specifies the self-test requirements for each PQC algorithm.

Self-test types include conditional algorithm self-tests (CASTs) and pair-wise consistency tests (PCTs). CASTs must be performed at least once after the module is powered on and before the corresponding algorithm is used. PCTs must be performed for every pair of public and private keys that are generated or imported.

IG 10.3.A specifies the following required algorithm self-tests (when applicable functionality is implemented):

• ML-KEM CASTs as described in #15 of IG 10.3.A:
  • ML-KEM encapsulation CAST
  • ML-KEM decapsulation CAST
  • ML-KEM key generation CAST
• ML-DSA CASTs as described in #16 of IG 10.3.A:
  • ML-DSA signature generation CAST (including all rejection sampling loop paths)
  • ML-DSA signature verification CAST
  • ML-DSA key generation CAST
• SLH-DSA CASTs as described in #17 of IG 10.3.A:
  • SLH-DSA signature generation CAST (separate tests required on SHA2 and SHAKE, recommended on both “s” and “f” algorithms)
  • SLH-DSA signature verification CAST (separate tests required on SHA2 and SHAKE, recommended on both “s” and “f” algorithms)
  • SLH-DSA key generation CAST
• ML-KEM PCTs: “For key pairs generated for use with approved KEMs in FIPS 203, the PCT…shall consist of applying the encapsulation key ek to encapsulate a shared secret K leading to ciphertext c, and then applying decapsulation key dk to retrieve the same shared secret K. The PCT passes if the two shared secret K values are equal.”
• ML-DSA PCTs: “test for pair-wise consistency by calculation and verification of a signature. If the signature cannot be verified, the pair-wise consistency test shall fail.”
• SLH-DSA PCTs: “the PCT…may be limited to confirming the same key identifier (…SEED for SLH-DSA) is shared by the resulting public and private key following generation.”

FIPS 140-3 with PQC

With the CMVP’s swift updates, all the pieces are now in place to start designing and testing FIPS 140-3 modules with approved PQC algorithms! We’re hard at work, and we look forward to offering one of the first FIPS 140-3 validated modules with PQC algorithms!

In the meantime, you can try out the PQC algorithms above and several others with SafeLogic’s PQC Early Access Program, which we announced earlier this year: https://www.safelogic.com/blog/safelogic-announces-post-quantum-cryptography-pqc-early-access-program-at-rsa-conference-2024. To learn more about SafeLogic’s PQC EAP, please reach out to sales@safelogic.com.