Range Queries Extension for OCSP

1.1. Conventions and Terminology

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here.¶

The following terminology is used throughout this document:¶

CLIENT: A client application accessing the OCSP responder to query for the status of a certificate.¶

RESPONDER: A client application accessing the OCSP responder to query for the status of a certificate.¶

OCSP: Online Certificate Status Protocol, version 1.¶

OCSP Extension: X.509 extension for OCSP requests or responses.¶

CRL: Certificate Revocation List.¶

CA: Certificate Authority.¶

DER: Distinguished Encoding Rules as defined in X.690.¶

PKI: Public Key Infrastructure, as defined in [RFC5280].¶

2.1. OCSP Range Queries

The OCSP Range Queries extension allows OCSP responders to provide only a handful of responses, thus removing the need for large CDN deployments or the need of shortening the lifetime of certificates with the ultimate goal of removing revocation checks (which breaks the trust model used in PKIs).¶

When the OCSP Range Query extension (i.e., OCSPRangeQuery) is provided in the OCSP request, the client indicates that they support range queries. In this case, if the responder does not provide support for range queries or the status associated with the requested serial number is revoked, the responder replies with a standard OCSP response that the client processes as usual.¶

However, when the responder supports range queries and the requested serial number is not revoked, the responder will reply with an OCSP response that carries the OCSPRangeResponse extension that specifies the range of certificates for which the response is valid.¶

The serial number of the CertID is set to a well-know value that the client ignores when the OCSPRangeResponse extension is present in the response. The client will then use the startCertID and endCertID values to determine the range of certificates for which the response is valid.¶

The startCertID and endCertID values are the first and last certificate serial numbers for which the response is valid (inclusive). If the startCertID is not present, the default value to use is 0. If the endCertID is not present, the default value to use is +Infinite (meaning the largest value supported).¶

2.2. The OCSP Range Queries Extension

When an OCSP client supports OCSP range responses, the client MUST include the OCSPRangeResponse extension with the value set to NULL. OCSP clients that do not support range queries SHALL NOT include the OCSPRangeResponse extension. The extension is defined as follows:¶

   id-range-response OBJECT IDENTIFIER ::= { id-pkix-ocsp 10 }

   OCSPRangeResponse ::= NULL

2.3. The OCSPRange Extension

When an OCSP client includes the OCSPRangeResponse extension in the OCSP request message, the responder MUST include the OCSPRange extension in the OCSP response message. The OCSPRange extension allows a responder to indicate the range of responses for which the response is valid. The extension is defined as follows:¶

   id-ocsp-range-response OBJECT IDENTIFIER ::= { id-pkix-ocsp 11 }

   OCSPRange ::= SEQUENCE {
       startCertID  [0]     INTEGER OPTIONAL,
                                --- Beginning of the range of certificates
                                --- for which the response is valid. If the
                                --- value is not present, the default value
                                --- to use is 0.

       endCertID    [1]     INTEGER OPTIONAL
                                --- End of the range of certificates for
                                --- which the response is valid. If the value
                                --- is not present, the default value to use
                                --- is +Infinite.
   \}

Where the startCertID and endCertID values are the first and last certificate serial numbers for which the response is valid (inclusive). If the startCertID is not present, the default value to use is 0. If the endCertID is not present, the default value to use is +Infinite (meaning the largest value supported).¶

3.1. Processing OCSP Requests

When an OCSP client sends a request to an OCSP responder and includes the OCSPRangeResponse extension, the responder builds the response to bew sent to the client according to the following algorithm:¶

IF OCSPRangeResponse extension is present in the request THEN
    IF OCSPRangeResponse extension is supported by the responder THEN
        IF the requested serial number is not revoked THEN
            Include the OCSPRange extension in the response
            Set the startCertID and endCertID values in the OCSPRange extension
        ELSE
            Do not include the OCSPRange extension in the response
            Send the standard OCSP response for the revoked certificate
        END IF
    ELSE
        Send the standard OCSP response for the revoked certificate
    END IF
ELSE
    Send the standard OCSP response for the revoked certificate
END IF

When a responder does not support the OCSPRangeResponse extension, the responder SHALL ignore it and respond with a standard OCSP response that the client processes as usual.¶

3.2. Processing OCSP Responses

When an OCSP client receives a response from an OCSP responder, the client processes the response according to the following algorithm:¶

IF OCSPRange extension is present in the response THEN

    1. Ignore the serial number used in the CertID and Use the startCertID
       and endCertID values in the OCSPRange extension to determine if the
       response is valid for the certificate in the request.

    2. Process the response as usual

ELSE
    1. Process the response as usual

END IF

3.3. Pre-Computation of OCSP Responses

To optimize the performance of the OCSP responder, the responder MAY pre-compute the responses for the ranges of active certificates population (one for each revoked certificate or range of revoked certificates plus one for each of valid certificates).¶

For example, when the population of active certificates is 1,000,000 (1,000 of which are revoked), the responder, instead of pre-computing 1,000,000 responses, only pre-computes the responses for the ranges of certificates that share the same status (revoked or valid) according to the following algorithm:¶

# Load the current CRL
aCRL :== Load(CRL)

# Sort the CRL by certificate serial number {R0, ..., RN}
aCRL :== Sort(aCRL)

# Initialize the variables
aStatus :== VALID
aRangeStart :== 0
aRangeEnd :== 0
idx :== 0

# Process the CRL entries
FOREACH aEntry in the aCRL DO

    # Check the status of the current range
    IF aStatus == VALID THEN
        # We are in a range of valid certificates
        aRangeEnd :== aEntry - 1
        Responses(idx++) = Valid{aRangeStart, aRangeEnd}

        # Start for the next set of revoked certificates
        aRangeStart :== aRangeEnd :== aEntry.serial
        aStatus :== REVOKED

        # Skip to the next entry
        CONTINUE
    ELSE
        # The next entry is the next serial, we can extend the range
        IF aEntry.serial == aRangeEnd + 1 THEN
            # Extend the current range of revoked entries
            aRangeEnd++
            CONTINUE
        ELSE
            # Generate "REVOKED" response for the previouse range
            Responses(idx++)=Revoked{aRangeStart, aRangeEnd}

            # Sets the "VALID" response for the current range
            aRangeStart :== aRangeEnd + 1
            aRangeEnd :== aEntry.serial - 1
            Responses(idx++) :== Valid{aRangeStart, aRangeEnd}

            # Prepare for the next range of revoked entries
            aRangeStart :== aRangeEnd :== aEntry.serial
            aStatus :== REVOKED
        END IF
    END IF

For example, for a CA with an active population of 10,000,000 certificates and a revoked population of 1,000 certificates, the responder will generate one response for the range of serial numbers from 0 to the first revoked certificate, one response for each range of certificates with the same status (revoked or valid), and one response for the range of serial numbers from the last revoked certificate to the largest serial number supported (i.e., +Infinite). In case all 1,000 revocation entries are not contiguous, the responder will generate 1,002 responses instead of 10,000,000 responses.¶

For high-performance OCSP responders, the pre-computation of responses for the ranges of certificates is a viable solution that can optimize the performances of responders: by reducing the number of responses that need to be generated, the responder can produce the responses in few seconds every few minutes/hours and directly serve them from memory or cache.¶