# CRL and OCSP at PQC Signature Sizes **Source**: https://quantumsequrity.com/blog/crl-ocsp-pqc-scale **Category**: Operations --- [← Back to Blog](../../blog.html) Operations # CRL and OCSP at PQC Signature Sizes 10 min read The X.509 revocation infrastructure has been showing strain for years. Certificate Revocation Lists (CRLs) grow large with active CAs. Online Certificate Status Protocol (OCSP) responders are operationally expensive. Browsers have invented hybrid approaches like CRLite and CRLSets to make revocation status both fast and current. None of this was easy before post-quantum cryptography. With ML-DSA signatures running 3 KB or larger, every component of the revocation chain feels the bloat. This article walks through how PQC signatures interact with revocation infrastructure, where the bottlenecks are, and what mitigations the community has been building. ## The Two Revocation Mechanisms Brief recap, since this matters for what changes: **CRL (RFC 5280)**: A signed list of revoked certificate serial numbers, published periodically by the CA. Clients download the CRL, parse it, and check whether the cert they want to validate is on the list. The whole list goes through the network on every refresh. **OCSP (RFC 6960)**: A query/response protocol. The client asks "is this serial number revoked?" The OCSP responder signs a small response with the answer. The signature is checked, the answer is trusted. CRL is bandwidth-heavy but cache-friendly. OCSP is bandwidth-light per query but requires online infrastructure and adds round-trip latency. Neither scales gracefully in all dimensions. ## Why PQC Signatures Make This Harder PQ signatures are big. Approximate sizes: | Algorithm | Public Key | Signature | |---|---|---| | Ed25519 | 32 B | 64 B | | ECDSA P-256 | 64 B | 64-72 B | | RSA-2048 | 256 B | 256 B | | ML-DSA-44 | 1312 B | 2420 B | | ML-DSA-65 | 1952 B | 3309 B | | ML-DSA-87 | 2592 B | 4627 B | | Falcon-512 (FN-DSA-512) | 897 B | 666 B | | Falcon-1024 (FN-DSA-1024) | 1793 B | 1280 B | | SLH-DSA-128f | 32 B | 17088 B | ML-DSA at the most common security level (ML-DSA-65) is about 3.3 KB per signature. SLH-DSA, the conservative hash-based alternative, is 17 KB. Falcon (FN-DSA) is the smallest at the cost of more complex implementation requirements. In CRLs and OCSP responses, the signature appears once per signed artifact. The size growth has the following implications. ## CRL Bloat A CRL contains: 1. CRL header (issuer, this update, next update, signature algorithm). 2. List of revoked entries: serial number + revocation time + optional reason + optional CRL extensions. 3. CRL signature. The signature is one entry per CRL, but the CRL itself can be large. A busy public CA may have a CRL with millions of entries; even if each entry is small (~30 bytes), the CRL is 30+ MB. Adding 3 KB of PQ signature is negligible against that backdrop. But many internal CAs and smaller public CAs have CRLs in the kilobyte range. For these, the PQ signature dominates. A 5-entry CRL signed with ML-DSA-65 might be 4 KB total, of which 3.3 KB is signature. This affects: - **Network distribution**: More bytes per CRL fetch. - **Cache invalidation**: PQ-sized CRLs blow through cache assumptions. - **Embedded validators**: Small devices with limited memory may not hold large CRLs. Mitigation strategies: - **Delta CRLs**: Publish only changes since last full CRL. Reduces fetch size for already-cached clients. - **CRL distribution points**: Spread CRLs across multiple URLs for parallel fetch. - **CRLite-style approaches**: Bloom-filter or similar compact representations of revocation status. Browsers (Firefox in particular) have been driving these. ## OCSP Response Inflation An OCSP response is smaller than a CRL but, with PQ signatures, the signature can be larger than the actual answer. A typical OCSP response includes: 1. Response header (responder ID, this update, next update). 2. Cert status (good, revoked, unknown). 3. Single response signature. With Ed25519, the signature was 64 bytes. The whole response was maybe 200 bytes. With ML-DSA-65, the signature alone is 3309 bytes. The whole response is closer to 4 KB. This affects: - **OCSP responder bandwidth**: 20x more bytes per response. A high-traffic responder feels this immediately. - **OCSP stapling**: When the server staples the OCSP response into the TLS handshake, the handshake gets bigger. Initial connection latency goes up. - **Mobile networks**: On constrained networks, the larger response is more painful. Mitigation strategies: - **OCSP stapling**: Server fetches and caches OCSP responses, includes them in the handshake. Cuts the per-client OCSP traffic to zero. - **OCSP must-staple**: Cert says "this cert MUST come with a stapled OCSP response." Browsers refuse to connect without it. - **Smaller PQ signatures where appropriate**: Falcon (FN-DSA) is much smaller than ML-DSA. For OCSP responders specifically, FN-DSA is attractive. - **Hybrid signatures with shorter classical component**: If the OCSP response carries both classical and PQ signatures, the classical one is the day-to-day verifier with the PQ one as backup. ## CRLite and Modern Browser Approaches CRLite, developed by Mozilla and used in Firefox, takes a different approach to revocation. Instead of fetching CRLs or OCSP responses, the browser downloads a compact data structure (cascading Bloom filters) that represents all known revocations. The data structure is updated periodically. CRLite advantages: - **Much smaller than full CRLs**: A few hundred KB for the entire web's revocations. - **Offline-checkable**: No round trip per query. - **Privacy-preserving**: The CA does not know which certs the browser is checking. For PQC, CRLite is largely insulated from signature bloat because the data structure does not embed per-cert signatures. The signature is on the CRLite update artifact itself, which is a once-per-update overhead, not per-cert. Chrome's CRLSets (a coarser equivalent) and Apple's revocation infrastructure follow similar patterns. As PQC adoption grows, expect more browsers to move toward CRLite-style mechanisms. ## OCSP Stapling at PQ Sizes OCSP stapling embeds the OCSP response in the TLS handshake. The server fetches OCSP responses periodically and serves them to clients. With PQ signatures, the stapled response is bigger: - Pre-PQC stapled OCSP: ~200 bytes - ML-DSA-65 stapled OCSP: ~4 KB - ML-DSA-87 stapled OCSP: ~5 KB - SLH-DSA stapled OCSP: ~18 KB (impractically large) Adding 4 KB to every TLS handshake is meaningful but not catastrophic. TLS 1.3 records are typically 16 KB, so a 4 KB OCSP response fits in one record. The handshake gets one extra frame compared to a non-PQ stapled response. For SLH-DSA, stapling at full size is impractical. SLH-DSA may be relegated to long-term archival signatures rather than online revocation responses. ## OCSP Server Performance OCSP responders sign each response. With PQ signatures, the signing cost matters: - ECDSA P-256 signing: ~50 microseconds on modern CPU - Ed25519 signing: ~50 microseconds - ML-DSA-65 signing: ~500 microseconds - ML-DSA-87 signing: ~1 millisecond - SLH-DSA signing: 5-50 milliseconds depending on parameter set For a high-traffic OCSP responder doing thousands of signatures per second, the 10-100x slowdown affects capacity planning. Hardware acceleration for PQ signing is starting to appear in HSMs and CPUs but is not yet universal. Mitigation: pre-sign and cache OCSP responses with longer validity, accepting some staleness in exchange for lower signing rate. The OCSP `nextUpdate` field already supports this. ## CT Logs and Revocation Certificate Transparency (see [certificate transparency PQC](certificate-transparency-pqc.md)) is closely related to revocation. CT logs publish certificates as they are issued, providing a public record. Revocation is a separate mechanism, but the two interact: a revoked cert's SCTs (Signed Certificate Timestamps) remain in CT logs as historical records. For PQC migration, CT log entries that include PQ-signed certificates grow larger. The SCT itself is a small signature (currently classical) on the cert hash, but the embedded cert can be 6-8 KB. CT log retrieval for audit purposes pulls these larger artifacts. ## Operational Recommendations For organizations operating PKI with revocation infrastructure: 1. **Audit current CRL and OCSP volume**. Measure per-day bandwidth, response time, peak query rate. 2. **Project PQ overhead**. Roughly 20x signature size for ML-DSA-65 versus ECDSA. Apply this multiplier to current OCSP bandwidth. 3. **Staple aggressively**. OCSP stapling cuts client-side OCSP traffic to zero. With PQ, this is more important than ever. 4. **Pre-compute OCSP responses**. Reduces signing rate. Accept longer validity windows. 5. **Plan for CRLite-style approaches** for browser-facing PKI. CRLite scales gracefully with PQ. 6. **Consider Falcon (FN-DSA)** for OCSP responder keys. Smaller signatures, same security level. 7. **Monitor signing capacity**. PQ signing is slower; ensure HSMs and software signers have headroom. ## Short-Lived Certificates as a Revocation Alternative A different approach to revocation is making it unnecessary by using very short-lived certificates. If a certificate is valid for only 7 days, the operational case for revocation weakens substantially: by the time you would publish a revocation, the certificate has nearly expired anyway. Short-lived certificates have been gaining traction independent of PQC. The CA/Browser Forum has approved a phased validity reduction: 398 days today, 200 days in March 2026, 100 days in 2027, possibly 47 days in 2027 H2 or 2028, and potentially 10 days thereafter. See [Certificate Lifecycle Management and PQC](cert-lifecycle-pqc.md) for the timeline. For PQ migration, short-lived certs are doubly attractive: - Less revocation infrastructure pain. CRLs and OCSP responses become smaller because fewer certs are simultaneously revoked. - More opportunities to refresh algorithms. Each renewal can upgrade to newer parameters. - Reduced harvest-now-decrypt-later exposure. Old encrypted handshakes become irrelevant faster. The trade-off is operational pressure. ACME automation becomes mandatory. Renewal failures become incidents. The infrastructure for issuing certificates must be more reliable than the application using them. ## OCSP Must-Staple and PQ OCSP Must-Staple is an X.509 extension that says "this certificate MUST be presented with a stapled OCSP response." Browsers refuse to connect if the staple is missing. For PQ certificates, Must-Staple is essentially required because: - Without stapling, every TLS handshake triggers a separate OCSP fetch (more round trips, more bandwidth) - With PQ-sized OCSP responses, those separate fetches multiply the bandwidth penalty - Stapling consolidates the OCSP response into the handshake itself, paid for once per server cache cycle For Must-Staple to work, server software must reliably fetch OCSP responses, cache them, and include them in handshakes. Apache, nginx, HAProxy, Caddy, and Traefik all support this; configuration varies. PQ migration is a good time to verify Must-Staple is correctly configured. ## CRLite Operational Considerations Mozilla's CRLite is the most ambitious revocation scaling approach. It compresses every public web revocation into a few hundred KB Bloom filter cascade. The Bloom filter is updated periodically (typically daily) and pushed to browsers. For PQC migration, CRLite is largely insulated from signature bloat. The data structure does not embed per-cert signatures. The only PQ artifact is the signature on the CRLite update itself, which is a single PQ signature on the bloom filter cascade. With ML-DSA-65, this adds about 3.3 KB to the update. Negligible. Operating CRLite at the public scale requires: - Aggregating revocation data from all CT-logged CAs - Computing the cascading Bloom filter (this is a multi-stage process to manage false positives) - Signing the result with the CRLite operator's key - Distributing the update to clients For internal CT systems, scaled-down CRLite implementations are feasible. The Bloom filter math is the same regardless of scale. ## OCSP Responder HSM Capacity Planning For organizations running their own OCSP responders backed by HSMs, the PQ signing throughput requires capacity planning. ML-DSA-65 signing on a typical HSM runs roughly 100 to 500 signatures per second versus 5,000 to 50,000 for ECDSA P-256. Mitigations include pre-signing OCSP responses with longer validity windows (the nextUpdate field allows up to 7 days), front-end response caching, using FN-DSA instead of ML-DSA for smaller signatures and faster signing, and adding HSM capacity from PQ-aware vendors like Thales, Entrust, and Utimaco. ## Frequently Asked Questions **Will my browser's revocation checking break with PQ certs?** Probably not. Browsers are gradually adding PQ awareness. The first wave of PQ public-facing certs will likely use hybrid signatures, so legacy browsers see classical and modern browsers see PQ. Pure PQ-only certs are still in pilot phase. **Should I deploy SLH-DSA for OCSP?** No. SLH-DSA signatures are too large for online revocation. Reserve SLH-DSA for long-term archival signatures where size is less critical. **Can I use Falcon for OCSP?** Yes. Falcon (FN-DSA) has substantially smaller signatures than ML-DSA. The FN-DSA-512 signature is ~666 bytes, comparable to RSA-2048. The implementation is more complex (requires Gaussian sampling) but is reasonable for server use. NIST FIPS 206 covers FN-DSA. **How does QNSQY handle revocation?** QNSQY's identity model is simpler than X.509 PKI. There is no public CRL or OCSP responder. Instead, identities have a recipient usage period (RUP), and a recipient key directory tracks which identities are active. Revocation is operationally a directory update. **What is the minimum bandwidth headroom I should plan for?** For PQ migration, plan for roughly 5-10x the current revocation traffic to be safe. ML-DSA-65 alone is ~20x the size of ECDSA, but stapling, caching, and CRLite-style approaches dampen the increase substantially. **Will PQ change how I monitor OCSP availability?** Mostly no. The monitoring patterns (uptime, response time, error rate) remain the same. What changes: response time may increase by 1 to 5 ms because of larger response size and slower signing. Set alerting thresholds with the new baseline in mind. Also monitor HSM utilization more carefully because PQ signing capacity is the new bottleneck. **How does CRLite compare to OCSP for PQ?** CRLite is much friendlier to PQ migration because the per-cert overhead does not include a signature. OCSP carries one signature per response. For browsers managing public web revocation, CRLite scales gracefully into the PQ era. For private PKI revocation, OCSP with stapling and pre-signing remains practical. The right answer depends on scale and the verifier population. ## Sources 1. RFC 5280 (X.509 Public Key Infrastructure Certificate and CRL Profile) — https://datatracker.ietf.org/doc/html/rfc5280 2. RFC 6960 (X.509 Internet Public Key Infrastructure OCSP) — https://datatracker.ietf.org/doc/html/rfc6960 3. NIST FIPS 204 (ML-DSA Standard) — https://csrc.nist.gov/pubs/fips/204/final 4. NIST FIPS 205 (SLH-DSA Standard) — https://csrc.nist.gov/pubs/fips/205/final 5. Mozilla CRLite Documentation — https://blog.mozilla.org/security/2020/01/09/crlite-part-3-speeding-up-secure-browsing/ 6. NIST FIPS 206 Draft (FN-DSA / Falcon) — https://csrc.nist.gov/pubs/fips/206/ipd 7. RFC 7633 (OCSP Must-Staple X.509 Extension) — https://datatracker.ietf.org/doc/html/rfc7633 8. CA/Browser Forum Baseline Requirements — https://cabforum.org/baseline-requirements-documents/ ## Related Articles - [Certificate Lifecycle Management and PQC](cert-lifecycle-pqc.md) - [Certificate Transparency Logs and PQC](certificate-transparency-pqc.md) - [Crypto-Agility Explained](crypto-agility-explained.md) - [NIST FIPS Guide for Post-Quantum Cryptography](nist-fips-guide.md) - [Hybrid Encryption: Belt and Braces for the Quantum Transition](hybrid-encryption.md) --- ### Protect Your Data Before Q-Day Arrives QNSQY's NIST-standardized post-quantum encryption protects files against both current and quantum-era threats. [Try QNSQY](../../pricing.html)