1ML-KEM Design 2============= 3 4This document covers OpenSSL-specific ML-KEM implementation details. 5**ML-KEM** is specified in [FIPS 203], which includes comprehensive pseudo-code 6for all its algorithms. 7 8ML-KEM Parameters & Functions 9----------------------------- 10 11There are 3 different parameter sets in FIPS 203 (see Section 8). 12 13To support these variants, OpenSSL has 3 associated key managers and 3 14corresponding KEM function sets. 15The key management and KEM algorithm names are **ML-KEM-512**, **ML-KEM-768** 16and **ML-KEM-1024**. 17At the TLS layer, the associated key exchange *groups* are, respectively, 18**MLKEM512**, **MLKEM768** and **MLKEM1024**. 19 20**ML-KEM** makes extensive use of four **SHA3** primitives: **SHA3-256**, 21**SHA3-512**, **SHAKE128** and **SHAKE256**. 22To improve **ML-KEM** execution performance, the EVP handles for these are 23pre-fetched during **ML-KEM** key initialisation and stored with each key. 24These are then used in key generation, encapsulation and decapsulation. 25These are also duplicated by reference (**EVP_MD** handles uprefed) when an 26**ML-KEM** key is duplicated. 27 28ML-KEM keys 29----------- 30 31**ML-KEM** is an asymmetric algorithm, and has both public and private keys. 32Since the public key is exchanged between the two parties as part of key 33agreement, the encoding (*wire-form*) of the public key is clearly defined and 34there are unambiguous choices for its encoding and decoding functions. 35 36It may be noted that the *wire-form* public key is "compressed". 37Instead of the bulky "A" ("m" in the code) matrix, which represents the majority 38of the storage required for ML-KEM public and private keys, the *wire-form* public 39key, holds a 32-byte seed from which the the matrix is regenerated by the recipient 40of the public key. 41In the OpenSSL implementation, the matrix is *eagerly* evaluated as part of 42decoding the public key, and stored in memory in the internal form needed for 43subsequent computations (encapsulation). 44Since the private key includes the public key as one of its components, the matrix 45is also pre-computed and stored with the private key, and then need not be 46regenerated during decapsulation. 47During encapsulation (typically peformed by servers), it is in principle 48possible to save space and compute the matrix elements *just-in-time*, as each 49matrix element is used exactly once. 50This is not currently implemented, and the matrix is pre-computed in full. 51 52However, the same matrix is used both during key generation and decapsulation 53and computing it twice would have a noticeable performance impact (typically on 54the client). 55If we wanted to do *just-in-time* matrix computation for decapsulation, we'd 56need to have a different memory layout for public keys when only the public key 57is known, and to change the algorithm code to generate matrix elements on 58demand during encapsulation. 59This can be considered later, if it is determined that the space savings (9 * 60512 bytes in memory for ML-KEM-768, for the full matrix, instead of 512 bytes 61for a just-in-time element). 62Since servers will generally destroy the client public key soon after the 63shared secret is computed, these don't stay in memory long, and briefly saving 64~2KB may not to be of much benefit). 65 66The private key format is yet to be clearly standardised, though (to be able to 67fully describe the algorithms) FIPS 203 documents a format that is commonly 68referred to as the "extended" format. 69This is the private key format supported by our key management provider 70interface. 71The IETF voices interest in using the "seed-based" format (the 64-byte (*d*, 72*z*) seed pair from which the key is generated and can be recovered). 73Recovery of the key from the seed (*d*, *z* pair) is supported by the [FIPS 74203] internal deterministic key generation functions, which are used in the 75*keygen* portion of the Known Answer Tests (KATs). 76 77The design therefore caters to both options: The default key generation and KEM 78encapsulation/decapsulation functions operate on "extended keys" in the 79[FIPS 203] format, but it will be possible to use the "seed-based" private key 80format by using the (currently test-only) deterministic *keygen* interface. 81When keys are generated randomly, we don't presently provide a mechanism 82to obtain and store the seed. 83This can be added later if required. 84 85Key generation API 86------------------ 87 88Keys can be generated via the usual **EVP_PKEY_generate()** and 89**EVP_PKEY_Q_keygen()** functions. 90 91An explicit seed can be specified by setting the key generation 92**OSSL_PKEY_PARAM_ML_KEM_SEED** parameter to a 64-byte octet-string 93(concatentation of the **d** and **z** values (32-bytes each) in that order). 94 95KEM API 96------- 97 98**ML-KEM** is meant to be a drop-in replacement for existing KEM algorithms. 99Accessed in the usual way via: 100 101- **EVP_PKEY_encapsulate_init()**, 102- **EVP_PKEY_encapsulate()**, 103- **EVP_PKEY_decapsulate_init()**, and 104- **EVP_PKEY_decapsulate()**. 105 106For the encapsulation operation, a test-only option exists to bypass the random 107number generator (secret random inputs are required for security) and pass in 108a pre-determined 32-byte random value, by setting of the 109**OSSL_KEM_PARAM_IKME** parameter. 110 111Buffers 112------- 113 114The **ML-KEM** key management and KEM providers interface with the underlying 115libcrypto implementation via functions that validate the sizes of all provided 116input/output buffers (encoded keys, ciphertext, shared secrets and seeds) against 117the values expected for the provider's ML-KEM variant (a pointer to the variant 118parameters is stored with each key). 119 120The underlying libcrypto **ML-KEM** APIs are not directly exposed to users, 121only the abstracted key management and KEM **EVP** APIs are public interfaces. 122 123Constant Time Considerations 124---------------------------- 125 126The usual constant time methods are used in the implementation. 127However, we avoid using a *value-barrier* to set the masks that perform 128constant-time *select* between one of two values. 129This avoids a 30-50% performance penalty and is expected to be robust even in 130the face of plausible future compiler optimisations. 131Remainders module the prime are computed via Barret Reduction and the decoding 132and decompression of the decrypted *message* has been tested to not be 133vulnerable to the "clangover" attack in our implementation. 134 135All the libcrypto functions (other than **ML_KEM_KEY** allocation, which 136returns **NULL** on error) return 1 for success or zero on error. 137It should be noted that to avoid chosen-ciphertext attacks, the 138**decapsulate** implementation **must** return success and a synthetic 139shared secret (generated in constant-time whether synthetic or successfully 140decrypted) whenever the input is a well-formed ciphertext. 141 142The only exception to the above is when, unexpectedly, one of the **SHA3** 143functions fails, in that case all hope of constant-time computation is 144lost, but we don't expect such failures to be influenced by the content 145of chosen-ciphertexts, so this should not be an issue). 146 147Nevertheless, even then we fall back on returning a shared secret from the RNG 148along with an error indication only when the key derivation function 149for the synthetic shared secret fails. 150In all other conditions we return success and, as appropriate, either 151the correct shared secret, or the synthetic alternative generated by the KDF. 152 153<!-- Links --> 154 155[FIPS 203]: 156 <https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.203.pdf> 157