C 801: ML_KEM Key Agreement (10 pts extra)

What You Need

Any machine with Python 3. I used Google Colab.

Purpose

To learn how ML-KEM works, a quantum-resistant key agreement protocol specified in FIPS 203 and approved by NIST in NIST SP 800-131Ar3 ipd in October 2024.

Key-Encapsulation Mechanisms (KEM) (from FIPS 203)

A KEM is a cryptographic scheme that, under certain conditions, can be used to establish a shared secret key between two communicating parties. This shared secret key can then be used for symmetric-key cryptography.

A KEM consists of three algorithms and a collection of parameter sets. The three algorithms are:

Here are the steps:
  1. Alice runs KeyGen to generate a (public) encapsulation key and a (private) decapsulation key. Alice sends the public key to Bob.
  2. Bob runs Encaps algorithm, which produces Bob’s copy of the shared secret along with an associated ciphertext. Bob sends the ciphertext to Alice.
  3. Alice runs the Decaps algorithm using her (private) decapsulation key and the ciphertext. This produces Alice’s copy of the shared secret.

Establishing a Shared Secret

In Google Colab, execute these commands. 
!pip install kyber-py
from kyber_py.ml_kem import ML_KEM_512

# 1. Alice generates a key pair
encap_key, decap_key = ML_KEM_512.keygen()

print("\nAlice's (public) encapsulation key has length=", len(encap_key), encap_key.hex()[:20], "...")
print("Alice's (private) decapsulation key has length=", len(decap_key), decap_key.hex()[:20], "...")

# 2. Bob calculates the shared secret and a ciphertext
shared_secret_bob, ciphertext = ML_KEM_512.encaps(encap_key)

print("\nBob's shared secret has length=", len(shared_secret_bob), shared_secret_bob.hex()[:20], "...")
print("Bob's ciphertext has length=", len(ciphertext), ciphertext.hex()[:20], "...")

# 3. Alice calculates the shared secret
shared_secret_alice = ML_KEM_512.decaps(decap_key, ciphertext)

print("\nAlice's shared secret has length=", len(shared_secret_alice), shared_secret_alice.hex()[:20], "...")
As shown below, Alice and Bob end up with the same shared secret:

Generating an AES Key from the Shared Secret

In Google Colab, execute these commands. 
!pip install pycryptodome
import hashlib
from Crypto.Cipher import AES

aes_key = hashlib.pbkdf2_hmac('sha256', shared_secret_alice, b"", 1024, 16)
print("\nAES Key: length=", len(aes_key), aes_key.hex())
You see a key that is 16 bytes long, as shown below.

Encrypting Text

Execute these commands, as shown below: 
cleartext = b'Using Post-Quantum Cryptography!'
iv = b"0000111122223333"
cipher = AES.new(aes_key, AES.MODE_GCM, nonce=iv)
ciphertext = cipher.encrypt(cleartext)
print("Ciphertext: ", ciphertext.hex())
THe ciphetext is random-appearing hex bytes, as shown below.

Decrypting Text

Execute these commands, as shown below: 
iv = b"0000111122223333"
cipher = AES.new(aes_key, AES.MODE_GCM, nonce=iv)
decrtext = cipher.decrypt(ciphertext)
print("Decrypted text: ", decrtext)
The cleartext message is recovered, as shown below.

C 801.1: Using a Fixed Seed (10 pts)

To generate a predictable flag, execute this command, which specifies a fixed seed for the pseudo-random number generator: 
ML_KEM_512.set_drbg_seed(b'0'*48)
Now generate a shared secret, as shown above. Your shared secret should begin with 888.

Generate an AES key, as shown above. Your AES key should begin with cc.

Decrypt this ciphertext to find the flag: 

iv = b"0000000011111111"
ciphertext = bytes.fromhex("c6a407ba2b632a7644c706d1b73277404b23801955851ab6e289afd24d20a7eb")

Sources

ML-KEM (formerly known as Kyber)
ML-KEM / CRYSTALS-Kyber Python Implementation
NIST Special Publication 800 NIST SP 800-131Ar3 ipd Transitioning the Use of Cryptographic Algorithms and Key Lengths Initial Public Draft
FIPS 203 Module-Lattice-Based Key-Encapsulation Mechanism Standard

Posted 4-16-25