Building certgrep.sh: a free certificate transparency search engine

Certificate transparency is one of the best public datasets in security. Every certificate issued by a publicly trusted certificate authority lands in an append-only, cryptographically verifiable log, usually before the certificate is ever used. For anyone hunting malicious infrastructure, that makes certificate transparency (CT) one of the earliest observable signals there is. The certificate for a lookalike domain typically shows up in a log before the site serves its first byte.

Having access to such a dataset is one of the key ways we are able to power our detections and being tied to a third-party means that we are directly pegged to their uptime, capabilities, and costs. Culturally we strongly believe that all aspects of our detections should be engineered internally, from the ground up, for our specific use-case(s) and whenever possible, provide it back to the community or the general public.

We built certgrep.sh so that anyone can search (grep) certificates, with full regular expression (regex) support, for free. In this blog post, we wanted to cover the technical underpinning behind certgrep, and how deliberate tradeoffs allowed us to offer this to the community as well as utilize it internally. It covers the first design, which we ran in production for about three months, the specific wall we hit with it, and the pivot that made giving the whole thing away viable.

The problem#

certgrep.sh started as an internal tool. Our detection pipeline at Have I Been Squatted constantly needs to query CT logs at scale, where every existing option was a bad fit for either technical or financial reasons. The free public search tools were either unreliable or could not keep up with the query volume we needed. Commercial APIs could keep up, but slowly, and at a price that made putting them on a hot path absurd. We were going to have to run our own index regardless, so the only question that mattered was what, exactly, it needed to hold.

Certificate transparency is a firehose. Across all active logs, entries arrive at a rate of tens of millions per day, and each entry carries a few kilobytes of encoded certificate and chain material.

Storing all of it in order to search a fraction of it is expensive and operationally heavy. Borrowing someone else's index means taking whatever query semantics they hand you, usually exact or substring matching over names.

Neither worked for us -- our key insights are not actually about certificates, but rather about domains. More specifically the occurrences of domains. Certificate metadata is secondary to that.

When our detection pipeline asks a question, it is a question like "has any fully qualified domain name (FQDN) matching this pattern appeared in certificate transparency in the last 90 days, and when, and in which log". The certificate itself, the chain, the issuer, the key material, all of it is secondary. It matters occasionally, for enrichment or takedown evidence, but it is never on the hot path. The hot path is name lookup, and increasingly name lookup by regular expression, because typosquatting and phishing patterns are naturally expressed as patterns, not literals.

There is a second half to that insight, and it is the part that makes the economics work. Anything our pipeline actually matches on, we persist ourselves anyway, so the index never has to be the system of record. It only has to answer one question quickly, over a recent window, and hand back a pointer for the rare moment someone wants the certificate itself. We suspected this was not unique to us. Most analysts we know reach for certificate transparency the same way: has this pattern shown up lately, and where.

Once you accept that, storing certificates starts to look absurd. You would be paying to persist gigabytes per day of data you will read approximately never.

The entire system begins to take shape around this decision. Domains go in, certificate stay out, and the public logs double as the cold store.

Attempt one: finite state transducers#

The first engine was built on finite state transducers (FSTs), via the Rust fst crate. An FST is a finite state machine used as a data structure rather than as a model of computation. Take an ordered collection of keys and compile it into a deterministic acyclic automaton where the keys live in the transitions themselves. Ian and I were on a train ride somewhere in the UK reading about the structure and were immediately fascinated. Feed the machine a string byte by byte, and the string is in the collection if and only if it lands in a final state. Think of it as a trie (another fun data structure) that shares suffixes as well as prefixes, minimized into a single machine. There are some caveats to this, but Andrew's extensive blog below covers it far better than we ever could.

Three properties made it look perfect for us. Lookups cost time proportional to the key length, independent of how many keys are stored. The whole structure is a flat byte sequence you memory-map (mmap) straight from disk, with no deserialization step. And because the collection is itself an automaton, you can intersect it with another automaton, which is how a regex runs over it: compile the pattern to a deterministic finite automaton (DFA), intersect, walk the resulting tree, and prune entire subtrees of the key space that can never match.

The canonical treatment is Andrew Gallant's Index 1,600,000,000 Keys with Automata and Rust, written by the author of the fst crate. It remains one of the best data structure posts on the internet, and its headline experiment is why we started here: 1.6 billion deduplicated Common Crawl URLs, 134 GB of raw keys, compiled into a single 27 GB index that serves regex queries in fractions of a second. Domain names are an even friendlier corpus than URLs. They are short, highly repetitive strings with enormous shared structure, so they compress absurdly well.

Building one is pleasant:

let mut builder = SetBuilder::new(writer)?;

// Keys must be inserted in lexicographic order
for fqdn in sorted_fqdns {
    builder.insert(fqdn)?;
}

builder.finish()?;

Keys must arrive sorted, and once you call finish, the FST is frozen and immutable. Not to foreshadow too much, however certificate transparency is the opposite of frozen. It is a continuous append-only stream, and a 90-day retention window means we delete continuously from the other end too.

So we built the machinery an immutable structure needs to behave like a live index. Global snapshots, compaction, custom binary format to track occurrences, rolling index updates and so forth. By late October the engine ingested multiple logs and served queries. What we had, in effect, was a hand-rolled log-structured merge (LSM) tree with the certificate-transparency-specific parts bolted on. Exciting stuff, but it did feel like we were forcing a square peg into a round hole.

This initial version of certgrep.sh did work for about three months; serving real queries in production. It answered exact lookups, prefix and suffix queries, fuzzy matches, and regex. Two of those I'd like to mention, because they show how far the automaton model stretches:

• Suffix search: FSTs only do prefix search cheaply. To answer "every name under this registrable domain" we built a second FST with the labels reversed (com.example.www), so a suffix query became a prefix query on the reversed set. I wouldn't say this doubled the storage, as compaction varies, but it significantly increased it.
• Fuzzy search: The fst crate ships a Levenshtein automaton. Intersect it with the names FST and you get every name within an edit distance of a target, using the same walk as regex. For catching typosquats that is close to the ideal primitive. That said, the memory allocation overhead for another above an edit distance of 3 was quite large and was heavily truncated internally within the library which was a known issue.

We did eventually hit our first major wall. The problem was not mutability, which was our prime suspect. The problem was regex latency under load. A regex over a bare FST intersects the pattern's automaton against the whole names automaton. For an anchored or prefix-heavy pattern that prunes beautifully. For the substring and alternation patterns real hunting produces (.*paypa1.*, homoglyph families, phishing-kit naming conventions), it prunes almost nothing, so the walk visits a large fraction of the key space on every query. That work is CPU-bound, it does not shard away cleanly, and it got worse as the index grew. The index builds were memory-hungry enough to start crashing under the larger multi-log corpus, which we spent the first week of December fighting.

The realization at this point was that we do still want FSTs, however we need some external structure that reduces the candidate set that we need to search over. Similar to a dimension reduction problem. We wanted the automaton walk to run against a small candidate set instead of the entire corpus, and we wanted someone else to own the segment lifecycle we had been hand-maintaining.

Whether a regex is cheap or not comes down to whether the pattern lets the walk prune. We try to showcase this in a few examples below against both the forward and inverse FST structures we mentioned.

The first example shows an ideal happy path, were all but one branch are immediately pruned from the search. The last two examples show the strength that the inverse FST provided to us.

Attempt two: Tantivy and a trigram index#

FSTs are exceptionally powerful, and we're really grateful to Andrew for not only publishing the fst crate, but also documenting the structure at length. I'm sure we'll have more use-cases for it in the future, and feel confident that we'd be able to equip it better next time. For now, we had to take a step back and re-assess our second option, trigrams/ngrams using Tantivy.

Tantivy is a full-text search engine library in Rust, in the same architectural family as Lucene. Immutable segments, background merges, a term dictionary, mmap-friendly on-disk formats. It gave us, off the shelf, the segment lifecycle we had been hand-maintaining, plus the one thing the FST engine could not offer: a way to avoid scanning the whole corpus for every regex.

That way is a trigram index. Every name is broken into overlapping three-character grams and stored in an inverted index, wrapped in anchors (^name$) so edge matches stay exact. A regex query is decomposed into the trigrams any match must contain, those trigrams select a small candidate set, and the expensive automaton match runs only against the candidates. The full-corpus walk that made FST regex CPU-bound never happens.

There is a satisfying footnote here. Tantivy's term dictionary is itself built on FSTs. We did not abandon the data structure! We moved to a system that embeds it behind the operational machinery it needs, and the regex path certgrep.sh serves today still bottoms out in automaton matching against an FST, exactly as the first design intended. The difference is that the automaton now runs against candidates rather than the whole world, and someone else maintains the engine around it.

The schema is deliberately tiny. Each indexed name carries:

• domain_raw, a raw-tokenized copy of the name for exact and regex matching.
• domain_ngram, the 3-gram tokenized copy for substring and fuzzy matching.
• a pointer, the byte offset of that name's occurrence history (more on this later).
• a few fast fields for sorting and retention: last-seen timestamp, certificate validity window, and total occurrence count.

To reiterate briefly, no certificate bodies, no chains, no parsed X.509 fields. Domains, where each domain occurred (through the pointer), and just enough timestamp metadata to sort by recency and trim by age.

The trigram path turns the same query inside out. Rather than walk the whole automaton, it narrows to candidates first, so the expensive match only ever runs against a small set.

Just-in-time hydration#

The part of the design we like most is what happens when someone actually needs a certificate.

Every occurrence in the index carries a compact binary record that says where the entry lives: which log, and the leaf index needed to retrieve it. When a result needs to become a full certificate, for evidence, for enrichment, or for a human who wants to read the chain, we fetch that exact entry from the log itself, on demand.

Each name maps to a block of these records in a single postings file. The block is a little-endian u32 count followed by fixed-width records, ordered newest first, so the first record is always the latest occurrence. The current record is 30 bytes, and trades some storage overhead for predictable and fast access.

That is the entire cost of remembering an occurrence. Thirty bytes, plus a pointer from the trigram index into the postings file. The certificate that record points at might be four kilobytes. We store the thirty bytes. The public logs store the four kilobytes.

This works because certificate transparency logs are, by design, the perfect cold store. They are public, append-only, tamper-evident, and operated by parties whose entire job is keeping them available. There is no reason to mirror a blob store the ecosystem already runs for you. We pay to store pointers. The internet stores the payload.

We call this just-in-time hydration. The index answers "what appeared, where, and when" instantly. The logs answer "show me the full artifact" on demand, at the cost of one fetch, for the vanishingly small fraction of entries anyone ever looks at. It is the single decision that collapses the cost structure of the whole system, and it is the reason we can run this as a free service rather than a loss leader with a countdown timer.

Turning a hit into a full certificate is a single round trip to the log that already holds it.