[论文阅读分享] Prefix Siphoning: Exploiting LSM-Tree Range Filters For Information Disclosure
[论文阅读分享] Prefix Siphoning: Exploiting LSM-Tree Range Filters For Information Disclosure
摘要：键值存储通常将访问控制交由其所服务的系统来处理。然而，攻击者可能通过对键值存储进行计时攻击来绕过这些读取访问控制，这些攻击利用查询响应时间的差异来获取存储数据的信息。到目前为止，键值存储的计时攻击主要集中在泄露存储的值上，本文指出，密钥泄露也是一个安全威胁，并展示了利用键值存储机制本身的密钥泄露计时攻击。本文从安全角度分析了SuRF和前缀布隆过滤器对LSM树的影响，通过实验表明了它们存在“前缀虹吸”的密钥泄露的计时攻击漏洞，从而提醒人们在追求LSM效率的同时还要考虑隐私安全问题。
华东师范大学区块链实验室论文阅读分享会于2024年7月16日在线下进行，硕士研究生钱堃分享了论文。该论文由特拉维夫大学和和IBM研究院在USENIX ATC 2023上发表，作者是Adi Kaufman, Moshik Hershcovitch,和Adam Morrison。
论文链接：https://www.usenix.org/conference/atc23/presentation/kaufman
1. 论文简介
Key-Value键值存储充当了许多云和企业系统的存储引擎，包括但不限于对象缓存、流处理及数据库系统。这些现代数据密集型系统的性能通常取决于其键值存储引擎的性能。因此，对键值存储的研究绝大多数集中在效率上，包括写入的 I/O 效率、点查询和范围查询到内存效率、能源效率、多核可扩展性以及减少 I/O 写入放大。
另一个问题是键值存储引擎中存储数据的安全性问题，也是本文关注的问题。因为键值存储通常只提供字典抽象，而没有访问控制机制，访问控制完全留给系统本身实现。系统通常将访问控制列表 (ACL)作为值的元数据存储在键值存储中，用户通过查询键值存储中的ACL来实现访问控制。虽然这种方法可以阻止用户直接进行未经授权的查询，但如果键值存储容易受到定时攻击，用户仍然可以间接收集有关受限数据的信息。定时攻击利用查询响应时间的差异来收集有关存储数据的信息，使用容易受到定时攻击的键值存储的系统本身也容易受到此类攻击，因为系统的查询响应时间取决于存储引擎的响应时间，使得键值查询响应时间的差异表现为系统的响应时间。
迄今为止，键值存储定时攻击的目的是泄露存储的值，Schwarzl等人在NDSS 2022和IEEE S&P 2023中分别提出了针对内存去重和内存压缩的时间攻击。然而，本文指出，密钥泄露也是一种安全威胁。在某些系统中，密钥可以明确包含秘密数据。例如，使用键值存储引擎的数据库系统（例如，CockroachDB、YugabyteDB 或 MyRocks）将行（或行的子集）编码到键上。这使得密钥泄露等同于数据库数据泄露。密钥也可能是隐含的秘密，用户并不希望它们被轻易获得。例如，在 Amazon S3 等对象存储系统中，识别有效密钥可能会产生不安全的直接对象引用漏洞（图1），这使得攻击者能够探测对与所公开的密钥关联的对象的访问。
本文表明某些范围过滤器可以对 LSM 树进行密钥泄露定时攻击。本文描述了一种称为前缀虹吸的攻击框架，它利用了 SuRF 和 PBF 中存在的一般范围过滤器特征。在暴力搜索密钥（通过详尽枚举或随机猜测）不可行的情况下，前缀虹吸成功地利用对不存在密钥的良性点查询来识别实际密钥的前缀（在某些情况下，识别完整密钥）。本文通过分析和经验评估了前缀虹吸对 SuRF 和 PBF 的影响，并在实践中证明了其可行性。
图1. Amazon S3 的对象引用漏洞报道
2. 研究背景
键值存储：键值存储有以下三个操作。1.插入操作put(k, v)。 put 存储从键k到值v的映射。如果存储中已存在键，则更新其值。2.单点查询操作get(k)。返回和请求的键k关联的value值。3.范围查询操作range_query (k1, k2)。范围查询返回给定范围内的所有键值对。键值存储可用作许多更复杂系统的存储引擎。此类系统的示例包括数据库系统（例如 Cassandra、MongoDB）和存储系统（例如 CEPH）。
基于LSM的数据存储：日志结构合并树（LSM）是写优化的键值存储的核心存储结构。 LSM 树由多个级别组成，每个级别包含多个存储键/值对的不可变静态排序表 (SSTable) 。同一级别的两个 SSTable 在存储的键范围上永远不会重叠，但不同级别的 SSTable 可能会重叠。 put 请求将键值对插入到 Memtable 的内存缓冲区中，Memtable 是 LSM 树唯一的可变存储对象。一旦 Memtable 填满，其数据就会作为 SSTable 文件刷新到辅助存储。 LSMtree 定期执行压缩，统一级别之间的 SSTable，以消除重复的键值对。 get 查询以自上而下的方式搜索目标键：首先在 Memtable 中查找，然后在每个级别的相关 SSTable中查找。通过布隆过滤器的引入，LSM 树可以减少不必要的sstable的 I/O。同样，范围过滤器使 LSM 树能够避免范围查询的多余 I/O，这可以将范围查询吞吐量提高几个数量级。
布隆过滤器：布隆过滤器（Bloom Filter）是一种高效的概率型数据结构，用于快速判断一个元素是否可能存在于一个集合中。它由一个位数组和多个哈希函数组成。其基本工作原理如下：1.初始化：创建一个包含m位的位数组，并将所有位初始化为0。2.插入元素：对于每个要插入的元素，使用k个哈希函数生成k个哈希值，并将这k个哈希值对应的位数组位置设为1。3.查询元素：对于查询的元素，同样使用k个哈希函数生成k个哈希值，然后检查这k个位置的值是否全为1。如果是，则该元素可能在集合中；如果有任意一个位置为0，则该元素一定不在集合中。布隆过滤器的优点在于其空间效率和插入、查询操作的快速性。缺点是存在一定的误判率。
SuRF：SuRF通过类似trie树的数据结构实现range filter。 其核心数据结构就是 Fast Succinct Tries（FST），一种空间节省，支持 point 和 range query 的静态 trie。在很多时候，对于一棵树来说，上层的 trie 节点较少，但访问频繁，也就是我们俗称的 hot，而下层的节点则相对的 cold 一点。因此，SuRF 使用了两种数据结构来分别处理 hot 和 cold 节点。在 upper 层上面使用了 LOUDS-Dedense，而在 lower 层上面使用 LOUDS-Sparse。对于通常的 SuRF 来说，它因为对这个 trie 都进行了编码，所以它是完全精确的，虽然它是一种省空间的数据结构，但很多时候，为了更进一步节省空间，需要对 SuRF 进行裁剪，不存储所有的信息，从而在查询的 False Positive Rate（FPR）和空间上面做一个权衡。
作者：钱堃，华东师范大学区块链实验室硕士研究生
