Notebook 08 — Hybrid KEM: classical + post-quantum

Why hybrid? ML-KEM has had less cryptanalytic attention than X25519. Until PQC gets more battle-testing, deployed protocols (TLS 1.3 draft-ietf-tls-hybrid-design, SSH, IKEv2) combine both: the hybrid key is secure as long as either scheme is.

import hashlib
from cryptography.hazmat.primitives.asymmetric.x25519 import X25519PrivateKey
from pqc_edu.ml_kem import ml_kem_keygen, ml_kem_encaps, ml_kem_decaps
from pqc_edu.params import ML_KEM_768

Protocol

• Alice: generates (x25519_sk_A, x25519_pk_A) and (ek, dk). Sends (x25519_pk_A, ek).

• Bob: generates (x25519_sk_B, x25519_pk_B). Computes ss_x = x25519(sk_B, pk_A) and (ss_mlkem, ct) = ml_kem_encaps(ek). Sends (x25519_pk_B, ct).

• Both derive K = SHAKE256(ss_x || ss_mlkem || transcript, 32).

# Alice: classical + PQ keys
alice_x25519 = X25519PrivateKey.generate()
alice_x25519_pk = alice_x25519.public_key().public_bytes_raw()
ek, dk = ml_kem_keygen(ML_KEM_768)

# Bob: classical keypair + encapsulate to Alice's ek
bob_x25519 = X25519PrivateKey.generate()
bob_x25519_pk = bob_x25519.public_key().public_bytes_raw()
ss_x_bob = bob_x25519.exchange(
    __import__('cryptography').hazmat.primitives.asymmetric.x25519.X25519PublicKey
    .from_public_bytes(alice_x25519_pk)
)
ss_mlkem_bob, ct = ml_kem_encaps(ML_KEM_768, ek)

# Alice: completes both halves
from cryptography.hazmat.primitives.asymmetric.x25519 import X25519PublicKey
ss_x_alice = alice_x25519.exchange(X25519PublicKey.from_public_bytes(bob_x25519_pk))
ss_mlkem_alice = ml_kem_decaps(ML_KEM_768, dk, ct)

transcript = alice_x25519_pk + ek + bob_x25519_pk + ct

def derive(ss_x, ss_mlkem):
    h = hashlib.shake_256()
    h.update(ss_x + ss_mlkem + transcript)
    return h.digest(32)

K_alice = derive(ss_x_alice, ss_mlkem_alice)
K_bob = derive(ss_x_bob, ss_mlkem_bob)
print('X25519 halves match      :', ss_x_alice == ss_x_bob)
print('ML-KEM halves match      :', ss_mlkem_alice == ss_mlkem_bob)
print('final hybrid K match     :', K_alice == K_bob)
print('K (hex) =', K_alice.hex())

X25519 halves match      : True
ML-KEM halves match      : True
final hybrid K match     : True
K (hex) = eb309188079edb0bc92305f90ba044d165446631d0fdfb821f363dedc984a3c8

Security property

An adversary needs to break both X25519 and ML-KEM to recover K. Quantum breaks X25519 but (conjecturally) not ML-KEM. Classical cryptanalysis might eventually break ML-KEM but (very likely) not X25519. Hybrid survives either world.

Tamper test

Flip one bit of the ML-KEM ciphertext. Because of the FO transform’s implicit rejection, Alice derives a pseudo-random ss_mlkem — not an error — so her hybrid key is garbage but she can’t tell it was tampered. In a real protocol, an authentication tag over the transcript catches this.

ct_tampered = bytearray(ct); ct_tampered[0] ^= 0x01
ss_mlkem_alice_bad = ml_kem_decaps(ML_KEM_768, dk, bytes(ct_tampered))
K_alice_bad = derive(ss_x_alice, ss_mlkem_alice_bad)
print('ss_mlkem changed:', ss_mlkem_alice_bad != ss_mlkem_alice)
print('hybrid K now differs from Bob\'s:', K_alice_bad != K_bob)

ss_mlkem changed: True
hybrid K now differs from Bob's: True