Skip to content

Chapter 7: PQC Testing and Validation

7.1 Overview of PQC Testing

Testing PQC implementations requires multiple complementary approaches:

  1. Known Answer Tests (KAT): Verify functional correctness against reference vectors.

  2. NIST ACVP: Automated Cryptographic Validation Protocol for FIPS validation.

  3. Interoperability testing: Cross-implementation compatibility.

  4. Performance benchmarking: Cycle counts, latency, throughput.

  5. Fuzzing and memory safety: Security testing for implementation bugs.

  6. Formal verification: Mathematical proof of correctness.

  7. 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

Table 7.1. ACVP Test Types for PQC Algorithms
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.

Table 7.2. PQC Interoperability Test Matrix
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

Table 7.3. PQC Implementation Compliance 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.