Testing

Post-Quantum Cryptography Migration Testing: CRYSTALS-Kyber and Dilithium

HelpMeTest

HelpMeTest

— 7 min read
Post-Quantum Cryptography Migration Testing: CRYSTALS-Kyber and Dilithium

NIST finalized its post-quantum cryptography standards in 2024: FIPS 203 (ML-KEM, based on CRYSTALS-Kyber), FIPS 204 (ML-DSA, based on CRYSTALS-Dilithium), and FIPS 205 (SLH-DSA, based on SPHINCS+). If you're running any system that encrypts data with RSA or ECDH, or signs with ECDSA, you have migration work ahead. The question isn't whether to migrate — it's how to test the migration without breaking production.

This post covers the testing strategy for PQC migrations: how to validate Kyber KEM implementations, test Dilithium signature correctness, run hybrid classical+PQC tests, and benchmark performance regressions before they hit your users.

What You're Actually Testing

PQC migration testing splits into four concerns:

  1. Correctness — Does the implementation produce valid ciphertexts/signatures that verify correctly?
  2. Interoperability — Does your Kyber implementation talk correctly to other FIPS 203-compliant implementations?
  3. Hybrid compatibility — Does your hybrid X25519+Kyber or ECDSA+Dilithium work end-to-end?
  4. Performance — What's the latency/throughput regression versus the classical algorithms you're replacing?

The reference implementation for all of this is liboqs, the Open Quantum Safe project's C library. It ships Python bindings via liboqs-python.

Setting Up the Test Environment

Install liboqs and its Python bindings:

# Build liboqs from source (required for FIPS 203/204 compliant builds)
git clone --depth 1 https://github.com/open-quantum-safe/liboqs.git
cd liboqs
mkdir build && cd build
cmake -GNinja \
  -DOQS_USE_OPENSSL=ON \
  -DBUILD_SHARED_LIBS=ON \
  -DOQS_DIST_BUILD=ON \
  ..
ninja
sudo ninja install

# Install Python bindings
pip install liboqs-python

Verify the installation exposes the FIPS 203 algorithms:

import oqs

# Should include ML-KEM-512, ML-KEM-768, ML-KEM-1024
kems = oqs.get_enabled_kem_mechanisms()
assert "Kyber512" in kems or "ML-KEM-512" in kems, "FIPS 203 KEM not available"

sigs = oqs.get_enabled_sig_mechanisms()
assert "Dilithium2" in sigs or "ML-DSA-44" in sigs, "FIPS 204 DSA not available"

Testing Kyber KEM (FIPS 203 / ML-KEM)

Kyber is a key encapsulation mechanism. The basic flow: Alice generates a keypair, Bob encapsulates a shared secret using Alice's public key, Alice decapsulates using her private key. Both end up with the same shared secret.

Basic Correctness Test

import oqs
import pytest

@pytest.fixture(params=["Kyber512", "Kyber768", "Kyber1024"])
def kem_variant(request):
    return request.param

def test_kyber_kem_roundtrip(kem_variant):
    """Encapsulated secret must match decapsulated secret."""
    with oqs.KeyEncapsulation(kem_variant) as kem_alice:
        public_key = kem_alice.generate_keypair()

        with oqs.KeyEncapsulation(kem_variant) as kem_bob:
            ciphertext, shared_secret_bob = kem_bob.encap_secret(public_key)

        shared_secret_alice = kem_alice.decap_secret(ciphertext)

    assert shared_secret_alice == shared_secret_bob, (
        f"Shared secret mismatch for {kem_variant}"
    )
    assert len(shared_secret_alice) == 32, "Shared secret must be 32 bytes"

def test_kyber_wrong_private_key_produces_different_secret(kem_variant):
    """Decapsulation with wrong key must not yield the correct secret."""
    with oqs.KeyEncapsulation(kem_variant) as kem_alice:
        public_key = kem_alice.generate_keypair()

    with oqs.KeyEncapsulation(kem_variant) as kem_bob:
        ciphertext, shared_secret_bob = kem_bob.encap_secret(public_key)

    # Different key — decapsulation should return a pseudorandom garbage value
    # (Kyber is designed to be IND-CCA2: wrong key gives random-looking output)
    with oqs.KeyEncapsulation(kem_variant) as kem_eve:
        kem_eve.generate_keypair()
        shared_secret_eve = kem_eve.decap_secret(ciphertext)

    assert shared_secret_eve != shared_secret_bob, (
        "Wrong private key must not recover correct shared secret"
    )

def test_kyber_ciphertext_tampering_produces_different_secret(kem_variant):
    """Bit-flipped ciphertext must not yield original shared secret (IND-CCA2)."""
    with oqs.KeyEncapsulation(kem_variant) as kem:
        public_key = kem.generate_keypair()
        ciphertext, original_secret = kem.encap_secret(public_key)

        # Flip a bit in the ciphertext
        tampered = bytearray(ciphertext)
        tampered[len(tampered) // 2] ^= 0x01
        recovered = kem.decap_secret(bytes(tampered))

    assert recovered != original_secret

Known-Answer Tests (KAT)

NIST publishes KAT vectors for all PQC standards. Always run against them:

import json

def load_kat_vectors(path: str) -> list[dict]:
    with open(path) as f:
        return json.load(f)

def test_kyber768_kat_vectors():
    """Validate against NIST KAT vectors for ML-KEM-768."""
    vectors = load_kat_vectors("tests/kat/ml-kem-768.json")

    for vec in vectors[:10]:  # Run first 10 for CI speed
        pk = bytes.fromhex(vec["pk"])
        sk = bytes.fromhex(vec["sk"])
        ct = bytes.fromhex(vec["ct"])
        expected_ss = bytes.fromhex(vec["ss"])

        with oqs.KeyEncapsulation("Kyber768", secret_key=sk) as kem:
            recovered_ss = kem.decap_secret(ct)

        assert recovered_ss == expected_ss, (
            f"KAT failure: expected {expected_ss.hex()}, got {recovered_ss.hex()}"
        )

You can obtain KAT vectors from the NIST PQC submission packages.

Testing Dilithium Signatures (FIPS 204 / ML-DSA)

Dilithium is a lattice-based signature scheme. Testing it requires validating sign/verify correctness, rejection of tampered signatures, and cross-implementation compatibility.

import oqs
import pytest

@pytest.fixture(params=["Dilithium2", "Dilithium3", "Dilithium5"])
def sig_variant(request):
    return request.param

def test_dilithium_sign_verify_roundtrip(sig_variant):
    message = b"The quick brown fox jumps over the lazy dog"

    with oqs.Signature(sig_variant) as signer:
        public_key = signer.generate_keypair()
        signature = signer.sign(message)

    with oqs.Signature(sig_variant) as verifier:
        is_valid = verifier.verify(message, signature, public_key)

    assert is_valid, f"Valid signature rejected for {sig_variant}"

def test_dilithium_rejects_tampered_message(sig_variant):
    message = b"Original message"
    tampered = b"Tampered message"

    with oqs.Signature(sig_variant) as signer:
        public_key = signer.generate_keypair()
        signature = signer.sign(message)

    with oqs.Signature(sig_variant) as verifier:
        is_valid = verifier.verify(tampered, signature, public_key)

    assert not is_valid

def test_dilithium_rejects_tampered_signature(sig_variant):
    message = b"Test message"

    with oqs.Signature(sig_variant) as signer:
        public_key = signer.generate_keypair()
        signature = signer.sign(message)

    tampered_sig = bytearray(signature)
    tampered_sig[0] ^= 0xFF
    tampered_sig[-1] ^= 0xFF

    with oqs.Signature(sig_variant) as verifier:
        is_valid = verifier.verify(message, bytes(tampered_sig), public_key)

    assert not is_valid

def test_dilithium_signature_is_deterministic(sig_variant):
    """ML-DSA (Dilithium) produces deterministic signatures."""
    message = b"Determinism test"

    with oqs.Signature(sig_variant) as signer:
        public_key = signer.generate_keypair()
        sig1 = signer.sign(message)
        sig2 = signer.sign(message)

    # Dilithium uses randomized signing — sig1 may differ from sig2
    # but BOTH must verify correctly
    with oqs.Signature(sig_variant) as verifier:
        assert verifier.verify(message, sig1, public_key)
        assert verifier.verify(message, sig2, public_key)

Note: Dilithium supports both randomized and deterministic signing modes. FIPS 204 specifies ML-DSA with randomized signing by default. Your tests should document which mode is in use.

Hybrid Classical + PQC Testing

During migration, you'll likely run hybrid schemes: X25519+Kyber for key exchange, or ECDSA+Dilithium for signatures. This is the approach recommended by IETF (see draft-ietf-tls-hybrid-design) and already deployed by Google and Cloudflare.

Testing Hybrid KEM

from cryptography.hazmat.primitives.asymmetric.x25519 import X25519PrivateKey
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from cryptography.hazmat.primitives import hashes
import oqs
import os

def hybrid_kem_combine(classical_secret: bytes, pqc_secret: bytes) -> bytes:
    """Combine X25519 and Kyber shared secrets via HKDF."""
    combined_input = classical_secret + pqc_secret
    hkdf = HKDF(
        algorithm=hashes.SHA256(),
        length=32,
        salt=None,
        info=b"hybrid-kem-v1",
    )
    return hkdf.derive(combined_input)

def test_hybrid_x25519_kyber_roundtrip():
    # Classical: X25519
    alice_classical = X25519PrivateKey.generate()
    bob_classical = X25519PrivateKey.generate()

    alice_classical_pub = alice_classical.public_key()
    bob_classical_pub = bob_classical.public_key()

    classical_secret_alice = alice_classical.exchange(bob_classical_pub)
    classical_secret_bob = bob_classical.exchange(alice_classical_pub)
    assert classical_secret_alice == classical_secret_bob

    # PQC: Kyber768
    with oqs.KeyEncapsulation("Kyber768") as kem_alice:
        kyber_pub = kem_alice.generate_keypair()

        with oqs.KeyEncapsulation("Kyber768") as kem_bob:
            ct, pqc_secret_bob = kem_bob.encap_secret(kyber_pub)

        pqc_secret_alice = kem_alice.decap_secret(ct)

    # Combine
    final_alice = hybrid_kem_combine(classical_secret_alice, pqc_secret_alice)
    final_bob = hybrid_kem_combine(classical_secret_bob, pqc_secret_bob)

    assert final_alice == final_bob
    assert len(final_alice) == 32

Performance Benchmarking

PQC algorithms have different performance profiles. ML-KEM-768 is comparable to X25519 for keygen and encapsulation, but larger ciphertexts (1088 bytes vs 32 bytes for X25519) can matter for high-throughput systems.

import time
import statistics
import oqs

def benchmark_kem(algorithm: str, iterations: int = 1000) -> dict:
    keygen_times = []
    encap_times = []
    decap_times = []

    for _ in range(iterations):
        with oqs.KeyEncapsulation(algorithm) as kem:
            t0 = time.perf_counter()
            pk = kem.generate_keypair()
            keygen_times.append(time.perf_counter() - t0)

            t1 = time.perf_counter()
            ct, ss = kem.encap_secret(pk)
            encap_times.append(time.perf_counter() - t1)

            t2 = time.perf_counter()
            kem.decap_secret(ct)
            decap_times.append(time.perf_counter() - t2)

    return {
        "algorithm": algorithm,
        "keygen_ms_p50": statistics.median(keygen_times) * 1000,
        "keygen_ms_p99": sorted(keygen_times)[int(iterations * 0.99)] * 1000,
        "encap_ms_p50": statistics.median(encap_times) * 1000,
        "decap_ms_p50": statistics.median(decap_times) * 1000,
        "ciphertext_bytes": len(ct),
        "public_key_bytes": len(pk),
    }

def test_kyber768_performance_regression():
    """Fail if Kyber768 exceeds 2ms median for any operation."""
    results = benchmark_kem("Kyber768", iterations=500)

    assert results["keygen_ms_p50"] < 2.0, (
        f"Keygen too slow: {results['keygen_ms_p50']:.3f}ms"
    )
    assert results["encap_ms_p50"] < 2.0, (
        f"Encap too slow: {results['encap_ms_p50']:.3f}ms"
    )
    assert results["decap_ms_p50"] < 2.0, (
        f"Decap too slow: {results['decap_ms_p50']:.3f}ms"
    )

Run this in CI with baseline thresholds committed to the repo. When you upgrade liboqs versions, catch performance regressions before they ship.

Migration Regression Testing

The highest-risk part of a PQC migration is the transition period, where old clients use classical crypto and new clients use PQC or hybrid. You need to test both paths simultaneously.

import pytest

@pytest.mark.parametrize("old_algo,new_algo", [
    ("P-256", "Kyber768"),       # ECDH → Kyber
    ("RSA-2048", "Kyber1024"),   # RSA KEM → Kyber
])
def test_no_regression_in_classical_path_during_migration(old_algo, new_algo):
    """Classical key exchange must still work while PQC is being deployed."""
    # This is a schema test — replace with your actual classical KEM calls
    assert old_algo != new_algo  # Sanity check

def test_serialization_round_trip_kyber768():
    """Public keys and ciphertexts must survive serialization."""
    import base64

    with oqs.KeyEncapsulation("Kyber768") as kem:
        pk = kem.generate_keypair()
        pk_b64 = base64.b64encode(pk).decode()

        # Simulate storing and retrieving from a database
        pk_restored = base64.b64decode(pk_b64)

        ct, ss_original = kem.encap_secret(pk_restored)
        ss_recovered = kem.decap_secret(ct)

    assert ss_original == ss_recovered

C Integration Testing with liboqs

If you're integrating at the C level (common for embedded or performance-critical paths):

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

void test_kyber768_roundtrip(void) {
    OQS_KEM *kem = OQS_KEM_new(OQS_KEM_alg_kyber_768);
    assert(kem != NULL);

    uint8_t *pk = malloc(kem->length_public_key);
    uint8_t *sk = malloc(kem->length_secret_key);
    uint8_t *ct = malloc(kem->length_ciphertext);
    uint8_t *ss_enc = malloc(kem->length_shared_secret);
    uint8_t *ss_dec = malloc(kem->length_shared_secret);

    assert(OQS_KEM_keypair(kem, pk, sk) == OQS_SUCCESS);
    assert(OQS_KEM_encaps(kem, ct, ss_enc, pk) == OQS_SUCCESS);
    assert(OQS_KEM_decaps(kem, ss_dec, ct, sk) == OQS_SUCCESS);

    assert(memcmp(ss_enc, ss_dec, kem->length_shared_secret) == 0);
    printf("Kyber768 C roundtrip: PASS (shared secret length: %zu)\n",
           kem->length_shared_secret);

    free(pk); free(sk); free(ct); free(ss_enc); free(ss_dec);
    OQS_KEM_free(kem);
}

int main(void) {
    OQS_init();
    test_kyber768_roundtrip();
    OQS_destroy();
    return 0;
}

Compile with: gcc -o test_pqc test_pqc.c -loqs -lssl -lcrypto

What to Prioritize First

If you're starting a PQC migration today:

  1. Inventory your key exchange surfaces — TLS handshakes, SSH sessions, encrypted storage keys. These need Kyber first.
  2. Inventory your signature surfaces — code signing, JWT issuance, certificate signing. These need Dilithium.
  3. Start with hybrid — X25519+Kyber for TLS, ECDSA+Dilithium for code signing. You get classical security today and PQC security when needed.
  4. Run KAT vectors in CI — this is non-negotiable. A PQC implementation that doesn't pass NIST KAT vectors is not compliant.
  5. Benchmark against your SLA — Dilithium5 signatures are ~3KB. If you sign JWTs at high volume, measure the overhead.

The NIST standards are final. The algorithms are stable. The liboqs implementation is production-ready for testing. Start building your test suite now — the window for migration testing before regulatory requirements land is narrowing.

Read more

Start now free