PQC algorithm standardization in the context of FIPS 140-3 and ISO

[Samuel Lee]

Hey folks,

 

I raised a concern last August that I did not think the FIPS 140-3 IG updates for finalized PQC algorithms were quite right: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/s_Wez9FanHw/m/tPeaMCPwCgAJ

I am now working to give feedback to 140-3 IG (Implementation Guidance for FIPS 140-3 10.3.A Additional Comments) through CMUF and an RFG (Request for Guidance), to clarify requirements around pair-wise consistency tests. I am looking for folks from the PQC forum to weigh in to help inform the discussion at CMUF.

 

I see there are a few process problems going on here:

1. Standardization of new algorithms is not explicitly taking into account requirements on FIPS modules, leading to ambiguity about how to apply FIPS 140-3 to these new algorithms.

2. ISO requirements in ISO/IEC 19790-2012 are based on algorithms and cryptographic problems that existed at a point in time, and do not necessarily reflect the reality of failure modes of new algorithms.

3. There is general ambiguity around where requirements end up being specified. The FIPS 140-3 IG seems like it should be there to guide implementors on how to be certifiable, not to specify what is certifiable.

 

 

Some background:

FIPS 140-3 derives from ISO/IEC 19790-2012, which has requirements about self-tests algorithms must have.

FIPS 140-3 IG does override ISO requirements in some instances.

 

The requirement I am particularly interested in at present is ISO/IEC 19790-2012 7.10.3.3, which is that when a cryptographic module generates a private/public key pair, a pair-wise consistency shall be performed.

This requirement is made more prescriptive in the related ISO/IEC 24759-2017 document with VE10.35.01 / VE10.35.02 / VE10.35.03 specifying tests for specific types of cryptographic scheme:

 

Key transport / Asymmetric ciphers, the test is public encryption followed by private decryption
Signatures, the test is signing followed by verification
Sensitive security parameter (SSP) agreement, the test is a little underspecified, leaving the test up to documentation and details of the algorithm

 

So there are a few questions for the community here:

1. For keypairs used in an ephemeral scheme, with some expected failure rate due to transferring public key material and/or ciphertexts over a lossy channel, do we see there is real benefit to performing a pair-wise consistency test on every generated keypair?
   Both SP800-56a rev3 and FIPS 203 do not expect extra tests on keypair generation for ephemeral use, but ISO / FIPS 140-3 require them, which IMHO basically just makes FIPS modules slower than non-FIPS modules for no real-world benefit.

2. For ML-KEM and ML-DSA specifically, each E2E use with a keypair only uses a subset of the key material, so existing defined pair-wise consistency tests do not guarantee consistency.
   
   Specifically for ML-KEM (FIPS 203), in encapsulation, the public vector t is only partially used because it is multiplied by y vector (in line 21 of Algorithm 14 to produce v), and the y vector has polynomials with many 0 coefficients (line 10 of Algorithm 14).
   Similarly for ML-DSA (FIPS 204), in verification, the public polynomial t1 is only partially used because it is multiplied by c (in line 9 of Algorithm 8), and the c polynomial has many 0 coefficients (line 8 of Algorithm 8).
   
   In both cases, if the keygen process was faulty and the public key has a coefficient with bit flipped compared to the correct keygen process, the produced faulty keypair may succeed a high-level pairwise consistency test (encaps+decaps / sign+verify), but still fail if the faulty coefficient is used in a subsequent operation.

3. There is precedent for defining a different pair-wise consistency test in FIPS 140-3. The current FIPS 140-3 IG for hash-based signatures defines a much-simplified pair-wise consistency test for hash-based signatures (LMS, XMSS, and SLH-DSA) primarily because the performance of a traditional PCT is really bad. Do folks agree that this should also apply to ephemeral keypair generation for ML-KEM?

4. Do we agree that future FIPS algorithm specification documents should address recommendations around self-tests explicitly such that there is less divergence between implementing an algorithm correctly per the algorithm standard and implementing the algorithm correctly in the context of a FIPS module?
   If this is done, then perhaps the FIPS 140-3 IG can defer to the explicit guidance in the algorithm specifications unless and until there is a reason to make a change.

Any opinions on one or all of questions a-d, and perceived problems 1-3, very much appreciated!

Thanks,

Sam

[Samuel Lee (ENS/Crypto)]

Thought I should note a correction for (b). While the effect of a single E2E operation not checking the consistency of the keypair is accurate for ML-KEM / ML-DSA, I made a mistake in reasoning about the mechanism.

Before starting this thread, I had tested locally by flipping random public key bits, recomputing the hash of the public key kept in the secret key, and observing the flaky success/failure.

I jumped to the conclusion that it is due to some coefficients being unused as the sample values (y in ML-KEM, c in ML-DSA) have many zero coefficients. This doesn't actually make sense, because the polynomial multiplication is not element-wise in the coefficients.

My understanding now is that we don't exercise the full value of the public vector due to rounding meaning that least-significant bits often don't affect the result. Thanks to Joost Renes for pointing this out here: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/GPtJRsk67TY/m/kkUUSU97BQAJ

Would still appreciate if folks have any input on the questions.

I have received some feedback directly, but public posts would help with a shared understanding. 🙂

Best,

Sam

---

From: 'Samuel Lee' via pqc-forum <pqc-...@list.nist.gov>
Sent: 24 March 2025 19:00
To: pqc-forum <pqc-...@list.nist.gov>
Subject: [EXTERNAL] [pqc-forum] PQC algorithm standardization in the context of FIPS 140-3 and ISO

 

--
You received this message because you are subscribed to a topic in the Google Groups "pqc-forum" group.
To unsubscribe from this topic, visit https://groups.google.com/a/list.nist.gov/d/topic/pqc-forum/qbHGXx09daw/unsubscribe.
To unsubscribe from this group and all its topics, send an email to pqc-forum+...@list.nist.gov.
To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/9e9fd16f-b432-4d6a-8e8d-71ad55a94bb4n%40list.nist.gov.