AccuRevoke: Enhancing Certificate Revocation with Distributed Cryptographic Accumulators

AccuRevoke: Enhancing Certificate Revocation with Distributed Cryptographic Accumulators

Speakers: Munshi Rejwan Ala Muid, PhD Student; Tijay Chung; Thang Hoang

Conference: IEEE S&P

YouTube: https://www.youtube.com/watch?v=kF-tH8xbsVc

Overview

The internet relies heavily on TLS certificates to establish trust and secure communication between clients and websites. When a website's private key is compromised, its certificate must be revoked to prevent malicious actors from impersonating the legitimate site. However, existing certificate revocation mechanisms suffer from significant drawbacks, including scalability issues, high bandwidth consumption, privacy concerns, and latency. "AccuRevoke: Enhancing Certificate Revocation with Distributed Cryptographic Accumulators" proposes a novel solution to these long-standing problems.

Presented by Munshi Rejwan Ala Muid, a second-year PhD student at Virginia Tech, alongside co-authors Tijay Chung and Thang Hoang, AccuRevoke introduces a robust and efficient system for certificate revocation. The core innovation lies in its use of dynamic universal accumulators and secure multi-party computation (MPC), distributed across Edge Compute Providers (ECPs). This architecture aims to deliver a revocation scheme that is fast, private, scalable, and bandwidth-efficient, addressing the critical shortcomings of current industry practices.

This work is particularly significant because it tackles a foundational security challenge that impacts every internet user. By providing a more reliable and performant method for verifying certificate revocation status, AccuRevoke can significantly enhance the overall security posture of the web, making it harder for attackers to exploit compromised certificates and easier for browsers to trust the legitimacy of websites. The research demonstrates a path towards a more resilient and privacy-conscious certificate ecosystem.

Background

▶ Watch: Introduction and challenges of certificate revocation (0:00)

The foundation of secure web communication is the TLS (Transport Layer Security) protocol, which relies on digital certificates to authenticate websites. When a browser connects to a website, the site presents a TLS certificate, signed by a trusted Certificate Authority (CA). This certificate binds the website's public key to its identity. The system works well as long as the website's private key remains secure. However, if a private key is compromised, the associated certificate becomes a liability and must be revoked immediately to prevent its misuse. The challenge lies in efficiently and reliably informing clients (browsers) about this revocation status.

Historically, several mechanisms have been developed for certificate revocation, each with its own set of advantages and critical limitations.

One of the earliest solutions is the Certificate Revocation List (CRL). In this model, CAs periodically publish a list of all revoked certificates. Browsers are then expected to download and consult these lists. The primary problem with CRLs is their size and the associated bandwidth and latency costs. As the number of revoked certificates grows, CRLs can become exceptionally large; for instance, the speaker cited Apple's CRL as being 76 MB. Downloading such a large file for every TLS handshake is "untenable," making CRLs impractical for frequent, real-time revocation checks.

To address the scalability issues of CRLs, the Online Certificate Status Protocol (OCSP) was introduced. With OCSP, instead of downloading a full list, a browser sends a specific query to the CA (or an OCSP responder) asking, "Is this certificate revoked?" The CA then responds with a simple "yes" or "no." While OCSP reduces bandwidth for the client, it shifts the burden to the CA, which can become "overloaded by millions of OCSP requests from millions of clients." Furthermore, OCSP raises significant privacy concerns as the CA learns which websites a user is visiting by observing their revocation queries.

A more recent attempt to improve revocation efficiency is CRLite, developed by Mozilla. CRLite works by having Mozilla collect all revoked and non-revoked certificates from CAs. It then creates a "filter cascade," which are essentially cascaded Bloom filters, and pushes this compact representation to clients. Delta updates are sent regularly to keep the client's local filter current. While CRLite offers local revocation checking, leading to low latency, it introduces a new set of problems. Clients must place a significant amount of trust in Mozilla, as they "rarely audit the filter cascade." Distributing the initial filter cascade and regular delta updates to all Mozilla clients can also be "very inefficient." Moreover, clients might "miss the intermediate revocation between two delta updates," leaving them vulnerable during those windows.

The talk highlights a set of desired properties for an ideal revocation strategy: low client bandwidth cost, low latency, no over-fetching (clients download only what they need), strong privacy, robustness, and scalability for CAs. Crucially, as the speaker points out, "none of the existing schemes achieves all of the goals," underscoring the pressing need for a new approach like AccuRevoke.

Key Findings

▶ Watch: Key goals for an ideal certificate revocation scheme (3:00)

AccuRevoke presents a comprehensive solution that demonstrably achieves all the desired properties of a robust certificate revocation scheme, a feat none of the prior methods could accomplish. The core innovations and findings are rooted in its cryptographic design and distributed architecture.

A primary finding is the successful integration of dynamic universal accumulators to represent the set of revoked certificates. This cryptographic primitive allows for a "concise representation of a set of elements," where the size of the accumulator remains constant regardless of the number of elements added. Specifically, the accumulator size is a remarkably small 21 bytes, making it highly efficient for dissemination and storage. Updates to this accumulator are also very fast, averaging 0.47 milliseconds.

Another significant finding is the effective use of Secure Multi-Party Computation (MPC) among Edge Compute Providers (ECPs). This distributed approach allows for the generation of membership or non-membership proofs (witnesses) for certificates without any single ECP or the CA learning the client's queries or private information. This directly addresses the privacy concerns inherent in OCSP. The system is also designed for robustness, ensuring that witness generation can proceed even if some ECPs are offline, as long as a sufficient number of shares (defined by a threshold) are available.

From a performance perspective, AccuRevoke exhibits superior characteristics compared to existing strategies. Simulations show that for a client visiting 1,000 websites, the data downloaded by the client is significantly lower than with CRL, OCSP, or CRLite, making AccuRevoke the "clear winner" in terms of bandwidth efficiency. While the experienced delay is slightly higher than CRLite (which benefits from local checking), it is comparable to OCSP, and the speaker argues that the overall advantages of AccuRevoke outweigh this minor difference.

The research also explores practical optimizations, particularly for generating witnesses for non-revoked certificates, which can be computationally intensive. By leveraging GPU acceleration, the time taken to generate a non-revoked witness was reduced to 15 milliseconds. Further analysis identified data copying between CPU and GPU memory as a bottleneck, leading to the implementation of amortization techniques that yielded an impressive 8.9-fold speedup. This demonstrates AccuRevoke's practical viability for real-world deployment, especially with the increasing availability of edge computing services from CDNs.

In summary, AccuRevoke's key findings highlight its ability to provide a scalable, private, bandwidth-efficient, and robust certificate revocation system, fulfilling all previously unmet requirements for an ideal revocation scheme.

Technical Deep Dive

▶ Watch: AccuRevoke: Leveraging accumulators and MPC (3:30)

AccuRevoke's innovative approach to certificate revocation is built upon two advanced cryptographic primitives: dynamic universal accumulators and secure multi-party computation (MPC). These are orchestrated within a distributed system model involving the Certificate Authority (CA), multiple Edge Compute Providers (ECPs), and the client (browser).

At the heart of AccuRevoke is the dynamic universal accumulator. An accumulator is a cryptographic primitive that allows for the creation of a "concise representation of a set of elements." In the context of AccuRevoke, this set consists of all currently revoked certificates. A crucial property of this accumulator is that its "value," or size, remains constant regardless of how many elements (revoked certificates) are added to it. The speaker highlights this as "like a magic," emphasizing its efficiency. Beyond its compact size, the dynamic universal accumulator supports both the addition and deletion of elements, which is essential for managing a constantly changing list of revoked certificates. It also enables the generation of membership proofs (proving a certificate is in the revoked set) and non-membership proofs (proving a certificate is not in the revoked set). The CA acts as a trusted entity, choosing a secret trapdoor (denoted as alpha) and using it to create the public key for the accumulator.

The second foundational technology is Secure Multi-Party Computation (MPC). MPC allows multiple parties, each possessing their own private input, to jointly compute a function without revealing their individual confidential inputs to each other. AccuRevoke leverages MPC to enable ECPs to collaboratively generate witness shares without exposing the client's specific certificate query to any single ECP, thereby preserving client privacy.

The AccuRevoke system model comprises three main entities:

1. Certificate Authority (CA): The CA remains the "main source of trust," similar to other revocation strategies. It is responsible for:

• Choosing a secret trapdoor alpha for the accumulator.
• Creating the accumulator from the current list of revoked certificates.
• Generating secret shares of the trapdoor alpha using a threshold secret sharing scheme, such as Shamir secret sharing. This scheme defines a threshold value, indicating the minimum number of shares required to reconstruct the original secret.
• Sending these secret shares to all ECPs.
• Disseminating the public accumulator value to all ECPs and clients.

1. Edge Compute Providers (ECPs): These are "multiple third-party servers" that the CA delegates some trust to. ECPs are typically content delivery networks (CDNs) that offer edge computing capabilities, enabling revocation checks "very fast and near to the clients." Their primary role is to generate membership or non-membership witnesses for certificates.

1. Client (Browser): The client initiates the revocation check process. After receiving a TLS certificate from a website, the browser requests a witness for that certificate from an ECP, using the certificate's serial number.

The witness generation process is a critical component of AccuRevoke:

• When a browser needs to verify a certificate's status, it sends a request for a witness to an ECP (e.g., ECP3).
• The ECPs, using the secret shares provided by the CA, engage in secure multi-party computation. During this MPC protocol, they jointly compute their respective "shares of the witness" for the requested certificate.
• The system supports two primary methods for witness reconstruction:

1. Client-side reconstruction: Each participating ECP sends its computed witness share directly to the client. The client then collects these shares and reconstructs the actual witness itself.
2. ECP-side reconstruction: One designated ECP (e.g., the ECP that initially received the client's request) collects all the witness shares from the other participating ECPs. This ECP then reconstructs the full witness on behalf of the client and sends the complete witness back to the client. This approach reduces the client's computational burden.

• Once the client receives the reconstructed witness, it can use this cryptographic proof to verify the revocation or non-revocation status of the certificate against the public accumulator value.
• For frequently queried certificates or popular domains, ECPs can pre-compute and store witnesses, allowing for "instant" replies to client requests, further reducing latency.

Robustness is a key design goal. Because the CA distributes secret shares of its trapdoor using a threshold scheme, the system can tolerate failures of individual ECPs. As long as a sufficient number of ECPs (equal to or greater than the threshold) remain operational, the witness can still be generated and reconstructed, ensuring continuous service availability.

The integration with CDNs is a practical advantage. CDNs already provide a distributed network of edge servers, making them ideal candidates for hosting ECPs. This leverages existing infrastructure, bringing revocation checks physically closer to clients, and enhancing both speed and resilience.

In essence, AccuRevoke decentralizes the computationally intensive and privacy-sensitive aspects of revocation checking, moving them from a single CA to a distributed network of ECPs, while maintaining the CA's ultimate authority over the trust anchor.

Demo / Proof of Concept

▶ Watch: How AccuRevoke generates and verifies revocation witnesses (6:00)

While the talk did not feature a live, interactive demonstration of AccuRevoke, the speakers presented a thorough evaluation of its performance through experimental results and simulations. These results served as a strong proof of concept, illustrating the practical viability and superior performance of their proposed system compared to existing revocation strategies.

The evaluation began by quantifying the costs associated with the accumulator:

• Accumulator evaluation: This is a one-time cost incurred by the CA to initialize the accumulator. The process benefits significantly from parallel processing, as shown in the presented graphs.
• Accumulator size: A critical metric, the accumulator size is a constant 21 bytes, regardless of the number of revoked certificates it contains. This remarkably small size is a major advantage for distribution and storage.
• Accumulator update time: On average, updating the accumulator (e.g., adding or deleting a revoked certificate) takes approximately 0.47 milliseconds, demonstrating its dynamic efficiency.

The performance of witness generation was also meticulously measured:

• Revoked certificate witness:
• Size: 21 bytes.
• Generation time: Approximately 0.46 milliseconds on average.
• Non-revoked certificate witness:
• Size: 61 bytes.
• Generation time: Initially, this was observed to be directly proportional to the number of accumulated revoked certificates, implying a potentially high cost for large revocation lists.

To mitigate the computational cost of non-revoked witness generation, especially given the high number of non-revoked certificates in practice, the researchers explored GPU acceleration. They noted that Cloudflare, a major CDN and potential ECP, already offers GPU services.

• Using GPUs, the time to generate a non-revoked witness was reduced to approximately 15 milliseconds.
• Further investigation revealed that a significant portion of this time was spent on data copying between CPU and GPU memory.
• By implementing amortization techniques to optimize this data transfer, they achieved an impressive 8.9-fold speedup, making non-revoked witness generation highly efficient.

The witness reconstruction time by either an ECP or the client was also evaluated, with its duration depending on the threshold value chosen by the CA for the Shamir secret sharing scheme.

The article concluded with a client behavior simulation to compare AccuRevoke against CRL, OCSP, and CRLite across key metrics:

• Data downloaded by client: For a scenario where a client visits 1,000 websites, AccuRevoke emerged as the "clear winner," demonstrating the lowest data download compared to all other strategies. This highlights its exceptional bandwidth efficiency.
• Delay experienced by client: AccuRevoke's delay was found to be "very similar to OCSP." While it was "slightly higher than the CRLite" due to CRLite's local revocation checking, the speaker emphasized that "given the advantages AccuRevoke has," this minor difference is acceptable.

These experimental results and simulations robustly demonstrate that AccuRevoke not only addresses the theoretical shortcomings of previous revocation schemes but also offers a practically implementable solution with superior performance characteristics in terms of bandwidth, latency, and computational efficiency, especially when leveraging modern hardware like GPUs and distributed edge infrastructure. The availability of source code on GitHub further supports its practical application and verifiability.

Defensive Implications

▶ Watch: AccuRevoke's robustness and pre-computation for efficiency (7:30)

AccuRevoke introduces several critical defensive implications for organizations, CAs, and individual internet users, significantly bolstering the security and privacy posture of the web.

Firstly, for Certificate Authorities (CAs), AccuRevoke offers a path to enhanced scalability and reduced operational burden. By offloading the computationally intensive task of witness generation to a distributed network of Edge Compute Providers (ECPs), CAs can avoid the overload issues that plague OCSP responders. This allows CAs to focus on their core responsibility of issuing and revoking certificates, while ensuring timely and efficient dissemination of revocation status without becoming a bottleneck. The system's robustness, allowing for ECP failures, also improves the overall resilience of the revocation infrastructure.

Secondly, website operators and service providers benefit from a more reliable and faster revocation mechanism. In the event of a private key compromise, the ability to quickly and widely propagate revocation information through AccuRevoke's distributed ECP network means that vulnerable certificates can be invalidated much more rapidly. This reduces the window of opportunity for attackers to impersonate legitimate services, thereby mitigating potential brand damage, data breaches, and financial losses. The system provides strong assurances that clients will receive accurate and up-to-date revocation status.

Thirdly, for defenders and security professionals managing client-side security (e.g., enterprise network administrators), AccuRevoke provides a more secure and private method for verifying certificate validity. Unlike OCSP, which can expose user browsing habits to CAs, AccuRevoke's use of Secure Multi-Party Computation (MPC) protects client privacy during witness generation. This is a significant improvement, as privacy-preserving revocation checks are crucial in sensitive environments. Furthermore, the low bandwidth and latency benefits mean that security checks can be performed more frequently without degrading user experience, leading to a more consistently secure browsing environment.

Fourthly, the architecture's reliance on CDNs as ECPs offers a natural defensive synergy. CDNs are already distributed globally and designed for high performance and availability. By adopting the ECP role, CDNs can enhance their value proposition by providing integrated, high-speed, and privacy-preserving certificate revocation services. This leverages existing, robust infrastructure to strengthen a critical security function at the network edge, closer to the end-users.

Finally, AccuRevoke contributes to a more decentralized and resilient trust model for revocation. By distributing the trust (in terms of witness generation) across multiple ECPs and using threshold secret sharing, the system avoids creating a single point of failure or an overly centralized trust burden, as seen in CRLite's reliance on Mozilla. This distributed trust enhances the overall security posture by making the revocation system more resistant to attacks targeting a single entity. Defenders should advocate for the adoption of such robust, privacy-preserving, and scalable revocation mechanisms to fortify the internet's trust infrastructure.

Key Takeaways

• AccuRevoke addresses the critical limitations of existing certificate revocation schemes (CRL, OCSP, CRLite) by offering a solution that is simultaneously scalable, private, bandwidth-efficient, and robust.
• The system leverages dynamic universal accumulators to represent revoked certificates in a constant, extremely compact size (21 bytes), enabling efficient updates and dissemination.
• Secure Multi-Party Computation (MPC) is employed among distributed Edge Compute Providers (ECPs) to generate revocation witnesses, ensuring client privacy by preventing any single entity from learning specific certificate queries.
• AccuRevoke significantly reduces client bandwidth consumption, demonstrating the lowest data download compared to other strategies when simulating client browsing behavior across 1,000 domains.
• Experimental results showcase efficient witness generation, with GPU acceleration and amortization yielding an 8.9-fold speedup for non-revoked certificates, making the solution practically viable for high-volume environments.
• The distributed architecture with ECPs (ideally CDNs) and threshold secret sharing ensures high availability and robustness, allowing the system to tolerate failures of individual ECPs without service interruption.

About the Speaker(s)

The primary speaker for "AccuRevoke: Enhancing Certificate Revocation with Distributed Cryptographic Accumulators" was Munshi Rejwan Ala Muid, a second-year PhD student at Virginia Tech. He presented the work as part of his research. The other authors and collaborators on this project, also affiliated with Virginia Tech, are Tijay Chung and Thang Hoang.