Thoughts on FIPS-certifiability of X-Wing hybrid ML-KEM + X25519
Mike Ounsworth
During the IETF PQ X.509 hackathon last weekend we were taking a close look at the recently-proposed X-Wing hybrid KEM [1], [2] with an eye for whether it would be easy to get it certified by a FIPS lab.
There are two considerations:
1. Non-approved algorithms.
Currently, nether ML-KEM nor X25519 are FIPS-approved, but X-Wing as a whole will become FIPS-approved as soon as FIPS 203 is published because SP 800-56C rev2 allows for the use of Z' which is the concatenation of a Z value and some other T value, which in this case would be the output of ML-KEM and X25519 respectively.
We can also consider other X-Wing-like combiners based on ECDH-P256 or ECDH-P384 that are FIPS-appoved today in the opposite way: we consider ECDH to be the FIPS-approved Z as per SP 800-56Cr2, and ML-KEM to be the non-approved T.
So this part is easy.
2. Is the combiner compliant with SP 800 56Cr2?
Anyone who has gone through FIPS certification knows that even minor discrepancies can lead to months of haggling with your lab.
For that reason, draft-ounsworth-cfrg-kem-combiners-04 uses the combiner
ss = KDF(counter || k_1 || ... || k_n || fixedInfo, outputBits)
where counter is initialized to the 4-byte value 0x00000001, and never incremented.
because it is unambiguously compliant with SP 800 56Cr2.
The X-Wing combiner is
SHA3-256(concat(
XWingLabel,
ss_M,
ss_X,
ct_X,
pk_X
))
XWingLabel = concat(
"\./",
"/^\",
)
So, we think this can be argued to be compliant with SP 800-56Cr2 in the following way:
The X-Wing KDF is compliant with SP 800-56Cr2 section 4 “One-Step Key Derivation” using Option 1 H(x) = hash(x) with SHA-3, and compliant with the Process on page 14 by initializing `counter` to ASCII(“\.//^\”) – which is a deviation both because it’s not 0x00000001 and because it’s 6 bytes rather than 4, but hopefully one that @NIST can bless in an IG – and `FixedInfo’ is Concat(ct_X, pk_X). You may also be able to haggle with your lab that the upper 2 bytes of “\.//^\” is an “augmentation to SP 800-56Cr2 to provide domain separation”, while the lower 4 bytes is an alternate initialization value for `counter`, or some argument like that. Either way, it would be a haggle, and an IG from NIST explicitly allowing this would help smooth this over.
We are looking for feedback:
• From NIST on whether this is a correct interpretation of SP 800-56Cr2, and whether NIST would be willing to publish an IG specifically allowing that substitution of `counter` initial value for the X-Wing domain separator string.
• From NIST on whether you would prefer to instead publish a SP 800-56Cr3 that defines a mode for SHA-3(context_lbl, Z, fixedInfo) – basically rename “counter” to “context label” and don’t bother with the iterations since SHA-3 is already an XOF, and then X-Wing and constructions like it would be more obviously compliant.
• From the X-Wing authors on whether you have already considered the FIPS certifiability of X-Wing (I don’t see any discussion in either the X-Wing paper or IETF internet draft).
• From anyone with FIPS certification experience about the amount of headache and delay you expect this to cause, and whether X-Wing would serve the community better by doing the obvious instantiation of the SP 800 56Cr2 combiner.
[1]: https://eprint.iacr.org/2024/039.pdf
[2]: https://datatracker.ietf.org/doc/html/draft-connolly-cfrg-xwing-kem
- - -
Mike Ounsworth Software Security Architect (pronouns: he/him)
|
COSTA Graham
THALES GROUP LIMITED DISTRIBUTION to email recipients
A couple of tidbit in passing that may be helpful or not:
- there is an existing IG D.P ‘SP 800-56Crev2 One-Step KDF Without a Counter’. In short it allows the counter mandated in SP800-56C for One-Step KDF to be dropped if the length ‘L’ requested is less than H_OutputBits (https://csrc.nist.gov/csrc/media/Projects/cryptographic-module-validation-program/documents/fips%20140-3/FIPS%20140-3%20IG.pdf#page=157). I’m not sure if that is any help or not but since you seemed to be fixing your counter, I assume that implies that your only looking for a small output.
- A different option to getting an IG or update to SP800-56Cr2 would be get the KDF recognized in SP800-135, ‘Recommendation for Existing Application-Specific Key Derivation Functions’ (SP 800-135 Rev. 1, Recommendation for Existing Application-Specific Key Derivation Functions | CSRC (nist.gov)). That specification is currently flagged as being under review at NIST.
- The simplest short-term path as you say may be to propose an IG to CMVP which you could do through the Cryptographic Module Users Forum (CMUF) but where I note that for this kind of thing, they typically delegate to the NIST CTG team. As such, it would be helpful to get them on board first.
- Linked to X25519 with ECDH in your option 1, this is explicitly currently disallowed for new implementations based on the list of permitted curves in SP800-56Ar3. There was at one point an allowance covered under FIPS 140-3, IG, C.A, ‘Use of non-Approved Elliptic Curves’ (https://csrc.nist.gov/csrc/media/Projects/cryptographic-module-validation-program/documents/fips%20140-3/FIPS%20140-3%20IG.pdf#page=89) but where that door tightened/closed on publication of NISTs, SP800-186. There have been multiple conversations on this topic but where this situation is unlikely to change in the short-term. The last post from NIST on this from Dec 8, 2023 (Chris Celi @NIST) is copied below for convenience:
“Hi all,
Recently the CMVP has received questions on if/how X25519 and X448 can be validated to FIPS 140-3. There are currently no paths forward for these algorithms within the SP 800-56 series nor the FIPS 140-3 IGs. X25519 and X448 are non-approved algorithms, even when used within otherwise approved key agreement schemes. The Cryptographic Technologies (CT) group at NIST has expressed to us that there is no on-going effort to add these algorithms to the SP 800-56 series documents. There is not much else the CMVP can do on this matter. We feel the allowance of these algorithms must be done in a standard after the withdrawal of FIPS 140-2 IG A.2. If a vendor would like the CT group to reconsider, it would be best to reach out to the new group manager, Jon Boyens.
Thanks,
Chris Celi”
(Source: https://cmuserforum.onlyoffice.co/Products/Projects/Messages.aspx?prjID=646174&id=309515#comments).
On a ‘how hard is FIPS 140-3 if you don’t comply’ – the main challenge here is whether your implementation will be testable under the NIST CAVP program or not. I do note for the ‘OneStep without Counter’, in addition to the IG, they also added dedicated testing for this to the ACVTS system used for CAVP.
Since the CAVP program is overloaded still working on new test for FIPS 203, 204 and 205, I suspect adding a new KDF testing option will suffer to get traction at the current time.
<Graham @Thales (HSM developer)>
--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CH0PR11MB57395F0517BEC9618DFC1A029F7E2%40CH0PR11MB5739.namprd11.prod.outlook.com.
COSTA Graham
THALES GROUP LIMITED DISTRIBUTION to email recipients
Following up on below following some questions. As a refinement, I agree with what is said under ‘consideration 1’ in the original email.
Despite, X25519 being explicitly disallowed with ECDH as an approved service, that doesn’t prohibit us implementing this in the module or doubling it up with an approved security function.
In the case that ECDH with P-256 or P-384 is separately used, and provided it complies with requirements in SP800-565Ar3 including requirements linked to full key validation, this would form the approved security function. It then doesn’t matter that we ultimately derive a key in parallel using a non-approved security function provided we use an approved KDF when combining the shared secrets.
As one thing I forgot to mention yesterday. Based purely on the ML-KEM draft, the approved KDF was limited to SP800-108. There were comments raised to request this be extended to add SP800-56Cr2 but I don’t think we yet know if this proposal will be accepted or not. That could be another wrinkle with the proposal that falls out with time.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/PR0P264MB37555F3D46A00C52A074C22D997D2%40PR0P264MB3755.FRAP264.PROD.OUTLOOK.COM.
Robinson, Angela Y. (Fed)
Dear Mike,
NIST Special Publication 800-56C specifies techniques for the derivation of keying material from a shared secret Z generated during the execution of a key-establishment scheme defined in NIST SPs 800- 56A or 800-56B. Thus, since neither ML-KEM nor X25519 are specified in 56A nor 56B, NIST does not find that 56C applies to the X-Wing hybrid KEM.
NIST intends to include guidance on hybrid KEMs and KEM combiners in the forthcoming SP 800-227. As pointed out in https://eprint.iacr.org/2018/903.pdf , https://link.springer.com/chapter/10.1007/978-3-319-76578-5_7 , among others, great care is needed when combining KEMs meant to achieve certain security properties. NIST hopes to address this in SP 800-227.
Kind regards,
Angela Robinson
NIST PQC
From: 'Mike Ounsworth' via pqc-forum <pqc-...@list.nist.gov>
Sent: Monday, January 29, 2024 5:29 PM
To: cf...@irtf.org; pqc-forum <pqc-...@list.nist.gov>
Cc: David Hook <David...@keyfactor.com>
Subject: [pqc-forum] Thoughts on FIPS-certifiability of X-Wing hybrid ML-KEM + X25519
During the IETF PQ X.509 hackathon last weekend we were taking a close look at the recently-proposed X-Wing hybrid KEM [1], [2] with an eye for whether it would be easy to get it certified by a FIPS lab.
--
Paul Hoffman
> NIST intends to include guidance on hybrid KEMs and KEM combiners in the forthcoming SP 800-227.
--Paul Hoffman
Mike Ounsworth
+1
---
Mike Ounsworth
From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> On Behalf Of Paul Hoffman
Sent: Wednesday, February 7, 2024 11:01 AM
To: Robinson, Angela Y. (Fed) <angela....@nist.gov>
Cc: pqc-forum <pqc-...@list.nist.gov>
Subject: [EXTERNAL] [pqc-forum] NIST SP 800-227
On Feb 7, 2024, at 08: 00, 'Robinson, Angela Y. (Fed)' via pqc-forum <pqc-forum@ list. nist. gov> wrote: > NIST intends to include guidance on hybrid KEMs and KEM combiners in the forthcoming SP 800-227. This is the first some of us have
-- You received this message because you are subscribed to the Google Groups "pqc-forum" group.To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.Robinson, Angela Y. (Fed)
The forthcoming “NIST Special Publication 800-227: Recommendations for key-encapsulation mechanisms” was mentioned in the FIPS 203 initial public draft (https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.203.ipd.pdf).
Yes, a draft version of SP 800-227 will be available before final publication. At a minimum, the announcement for the release of the initial public draft of SP 800-227 will be made on the PQC forum.
Angela
.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CH0PR11MB5739ECE0BA4C9AC6830DEAAD9F452%40CH0PR11MB5739.namprd11.prod.outlook.com.
Paul Hoffman
> The forthcoming “NIST Special Publication 800-227: Recommendations for key-encapsulation mechanisms” was mentioned in the FIPS 203 initial public draft.
Yes, but only in the context of "the secure use of KEMs", not specifically their use in hybrid KEMs and KEM combiners.
> Yes, a draft version of SP 800-227 will be available before final publication.
--Paul Hoffman
Bas Westerbaan
> Yes, a draft version of SP 800-227 will be available before final publication.
...with a request for comments? I ask because those of us active in the CFRG and the IETF know that there is a lot of differing opinions and an growing number of recent academic papers on the subject.
Mike Ounsworth
To phrase Paul’s thought a different way:
The CFRG is currently in a call for adoption for the whole research area of KEM Combiners [1], with the understanding that there are still unsolved research problems in this area both in terms of security proofs and engineering performance tradeoffs.
It would be unfortunate if NIST and CFRG were working on KEM Combiners completely in parallel and the KEM Combiners blessed by CRFG end up being non-conformant with SP 800-227.
[1]: https://mailarchive.ietf.org/arch/msg/cfrg/PSvLFyBWDdrRaOmaXBStRpGoH3c/
---
Mike Ounsworth
From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> On Behalf Of Paul Hoffman
Sent: Wednesday, February 7, 2024 12:14 PM
To: Robinson, Angela Y. (Fed) <angela....@nist.gov>
Cc: pqc-forum <pqc-...@list.nist.gov>
Subject: [EXTERNAL] Re: [Ext] [pqc-forum] RE: NIST SP 800-227
On Feb 7, 2024, at 10: 05, 'Robinson, Angela Y. (Fed)' via pqc-forum <pqc-forum@ list. nist. gov> wrote: > The forthcoming “NIST Special Publication 800-227: Recommendations for key-encapsulation mechanisms” was mentioned in the FIPS 203
-- You received this message because you are subscribed to the Google Groups "pqc-forum" group.To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.Robinson, Angela Y. (Fed)
Dear All,
Thank you for your interest and feedback on this matter. The existing NIST guidelines in 56A, 56B and 56C were not written with consideration of security definitions like IND-CCA2. We recognize that there is no current NIST guidance that explains how to achieve a hybrid KEM which includes ML-KEM and meets IND-CCA2 security. NIST would like to include some general guidance on the topic in 227 to complement the standardization of ML-KEM, and we hope to stay in alignment with other groups like the CFRG.
NIST hopes that the initial draft for public comment of SP 800-227 will be released around the same time as final version of FIPS 203, however delays are always possible.
Angela
NIST PQC
Watson Ladd
pqc-forum <pqc-...@list.nist.gov> wrote:
>
> Dear All,
>
>
>
> Thank you for your interest and feedback on this matter. The existing NIST guidelines in 56A, 56B and 56C were not written with consideration of security definitions like IND-CCA2.
> We recognize that there is no current NIST guidance that explains how to achieve a hybrid KEM which includes ML-KEM and meets IND-CCA2 security. NIST would like to include some general guidance on the topic in 227 to complement the standardization of ML-KEM, and we hope to stay in alignment with other groups like the CFRG.
indirectly for the entire industry. If we want to have deployment of
post-quantum ciphers ahead of the slow process of validating new
cryptopgraphic modules, we need to ensure that the hybrids are
permitted with today's modules. The absence of clear guidance on this
from NIST hurts, and a change later would be very unfortunate.
Sincerely,
Watson
--
Astra mortemque praestare gradatim
Robinson, Angela Y. (Fed)
Dear All,
As mentioned, the key-derivation methods described in NIST SP 800-56C are currently only applicable to shared secrets established during a key establishment scheme as specified in NIST SP 80056A or 800-56B. NIST intends to allow all key-derivation methods in NIST SP 800-56C to apply to the outputs of the ML-KEM key establishment scheme specified in FIPS 203.
NIST notes that ML-KEM outputs a shared secret key which can be interpreted as a shared secret (in the terminology of SP 800-56C) that does not require further key derivation. However, further key derivation is allowed. One situation where this may be desired is for the purpose of combining an ML-KEM shared secret key with another shared secret. NIST also notes that security of ML-KEM against an active adversary may or may not apply once an ML-KEM key is combined with another shared secret. NIST intends to offer guidance on various key combiners in the forthcoming NIST SP 800-227.
NIST also intends to allow the key derivation methods given in NIST SP 800-56C to apply to any future key establishment standards. Such allowance will be mentioned in an upcoming update to NIST SP 800-56C.
Angela
NIST PQC
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CO6PR09MB7975ED2ADCEFE1E9406B9FD28E4E2%40CO6PR09MB7975.namprd09.prod.outlook.com.