ML-KEM Design

This document covers OpenSSL-specific ML-KEM implementation details. ML-KEM is specified in FIPS 203, which includes comprehensive pseudo-code for all its algorithms.

ML-KEM Parameters & Functions

There are 3 different parameter sets in FIPS 203 (see Section 8).

To support these variants, OpenSSL has 3 associated key managers and 3 corresponding KEM function sets. The key management and KEM algorithm names are ML-KEM-512, ML-KEM-768 and ML-KEM-1024. At the TLS layer, the associated key exchange groups are, respectively, MLKEM512, MLKEM768 and MLKEM1024.

ML-KEM makes extensive use of four SHA3 primitives: SHA3-256, SHA3-512, SHAKE128 and SHAKE256. To improve ML-KEM execution performance, the EVP handles for these are pre-fetched during ML-KEM key initialisation and stored with each key. These are then used in key generation, encapsulation and decapsulation. These are also duplicated by reference (EVP_MD handles uprefed) when an ML-KEM key is duplicated.

ML-KEM keys

ML-KEM is an asymmetric algorithm, and has both public and private keys. Since the public key is exchanged between the two parties as part of key agreement, the encoding (wire-form) of the public key is clearly defined and there are unambiguous choices for its encoding and decoding functions.

It may be noted that the wire-form public key is "compressed". Instead of the bulky "A" ("m" in the code) matrix, which represents the majority of the storage required for ML-KEM public and private keys, the wire-form public key, holds a 32-byte seed from which the the matrix is regenerated by the recipient of the public key. In the OpenSSL implementation, the matrix is eagerly evaluated as part of decoding the public key, and stored in memory in the internal form needed for subsequent computations (encapsulation). Since the private key includes the public key as one of its components, the matrix is also pre-computed and stored with the private key, and then need not be regenerated during decapsulation. During encapsulation (typically peformed by servers), it is in principle possible to save space and compute the matrix elements just-in-time, as each matrix element is used exactly once. This is not currently implemented, and the matrix is pre-computed in full.

However, the same matrix is used both during key generation and decapsulation and computing it twice would have a noticeable performance impact (typically on the client). If we wanted to do just-in-time matrix computation for decapsulation, we'd need to have a different memory layout for public keys when only the public key is known, and to change the algorithm code to generate matrix elements on demand during encapsulation. This can be considered later, if it is determined that the space savings (9 * 512 bytes in memory for ML-KEM-768, for the full matrix, instead of 512 bytes for a just-in-time element). Since servers will generally destroy the client public key soon after the shared secret is computed, these don't stay in memory long, and briefly saving ~2KB may not to be of much benefit).

The private key format is yet to be clearly standardised, though (to be able to fully describe the algorithms) FIPS 203 documents a format that is commonly referred to as the "extended" format. This is the private key format supported by our key management provider interface. The IETF voices interest in using the "seed-based" format (the 64-byte (d, z) seed pair from which the key is generated and can be recovered). Recovery of the key from the seed (d, z pair) is supported by the FIPS 203 internal deterministic key generation functions, which are used in the keygen portion of the Known Answer Tests (KATs).

The design therefore caters to both options: The default key generation and KEM encapsulation/decapsulation functions operate on "extended keys" in the FIPS 203 format, but it will be possible to use the "seed-based" private key format by using the (currently test-only) deterministic keygen interface. When keys are generated randomly, we don't presently provide a mechanism to obtain and store the seed. This can be added later if required.

Key generation API

Keys can be generated via the usual EVP_PKEY_generate() and EVP_PKEY_Q_keygen() functions.

An explicit seed can be specified by setting the key generation OSSL_PKEY_PARAM_ML_KEM_SEED parameter to a 64-byte octet-string (concatentation of the d and z values (32-bytes each) in that order).

KEM API

ML-KEM is meant to be a drop-in replacement for existing KEM algorithms. Accessed in the usual way via:

• EVP_PKEY_encapsulate_init(),

• EVP_PKEY_encapsulate(),

• EVP_PKEY_decapsulate_init(), and

• EVP_PKEY_decapsulate().

For the encapsulation operation, a test-only option exists to bypass the random number generator (secret random inputs are required for security) and pass in a pre-determined 32-byte random value, by setting of the OSSL_KEM_PARAM_IKME parameter.

Buffers

The ML-KEM key management and KEM providers interface with the underlying libcrypto implementation via functions that validate the sizes of all provided input/output buffers (encoded keys, ciphertext, shared secrets and seeds) against the values expected for the provider's ML-KEM variant (a pointer to the variant parameters is stored with each key).

The underlying libcrypto ML-KEM APIs are not directly exposed to users, only the abstracted key management and KEM EVP APIs are public interfaces.

Constant Time Considerations

The usual constant time methods are used in the implementation. However, we avoid using a value-barrier to set the masks that perform constant-time select between one of two values. This avoids a 30-50% performance penalty and is expected to be robust even in the face of plausible future compiler optimisations. Remainders module the prime are computed via Barret Reduction and the decoding and decompression of the decrypted message has been tested to not be vulnerable to the "clangover" attack in our implementation.

All the libcrypto functions (other than ML_KEM_KEY allocation, which returns NULL on error) return 1 for success or zero on error. It should be noted that to avoid chosen-ciphertext attacks, the decapsulate implementation must return success and a synthetic shared secret (generated in constant-time whether synthetic or successfully decrypted) whenever the input is a well-formed ciphertext.

The only exception to the above is when, unexpectedly, one of the SHA3 functions fails, in that case all hope of constant-time computation is lost, but we don't expect such failures to be influenced by the content of chosen-ciphertexts, so this should not be an issue).

Nevertheless, even then we fall back on returning a shared secret from the RNG along with an error indication only when the key derivation function for the synthetic shared secret fails. In all other conditions we return success and, as appropriate, either the correct shared secret, or the synthetic alternative generated by the KDF.