Why Do Certificate Revocation Checking Mechanisms Never Work?

The certificate revocation system, just like any other cyber security mechanism, is needless, as long as everything is going well, but becomes essential when things go wrong, namely a certificate has been compromised. A compromised certificate makes it possible for a malicious third party to create a service that acts like the legitimate one or insert itself as a man-in-the-middle eavesdropping on any data transferred between the parties without any knowledge of the client or the server. The revocation system is about to give a chance to the client to learn a server certificate is revoked, as it has been compromised. Nothing shows better that we are facing a severe problem than the fact that several thousand certificates are revoked day by day.

Unfortunately, the revocation checking mechanisms have several theoretical and practical difficulties. Although the basis of the mechanisms is revocation, this alone is far from sufficient. There should be a revocation checking mechanism that could work under actual circumstances. Each stakeholder – client application developers, server administrators, middleware solution manufacturers, certificate authorities – have their requirement, and none of the existing revocation check mechanisms can satisfy all the requirements. It must be stated when a certificate gets compromised, we should assume that a malicious third party – who has no authority over the host(s), to which the certificate belongs – could impersonalize any service (web, mail, remote access, etc.) with any domain names the certificate is validated to. The situation should last only as long as the certificate is revoked, but clients have challenges learning the fact of revocation.

Revocation Check Mechanisms

First, take stock of the possibilities in chronological order and summarize how they work and their main issues.

1. Certificate Revocation List (CRL): The oldest mechanism which is nothing else than the collection of the revoked, but not expired certificates managed and published by certificate authorities. It is useless to keep the expired certificates on the revocation list as the expired certificates are handled as invalid by the clients independently from the fact that they have been revoked or not. As the Let's Encrypt CAA checking issue showed, it can happen that a certificate authority must revoke millions of certificates at the same time. In that case, the CRL size dramatically grows, and all the client applications (e.g., browsers, mail clients, ...) that want to check the revocation state of a certificate must download a large CRL file.
2. Online Certificate Status Protocol (OCSP): The mechanism aims to solve the size issue that CRL suffers from by making it possible to ask a central server, OCSP responder, about the revocation state. Any client can send a request to an OCSP responder – managed by the certificate authority – whether a certificate issued by that certificate authority is revoked or not. In terms of information theory, revocation state is just a bit of information that is not affected by the number of actually revoked certificates but makes it possible to track the client by its requests.
3. OCSP Stapling: OCSP Stapling is currently the best method for checking certificate validity. In the case of this mechanism, the server proves that the certificate authority has not revoked the certificate that it will show the client. The server obtains a time-stamped ("stapled") proof from the certificate authority, which has issued the server certificate, about the revocation state and caches it. When a client connects to the server, it offers the cached proof during the TLS handshake. This mechanism transfers the responsibility of the certificate revocation state serving from the certificate authority to the server maintainers. As the mechanism is optional, revocation check state serving depends on the server's capability and configuration.
4. OCSP Multi-Stapling: The mechanism is almost the same as the OCSP Stapling. The difference is that in part of OCSP Stapling, a server can send only one staple during the TLS handshake, but OCSP Multi-Staple makes it possible to send multiple staples, not only for the server certificate but also for the intermediate ones. Although this mechanism makes it possible to check the whole certificate chain, the most famous cryptographic library (OpenSSL), does not support it.

Problem factors

The evolution of the certificate revocation check mechanisms is not a success story. There are several stakeholders, and they sometimes have slightly different requirements against the certificate revocation system. Although the primary influence factor should be security, the operability challenges sometimes undermine this principle. Revocation check mechanisms cannot fulfill all the requirements of security professionals, software vendors, or user needs at the same time, which causes revocation check mechanisms to fail.

	CRL	OCSP	OCSP Stapling	OCSP Multi-Stapling	OCSP Stapling (TLS 1.3)
Source	✗	✗	✓	✓	✓
Integrity	✗	✗	✓	✓	✓
Access	✗	✗	✓	✓	✓
Size	✗	✓	✓	✓	✓
Privacy	✓	✗	✓	✓	✓
Full Chain	✓	✓	✗	✓	✓
Validity	✓	✗	✗	✗	✗
Penetration	✓	✓	✗	✗	✗

As you can see, there is no silver bullet of certificate revocation check mechanisms. Newer and newer mechanisms have appeared, but they could not solve the issues and only changed pre-existing problems into new ones.

Source

The first issue we have to discuss is how systems can know the source of revocation state information. Without this information, none of the stakeholders, client software (e.g., web, mail, remote access clients), middleware devices (e.g., firewalls) cannot acquire the essential information. The problem itself is independent of the type of the client software. It only depends on the kind of revocation check mechanism.

• Certificate Revocation List (CRL): There is an X.509 extension in the issued certificate, called CRL distribution points (CDP), which may contain one or more URIs pointing to the CRL, managed by the issuer certificate authority (CA). The problem is that the CDP extension is non-critical, so not necessarily found in a certificate. However, the vast majority of the certificate authorities fill the extension (filled in 2207 out of 2233 intermediate CA certificates), but not all of them. Middleware devices could use certificate revocation lists very effectively as they have the necessary resources to prefetch the information on which certificates have been revoked and regularly update that. The list of distribution points of all the certificate authorities is a prerequisite, but there is no official list, even though the PKI is a highly centralized system. Mozilla has an intermediate CA certificate collection, which can be used to achieve the CDP locations in the case of the intermediate certificates but cannot be used in case of server certificates. The latter would be more important as the probability of compromise is much higher in a server certificate than an intermediate one. It should also be considered that the number of server certificates is much higher than the number of intermediate certificates. Anyway, CRL fetching could be done on the fly when a connection has been initiated, but it may take a relatively long time. Until the fetch has finished, the client must be awaited, which may cause significant latency for the client.
• Online Certificate Status Protocol (OCSP): The working method is almost the same as the CRL. There is an X509 extension in the issuer certificate, called Authority Information Access, which may contain one or more URIs pointing to the OCSP responder of the CA. The problem is that the extension is non-critical, so it is not necessarily found in a certificate. Although the vast majority of the certificate authorities fill the extension (filled in 1994 out of 2233 intermediate CA certificates), there is still a shortage. Middleware devices could use OCSP responders to prefetch, cache, and update the revocation information of the most popular sites. Still, there is a prerequisite – the OCSP responder locations of all the certificate authorities – which is not satisfying lack of an official list of responder URLs, even if the fact that Mozilla's intermediate CA certificate collection can also be used to achieve the OCSP responder locations of the intermediate certificates, but cannot be used in case of server certificates.
• OCSP Stapling: The source question does not occur according to the working method as the proof about the revocation status of the server certificate is sent by the server itself, so no extra information (URI) is needed to achieve it.

Integrity

Data integrity is an important question when discussing revocation mechanisms, as the client must be sure that a malicious third party cannot modify the revocation information. The revocation information goes without encryption on the network, but this in itself is not a problem.

• Certificate Revocation List (CRL): The most commonly used protocol to achieve the CRL is HTTP, not HTTPS, regardless that HTTP cannot guarantee either the integrity of the CRL or the whole HTTP traffic. The CRL is digitally signed by the certificate authority that manages and publishes the CRL and has earlier issued the certificate that has been revoked later, so a malicious third party cannot forge it without the user's knowledge, assuming that it verifies the signature. Modifying the HTTP traffic during a man-in-the-middle attack could not compromise the CRL directly. Still, it can indirectly disrupt download by changing HTTP-related parameters, forcing clients to use a soft fail mechanism. It must be noted that the hash algorithm of the CRL's digital signature is as important an issue as in the case of certificate signing.
• Online Certificate Status Protocol (OCSP): OCSP responders also use the HTTP protocol to serve the responses, just like CRL distribution points. The certificate authority issued the certificate whose revocation state is in question, manages the responder, and digitally signs any response. The integrity of OCSP responses is guaranteed identical to CRL distribution points, and disruption can be done in the same way.
• OCSP Stapling: The server provides the OCSP staple during the cleartext part of the TLS handshake. As the certificate authority digitally signs the staple with the certificate used to sign the server certificate, the integrity is implemented in the same way as for CRL distribution points and the OCSP responders. Anyway, the TLS handshake closes with a verification, where the parties calculate the checksum of the handshake received by them from the other party and compare it with the checksum sent by the other party in the encrypted form integrity is double-checked in that way.

Access

Client applications may have difficulties accessing revocation state information, primarily when a firewall or other security system controls the internet and the revocation information comes from another server than the original server that the client wanted to be accessed.

• Certificate Revocation List (CRL): Revocation information comes from a different IP address (CDP IP address instead of the server's one), port (80 instead of 443). It uses a different protocol (HTTP instead of HTTPS) than the original server. According to these differences, the firewall policy may not permit the client to access the CDP, even if it permits accessing the server.
• Online Certificate Status Protocol (OCSP): The problem is precisely the same as in the case of the CRL distribution point. OCSP responders are also on different IP addresses (OCSP responder IP address instead of the server's one), port (80 instead of 443), and use a different protocol, so the OCSP could not solve the problem that occurred on CRL distribution points.
• OCSP Stapling: As the server sends OCSP staple during the TLS handshake, the problem is not applicable, as the client application has already accessed the server. Only the OCSP stapling could fully solve the problem of access.

Size

As the Let's Encrypt CAA checking issue showed, it can happen that millions of certificates must be revoked at the same time, so a revocation check mechanism must be able to handle that case.

• Certificate Revocation List (CRL): The CRL size can grow dramatically. All the client applications (e.g., browsers, mail clients) that want to check a certificate's revocation state must download the CRL file. The revocation list is an unsuitable mechanism for client software as the size may extend suddenly. Even small revocation lists would cause significant memory usage on mobile devices because clients should store all the revocation lists of the considerable amount of intermediate certificates in memory. Regular updates of the revocation lists would cause significant traffic charges, which may have financial implications on mobile devices. Major browsers do not use this mechanism at all. Chrome and Firefox have their mechanism respectively called CRLSets and OneCRL to solve the problem. CRL collections maintained by Google and Mozilla are updated regularly in the background without restarting or updating the browser. Several other browsers and other clients (e.g., mailing clients) do not use CRLs at all. For middleware devices, revocation lists could be the optimal solution. They could prefetch, regularly update, and cache the revocation lists, as the vast majority of certificate authorities support the revocation list both in intermediate and root certificates, so they can use revocation lists to check a complete certificate chain. However, there are massive deficiencies. The first one is the fact that the most popular certificate authority does not support CRL for server certificates, so almost 200 million actively used certificates cannot be checked that way. The second is that middleware devices can not prefetch CRLs without an official list of all CRL distribution points. CRL is a comfortable mechanism for certificate authorities as client applications (e.g., browsers) mostly do not use it. Meaning there is no considerable load on CRL distribution points from distributed sources, making it difficult to defend against a DDoS attack.
• Online Certificate Status Protocol (OCSP): The mechanism solves the size issue that CRL suffers from by making it possible to ask a central server, OCSP responder, about the revocation state. Any client can send a request to an OCSP responder, managed by the certificate authority, whether a certificate issued by that certificate authority is revoked or not. It is just a bit in terms of information theory, and the amount of information is not affected by the number of actually revoked certificates. OCSP completely solved the size problem for client software as it is small enough to download it even for all new connections. For middleware devices, the size has never been a significant problem. The necessary bandwidth is given in a typical environment where they are used. Nevertheless, OCSP is imperfect as OCSP responses cannot be prefetched and used as a database like a certificate revocation list. However, it can be fetched on-demand and cached for later use for a moderate amount of time. For certificate authorities, it is a comfortable mechanism. In practice, no client uses that mechanism to check the certificate revocation, so it causes minimal load on the OCSP responder.
• OCSP Stapling: As OCSP staple has almost the same size as an OCSP response, the size problem has been solved for both client software and middleware devices. It is especially true since the server sen the OCSP staple, so it is just some extra bytes during the TLS handshake. For the certificate authorities, OCSP stapling is a demanding mechanism, if we consider that a certificate authority can have 200 million active certificates, which is the actual case of Let's Encrypt. Only if a third of servers supported OCSP stapling and a validity period of the staple was 5 minutes, it would result in 200.000 requests per second on the OCSP responder, which is apparently causing difficulties.

Privacy

We can think of certificate revocation states as a database, where the fact of a query is sensitive data as if you perform a query for a certificate of a specific website, likely, you are just visiting that site so that you can be tracked in that way. As the overwhelming majority of the web traffic nowadays is encrypted, the overwhelming majority of the traffic can be tracked in that way.

• Certificate Revocation List (CRL): A certificate revocation list can be considered a database, so the problem is not applicable, as the whole database can be downloaded and queried locally, not on the certificate authority side.
• Online Certificate Status Protocol (OCSP): An OCSP response contains verified information about the revocation state of a certificate that has been issued by a CA managing the OCSP responder, so the OCSP request that the client has sent must contain information that identifies the certificate in question. A certificate is issued for a domain that the client wants to visit, so by an OCSP request, the CA learns what domain the client visited. For a client software, it is a considerable risk as this mechanism makes the user of the client software trackable by a third party whose responsibility would be to increase the privacy level, not to decrease it. For a middleware device, it can be a considerable risk, as the organization using the device can be tracked, but a specific member of the organization is not.
• OCSP Stapling: OCSP staples are served by servers, so the problem is not applicable, as the client application has already accessed the server so that it can be tracked by the server anyway.

Full Chain

Certificate revocation checking should not be limited to the server certificate itself. Revocation check of the issuer certificates is also essential. If an intermediate certificate is compromised, any server certificate can be issued to any domain by the malicious third party that compromised the certificate. Revocation check of a root CA certificate is like a serpent eating its tail. They are self-signed, so they verify themselves.

• Certificate Revocation List (CRL): As the vast majority of the certificates, both intermediate and leaf ones, contain CRL distribution points, their revocation state can be checked by CRLs so that the complete certificate chain can be checked in practice.
• Online Certificate Status Protocol (OCSP): As more than ten percent of the intermediate CA certificates do not contain OCSP responders, their revocation state cannot be checked by OCSP. If we want to be sure, the revocation check must be combined with CRL checking.
• OCSP Stapling: As discussed earlier, this mechanism depends on the certificate authority OCSP support. Hence, customers of almost ten percent of the certificate authorities cannot provide OCSP stapling as a mechanism to the clients. Another major problem is that a server can send only one revocation state during the TLS handshake before TLS 1.3. In contrast to CRL and OCSP, a client cannot validate the full certificate chain but just the server certificate itself. For client software, OCSP stapling might even be suitable, as mechanisms like CRLSet or OneCRL can check intermediate certificates. For middleware devices, OCSP stapling could be a perfect mechanism as server certificates can be checked by OCSP stapling, and other certificates can be checked by CRLs. Still, we must not forget about the relatively low level of server support, 34-36 percent among the top 150 thousand domains, in that case.

The situation is exacerbated by the fact that more than one percent of the intermediate CA certificates contain neither CRL distribution points nor OCSP responder, making the whole chain revocation check impossible in the case of these certificate authorities.

Validity

Certificate status information – independently from the revocation check mechanism – must be verified by the certificate authority which issued the certificate in question. Without this, the status information would not be authoritative, and a malicious third party can modify it without the knowledge of the peer who tries to verify the status information.

• Certificate Revocation List (CRL): Revocation lists can be signed by the certificate authority, which issues the server certificate directly or indirectly. It can be verified easily – when the revocation list is signed by the issuer of the server certificate – as the peer must have all the issuer certificates to verify the server certificate itself. There is an additional step if the revocation list is signed indirectly by the issuer of the server certificate, as the revocation state of that intermediate certificate – which has signed the revocation list – has to be also checked, which means that we have to acquire revocation list for this intermediate certificate. This revocation check mechanism highly depends on digital signatures, as the integrity of the revocation list is guaranteed by a signature. Weak signature algorithms (e.g.: MD5, SHA1) have completely disappeared as a certificate signature algorithm – according to Qualys SSL Pulse – but already used as a signature algorithm of the revocation lists, which potentially makes possible compromising the revocation information. Two fields control the lifecycle of a revocation list. The update field shows when the CA issued the revocation list. The revocation list will be issued no later than the value of the next update field, independently of whether the content of the revocation has been changed. A revocation list is considered valid between these two dates, apart from delta CRLs – however, updating the revocation list before a validity check is necessary.
• Online Certificate Status Protocol (OCSP): OCSP responses, just like revocation lists, can be signed by the certificate authority which issues a server certificate directly or indirectly, so the problem is the same as it was in the case of the revocation list. There could be an intermediate certificate in which revocation state should also be checked, so an extra OCSP response or revocation list should be acquired. OCSP responses also depend on digital signatures. They still use weak signature algorithms even though OCSP is a more modern revocation check mechanism than the revocation list. OCSP requests and responses contain the hash of the issuer's distinguished name and the hash of the issuer's public key to identify the issuer, so there is another place where weak hash algorithms are possibly used. OCSP responses contain this update and next update fields defining a recommended validity interval, just like revocation lists. This interval corresponds to the this update and the next update interval in revocation lists. OCSP responses where next update value is earlier than the current time or the this update value is later than the current time should be considered unreliable.
• OCSP Stapling: The situation is almost the same as in the case of OCSP, but there is an additional issue we have to consider. Along with the fact that the server serves OCSP staple, the validation cannot be entirely performed without checking the staple issuer's revocation state, which needs acquiring an OCSP or a revocation list from another port of another server with notable latency.
• OCSP Multi Stapling: OCSP multi stapling cannot solve all the issues above. Although a server can send staples about the revocation state of the server certificate and all the intermediate certificates, the number of OCSP staples must not be higher than there were the number of certificates in the chain, so delegated OCSP issuer certificates are uncovered. TLS 1.3 deprecates OCSP multi stapling, but OCSP staple can be attached to each certificate in the chain, that would seem correct at first sight, but it suffers from the same problem as OCSP multi-stapling. Suppose delegated certificates are used to issue the OCSP responses. In that case, a server cannot send their revocation status to the client part of the TLS handshake, so the comprehensive revocation check needs either extra OCSP requests causing additional latency or prefetched revocation lists that traces back OCSP stapling to the plain old revocation list.

Penetration

• Certificate Revocation List (CRL): As CRL is the oldest revocation check mechanism, the original RFC (2459) was published more than twenty-one years and the latest major update was released seven years ago, cryptographic libraries support it very well.
• Online Certificate Status Protocol (OCSP): As OCSP is not a new story, the related RFC (6960) was released eight years ago, cryptographic library support is vital.
• OCSP Stapling: The mechanism cannot be considered new, as there is a proposed standard from eight years ago, and the technical background is the same as OCSP, so both cryptographic libraries and significant web servers have been supporting the mechanism for several years, but it must be noted that early TLS versions do not support OCSP Staple extension. For server software, OCSP stapling is a demanding mechanism because they have to take over a part of the burden from the OCSP responder as they have to be the reliable sources of the staple. For server maintainers, OCSP stapling is a risky mechanism. For security reasons, the OCSP stapling should go together with the OCSP Must-Staple extension in the certificate, which tells the client if a certificate with that extension is served. An OCSP staple must also be served, but if there is an outage on the OCSP responder side or any fetching problem on the server-side, it causes validation failure on the client-side. However, browsers do soft fail revocation check, meaning if the requested staple is not served or not served fast enough, browsers will ignore it. Because of that or not, only the third of the top 150.000 sites provides OCSP stapling, and the dynamic growth in recent years (3-5 percent point per year) seems to have come to a halt.
• OCSP Multi Stapling: Although OCSP multi stapling RFC (6961) published right after the OCSP RFC, the most popular cryptographic library, OpenSSL, does not support it neither in its latest stable release (1.1.1g), nor in its development release (3.0 alpha3), even though one of its competitor, wolfSSL, has OCSP multi stapling support since 2017.

Nowadays the focus is on the major browsers, however the problem is the same when we are using a minor text-based web browser or a popular command line tool in an automated environment. Not to mention that although the majority of the internet traffic is HTTPS, we should not forget about the several other protocols (FTP, IMAP, LDAP, LMTP, MySQL, NNTP OpenVPN, POP3, PostgreSQL, RDP, Sieve, SIP, SMTP, XMPP, …) which use TLS, and some others (IPSec/IKE, WireGuard, QUIC, ...) which are not, but may also be affected by the problems of certificate revocation.

Conclusions

The revocation check system has some theoretical and practical problems, making the situation difficult for all stakeholders (client, server, middle application, cryptographic library developers). No revocation check mechanism can fulfill the requirements alone, and their combination also had severe difficulties. The TLS version 1.3 solves the theoretical problems – making it possible to serve OCSP staple for each certificate in the chains – in vain if it increases the load on the shoulders of client and server software developers and decentralizes the problem by involving the new player in the game, namely the system administrator, who is responsible for making this best mechanism available for the customers. In vain, the more and more recent versions of revocation check mechanisms (OCSP, OCSP stapling, and OCSP multi stapling) when they may still trace back to the plain old CRL. In vain is the high penetration of CRL if some certificate authorities do not support this mechanism. In vain, PKI is highly centralized if there is no official collection of revocation check resources. There are too many tripping hazards to do it flawlessly.

---

Licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Photo by Bernard Hermant on Unsplash.