Define API for Module-Lattice-based Key-Encapsulation Mechanism (ML-KEM aka Crystals-KYBER)

[athoelke]

Updated 02-09-2024: The final version of the specification is now published https://csrc.nist.gov/pubs/fips/203/final.

NIST has now published a draft specification for a Key Encapsulation algorithm based on Crystals-KYBER. The algorithm is designated ML-KEM, and will be published as FIPS 203. The draft (open for review until 22 Nov 2023) can be downloaded from https://csrc.nist.gov/pubs/fips/203/ipd.

NIST is planning to standardize three parameterized variants of ML-KEM: ML-KEM-512, ML-KEM-768, ML-KEM-1024, which provide increasing levels of security for increasing computation and size of keys and encapsulated key values.

The Crypto API should define an API for using this algorithm.

[athoelke]

API design thoughts

On first review of the specification, it might be tempting to try and implement the public-key encryption algorithm, K-PKE, that underlies ML-KEM, as a PSA Crypto API algorithm. K-PKE looks similar to other Crypto API asymmetric encryption algorithms, except that it requires an additional input of 512 bits of random data for the encryption step (this is required to support the ML-KEM decapsulation verification). Additionally, FIPS 203 states that K-PKE must not be used for asymmetric encryption:

K-PKE is only a component. The public-key encryption scheme K-PKE described in Section 5 shall not be used as a stand-alone cryptographic scheme. Instead, the algorithms that comprise K-PKE may only be used as subroutines in the algorithms of ML-KEM. In particular, the algorithms K-PKE.KeyGen (Algorithm 12), K-PKE.Encrypt (Algorithm 13), and K-PKE.Decrypt (Algorithm 14) are not approved for use as a public-key encryption scheme.

It seems technically possible to just define K-PKE (and the additional Hash and XOF functions) at the Crypto API layer, and leave the ML-KEM wrapper over K-PKE to the application layer; and so avoid introducing a new API category for KEMs. This would still require new API for asymmetric-encryption-with-context, and standardizing how to provide XOF algorithms via the API. However, this puts a significant responsibility for secure implementation of ML-KEM into the application.

Alternatively, we can introduce a new category of algorithm, "key encapsulation", along with associated key types, that is designed to directly support the ML-KEM operations. In anticipation of other KEMs being specified in future, this is probably the better approach.
Note the proposed SP 800-227 document, that:

will discuss the general properties of KEMs in detail. This will include basic definitions, security properties, and requirements for the use of KEMs in secure applications.

Is it possible that SP 800-227 could influence the design of a KEM API, given the possibility that ML-KEM might not present a typical KEM interface?

[athoelke]

It seems technically possible to just define K-PKE ...

At the moment, I am strongly leaning toward a new KEM API, and keeping K-PKE as an internal implementation detail rather than exposing it as an accessible algorithm.

[kriskwiatkowski]

Here one proposal of an API for KEM (see slide 15)
https://www.amongbytes.com/author/ppt/icmc22.pdf

I would be willing to contribute to that project. I've designed similar KEM API for PQShield, which is now used in production. Please, let me know if you're open for contributions/cooperation.

[athoelke]

Hi @kriskwiatkowski, thanks for the link. Great to see that you've picked up the PSA Crypto API for the project, and you've already been extending it to support the PQ algorithms!

Yes, we are happy to take contributions, whether that is specification text changes; or just an API design, and leave the detailed specification authoring to us. Contributions are accepted under the distribution licenses (see CONTRIBUTING.md).

So far, I have only had some initial thoughts about how to integrate the new PQ key types and algorithms into the Crypto API. So please do contribute, if you are able to.

[athoelke]

Last month, the approved versions of the new NIST PQ crypto standards was announced. That document includes a description of the comments and changes since the draft last summer.

The final specification is at https://csrc.nist.gov/pubs/fips/203/final.

Most details of the scheme are unchanged, the main change since the draft that affects the API design is that it is permitted to store the 64-byte seed, and regenerate the key-pair on demand, in place of storing the 1.6kB-3.1kB decapsulation key (which embeds the encapsulation key). This affects the decision on the default export format for the ML-KEM key-pair.

[athoelke]

API design thoughts

Table 2 in FIPS 203 describes three parameter sets for ML-KEM-512, ML-KEM-768, and ML-KEM-1024. These can most easily be accommodated into the Crypto API by specifying a single key type for ML-KEM, and using a "bit size" of 512, 768, or 1024, to identify the specific parameter set.

Following #196, the key type for ML-KEM should be a non-parameterized asymmetric key-pair/public key (see Non-parameterized asymmetric key encoding in the PR). If we use a NP-FAMILY value of 1, and parity P of 0, this would give us keys types of 0x4002 and 0x7002 for ML-KEM public-keys and key-pairs respectively.

ML-KEM only requires a single algorithm identifier, as all parameterization is contained within the key attributes. #182 which is defining an encapsulation/decapsulation API for ECIES, is currently reusing the 'Key agreement' algorithm category (0x09). It is possible to combine key agreement algorithms, and key encapsulation algorithms in a single category; but it might be more appropriate to allocate a new category (e.g. 0x0b) for KEMs?

The encapsulation and decapsulation API should be the same as the one being developed in #182, which would then support the use of ECC keys in an ECIES algorithm, or ML-KEM keys in the ML-KEM algorithm.

ML-KEM does not indicate that further key derivation is required for the shared secret key output, unless more than 256 bits of key material is needed. This is in contrast to ECIES, where the raw output is biased, and the use of a KDF is indicated for secure use of the shared secret,

This pattern is also present in the PAKE API, where some PAKEs output biased shared secrets, and others output pseudo-random shared secrets. In that case, we document the properties for each algorithm, and expect that the application developers implement a KDF where appropriate, or follow the KDF requirements of the higher level protocol that is using the PAKE.

I suggest that we do the same with the encapsulation API, and return the shared secret, leaving the caller to apply a suitable KDF as required.

The alternative is to construct 'combined key encapsulation and derivation' algorithms (similar to the key agreement API). This is inflexible, and only works for fully specified KDFs (with all additional inputs), such as the KDFs used by the TLS specifications. Returning the shared secret as a key object, permits any suitable KDF to be used subsequent to the KEM.

#182 also proposes ENCAPSULTE/DECAPSULATE usage flags for setting a key policy.