构建 certgrep.sh：一个免费的证书透明搜索引擎

# 构建certgrep.sh：一个免费的证书透明度搜索引擎 来源：https://haveibeensquatted.com/blog/building-certgrep 证书透明度是安全领域最佳的公共数据集之一。每一个由公共信任证书机构颁发的证书都会被记录到一个仅追加、可密码学验证的日志中，通常在证书被使用之前就会完成记录。对于任何追踪恶意基础设施的人来说，这使得证书透明度成为最早可观测的信号之一。一个仿冒域名的证书通常会在网站服务第一个字节之前就出现在日志中。 能够访问这样的数据集，是我们能够支撑其检测的关键方式之一。与第三方绑定意味着我们直接依赖于他们的正常运行时间、能力和成本。在文化上，我们坚信检测的各个方面都应从零开始，针对我们特定的用例进行内部工程化，并在尽可能的情况下将其回馈给社区或公众。 我们构建了 certgrep.sh (https://certgrep.sh/)，以便任何人都可以免费搜索（grep）证书，支持完整的正则表达式（regex）。在这篇博文中，我们希望介绍 certgrep 背后的技术基础，以及经过深思熟虑的权衡如何让我们既能够将其提供给社区，也能在内部使用。文章涵盖了第一个设计（我们在生产环境中运行了大约三个月），我们在其中遇到的具体障碍，以及促使整个项目变得可行的关键转变。 ## 问题所在 (https://haveibeensquatted.com/blog/building-certgrep#the-problem) certgrep.sh 最初是一个内部工具。我们在 Have I Been Squatted 的检测管道持续需要大规模查询 CT 日志，而现有的每一个选项由于技术或财务原因都不适合。免费的公共搜索工具要么不可靠，要么无法跟上我们所需的查询量。商业 API 可以跟上，但速度缓慢，且价格高到将其放在热路径上是荒谬的。无论如何，我们都需要运行自己的索引，因此唯一重要的问题是，它到底需要存储什么。 证书透明度是一个信息洪流。在所有活跃的日志中，条目以每天数千万条的速度到达，每条条目携带几千字节的编码证书和链材料。 信息洪流 所有网站 → 所有 CT 日志 → 一个索引 证书透明度信息洪流互联网上的网站持续获得 TLS 证书。每次颁发都会记录在公共、仅追加的证书透明度日志中。certgrep 从每个活跃日志中提取每条记录到一个单一索引——每天数千万条新记录。网站CT日志颁发的证书公共、仅追加被提取到 certgrepcertgrep 提取每条记录 每个活跃日志，每个颁发机构——每天数千万条新记录，全部提取到一个索引中。 存储所有这些数据，仅仅为了搜索其中一小部分，既昂贵又运维繁重。借用别人的索引意味着接受他们提供的任何查询语义，通常是对名称的精确或子串匹配。 这两种方式对我们都不适用——我们的关键洞察实际上并非关于证书，而是关于域名。更具体地说，是关于域名的*出现*。证书元数据是次要的。 当我们的检测管道提出一个问题时，它类似于：“在过去90天内，是否有任何符合此模式的完全限定域名（FQDN）出现在证书透明度中，出现在何时，以及在哪个日志中？” 证书本身、链、颁发者、密钥材料，所有这些都是次要的。它们偶尔在充实信息或作为下架证据时重要，但从未在热路径上。热路径是名称查找，并且越来越依赖于通过正则表达式进行名称查找，因为仿冒和钓鱼模式自然地表达为模式，而非字面值。 这个洞察的另一半，也是让经济性成立的部分，是：任何我们管道实际匹配到的内容，我们自己无论如何也会持久化，因此索引永远不必成为记录系统。它只需要快速回答一个关于近期窗口的问题，并在罕见的需要证书本身时返回一个指针。我们怀疑这并非我们独有。我们认识的大多数分析师都以同样的方式使用证书透明度：这个模式最近出现过吗，在哪里？ 一旦你接受了这一点，存储证书就开始显得荒谬。你将为存储每天数吉字节、可能永远不会去读的数据而付费。 整个系统围绕这个决定开始成形。域名进入，证书留下，公共日志兼作冷存储。 系统概览 名称进入，正文移出；日志是冷存储 certgrep 系统概览证书透明度日志馈送到一个索引器，该索引器提取域名并丢弃证书正文。出现索引存储名称和30字节指针，查询 API 搜索这些指针。为了返回完整证书，系统根据需要从公共日志（兼作冷存储）中动态获取单条记录。冷存储CT日志公共、仅追加有效负载存储于此索引器提取 FQDN出现索引+倒排列表名称 + 30字节指针查询 API正则、模糊、精确证书正文被丢弃动态获取：按需获取单条记录 我们的索引——我们存储的名称 + 30字节指针 公共 CT 日志——有效负载，按需获取 ## 尝试一：有限状态转换器 (https://haveibeensquatted.com/blog/building-certgrep#attempt-one-finite-state-transducers) 第一个引擎是基于有限状态转换器构建的，使用了 Rust 的 `fst` (https://crates.io/crates/fst) crate。FST 是一种用作数据结构而非计算模型的有限状态机。取一个有序的键集合，将其编译成一个确定性无环自动机，其中键存储在转换中。Ian 和我在英国的某次火车旅途中读到这种结构，立刻被它迷住了。向机器逐字节输入一个字符串，当且仅当该字符串落在终止状态时，它才属于该集合。可以将其想象成一个前缀树（另一种有趣的数据结构），它共享后缀和前缀，并被最小化为一个单一的机器。这里有一些注意事项，但 Andrew 下面详尽的博客比我们能写的要好得多。 有三个特性让它看起来非常适合我们。查找时间与键的长度成正比，与存储的键数量无关。整个结构是一个扁平的字节序列，可以直接通过内存映射（`mmap`）从磁盘读取，无需反序列化步骤。并且因为集合本身就是一个自动机，你可以将其与另一个自动机相交，这就是正则表达式运行的方式：将模式编译为一个确定性有限自动机，相交，遍历生成的树，并剪枝掉整个永远无法匹配的键空间子树。 权威的讲解是 Andrew Gallant 的《Index 1,600,000,000 Keys with Automata and Rust (https://burntsushi.net/transducers/)》，由 `fst` crate 的作者撰写。它仍然是互联网上最好的数据结构文章之一，其标题实验也是我们从这里开始的原因：16亿个去重的 Common Crawl URL，134 GB 的原始键，编译成一个 27 GB 的单一索引，能在几分之一秒内服务正则查询。域名甚至比 URL 更友好。它们是简短、高度重复的字符串，具有巨大的共享结构，因此压缩效果好得离谱。 构建一个很愉快： ```rust let mut builder = SetBuilder::new(writer)?; // Keys must be inserted in lexicographic order for fqdn in sorted_fqdns { builder.insert(fqdn)?; } builder.finish()?; ``` 键必须按顺序插入，一旦调用 `finish()`，FST 就被冻结并不可变。不过，证书透明度恰恰是冻结的反面。它是一个持续仅追加的流，而90天的保留窗口意味着我们也要从另一端持续删除数据。 因此，我们构建了不可变结构为了表现得像一个实时索引所需的机制。全局快照、压缩、用于跟踪出现的自定义二进制格式、滚动索引更新等等。到十月底，该引擎能够摄取多个日志并服务查询。实际上，我们得到的是一个手工打造的日志结构合并树，并附加了证书透明度特有的部分。令人兴奋的东西，但确实感觉像是在强求。 certgrep.sh 的这个初始版本运行了大约三个月；在生产环境中服务真实查询。它回答精确查找、前缀和后缀查询、模糊匹配和正则表达式。其中两个值得一提，因为它们展示了自动机模型的延展性： - **后缀搜索：** FST 只能廉价地执行前缀搜索。为了回答“此可注册域名下的所有名称”，我们构建了第二个 FST，其中标签被反转（`com.example.www`），因此后缀查询变成了对反转集的前缀查询。我不会说这使存储翻倍，因为压缩情况不同，但它显著增加了存储。 - **模糊搜索：** `fst` crate 附带了一个 Levenshtein 自动机。将其与名称 FST 相交，你就可以得到与目标编辑距离内的每个名称，使用与正则相同的遍历方式。对于捕捉仿冒，这接近理想的原语。也就是说，当编辑距离超过3时，内存分配开销相当大，并且在库内部被大量截断，这是一个已知问题 (https://github.com/BurntSushi/fst/blob/master/fst-levenshtein/src/lib.rs#L14)。 我们最终撞到了第一堵主要的墙。问题并非可变性——这是我们最初的怀疑对象。问题是负载下的正则延迟。裸 FST 上的正则表达式将模式自动机与整个名称自动机相交。对于锚定或前缀密集的模式，这可以很好地剪枝。对于真实狩猎产生的子串和交替模式（`.*paypa1.*`，同形字符组，钓鱼套件命名约定），它几乎不剪枝，因此遍历在每次查询时都会访问键空间的很大一部分。这项工作是 CPU 密集的，无法干净地分片，并且随着索引增长变得更糟。索引构建本身就非常消耗内存，以至于在更大的多日志语料库下开始崩溃，我们花了十二月的第一周来解决这个问题。 此时的领悟是：我们仍然想要 FST，但是我们需要某种外部结构来减少我们需要搜索的候选集。类似于一个降维问题。我们希望自动机遍历针对一个小候选集运行，而不是整个语料库，并且我们希望有人来负责我们一直在手工维护的段生命周期。 一个正则是否便宜取决于模式是否能让遍历进行剪枝。我们在下面的一些例子中尝试展示这一点，针对我们提到的正向和反向 FST 结构。 遍历自动机 FST 正则遍历与剪枝 域名的一个前缀树。锚定模式剪枝到一个分支；子串或后缀模式迫使遍历访问几乎每个状态；在反向标签前缀树上，后缀再次变成廉价的前缀遍历。wwwexamplecomnetacmecomloginexamplecomacmeiopaypa1examplecomsecurecomailacmecom 正向 FST 7/20个状态 廉价 锚定在第一个标签上，遍历沿单个分支下降，并在根节点剪掉所有其他分支。 第一个例子展示了一个理想的顺畅路径，除了一个分支之外的所有分支都被立即从搜索中剪枝。最后两个例子展示了反向 FST 为我们提供的优势。 ## 尝试二：Tantivy 和三元组索引 (https://haveibeensquatted.com/blog/building-certgrep#attempt-two-tantivy-and-a-trigram-index) FST 极其强大，我们真的非常感谢 Andrew 不仅发布了 `fst` crate，还详尽地记录了这种结构。我确信未来我们会有更多用例，并且有信心下次能更好地运用它。现在，我们不得不后退一步，重新评估我们的第二个选项：使用 Tantivy 进行三元组/ n-gram 处理。 Tantivy (https://github.com/quickwit-oss/tantivy) 是 Rust 中的一个全文搜索引擎库，与 Lucene 属于同一架构家族。不可变的段、后台合并、术语词典、对 mmap 友好的磁盘格式。它为我们开箱即用地提供了我们一直在手工维护的段生命周期，以及 FST 引擎无法提供的一样东西：一种避免每次正则都扫描整个语料库的方法。 这种方法就是三元组索引。每个名称被分解为重叠的三个字符的 gram 并存储在倒排索引中，用锚点（`^name$`）包裹以使边缘匹配保持精确。一个正则查询被分解为任何匹配都必须包含的三元组，这些三元组选择一个小的候选集，而昂贵的自动机匹配只针对这些候选运行。使 FST 正则成为 CPU 瓶颈的全语料库遍历永远不会发生。 索引时的三元组索引 一个名称 → 重叠的 grams → 倒排索引 三元组索引构建名称 paypal.com 被包裹在锚点中为 ^paypal.com$。一个三字符窗口在其上滑动，每次一个位置，产生重叠的三元组，包括锚定的边缘 grams ^pa 和 om$。每个 gram 成为倒排索引中的一个键，其倒排列表保存包含该 gram 的每个名称。索引一个名称^paypal.com$锚定^pa^papaypayaypayp⋮⋮comcomom$om$滑动一个3字符窗口；每步发出一个重叠的gram倒排索引pay→paypal.com,paypa1.com,mypaypal.ioypa→paypal.com,paypa1.com,typo-ypa.netcom→paypal.com,example.com,login.com每个gram → 包含它的每个名称 每个 gram 映射到包含它的每个名称。一个正则命名了匹配必须包含的 grams；对这些短列表求交集产生自动机实际检查的小候选集。 这里有一个令人满意的注脚。Tantivy 的术语词典本身就是建立在 FST 上的。我们并没有放弃这种数据结构！我们转向了一个在其背后嵌入了它所需的运行时机制的系统，而 certgrep.sh 今天服务的正则路径仍然归结为对 FST 的自动机匹配，正如第一个设计所意图的。区别在于，自动机现在针对候选者而非整个世界运行，并且由其他人维护其周围的引擎。 模式设计得刻意精简。每个被索引的名称携带： - `domain_raw`，用于精确和正则匹配的原始分词名称副本。 - `domain_ngram`，用于子串和模糊匹配的3-gram分词副本。 - 一个 `pointer`，该名称出现历史的字节偏移量（稍后详述）。 - 一些用于排序和保留的快速字段：最后出现时间戳、证书有效期窗口和总出现次数。 简要重申一下，没有证书正文，没有链，没有解析的 X.509 字段。只有域名，每个域名出现的位置（通过指针），以及刚好足够的元数据用于按新鲜度排序和按年龄修剪。 三元组路径将相同的查询颠倒过来。它首先缩小到候选者，因此昂贵的匹配只针对一个小集合运行。 三元组候选过滤器 先缩小范围，然后匹配 三元组候选过滤器一个正则被分解为必需的三元组。Tantivy 三元组索引只返回包含每个三元组的名称，这是一个小的候选集。每个候选与原始名称匹配，命中的记录通过指针跟随到其出现历史。正则 .*paypa1.*分解payaypypapa1查找Tantivy 三元组索引数百万个名称候选者一个小集合与 domain_raw 匹配命中 → 跟随指针 → 出现历史 只有名称