Chapter 7: PQC Testing and Validation¶
7.1 Overview of PQC Testing¶
Testing PQC implementations requires multiple complementary approaches:
-
Known Answer Tests (KAT): Verify functional correctness against reference vectors.
-
NIST ACVP: Automated Cryptographic Validation Protocol for FIPS validation.
-
Interoperability testing: Cross-implementation compatibility.
-
Performance benchmarking: Cycle counts, latency, throughput.
-
Fuzzing and memory safety: Security testing for implementation bugs.
-
Formal verification: Mathematical proof of correctness.
-
Side-channel testing: Physical security validation (Chapter 8).
7.2 Known Answer Tests (KAT)¶
KAT vectors are the primary method for verifying algorithm implementations against NIST reference implementations.
7.2.1 KAT Format¶
# NIST KAT file: PQCkemKAT_2400.rsp (ML-KEM-768)
# Each test case contains:
count = 0
seed = 061550234D158C5EC95595FE04EF7A25767F2E24CC2BC479D09D86DC9ABCFDE7056A8C266F9EF97ED08541DBD2E1FFA1
pk = ... (1184 hex bytes = 2368 hex chars)
sk = ... (2400 hex bytes = 4800 hex chars)
ct = ... (1088 hex bytes = 2176 hex chars)
ss = ... (32 hex bytes = 64 hex chars)
count = 1
seed = ...
pk = ...
# etc.
7.2.2 Running KAT Tests¶
# Clone PQClean and run KAT tests
git clone https://github.com/PQClean/PQClean.git
cd PQClean
# Build and run ML-KEM-768 KAT test
cd crypto_kem/ml-kem-768/clean
make kat
./kat_ml-kem-768_clean
# Expected output:
# Generating KAT for ML-KEM-768/CLEAN
# OK! Tests passed for count = 0 through 99
# Run all NIST standard algorithm KATs
cd PQClean
python3 test/test_pqclean.py --kem ml-kem-768 ml-kem-512 ml-kem-1024
python3 test/test_pqclean.py --sign ml-dsa-44 ml-dsa-65 ml-dsa-87
python3 test/test_pqclean.py --sign sphincs-sha2-128f-simple
7.2.3 KAT Testing with liboqs¶
import oqs
import binascii
def verify_kat_vector(kat_file: str, algorithm: str) -> bool:
"""Verify implementation against NIST KAT vectors."""
kem = oqs.KeyEncapsulation(algorithm)
with open(kat_file) as f:
lines = f.readlines()
passed = failed = 0
i = 0
while i < len(lines):
if lines[i].startswith('seed = '):
seed = bytes.fromhex(lines[i].split(' = ')[1].strip())
pk_ref = bytes.fromhex(lines[i+1].split(' = ')[1].strip())
sk_ref = bytes.fromhex(lines[i+2].split(' = ')[1].strip())
ct_ref = bytes.fromhex(lines[i+3].split(' = ')[1].strip())
ss_ref = bytes.fromhex(lines[i+4].split(' = ')[1].strip())
# Set deterministic seed
oqs.randombytes_custom_algorithm(seed)
pk = kem.generate_keypair()
ct, ss_enc = kem.encap_secret(pk)
ss_dec = kem.decap_secret(ct)
if pk == pk_ref and ct == ct_ref and ss_enc == ss_ref:
passed += 1
else:
print(f"FAIL at seed {binascii.hexlify(seed[:8])!r}")
failed += 1
i += 5
else:
i += 1
print(f"KAT {algorithm}: {passed} passed, {failed} failed")
return failed == 0
7.3 NIST Automated Cryptographic Validation Protocol (ACVP)¶
ACVP is the automated testing protocol used for FIPS 140-3 CMVP validation.
7.3.1 ACVP JSON Test Format¶
// ACVP ML-KEM-768 KeyGen test request
{
"vsId": 1,
"algorithm": "ML-KEM",
"mode": "keyGen",
"revision": "FIPS203",
"parameterSets": ["ML-KEM-768"],
"testGroups": [{
"tgId": 1,
"testType": "AFT", // Algorithm Functional Test
"parameterSet": "ML-KEM-768",
"tests": [
{"tcId": 1, "dkSeed": "..."},
{"tcId": 2, "dkSeed": "..."}
]
}]
}
// ACVP ML-KEM-768 KeyGen response
{
"vsId": 1,
"testGroups": [{
"tgId": 1,
"tests": [
{"tcId": 1, "ek": "...", "dk": "..."},
{"tcId": 2, "ek": "...", "dk": "..."}
]
}]
}
7.3.2 ACVP Test Types¶
| Test Type | Abbreviation | Description |
|---|---|---|
| Algorithm Functional Test | AFT | Verify basic algorithm operations with given inputs |
| Monte Carlo Test | MCT | Iterative testing to expose subtle errors |
| Known Answer Test | KAT | Compare against pre-computed reference values |
| Decapsulation Failure | N/A | Verify correct behavior on invalid ciphertext |
| Verification Failure | N/A | Verify correct rejection of invalid signatures |
7.4 Interoperability Testing¶
Interoperability ensures that implementations from different vendors can communicate correctly.
| Implementation | liboqs | BouncyCastle | AWS-LC | wolfSSL |
|---|---|---|---|---|
| liboqs (C) | — | ✓ | ✓ | ✓ |
| BouncyCastle (Java) | ✓ | — | ✓ | ✓ |
| AWS-LC (C) | ✓ | ✓ | — | ✓ |
| wolfSSL | ✓ | ✓ | ✓ | — |
| pqm4 (M4 asm) | ✓ | — | — | — |
7.4.1 TLS Interoperability Test¶
#!/bin/bash
# Test TLS interoperability between OQS-OpenSSL and wolfSSL
echo "=== Starting PQC TLS Interop Test ==="
# Start OQS-OpenSSL server (ML-DSA-65 cert, ML-KEM-768 KEM)
openssl s_server -cert mldsa65.pem -key mldsa65_key.pem \
-accept 4433 -tls1_3 -curves mlkem768 \
-provider oqsprovider -provider default &
SERVER_PID=$!
sleep 1
# Test 1: OQS-OpenSSL client -> OQS-OpenSSL server
echo "Test 1: OQS -> OQS"
echo "GET / HTTP/1.0" | openssl s_client -connect localhost:4433 \
-groups mlkem768 -provider oqsprovider -provider default \
-verify_return_error 2>&1 | grep -E "(Cipher|Verify|CONNECTED)"
# Test 2: wolfSSL client -> OQS-OpenSSL server
echo "Test 2: wolfSSL -> OQS"
./wolfssl_client -h localhost -p 4433 --pq 2>&1 | grep -E "Cipher|Version"
# Test 3: Check key exchange group negotiation
openssl s_client -connect localhost:4433 \
-provider oqsprovider -provider default \
-groups mlkem768 2>&1 | grep "Server Temp Key"
kill $SERVER_PID
echo "Interop tests complete"
7.5 Performance Benchmarking¶
7.5.1 SUPERCOP / pqcrypto-speed¶
# SUPERCOP (System for Unified Performance Evaluation Related to Cryptographic Operations)
# https://bench.cr.yp.to/supercop.html
# After building:
./do-part crypto_kem ml-kem-768
./do-part crypto_sign ml-dsa-65
# Results are in benchmarks/crypto_kem/ml-kem-768/
# Format: cycles implementation operation
cat benchmarks/crypto_kem/ml-kem-768/*/cycles
# pqcrypto-speed (simpler alternative)
git clone https://github.com/PQCrypto/pqcrypto.github.io
python3 speed_comparison.py --algorithm ML-KEM-768 --iterations 10000
7.5.2 Benchmark Script¶
import time
import statistics
import oqs
def benchmark_kem(algorithm: str, iterations: int = 1000):
"""Benchmark a KEM algorithm: keygen, encaps, decaps."""
kem = oqs.KeyEncapsulation(algorithm)
keygen_times, encaps_times, decaps_times = [], [], []
for _ in range(iterations):
# KeyGen
t0 = time.perf_counter_ns()
pk = kem.generate_keypair()
keygen_times.append(time.perf_counter_ns() - t0)
# Encapsulate
t0 = time.perf_counter_ns()
ct, ss = kem.encap_secret(pk)
encaps_times.append(time.perf_counter_ns() - t0)
# Decapsulate
t0 = time.perf_counter_ns()
ss2 = kem.decap_secret(ct)
decaps_times.append(time.perf_counter_ns() - t0)
assert ss == ss2, "Shared secret mismatch!"
def stats(times):
med = statistics.median(times)
return f"{med/1000:.1f}μs (median), {min(times)/1000:.1f}μs (min)"
print(f"\n=== {algorithm} (n={iterations}) ===")
print(f" KeyGen: {stats(keygen_times)}")
print(f" Encaps: {stats(encaps_times)}")
print(f" Decaps: {stats(decaps_times)}")
print(f" pk: {len(pk)}B, ct: {len(ct)}B, ss: {len(ss)}B")
# Run benchmarks
for alg in ["ML-KEM-512", "ML-KEM-768", "ML-KEM-1024"]:
benchmark_kem(alg)
7.6 Security Testing: Fuzzing¶
Fuzzing is critical for finding implementation bugs (buffer overflows, out-of-bounds access) that could create security vulnerabilities.
7.6.1 libFuzzer Integration¶
#include <oqs/oqs.h>
#include <stdint.h>
#include <stddef.h>
#include <string.h>
/* libFuzzer entry point */
int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) {
OQS_KEM *kem = OQS_KEM_new(OQS_KEM_alg_ml_kem_768);
if (!kem) return 0;
/* Only proceed if we have enough data for a secret key */
if (size < kem->length_secret_key) {
OQS_KEM_free(kem);
return 0;
}
/* Use fuzz input as the secret key */
const uint8_t *sk = data;
/* Use remainder as ciphertext (padded/truncated to correct size) */
uint8_t ct[1088] = {0}; /* ML-KEM-768 ciphertext size */
size_t ct_data_len = size - kem->length_secret_key;
memcpy(ct, data + kem->length_secret_key,
ct_data_len < sizeof(ct) ? ct_data_len : sizeof(ct));
uint8_t ss[32];
/* Should never crash or abort -- just return error/implicit rejection */
OQS_KEM_decaps(kem, ss, ct, sk);
OQS_KEM_free(kem);
return 0;
}
/* Build: clang -fsanitize=fuzzer,address -o fuzzer fuzzer_mlkem.c -loqs */
/* Run: ./fuzzer -max_len=4000 corpus/ */
7.7 Formal Verification¶
7.7.1 mlkem-native CBMC Verification¶
mlkem-native uses CBMC (C Bounded Model Checker) to formally verify:
# Install CBMC
apt-get install cbmc
# Clone mlkem-native
git clone https://github.com/pq-code-package/mlkem-native.git
cd mlkem-native
# Run CBMC verification (memory safety)
cbmc --unwind 256 --object-bits 14 \
mlkem/poly.c \
--function poly_ntt \
--memory-check --pointer-check \
--bounds-check --overflow-check
# Expected: VERIFICATION SUCCESSFUL
# This proves: no buffer overflows, no UB, no null pointer dereferences
# Run full formal verification suite
make verify # Runs all CBMC proofs
7.8 Compliance Validation Checklist¶
| Category | Requirement | Status |
|---|---|---|
| Algorithm | All KAT vectors pass | ✓ |
| Algorithm | ACVP test vectors pass | ✓ |
| Algorithm | Correct handling of invalid ciphertext (implicit rejection) | ✓ |
| Algorithm | Correct rejection of invalid signatures | ✓ |
| Implementation | Constant-time execution (no secret-dependent branches) | ✓ |
| Implementation | No secret-dependent memory accesses | ✓ |
| Implementation | Memory safety (no buffer overflows, no UAF) | ✓ |
| Implementation | Secure key zeroization (secrets wiped from memory after use) | ✓ |
| Interoperability | Compatible with at least one other validated implementation | ✓ |
| Performance | Meets application latency requirements | ✓ |
| FIPS | FIPS 140-3 module validation (if required) | In progress |
| Side-channel | TVLA power analysis evaluation (if required) | In progress |
7.9 Summary¶
-
KAT vectors from NIST provide the primary correctness check for PQC implementations.
-
NIST ACVP automates validation and is mandatory for FIPS 140-3 CMVP certification.
-
Interoperability testing across implementations (liboqs, BouncyCastle, AWS-LC, wolfSSL) is critical for deployed systems.
-
libFuzzer harnesses with address sanitizer are essential for finding memory safety bugs.
-
Formal verification (CBMC for C, Jasmin for assembly) provides the highest assurance level.
-
Constant-time execution must be verified via tools like dudect, TVLA, or formal methods.
-
The compliance checklist covers algorithm correctness, implementation security, interoperability, and FIPS requirements.