ML-KEM-768
Purpose
When communicating with another party, you often need a way to establish a shared secret (symmetric) key without having an existing secure channel. An algorithm that allows this over a public (insecure) channel is called a key-establishment scheme.
Key encapsulation mechanisms (KEMs) are one type of key-establishment scheme, and they're the interface of choice for post-quantum algorithms, which protect against cryptographically relevant quantum computers (CRQCs). Even without a CRQC today, an adversary can capture encrypted data that relies on traditional key-establishment algorithms ready for decryption when such a CRQC becomes available (a store now, decrypt later attack).
Unlike a traditional key exchange, the sender's key pair isn't involved, a ciphertext needs to be sent to the recipient, and the shared secret is uniformly random. From the sending side, the algorithm is randomised rather than deterministic (the sender doesn't choose the shared secret).
Here is how it works when doing one trip of communication (real protocols often do multiple trips):
Key generation: the recipient generates a key pair and shares the public key with the sender.
Encapsulation: the sender uses the recipient's public key to generate a shared secret and an associated ciphertext. This ciphertext is sent to the recipient.
Decapsulation: the recipient uses the ciphertext and their private key to compute the same shared secret.
ML-KEM-768 is the middle (192-bit) security strength variant of ML-KEM, which is one of the algorithms standardised by NIST as part of the Post-Quantum Cryptography (PQC) Standardization (competition) process. This variant provides protection against cryptanalysis advancements compared to ML-KEM-512 whilst being lighter (smaller parameters/marginally faster) than ML-KEM-1024. All variants are faster than traditional key exchange algorithms (e.g., X25519) but have larger parameters.
Private keys MUST NOT be shared. They MUST remain secret and be protected from modification.
Consider using X-Wing instead, which uses X25519 + ML-KEM-768 to provide classical security still if ML-KEM-768 is unexpectedly broken. Whilst this is arguably unnecessary and has some drawbacks, it is a popular/recommended approach.
However, X-Wing isn't suitable in all cases, like when doing protocols requiring plausible deniability or censorship-resistance. In such cases, one may need to create their own hybrid KEM.
Usage
GenerateKeyPair
Fills a span with a randomly generated private key and another span with the associated public key.
Exceptions
publicKey has a length not equal to PublicKeySize.
privateKey has a length not equal to PrivateKeySize.
Error generating key pair.
GenerateKeyPair
Fills a span with a private key generated using a random seed and another span with the associated public key.
Exceptions
publicKey has a length not equal to PublicKeySize.
privateKey has a length not equal to PrivateKeySize.
seed has a length not equal to SeedSize.
Error generating key pair from seed.
Encapsulate
Fills a span with the computed shared secret and another span with the ciphertext to send to the recipient based on the recipient's public key.
Exceptions
sharedSecret has a length not equal to SharedSecretSize.
ciphertext has a length not equal to CiphertextSize.
recipientPublicKey has a length not equal to PublicKeySize.
Invalid public key.
Decapsulate
Fills a span with the computed shared secret based on the recipient's private key and the ciphertext the recipient was sent.
Exceptions
sharedSecret has a length not equal to SharedSecretSize.
ciphertext has a length not equal to CiphertextSize.
recipientPrivateKey has a length not equal to PrivateKeySize.
Error performing decapsulation.
Constants
These are used for validation and/or save you defining your own constants.
Notes
A KEM does NOT provide authentication of either party. It's important to verify that any public keys and ciphertexts came from who you expect, which is typically done via digital signatures. For example, a certificate ties the identity of the key pair owner to the static public key and proves that they possess the corresponding private key (via certificate authority checks).
Key confirmation can also be used for proof of possession of the private key corresponding to the public key, which works with static and ephemeral key pairs. Successful use of the shared secret when decrypting an AEAD ciphertext is one form. Another is having one or both parties exchange and verify MAC tags over data involved in the key establishment, which is more complicated.
One would expect that different ciphertexts/public keys produce different shared secrets. However, an adversary that can control a private key can cause the same shared secret to be generated.
Technically, only protocols where the private key cannot be fully trusted (e.g., it's received from a third party or sometimes revealed) are at risk. However, it's best practice to hash ciphertexts/public keys alongside shared secrets during key derivation, which mitigates this.
Alternatively, one can store a random 256-bit seed as the private key and use a KDF to expand it to 512 bits for ML-KEM seeded key generation to derive the large private key, as done in X-Wing. This prevents a malformed private key because the attacker can't control the key derivation.
Not all uses of traditional key exchange can be replaced in a straightforward manner by KEMs. For example, KEMs don't provide non-interactive key exchange (NIKE) functionality (where both users can compute the shared secret without interaction if they know each other's public key).
KEMs are inherently synchronous and interactive because of the ciphertext. This prevents non-interactive authentication via static public keys, which avoids digital signatures. In an offline context, the best you can do is encapsulate to the recipient's static public key (no sender keys can be involved because that would require an interactive protocol).
ML-KEM public keys and ciphertexts are distinguishable from random (e.g., someone can tell that cryptography is being used). Therefore, it's not suitable for protocols requiring plausible deniability or censorship-resistance without using a scheme such as Kemeleon, which is not implemented in libsodium.
A collision-resistant KDF should be used to derive keys from shared secrets. There are two main approaches here:
For each KEM trip of communication, you can use the shared secret as the KDF key and the public key, ciphertext, and domain separation concatenated together as the message. Each derived key can then be concatenated together and fed to a KDF again to combine the keys and produce usable key material.
For all KEM trips of communication, you can concatenate the shared secrets for use as the KDF key and concatenate all public keys, ciphertexts, and some domain separation for the message.
There are multiple KDF designs, so the above may need to be adjusted. For example, hashing (with a modern hash function) shared secrets concatenated together to derive a KDF key. Alternatively, using an empty KDF key or modern hash function and feeding everything in as the message (shared secrets first).
Static (long-term) as well as ephemeral public keys can be used safely. Ephemeral public keys help provide forward secrecy, which protects prior communications in the event of a key compromise.
ML-KEM has a tiny probability of decapsulation failure. Even if everything is done honestly/correctly, both parties may not derive the same shared secret.
However, practically speaking, this will never happen. In other words, this isn't something to worry about.
If an attacker substitutes a public key or modifies/replaces a ciphertext, the derived shared secret will be different between the two parties, which will cause an error in any properly designed protocol.
However, if an attacker can substitute the stored copy of the public key used for encapsulation (by the sender) and decapsulation (by the recipient), they can introduce a malicious public key. This isn't possible if the private key is stored securely and protected against modification (e.g., encrypted with an AEAD scheme).
Encapsulation can error due to a check that the integers encoded in the public key are in the valid range. This sort of check is not performed for decapsulation.
Whilst the shared secret is 256 bits long, its security strength is actually 192 bits due to the security level of ML-KEM-768.
If you read about post-quantum algorithms, you may see the terms 'encapsulation key' and 'decapsulation key'. These mean 'public key' and 'private key' but are specific to KEMs.
Non-Interactive Pattern
This is a one-way pattern, so no back and forth between the sender and recipient is required. It's appropriate for offline applications (e.g., a file encryption program).
The recipient does not know who sent the message, and only the recipient can decrypt the message once the shared secret is erased from memory. This is the post-quantum equivalent of the N pattern. The security properties are discussed here.
It's not possible to get sender authentication in a non-interactive way using only KEMs. Therefore, this is the only non-interactive pattern.
The sender encapsulates to the recipient's static public key. They use the shared secret as input keying material to a KDF. The output keying material is used as the key to encrypt a message using an AEAD.
The KEM ciphertext is sent alongside the AEAD ciphertext to the recipient.
The recipient decapsulates using their static private key and the ciphertext from the sender. They use the shared secret to derive the same key and decrypt the AEAD ciphertext.
Interactive Patterns
These are two-way patterns, so back and forth between the sender and recipient is required. They are appropriate for online applications and can provide better security properties than the one-way patterns.
Bilateral Authenticated Key Establishment
Both parties are authenticated using static KEM key pairs (e.g., associated with certificates, with each other's certificates exchanged and verified before the below). This achieves weak forward secrecy due to ephemeral key pair involvement.
The sender generates an ephemeral key pair. They then encapsulate to the recipient's static public key. They send the ephemeral public key and static KEM ciphertext to the recipient.
The recipient encapsulates to the sender's static public key and encapsulates to the sender's ephemeral public key, sending both KEM ciphertexts to the sender. They also decapsulate the static KEM ciphertext from the sender.
The sender decapsulates the static and ephemeral KEM ciphertexts from the recipient.
Both parties now have three shared secrets - two static (each other) and one ephemeral (recipient to sender). These are combined using a KDF, with the output keying material used with an AEAD.
Last updated