ML-KEM (Kyber) Explained: Complete Implementation Guide

ML-KEM (Module-Lattice-Based Key-Encapsulation Mechanism) is the NIST post-quantum cryptography standard for secure key exchange. Published as FIPS 203 in August 2024, ML-KEM is based on the CRYSTALS-Kyber algorithm and provides quantum-resistant key encapsulation to replace vulnerable algorithms like RSA and ECDH.

This guide covers everything developers need to know about ML-KEM: how it works, security levels, implementation strategies, and practical code examples using the Open Quantum Safe library.

What is ML-KEM?

ML-KEM is a key encapsulation mechanism (KEM) that enables two parties to establish a shared secret key over an insecure channel. Unlike key exchange protocols like Diffie-Hellman, KEMs work by having one party encapsulate a secret into a ciphertext that only the holder of the corresponding private key can decapsulate.

How ML-KEM Works

ML-KEM consists of three algorithms:

1. KeyGen(): Generates a public/private key pair
2. Encaps(pk): Takes a public key, outputs a ciphertext and shared secret
3. Decaps(sk, ct): Takes a secret key and ciphertext, outputs the shared secret

The security of ML-KEM is based on the Module Learning With Errors (MLWE) problem, a mathematical problem believed to be hard for both classical and quantum computers to solve.

Security Levels and Parameters

ML-KEM comes in three security levels, each offering different trade-offs between security strength and performance:

Implementation with liboqs

The Open Quantum Safe (OQS) project provides the most widely-used open-source implementation of ML-KEM through the liboqs library. Here's how to get started:

Installation

# Ubuntu/Debian prerequisites
sudo apt install cmake gcc ninja-build libssl-dev

# Clone and build liboqs
git clone https://github.com/open-quantum-safe/liboqs.git
cd liboqs && mkdir build && cd build
cmake -GNinja -DCMAKE_INSTALL_PREFIX=/usr/local ..
ninja && sudo ninja install

C Implementation Example

#include <oqs/oqs.h>
#include <stdio.h>
#include <string.h>

int main() {
    // Initialize ML-KEM-768
    OQS_KEM *kem = OQS_KEM_new(OQS_KEM_alg_ml_kem_768);
    if (kem == NULL) {
        printf("ML-KEM-768 not available\n");
        return 1;
    }

    // Allocate memory
    uint8_t *public_key = malloc(kem->length_public_key);
    uint8_t *secret_key = malloc(kem->length_secret_key);
    uint8_t *ciphertext = malloc(kem->length_ciphertext);
    uint8_t *shared_secret_enc = malloc(kem->length_shared_secret);
    uint8_t *shared_secret_dec = malloc(kem->length_shared_secret);

    // Generate key pair (recipient)
    OQS_KEM_keypair(kem, public_key, secret_key);

    // Encapsulate (sender creates shared secret)
    OQS_KEM_encaps(kem, ciphertext, shared_secret_enc, public_key);

    // Decapsulate (recipient recovers shared secret)
    OQS_KEM_decaps(kem, shared_secret_dec, ciphertext, secret_key);

    // Verify shared secrets match
    if (memcmp(shared_secret_enc, shared_secret_dec,
               kem->length_shared_secret) == 0) {
        printf("Key exchange successful!\n");
    }

    // Clean up
    OQS_KEM_free(kem);
    free(public_key);
    free(secret_key);
    free(ciphertext);
    free(shared_secret_enc);
    free(shared_secret_dec);

    return 0;
}

Python Implementation

import oqs

# Initialize ML-KEM-768
kem = oqs.KeyEncapsulation("ML-KEM-768")

# Recipient generates key pair
public_key = kem.generate_keypair()
print(f"Public key size: {len(public_key)} bytes")

# Sender encapsulates a shared secret
ciphertext, shared_secret_sender = kem.encap_secret(public_key)
print(f"Ciphertext size: {len(ciphertext)} bytes")

# Recipient decapsulates to get the same shared secret
shared_secret_recipient = kem.decap_secret(ciphertext)

# Verify they match
assert shared_secret_sender == shared_secret_recipient
print("Key exchange successful!")
print(f"Shared secret: {shared_secret_sender.hex()[:32]}...")

TLS Integration

For TLS connections, use the oqs-provider with OpenSSL 3.x to enable post-quantum key exchange:

# Install oqs-provider
git clone https://github.com/open-quantum-safe/oqs-provider.git
cd oqs-provider && mkdir build && cd build
cmake -GNinja ..
ninja && sudo ninja install

# Configure OpenSSL to use the provider
# Add to openssl.cnf:
# [openssl_init]
# providers = provider_sect
# [provider_sect]
# oqsprovider = oqsprovider_sect
# [oqsprovider_sect]
# activate = 1

# Test with hybrid key exchange (X25519 + ML-KEM-768)
openssl s_client -groups x25519_mlkem768 -connect example.com:443

Implementation Best Practices

Security Considerations

• Key Generation: Use cryptographically secure random number generators. ML-KEM requires high-quality entropy.
• Memory Handling: Zero out secret keys and shared secrets after use to prevent memory disclosure attacks.
• Side-Channel Protection: Production implementations should include constant-time operations to prevent timing attacks.
• Hybrid Approach: Combine ML-KEM with classical algorithms (e.g., X25519) during the transition period.

Performance Optimization

ML-KEM is comparable in speed to classical algorithms, making it suitable for high-throughput applications. The main overhead is increased key and ciphertext sizes.

Migration Strategy

Follow these steps to migrate your applications to ML-KEM:

1. Inventory: Identify all systems using RSA, DH, or ECDH for key exchange
2. Test Environment: Deploy ML-KEM in a test environment using liboqs
3. Hybrid Mode: Implement hybrid key exchange (classical + ML-KEM) first
4. Performance Testing: Benchmark key sizes and operation times
5. Gradual Rollout: Enable ML-KEM for internal systems before external-facing services
6. Monitor: Track success rates and performance metrics