Written by Stephan Mueller
In late February, NIST held a workshop about practical aspects of Key Encapsulation Mechanisms (KEMs) and their deployments, with both vendors and researchers giving presentations about their uses of KEMs that outlined the challenges they faced and the resolutions they discovered. Each of these insightful presentations is available on the NIST KEM Website.
Of particular interest, NIST crypto technology group members also gave us a glimpse of the future, diving into developing new requirements using the current draft of SP800-227, with multiple proposed solutions, detailed below. Note that none of the outlined items are approved at the time of writing, but they highlight promising upcoming NIST standards.
Hybrid KEM Variants: Shared Keys
A hybrid KEM is a combination of two or more individual KEM algorithms, typically a post-quantum KEM like ML-KEM and a classic counterpart, such as ECDH. By adopting a hybrid approach, full security can be maintained even if one algorithm is broken.
SP800-56C Key Derivation
To establish a hybrid KEM, the two or more KEM algorithms must be combined using a “KeyCombiner”, which is usually provided by a key derivation function (KDF) from SP800-56C.
The naive approach is to generate the derived shared key by applying a KDF on the concatenated individual shared keys from the KEMs: K = KDF(K1 || K2). This security model, however, does not achieve IND-CCA security, even though one or more KEM algorithms provide that security level.
For the resulting derived shared key to achieve IND-CCA security when using at least one KEM with IND-CCA security, the encapsulation keys and/or the KEM ciphertexts would need to be added: K = KDF(K1 || K2 || ek1 || ek2 || c1 || c2).
Finally, to add a means for domain separation, an arbitrary string can be concatenated: K = KDF(K1 || K2 || ek1 || ek2 || c1 || c2 || OtherInput).
This construction results in a FIPS-approved derived shared key K, assuming at least one of the KEMs is a FIPS-approved algorithm. This explicitly allows the combination of approved and non-approved KEMs.
Note that the order of the inputs to the KDFs is of no relevance to security and can thus be defined by the implementor.
SP800-133 Key Generation
Applying the methods of SP800-133 is another approach to combine the shared keys from the individual KEMs, though the important difference compared to SP800-56C is that, with this method, all shared keys used as input to the KeyCombiner must be from FIPS-approved KEM algorithms.
The allowed solutions are:
- Concatenation: K = K1||K2
- XORing: K = K1 XOR K2 XOR OtherInput
- HMAC-extraction: K = Truncation(HMAC(salt, K1 || K2 || OtherInput))
ML-KEM and ML-DSA Seeds
FIPS 203 and FIPS 204 both allow the user to retain the seed value to re-generate the key pair from that seed later in lieu of the actual key pair.
As a refresher, the following requirements are defined in the standards:
* FIPS 203: Two 256-bit random numbers must form the seed. NIST made it explicitly clear that only two 256-bit random numbers derived from a fully seeded DRBG are allowed to be retained; the other methods discussed below are not currently allowed.
* FIPS 204: One 256-bit random number forms the seed.
The NIST CT group provided a preview of an upcoming change to SP800-133 that allows the use of KDFs to generate key material in addition to DRBGs. When considering the issue of the FIPS 203 seed, it may be permissible to only retain a single 256-bit random number obtained from a fully seeded DRBG and then apply a KDF on this value to stretch it to the required size.
For FIPS 203, this change would allow the following method: seed_64_bytes = KDF(seed_32_bytes), ultimately implying that a 256-bit random number can be stored which the full ML-KEM key pair can then be derived from.
Hybrid KEM Variants: Seeds
The interesting implications don’t end there, though, as the proposed change to SP800-133 may also allow the derivation of seeds for hybrid approaches. To understand the motive, the following needs to be considered: each KEM algorithm used as part of a hybrid construction has its own key pair, and that key pair is derived from a random number obtained from a DRBG.
The hybrid seed approach now allows for generating a 256-bit random number from which a KDF can derive the required seed material used to generate the different key pairs. Compared to the current approach, this cuts the stored data in half – a pretty staggering gain. Furthermore, the amount of seed material is exactly the size of an AES-256-bit symmetric key, implying that a key store may only need to implement one type of data storage.
For example, the current IETF proposal called X-Wing specifies key generation as follows:
1. Generate a 256-bit seed from a DRBG; this seed may be retained until the need arises to obtain the full KEM keys.
2. Expand the seed to 768 bits using SHAKE with the seed from step 1.
3. Generate the ML-KEM key pair from the left-most 512 bits of the expanded seed from step 2.
4. Generate the classic algorithm (X25519 in case of the discussed X-Wing proposal) key pair from the right-most 256 bits of the expanded seed from step 2.
With the proposed changes to SP800-133, this key generation method would become FIPS approved. Furthermore, even though a non-approved algorithm (X25519) is used in the X-Wing proposal, using the aforementioned SP800-56C KeyCombiner approach results in a shared key that would still be considered approved, meaning that the X-Wing proposal could be a completely approved mechanism. Should the proposal be approved, it would provide an approach for managing keys for hybrid KEM solutions currently discussed at the IETF.
CAVP Updates
The ML-KEM algorithm is currently supported by CAVP testing complying with the FIPS 203 specification. In the future, the ML-KEM decapsulation testing will be updated to add more induced error tests, as the current decapsulation test validates only one type of error handling. This enhanced error testing verifies that the ML-KEM implementation can identify and sort out incorrect input data to prevent cryptographic weaknesses.
NIST also plans to add a CAVP test of the PKE.Encrypt ML-KEM-internal algorithm and is fully aware this algorithm is not allowed to be used directly by callers. Therefore, the PKE.Encrypt test is intended to cover the test scenario where a module only supports ML-KEM decapsulation as an external service. As the decapsulation operation internally uses the PKE.Encrypt algorithm, NIST intends to require the PKE.Encrypt testing in the event only the ML-KEM decapsulation service is offered by a module.
NIST further explained that it enforces the testing of all algorithms on which ML-KEM depends: SHA3-256, SHA3-512, SHAKE128 and SHAKE256.
This blog serves as an open discussion platform for the cryptographic community, aiming to engage experts and practitioners in shaping future standards. While the insights shared here reflect ongoing deliberations and potential developments, it is crucial to emphasize that, for any current FIPS validation, implementers must adhere strictly to published standards. Speculative adoption or premature implementation of unpublished standards—those still under discussion—could lead to non-compliant designs and unnecessary risks. We encourage readers to stay informed, participate in the dialogue, and contribute to the responsible evolution of cryptographic security.
