Making Cert-to-CRL bindings fully static

[aarongable]

Today, our certs are assorted into CRL shards at the time those shards are generated. The decision of which shard a cert will end up in is based on: the number of shards, the configured "chunk width", and the cert's notAfter timestamp. This is good, and prevents us from moving certs between shards unnecessarily.

However, it is not good enough for us to be able to include CRL URLs directly in our certs. In order to do that, the mapping needs to be fully static.

#7007 was a necessary prerequisite for this work.

Our design is as follows:

---

Phase 1: Populating the revokedCertificates Table

We create a new database table with the following schema:

CREATE TABLE `revokedCertificates` (
`id` bigint(20) NOT NULL AUTO_INCREMENT,
`issuerID` bigint(20) NOT NULL,
`shardIdx` bigint(20) NOT NULL,
`notAfter` datetime NOT NULL,
`serial` varchar(255) NOT NULL,
`revokedDate` datetime NOT NULL,
`revokedReason` int(11) NOT NULL,
PRIMARY KEY (`id`),
KEY `notAfter_idx` (`notAfter`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4
PARTITION BY RANGE(id)
(PARTITION p_start VALUES LESS THAN (MAXVALUE));

This table has all of the information necessary to look up revoked certificates quickly by shard, and all of the information necessary to populate a Revoked Certificate entry in a CRL. All columns are NOT NULL because rows will only be inserted when a certificate is actually revoked, and all of this information is available.

We augment the SA’s RevokeCertificate method to take a new parameter, the CRL shard to which the certificate belongs. If it receives a request which contains a shard index, it writes a row to the new revokedCertificates table in addition to its current update to the certificateStatus table.

We augment the RA with the same CRL bucketing configuration parameters as the crl-updater has, specifically NumShards and ShardWidth, which control which shard a certificate falls into. We also add to the RA a version of the shard computation code which can quickly determine the correct shard number given the config values above and a certificate’s notAfter date. When the RA processes a revocation request, it will compute the shard index for that certificate, and include it in the request to the SA, triggering the codepath described above.

---

Phase 2: Using the revokedCertificates Table

When Phase 1 has been deployed for more than 90 days, and we are sure that all unexpired revoked certificates have rows in the revokedCertificates table, we can begin reading from it instead of reading from the certificateStatus table.

We will augment the SA’s GetRevokedCerts method to take a new parameter, the CRL shard which is being queried. If it receives a request which contains a shard index, it will query the revokedCertificates table instead of the certificateStatus table, and will include the shard index as an additional WHERE clause in the query.

We then greatly simplify crl-updater’s query mechanism. Rather than using its configuration parameters to compute complex sets of ExpiresBefore and ExpiresAfter dates that contribute to each shard, it will instead send a single query per shard, including that shard ID in the request to the SA. The request will still include ExpiresAfter and ExpiresBefore timestamps, because the crl-updater is the only entity which knows how far back our look-back needs to go and what timestamp is being used as the cutoff for this CRL.

[aarongable]

Implementation plan:

1. Create the table, fully implement the updated versions of RevokeCertificate, UpdateRevokedCertificate, and GetRevokedCertificates. None of the new code will be active until other components begin supplying shard indices in their requests.
2. Wait one deployment cycle, for the table to be created and the gRPC methods to be deployed.
3. Add code to the RA (and admin-revoker?) to compute and supply a ShardIdx when revoking a certificate. This will activate the RevokeCertificate and UpdateRevokedCertificate code paths.
4. Wait 100 days to ensure that all unexpired revoked certificates are represented in the new table.
5. Add code to the crl-updater to request revoked certs by shard, rather than by chunk boundaries. This will activate the GetRevokedCertificates code path.
6. Clean up old code paths.

This bug tracks all stages of this implementation plan.

[aarongable]

IN-9706 has been file to track creating the new table in prod. I've begun work on the RA code which cannot land until after the table actually exists.

[aarongable]

We've always known that this project would involve touching the CA's CRL issuance code. However, I incorrectly believed that that work would be able to be put off until it was time to actually include CRL URLs in our certs. Comments on #7133 have made it clear that no, that work should actually happen now. I'm tracking that work in #7159, which blocks this bug.

[aarongable]

This is not a hard computer science problem, but it is a hard engineering problem. Deciding the separation of responsibilities between the RA and the SA, encapsulating logic, preventing config from being duplicated between too many different services, etc.

Current plan:

• RA gets configured with number of CRL shards
• At issuance time, RA determines shard randomly, and informs CA of which shard the cert should be in
• CA uses this to bake the CRL URL into the cert
• At revocation time, RA parses the CRL URL out of the cert and writes the shard number into the revokedCerts table for the crl-updater to use

[jsha]

Current plan:

• RA gets configured with number of CRL shards
• At issuance time, RA determines shard randomly, and informs CA of which shard the cert should be in
• CA uses this to bake the CRL URL into the cert
• At revocation time, RA parses the CRL URL out of the cert and writes the shard number into the revokedCerts table for the crl-updater to use

How does this interact with certificates issued under the current scheme that uses temporal sharding?

Proposal: at CRL generation time, check for certificates by both issuance time and shardIdx.

Specifically, modify GetRevokedCerts (

boulder/sa/saro.go

Lines 1062 to 1068 in 7137605

	func (ssa *SQLStorageAuthorityRO) GetRevokedCerts(req *sapb.GetRevokedCertsRequest, stream grpc.ServerStreamingServer[corepb.CRLEntry]) error {
	if req.ShardIdx != 0 {
	return ssa.getRevokedCertsFromRevokedCertificatesTable(req, stream)
	} else {
	return ssa.getRevokedCertsFromCertificateStatusTable(req, stream)
	}
	}

) so that instead of doing something completely different when shardIdx is present, it does something additional (checks the revokedCertificates table) and combines the results.

Once that's deployed, modify crl-updater to unconditionally pass ShardIdx in its call to GetRevokedCerts.

Then add the code to recognize embedded CRL URLs at revocation time and write to revokedCertificates.

Then add the code to generate embedded CRL URLs at issuance time.

[aarongable]

I believe that plan would naively result in some certificates being included in multiple CRL shards -- they'd appear in one shard due to temporal sharding, and appear in a different shard due to the RevokedCerts table (if they were revoked after the RA starts supplying a shard number at revocation time).

The original plan was to have the RA supply a shard number, then wait for all certs that were revoked without a shard number to expire (so we have 100% coverage), then flip the flag. This would cause certs to move between shards, but they'd never be duplicated. And it would take 3 months to bake.

I think that your idea works, and works much faster, at the cost of temporarily inflating our CRL sizes. I'm not personally aware of any compliance issue with a cert appearing in multiple shards of a sharded CRL, as long as the data in each entry is identical.

[jsha]

Yes, it would definitely result in most revoked certificate showing up in two shards - its temporal shard and its explicitly assigned shard. I also think this is okay.

If we want to avoid that, another option: when assigning explicit shards (at issuance time), assign them from a range of numbers that don't overlap with the temporal sharding range at all. This would require temporarily doubling the number of shards we publish in CCADB. This has the advantage that it might be a little more obvious to debug. "This shard number is > 2000, so we expect it to be filled with certificates that had an explicit shard assigned at issuance time."

[aarongable]

I think simply inflating our current shards is the simpler and better solution. I'm doing some digging now, but so far nothing has popped up to indicate this would be a compliance issue.

[jsha]

#7918 is out for review.

Of course, having made that change and updated the tests, I'm now wondering: perhaps it would be better to expose a new SA RPC: GetRevokedCertsByShard, which only returns certificates by their explicit shard. Then the crl-updater could be responsible for calling both endpoints and merging the results. This would have some advantages:

Any possible memory bloat would be taken by the crl-updater (which already has some memory bloat), not the SA.

Also, it would let crl-updater get clever about when the "last" temporal shard is - that is, the last span of time that covers certificates without a CRLDP.

[aarongable]

I do like the idea of having crl-updater take the memory bloat, rather than the SA.

It could be done even without the new method: GetRevokedCerts's behavior could be conditioned on the presence of the ShardIdx field, doing only temporal if it is missing and only explicit if it is provided.