Post-quantum validator strategy: KEM probe + signature validators

[bradh11]

Background

CertMonitor currently has no visibility into post-quantum cryptography in TLS handshakes or certificates. As hybrid PQ key exchange (RFC 9794 family — X25519MLKEM768, SecP256r1MLKEM768, etc.) is now widely deployed by major CDNs and browsers, and NIST FIPS-204/205 PQ signature standards are finalized, operators need to monitor PQ posture.

This issue tracks adding PQ awareness across the validator surface.

Two distinct PQ surfaces

Surface	Risk model	2026 status
PQ key exchange (KEM)	HNDL — harvest now, decrypt later	Widely deployed in hybrid form
PQ certificate signatures	Only matters once CRQCs exist	NIST standards final; web PKI rollout starting

These need separate validators — different timelines, different data sources, different failure modes.

Current gaps

• certmonitor/validators/key_info.py — classifies SPKI as RSA / EC / Unknown. PQ keys silently fall through to is_valid=None with key_type="Unknown".
• certmonitor/validators/weak_cipher.py — allow-lists cipher suites, but TLS 1.3 KEMs are negotiated as named groups (not cipher suites), so PQ KEX is invisible here.
• rust_certinfo/src/x509/spki.rs — recognizes only rsaEncryption and ecPublicKey OIDs. ML-DSA, SLH-DSA, Falcon, and composite OIDs all collapse to PublicKeyAlgorithm::Unknown.
• Python stdlib ssl does not expose the negotiated TLS 1.3 group at all. There is no current path in the codebase to learn which KEM was negotiated.

Proposed work

1. Add PQ algorithm OIDs to the Rust SPKI parser

Extend PublicKeyAlgorithm enum and OID table in rust_certinfo/src/ to recognize:

• ML-DSA-44 / 65 / 87 (FIPS-204)
• SLH-DSA variants (FIPS-205)
• Falcon (when standardized)
• Hybrid composite signature OIDs (draft-ietf-lamps-pq-composite-sigs — table will need updates as registry stabilizes)

Additive change, no shape change to the Python-facing dict.

2. Upgrade key_info validator

Teach _is_key_strong_enough to recognize PQ algorithms as valid so existing users of key_info don't get misleading is_valid=None on PQ certs. Table-stakes change; should ship before the new validators.

3. New validator: pq_signature (cert-type)

Returns {leaf_key_alg, leaf_sig_alg, is_pq, is_hybrid_composite, is_valid}. Self-contained; depends only on cert parsing changes from (1).

4. New Rust module: tls/ submodule for TLS 1.3 handshake probing

A separate, second connection per scan that opens a raw TCP socket, sends a hand-crafted TLS 1.3 ClientHello with PQ groups in supported_groups, reads ServerHello or HelloRetryRequest, extracts the negotiated group ID, and closes. No crypto operations — handshake never completes; we just read the negotiated group off the wire.

Structure:

```
rust_certinfo/src/tls/
├── groups.rs ← IANA Supported Groups table (contributor-friendly)
├── handshake.rs ← ClientHello/ServerHello parsing
├── records.rs ← TLS record framing
└── probe.rs ← orchestration; exposed to Python via PyO3
```

Exposed as certmonitor.certinfo.probe_tls_handshake(host, port, sni, timeout_ms) returning a dict including {id, name, kind} for the negotiated group. The kind enum (classical_ecdh, hybrid_pq, pure_pq, etc.) is computed Rust-side so Python doesn't need its own copy of the table.

Implementation notes:

• Zero external Rust crates — uses std::net::TcpStream, std::io, existing der/ reader patterns.
• No randomness needed: fixed pattern (e.g. b\"CERTMONITOR-PROBE\\x00...\") for ClientHello random/session_id/key_share placeholder. Server doesn't validate client random before sending ServerHello.
• IANA group table lives in its own groups.rs file as a static slice of GroupInfo { id, name, kind }. Adding a new group is a one-line edit, no protocol code touched.
• Must include realistic extension set (SNI, supported_versions, signature_algorithms, ALPN) so WAFs don't drop the probe as a scanner.
• Read-only parsing with bounded buffers — no key derivation, no decryption, no certificate validation in the probe path.

5. New validator: pq_key_exchange (cipher-type)

Consumes the Rust probe result and judges whether the negotiated KEM is classical / hybrid PQ / pure PQ. Returns {kem_id, kem_name, kem_kind, is_pq, is_valid}. Handles TLS-1.2-only servers gracefully ({kem: \"n/a\", reason: \"server does not support TLS 1.3\"}).

6. New validator: pq_chain (cert-type)

Walks the cert chain (extending chain.py patterns) and reports per-cert {depth, key_alg, sig_alg, is_pq}. Useful during the staged migration period when leaf, intermediate, and root rotate at different times. Note in docstring that chains terminating at public trust anchors will report classical at the root for the foreseeable future.

Architectural decisions

• Wire protocol + binary format parsing lives in Rust. Establishes a clean boundary that future TLS-introspection features (signature_algorithms negotiated, ALPN, ECH, OCSP stapling, etc.) extend naturally.
• Single source of truth for IANA tables: Rust. Probe returns rich structured results (id + name + kind) so Python consumes classifications without duplicating data. If Python ever needs direct table access, expose via a one-line #[pyfunction].
• All new PQ validators are opt-in. Not added to DEFAULT_VALIDATORS until web PKI catches up; would be too noisy by default.
• "PQ" includes hybrid. is_valid=True for either hybrid (classical + PQ) or pure-PQ, with a separate is_hybrid field. Requiring pure PQ today would fail every real-world cert.

Open questions

• Composite signature OIDs (draft-ietf-lamps-pq-composite-sigs) are still in flux. Plan: keep the OID table in one Rust file and add a unit test per OID; expect periodic updates.
• ClientHello fingerprinting by WAFs — needs spot-checks against major CDNs once the probe is built.
• TLS 1.2-only servers: report "n/a" rather than "invalid" — TLS 1.2 will be the dominant signal that an endpoint cannot support PQ at all.

Suggested build order

1. Rust: add PQ OIDs to SPKI parser.
2. Upgrade key_info to recognize PQ algorithms.
3. Add pq_signature validator.
4. Add Rust tls/ module with handshake probe + PyO3 export.
5. Add pq_key_exchange validator on top of (4).
6. Add pq_chain validator.

(1)–(3) and (4)–(5) can proceed in parallel once (1) is merged.

[bradh11]

Amendment: graceful degradation for older TLS/SSL + EC curve scope

Behavior matrix for older protocols

The pq_key_exchange validator must return a clean, structured result for any protocol version, not just TLS 1.3.

Server speaks	Has named groups?	PQ KEMs defined?	Validator returns
TLS 1.3	Yes (ServerHello key_share)	Yes (RFC 9794)	Negotiated group + kind
TLS 1.2 ECDHE	Yes (in ServerKeyExchange, not ServerHello)	No	kem_kind: \"n/a\", reason: TLS 1.2 has no PQ KEMs
TLS 1.2 RSA kex	No — no forward secrecy at all	No	kem_kind: \"n/a\", reason: non-FS key exchange
TLS 1.1 / 1.0	No (legacy)	No	kem_kind: \"n/a\", reason: deprecated TLS version
SSL 3.0 / 2.0	No	No	kem_kind: \"n/a\"; already flagged by tls_version
Non-TLS / unreachable	—	—	Standard {error, message} dict per project convention

Design decisions

Skip the probe entirely for TLS < 1.3. The main SSLHandler already knows the negotiated TLS version via stdlib ssl. PqKeyExchangeValidator checks that first and short-circuits with {kem_kind: \"n/a\", reason: \"TLS <ver> — no PQ KEMs defined\"} without opening a second TCP connection. The probe still has to be robust against older responses (defense in depth), but the common case never triggers it.

is_valid is strict bool, not Optional[bool]. The PQ question is binary at the protocol level:

• TLS 1.3 + hybrid/pure PQ → is_valid: True
• TLS 1.3 + classical group → is_valid: False, reason: \"classical KEX — vulnerable to HNDL\"
• TLS 1.2 or older → is_valid: False, reason: \"TLS <ver> has no PQ KEMs\" (not PQ-capable at all is a stronger signal than "unknown")

Probe robustness requirements (defense in depth)

Even with the skip-for-legacy short-circuit, the probe in tls/probe.rs must:

• Cap read at 16 KB before bailing.
• Use set_read_timeout for the read.
• If ServerHello legacy_version < 0x0304 and supported_versions extension isn't echoed → return {kem_kind: \"n/a\", protocol: \"TLS 1.2 or older\"}.
• If a handshake alert comes back → return {kem_kind: \"n/a\", reason: \"server alert: <code>\"}.
• If the first record's content type ≠ 0x16 → return non-TLS error.
• Never panic, never block forever.

EC curve scope — clarification

The cert's subject public key curve is already captured by key_info.py via the existing SPKI parser in rust_certinfo/src/x509/spki.rs. No work needed there.

The negotiated ephemeral ECDHE curve in TLS 1.2 is a separate thing — it's a per-session forward-secrecy property, not a cert property. Python stdlib ssl doesn't expose it (same visibility gap as the TLS 1.3 group). This belongs in a new cipher-type validator (e.g. tls_kex_curve) consuming a Rust probe result, not in key_info — mixing long-lived cert identity with per-session KEX ephemerals muddies the validator's purpose.

Convenient property: TLS 1.2 ECDHE uses the same IANA Supported Groups registry as TLS 1.3, so tls/groups.rs covers both. Only the wire location differs:

• TLS 1.3: ServerHello.extensions.key_share
• TLS 1.2 ECDHE: ServerKeyExchange.ECParameters.namedcurve

The Rust tls/ module would need a small TLS 1.2 ServerKeyExchange parser added (~100 lines). Reasonable to defer to a follow-up issue once the TLS 1.3 path is shipped, but worth listing here so it's not forgotten.

Suggested build order — updated

1. Rust: add PQ OIDs to SPKI parser.
2. Upgrade key_info to recognize PQ algorithms.
3. Add pq_signature validator.
4. Add Rust tls/ module with TLS 1.3 handshake probe + PyO3 export.
5. Add pq_key_exchange validator on top of (4), including the skip-for-legacy short-circuit and strict is_valid mapping above.
6. Add pq_chain validator.
7. (Follow-up) Extend Rust tls/ module to parse TLS 1.2 ServerKeyExchange; add tls_kex_curve validator that reports the negotiated ephemeral curve regardless of version.

[bradh11]

Sub-issues (PR tracker)

Track A — cert-side

• Track A · PR 1/7 — Rust: add PQ algorithm OIDs to SPKI parser #29 — PR 1/7: Rust: add PQ algorithm OIDs to SPKI parser (blocks 30, 31, 35)
• Track A · PR 2/7 — key_info validator: recognize PQ algorithms #30 — PR 2/7: key_info validator: recognize PQ algorithms
• Track A · PR 3/7 — Add pq_signature validator #31 — PR 3/7: Add pq_signature validator
• Track A · PR 6/7 — Add pq_chain validator #35 — PR 6/7: Add pq_chain validator

Track B — wire-side

• Track B · PR 4a/7 — Rust: tls/ module (parsers, no networking) #32 — PR 4a/7: Rust: tls/ module (parsers, no networking) (blocks 33)
• Track B · PR 4b/7 — Rust: tls/probe.rs (probe + PyO3 export) #33 — PR 4b/7: Rust: tls/probe.rs (probe + PyO3 export) (blocks 34)
• Track B · PR 5/7 — Add pq_key_exchange validator #34 — PR 5/7: Add pq_key_exchange validator

Day 1 start: #29 and #32 in parallel.