|
布隆过滤器在NIST RDS和硬盘诊断方面的实际应用 非官方中文译文•安天技术公益翻译组 译注 | 文档信息 | | 原文名称 | Practical Applications of Bloom Filters to the NIST RDS and Hard Drive Triage | | 原文作者 | Paul Farrell, Simson L. Garfinkel, Douglas White | 原文发布日期 | 2008年ACSAC（年度计算机安全应用大会） | | 作者简介 | Simson L. Garfinke是美国海军研究生院计算机科学院的副教授，其研究方向是计算机安全、隐私、安全应用和数字取证。 Douglas White自1987年任职于NIST（美国国家标准与技术研究所），带领着NSRL（国家软件参考库）项目。其研究领域包括分布式系统、分布式数据库和电信协议、实时生物监测、实时视频处理、系统管理和网络监控。 | | 原文发布单位 | 美国海军研究生院, 美国国家标准与技术研究所
| | 原文出处 | | | 译者 | 安天技术公益翻译组 | 校对者 | | | 免责声明 | • 本译文译者为安天实验室工程师，本文系出自个人兴趣在业余时间所译，本文原文来自互联网的公共方式，译者力图忠于所获得之电子版本进行翻译，但受翻译水平和技术水平所限，不能完全保证译文完全与原文含义一致，同时对所获得原文是否存在臆造、或者是否与其原始版本一致未进行可靠性验证和评价。 • 本译文对应原文所有观点亦不受本译文中任何打字、排版、印刷或翻译错误的影响。译者与安天实验室不对译文及原文中包含或引用的信息的真实性、准确性、可靠性、或完整性提供任何明示或暗示的保证。译者与安天实验室亦对原文和译文的任何内容不承担任何责任。翻译本文的行为不代表译者和安天实验室对原文立场持有任何立场和态度。 • 译者与安天实验室均与原作者与原始发布者没有联系，亦未获得相关的版权授权，鉴于译者及安天实验室出于学习参考之目的翻译本文，而无出版、发售译文等任何商业利益意图，因此亦不对任何可能因此导致的版权问题承担责任。 • 本文为安天内部参考文献，主要用于安天实验室内部进行外语和技术学习使用，亦向中国大陆境内的网络安全领域的研究人士进行有限分享。望尊重译者的劳动和意愿，不得以任何方式修改本译文。译者和安天实验室并未授权任何人士和第三方二次分享本译文，因此第三方对本译文的全部或者部分所做的分享、传播、报道、张贴行为，及所带来的后果与译者和安天实验室无关。本译文亦不得用于任何商业目的，基于上述问题产生的法律责任，译者与安天实验室一律不予承担。 |
布隆过滤器在NIST RDS和硬盘诊断方面的实际应用
Paul Farrell 加利佛尼亚州，蒙特利尔， 美国海军研究生院 Simson L.Garfinkel 加利佛尼亚州，蒙特利尔， 美国海军研究生院 Douglas White 马里兰州，盖瑟斯堡， 美国国家标准与技术研究所 摘要
近年来，研究人员花费了大量精力根据已知文件创建大型哈希码集合。由于这些集合越来越大，所以分布它们也越来越困难。同时，随着硬盘存储容量急剧增加，这些集合排除分析“已知的良好文件”的价值也降低了。
本文评估了利用BF（布隆过滤器）来分布NSRL（国家软件参考库）RDS（参考数据集）版本2.19的情况，其中涉及1300万个SHA-1哈希值。我们提出了一个开源参考BF实现并用大量磁盘映像进行验证。我们讨论了过滤器的调整，探讨了如何用它们启动新的取证功能，并提出了针对布隆过滤器的新型攻击。
1. 简介
之前的研究已经确定了布隆过滤器是一个很有用的表示哈希集合的工具，而且能够将误差率保持到最低[17]。NIST（美国国家标准与技术研究所）发布了一个用Perl编写的样本布隆过滤器，以及两个包含NIST RDS 2.13子集的布隆过滤器[20]。然而，迄今为止还未发布任何关于速度优化的大型BF实现的研究；BF的磁盘表示尚未标准化；BF还未被公开纳入开源取证工具中。 与此同时，NSRL RDS持续增长[19]，2008年7月的RDS 2.21版本将47,553,722个已知文件映射到14,563,184个独特的哈希值。NIST还宣布，它打算公布急剧增加的哈希（每个文件的每个512字节块的哈希值）集合[20]。
存储这些1400万SHA1哈希值需要291 MB字节的空间（在当今世界这样的存储空间是小菜一碟），但是伴随这些哈希值的辅助资料将RDS增加到了6 GB，这使得这些文件难以分布和处理。搜索数据库的时间也增加了，因为大多数工具使用二进制搜索或某种索引树，其存取速度与数据集大小的对数成正比。我们用性能很好的参考硬件进行测试，使用SleuthKit hfind命令每秒只能进行17,000到85,000次 RDS哈希查询 [1]；当哈希值存储在MySQL InnoDB数据库时，每秒只能进行4,000次查询。
布隆过滤器是一个很有吸引力的处理大型哈希集合的方法。在本文中，我们提出了一种新的BF实现，可以在同样的硬件上每秒执98,000到220万次查询。 [2]
所述RDS包括每个文件的大量元数据，包括文件名、大小、其分布的软件包和操作系统，以及发布者。SleuthKit hfind命令、Guidance Software EnCase [11]，或我们评估的其他工具都不适用这些元数据。这些元数据在很大程度上未被使用，一旦有效地访问，就能够协助新硬盘的快速分析和诊断。
1.1本文的贡献
本文参考了BF的先前研究，并将其扩展到NSRL（国家软件参考库）RDS（参考数据集），特别是：
• 我们提出了nsrl_bloom，一种以C语言编写的新型、高效、高度可配置的开源布隆过滤器实现。 • 我们修改了基于SleuthKit的自动化取证工具fiwalk，将其用于我们的BF实现以便自动排除“已知的良好文件”。 • 我们评估用不同参数创建的BF的性能，并将NSRL RD实际结果与理论预测结果进行比较。 • 我们评估BF的性能，方法是将在平面文件（SleuthKit使用）中查询和在大型MySQL数据库中的哈希查询相比较。 • 在新安装Windows 2000、XP和Vista的情况下，评估RDS的覆盖范围。 • 我们提出了一种针对使用BF排除“已知的良好文件”的新型攻击。 • 我们对BF用于跨磁盘分析和提取特征的分布进行了评估。
1.2相关研究
Bloom在1970年引入了“容许误差的哈希码”理论[2]。Dillinger和Manolios展示了如何实现快速、准确、节省内存、可扩展的和灵活的布隆过滤器[8]。Fan等人引入了计数布隆过滤器，其中小的整数被存储在向量中而非各个位中[9]。Bloomier过滤器[5]采用分层的布隆过滤器，将各条目映射到多个集合之一。Broder提出了计算哈希函数最佳数量的方程，以便实现最低的误报率[3]。Manolios提供了一个简单的在线计算器来计算这些值[14]。
至今，BF（布隆过滤器）已被应用于各种取证程序[3]。Roussev等人提出利用BF来存储文件哈希值[17]。研究人员还指出通过对文件各部分进行哈希计算，来检测对象版本管理，并指出“使用相对高误报率（>15％）和低每单元比特数（3-5）的过滤器也有可能识别对象版本管理”。不幸的是，他们的项目md5bloom的源代码从来没有公布。2007年，Roussev等人用多分辨率相似散列扩展了这一研究，用来检测相似但不同的文件[18]。
White用Perl编写了一个样本BF实现并通过NIST网站予以公布[19]。此代码是有缺陷的，MD5或SHA1代码的每一个位都被多次用来计算多个布隆哈希函数。此外，因为它是用Perl编写的，过度的内存耗用使其无法诊断整个RDS。
1.3本文大纲
第2章讨论BF（布隆过滤器）和我们的BF实现。第3章讨论将我们的BF实现应用于NSRL RDS的经验。第5章讨论本文对主流取证研究和实践的影响。第6章总结全文。
2. 高性能布隆过滤器
2.1布隆过滤器介绍
根本上讲，BF（布隆过滤器）是一种数据结构，允许多个值V 0… Vn存储于单个有限位的向量F中。因此，BF支持两个原始操作：将新的值V存储于过滤器F；查询值V‘是否存在于F。
BF计算V的哈希值，将该哈希值置于0和m之间的序列中，从而生成位i。之后，该位被设置于大小为m的位向量F中。要查询V’是否存在，需要计算V’的哈希值，并生成位i‘。如果过滤器中没有设置这样的i’，则V’不可能存储于过滤器中。
如果位数i’被设置了，可能是因为V’之前被存储在过滤器中了。同样地，如果另一个值V’’的哈希值位数i’’与i’相同，则V‘和V’‘是彼此的别名；过滤器用户无法确定这两个值中的哪个是先存储的。由于这一性质，据说BF能够提供概率数据检索：如果BF认为一个值没有被存储在过滤器中，那么该值一定没有被存储。但如果BF认为一个值被存储在过滤器中，那么该值有可能被存储了；同样地，别名可能也被存储了。存储于BF的信息越多，则别名和误报的概率也会随之增加。
在实践中，多个哈希函数f1…fk将单个值V存储于过滤器F中。这样的位数排列被称为一个元素。存储数据要求在过滤器向量F中设置k个不同的位（i1…ik），而查询则需要检查这些位是否被设置了。 因此，BF可以用4个参数来描述：
m：过滤器中的位数（在本文中，我们用M来表示log2（m））；
k：每个元素的哈希函数的数量； b：过滤器中每个元素设置的位数； f：哈希函数。
一旦数据被存储在过滤器中，其他参数也可用来描述过滤器的状态：
n：过滤器中存储的元素的数量； p: 被报告存储于过滤器的值V真得存储于过滤器的概率。 正如其他研究所述[16，15，17]，过滤器中的位没有被设置的概率是：
这近似于：
理论的误报率是：
2.2 性能特征
BF（布隆过滤器）与HT（哈希表）类似，两者都是能够紧密存储大量稀疏值的单个数据结构。一旦存储，无论存储的数据量如何，该结构都允许查询某个值是否存在。与哈希表相比，布隆过滤器的优势是能够在很小的空间中存储数据，其劣势在于检索的概率性：给定的布隆过滤器可能认为数据存在但实际上数据却并不存在。
BF和HT的另一个共同点是引用局部性[7]，这是因为数据在整个结构中进行散列。因为内存缓存和内存层级的性能特征，现代计算机可以实现显著的性能优势，能够将数据结构的内存占用降到最低。对于像BF和HT这样不以任何预测顺序访问内存的结构来说尤其如此；除了将数据结构缩减到缓存中，没有其他任何方法能够实现引用局部性。
我们以基于英特尔酷睿2双核微处理器的现代MacintoshiMac台式机为例。处理器运行时内部时钟速度是2.4 GHz。因为没有引用局部性，忽略BF散列和记录的负载，则访问每个BF位的速度将大致等于存储元素的内存系统的速度（表1）。完全适合计算机32K L1数据缓存的16K BF能够每秒查询约4000万次和20个函数（缓存的其余部分用于之前所提到的BF散列和记录）。另一方面，500 MB的完全适合主内存的过滤器只能支持每秒71万次哈希查询，这是因为计算机的高性能内存子系统仍然需要70纳秒来读取每个散列位。
大多数内存系统是流水线式的，允许任何时间同时进行多个读取。此外，酷睿2双核可以每周期执行4条指令。这一功能可用来执行记录活动，例如递增循环计数器和移位；最终该线程将停止，直到从内存子系统中读取了所请求的位。如果我们能够减少内存读取的延迟和每次查询所需的读取次数，就可以显著加快哈希查询的速度。通过改变BF的哈希函数的大小和数量，我们可以优化数据集合的表示。
2.3 nsrl_bloom
White的原始代码[19]有个缺陷，导致MD5或SHA1代码的每一个位都被多次用来计算多个布隆哈希函数。其结果是，这些位相互关联，用perl编写的BF的误报比理论预计的多10个。为了使BF更加有效，哈希函数必须是真正随机和独立的。为了避免这种相关性，我们根据BF的大小简单地将哈希分为几个片段：k = 4和M = 28的BF使用SHA1的前28个位，将其用于布隆哈希函数f1；其后的28个位用于f2，等等。由于这些哈希函数都很强大，所以这些位彼此并不相关。结果是，通过MD5创建的BF的k×M必须小于128，通过SHA1哈希创建的BF的k×M必须小于160。
从这个代码库开始，我们实现了快速的、可配置的、用C和C++编写的布隆过滤器。过滤器向量被存储于二进制文件中，每个文件的前4096字节包含过滤器参数和注释。这一实现有简单可用的API（应用程序编程接口），其中包括6个C函数：
• next_bloom_create（）：创建指定哈希大小、M、k和可选注释的布隆过滤器。该布隆过滤器可驻留在内存中或备份到文件中。 • nsrl_bloom_open（）：打开一个先前创建的布隆过滤器，读取文件的参数。 • nsrl_bloom_add（）： 向布隆过滤器添加一个哈希值。 • nsrl_bloom_query（）： 查询布隆过滤器的哈希组成。 • nsrl_bloom_set_encryption_passphrase-：添加字符串作为布隆过滤器的加密密码（计算字符串的哈希值；在未来的添加和查询中，这被用作HMAC（哈希运算消息认证码的密））。 • nsrl_bloom_free（）： 释放与布隆过滤器有关的内存。
我们的C实现使用memmap将BF向量映射到内存中，以便进行快速查询；在实践中，这意味着，计算机的虚拟内存子系统根据需要将位向量映射到内存并且不会执行不必要的复制。如果整个BF都是必要的，则可以一次性地将过滤器映射到RAM（随机存取存储器），以尽量减少硬盘驱动器的延迟。
除了正确的哈希函数，这个新的实现比原始perl版本更快速和节省内存，使得我们可在完整的RDS上进行测试。
该实现还包含C++类代码，允许对C API的零负载存取。
3. 布隆过滤器用于RDS
在完成BF实现后，我们创建了大量包含NSRLRDS的SHA 1哈希值的布隆过滤器。
3.1构建过滤器
RDS作为ISO 9660格式的四个ISO图像分布。每个图像都包含多个文本文件。RDS的详细信息可在网上查询。[19]
我们从NIST网站上下载了RDS 2.19的ISO图像（本文编写时RDS 2.20尚未发布）。每个ISO图像包含若干文本文件和一个ZIP文件（ZIP文件又包含多个文本文件）。我们用两个程序处理这些图像：第一个是nsrlutil.py，这是一个Python程序，它将磁盘映像作为文件安装在Linux服务器上，打开ZIP压缩文件，将哈希发送至标准出口；另一个是bloom，该程序利用命令行中的参数创建新的布隆过滤器，然后使用从标准入口读取的哈希码加载过滤器。通过把这两个出现结合起来，我们可以快速创建大量的BF文件，每一个文件都有其具体的参数集。
表1：从现代iMac计算机（2.4GHz的英特尔酷睿2双核处理器E6600）的不同内存子系统中存储的布隆表或哈希表中访问位的相对速度。内存延迟的信息请参见[6,12]。磁盘访问时间大约是8.5ms。一次“哈希查询”需要访问20个随机的位。
3.2精度和验证
我们的目标是创建足够小的RDS（参考数据集） BF（布隆过滤器），使其能够用于CD和旧机器/更小的PDA式设备的主内存中。我们随机决定评估32 MB、64 MB、128 MB、256 MB和512 MB的BF。这样的BF可以通过228到232个一位元素创建（M =28…32）。但每个元素究竟能使用多少个哈希函数？也就是说，k的最优值是什么？是否有必要选择最优值？
我们知道所希望的过滤器尺寸，也知道RDS 2.19具有13,147,812个独特的哈希值，我们将这些数字代入最优过滤器方程，发现512 MB的过滤器需要226个哈希函数，误报率为6.89×10-69。显然，这种误报率远低于所需的水平，例如，它明显小于存储过滤器的硬盘或数字媒体的故障率。另外，160位的哈希值中没有足够的熵为226个哈希函数提供数据（即向每个函数提供32位不相关的输出）。
鉴于只能为哈希函数提供160位的数据，所以在RDS的现实要求中，需要为参数k和m选择正确的值。因为BF中的每个位对应于唯一的哈希值，当k = 1且m = 2160时，则不会产生任何误报；但这样的BF也不可能很大。好消息是，当k = 5，m = 232时，我们的样本集中并没有出现任何误报；这些设置允许SHA-1值的160位用于BF计算（5×32= 160），理论误报率是6.2×10-16。这种大小的布隆过滤器可以方便地下载，存储在USB记忆棒和32位工作站的内存中。当k = 4时，误报率也类似（并且实现速度稍快），但是k = 5使得我们的B能够容纳更多的信息，而不会降低精度。
为了验证我们的代码，我们编写了回归分析程序，用1百万个RDS哈希值和1百万个非RDS哈希值测试每个BF。根据BF的理论，在任何情况下是RDS中的值都不会出现在BF中。但是当参数k和m的值小于我们推荐的数值（表2）时，也会出现偶尔的误报。
3.3性能
在本节中，我们比较在分类文本文件和MySQL数据库（这两种系统被当今的取证工具广泛用于存储RDS哈希码）中查询BF中哈希值的性能。我们也探讨了调整参数k和m对BF性能的影响。
3.3.1 BF vs hfind和MySQL 在BF中，每个匹配查询执行f操作，而每个非匹配查询则执行1…f操作。存储在文本文件中分类的相同数据和执行二进制搜索大致需要log2（n）操作。MySQL被配置为使用InnoDB表，这样可以实现高性能的操作处理，而且具有行级锁和多版本并发控制。数据被存储在B树中。[13]
我们使用红帽FC6服务器 （两个四核Xeon处理器，2MB L2缓存，3.2GHz和8GB RAM）进行测试。用gcc 4.1.2编译代码并将代码运行于2.6.22.9-61内核。
RDS作为四个ISO映像分布。我们将这些映像的所有哈希值整合到一个文件中。这个RDS 2.19文件被导入到干净的BF（m = 232，k = 5）、SleuthKit[4]（hfind使用命令hfind -i nsrl-sha1 flatfile.txt），以及位于测试机上的单个MySQL数据库中，以便减少网络延迟负载对测试结果的影响。
表2：在加载了1310万RDS2.19哈希值的BF中查询1百万个伪随机哈希值，出现的预测和实际误报数量。表左侧的1,000,000表示每个哈希值都是误报；表右侧的0表明没有误报。n/a表示无法计算（因为160位的SHA-1没有足够的位数）。此分析表明m= 232，k =5似乎是存储SHA-1值的布隆过滤器的最佳值。
我们测量了两组查询所花费的时间。第一组是从RDS 2.19中获取的1百万个SHA1哈希值，这些哈希值一定在数据库中。下一步，我们测量执行1百万个哈希值（这些哈希值不在数据库中）的伪随机查询所花费的时间。通过测量的时间，我们可以得知每秒所执行的查询数量（图1）。
正如预期的，BF的查询速度快于SleuthKit分类文本文件二进制查询和MySQL InnoDB表查询。也正如所料，查询不在BF中的哈希值显著快于查询在BF中的哈希值，这是因为当搜索例程从向量F中检索到第一个未设置位i’时，就会停止搜索。
3.3.2 m对速度的影响
在2.2节中，我们提出，由于L1和L2缓存的性能，小型BF在现代硬件上具备更好的性能。为了验证这一点，我们构建了多个过滤器，其中k = 5，m的范围是28到232。然后，我们在哈希值中插入1百万个伪随机值并搜索每一个伪随机值。 [3]
这种测量L1和L2缓存影响的方法并不怎么高明，因为这些测试是在运行Linux的连网多用户机器上执行的，而且还有很多其他进程也在争夺缓存。另一方面，这种配置类似于大多数从业者使用的机器：即同时运行多个任务的复杂操作系统。尽管如此，我们确实发现当过滤器的大小增加时，BF查询性能会显著降低（图2）。图2还展示了图形大小达到基准系统的L2缓存时的拐点，如图中虚线所示。
3.3.3 k对速度的影响
在3.1节中，我们指出，哈希函数数量少的BF（即k值较小）具备较高的性能，这是因为每个哈希函数和从内存中检索相应位都会产生计算负载。为了确定这种影响，我们构建了多个过滤器，其中m = 220，k的范围是1到5。然后，将1百万个伪随机值插入哈希值中并查询每个伪随机值。正如预期的那样，当k增加时BF的性能会降低。的确，每秒查询次数大致与 成正比（图3）。
图1：M = 32，k = 5的情况下，布隆过滤器、SleuthKit hfind和MySQL SELECT语句（有InnoDB表）对160位哈希值的每秒查询。“In Set”指的是哈希值在RDS 2.19中，而“Not in Set”指的是哈希值不在RDS 2.19中。
3.4用fiwalk进行批量取证
我们已经将我们的BF实现纳入了开源批量磁盘取证分析程序fiwalk。fiwalk使用Carrier的SleuthKit来执行批量分析，并从要分析的磁盘映像的所有分区中提取被分配和删除的文件。fiwalk输出一个walk 文件，该文件包括所有文件的列表、文件的元数据，还有可能包括文件的MD5或SHA1加密哈希值。
Fiwalk的当前版本允许通过文件名或扩展名来指定文件。我们修改了fiwalk，使其可以使用BF也可以不使用BF。我们进一步修改fiwalk，以便它能够基于磁盘映像上发现的文件来生成BF。
3.5 RDS覆盖Windows系统
我们创建了虚拟机Windows 2000 Service Pack 4、Windows XP Service Pack 2和Windows Vista Business。通过qemu-img[1]将.vmdk文件转换为原始文件，然后用fiwalk处理原始文件来生成“walk”文件（包含磁盘映像中的所有文件和文件的SHA1哈希值）。之后，将walk文件与基准RDS v2.19布隆过滤器进行对比。接下来，我们用Microsoft Update的最新补丁修复所有虚拟机并重新处理虚拟机。虚拟机中的文件出现于RDS 2.19的百分比参见表3。
这产生了一些有趣的数据点。首先，即使是安装了最新补丁的基本操作系统，只有60-70％的文件出现于RDS中。为什么只有这么多呢？这是因为有些文件是系统独有的，例如硬件签名、收费注册密钥以及用户名。各机器之间的Swap文件也总是有所不同。这也表明了自RDS 2.19于2007年12月发布以来微软发布的更新的数量。
图2：由于缓存问题，布隆过滤器的大小增加会造成速度的降低。虚线展示了2 MB（8 Mbit）的基准系统L2缓存（注：这些速度是成功查询的速度；而查询不存在于过滤器的哈希值的速度大约是其12倍）。
图3：布隆过滤器每个元素的位数增加都会导致速度的降低，因为查询每个元素会需要更多的工作。
表3分析了存在于基本Microsoft Windows XP但不存在于RDS中的文件。其中大多数是软件安装导致的文件，或实际运行系统生成的日志文件。
表3：Windows XP基本安装中的1635个文件不存在于NSRL RDS中
图4：RDS 2.19覆盖Windows系统
总体而言，不存在于RSD中的文件的数量令人担忧：虽然很多不需检查的文件被删除了，但是大量的文件仍然存在。如果RDS的主要目的是消除已知的良好文件使其无需进行检查，那么这一目的并没有实现。
3.6实际数据的覆盖
为了评估RDS对现实世界数据的覆盖情况，我们在891个硬盘 （1998年至2006年之间在二手市场购买）上执行了文件系统walk。总体来说，45个硬盘的数据覆盖率达到80%以上，其中33个包含非常多的文件。对于280个多于100个文件的硬盘，RDS的平均覆盖率是36.64％。对于186个多于5000个文件的硬盘，RDS的平均覆盖率是36.62％。再次说明，RDS有助于减少需要检查的文件，但是效果并不是很好。
3.7剖析硬盘
虽然如今RDS主要用于消除“已知的良好文件”使其免于分析，但我们认为RDS的覆盖率限制了这种应用。另一种利用这一资源的方法是使用RDS元数据来分析硬盘的可能使用。
我们创建了一个应用程序。通过在RDS数据库中查询每个文件的SHA1、匹配哈希值来检索所有RDS对象的列表，以及检索NIST确定的产品名的列表，该程序试图分析硬盘。每个哈希码可能多次出现于RDS，每次出现对应于不同的产品。如果只有一个产品名匹配，则该产品名就被添加到列表中。
以这种方式使用RDS使我们能够迅速了解硬盘上安装了什么软件，即使文件删除导致了程序本身无法恢复。
4. 针对布隆过滤器的攻击
将哈希集合作为BF发布的显著问题是：攻击者能够很容易地构建与BF碰撞的哈希值，这比构建与防碰撞函数（如SHA-1）碰撞的哈希值容易得多。既然很容易发现碰撞，攻击者就可以利用这个方法来隐藏取证工具（使用BF来消除“已知的良好文件”）的错误数据。
假设SHA-1是一个强大的哈希函数，发现哈希碰撞的唯一方法是暴力破解攻击，其成功几率是1400万除以2160（假设RDS中存在1400万个独特的哈希值）。那么，使用哈希碰撞来隐藏错误数据就需要向其添加一个数据块，然后对数据块做微小的改动，直到发现哈希碰撞。在实践中，诸如此类的暴力破解方法永远无法发现碰撞。
然而，如果160位被分成5组，每组32位，并存储在m = 232和k = 5的布隆过滤器中，则查找碰撞就会容易得多。1400万个哈希码代表最多14 × 5 = 7000万个独特的32位代码，这些代码全都存储于同一个过滤器中。在k = 5的情况下，发现误报要求5个32位代码组的每一个都要有一个哈希值被设置在过滤器中。每个32位代码组的误报概率是7000万除以232或P = 0.016。所有5个组都出现误报的概率是p =（0.016）5，或约为2-30，这使得找到碰撞的难度大致等于破解一个30位的加密密钥的难度。
图5：创建布隆过滤器误报的测试图像
我们使用一个猫咪JPEG图像来验证该假设（图5），附加一个二进制计数器，计算SHA-1并检查误报。如果未发现误报，我们就增加计数器的字节并重复该操作。我们发现，当110,223,107次迭代增加十六进制字节03 df 91 06后，哈希值与M = 32，k = 4 的布隆过滤器发生了碰撞。找到别名的总计算时间大约是5.5 CPU小时。详细信息请参见表4。
针对这种攻击的唯一防御办法是使用加密的布隆过滤器，例如，用一个160位的随机密钥对每个160位SHA-1进行加密。由于对手不知道密钥，她就无法构建别名。不幸的是，密钥必须严格保密，且BF不能在无密钥的情况下使用。
在实践中，这意味着，虽然BF是在组织内部分布哈希集合的有用工具，但是将其公布于公开论坛会使其不再适用（因为对手可能会通过创建误报来隐藏数据）。
置换攻击也能有效地防止使用BF寻找“已知的坏文件”或跨磁盘分析，这种攻击也能够应对传统的哈希分析。也就是说，黑客工具或错误内容的微小改动都会改变文件的哈希值。因此，与传统的哈希工具相比，使用BF查找“已知的坏文件”并不会引入更多的漏洞，但确实会使搜索更加快速。
5. 影响
本章探讨了我们基于本文介绍的BF开发的各种取证应用程序。
5.1关注列表
BF（布隆过滤器）可以用来存储任何类型的哈希值。特别是，它们可以存储从文件或批量数据中提取的特征的哈希值[10]。
我们正在开发一个批量提取应用程序，它能够提取特征、使用可选密钥计算HMAC（哈希运算消息认证码的密钥），并将结果存储在BF中。这个程序可以应用于电子邮件地址列表、信用卡号码，或者其他种类的伪独特信息，以创建关注列表过滤器。这些过滤器可以现场使用来诊断可疑的硬盘，同时将过滤器中的特征遭到破坏的风险降到最低。
5.2跨磁盘分析
布尔运算可以直接应用到BF中。这使得BF可以用于跨磁盘分段。该过程很简单。首先，为数据库中的每个磁盘创建包含提取特征哈希值的BF。设置过滤器需要考虑的最大磁盘数量的阈值（阈值为n/3，其中n是数据库中的硬盘的数量）。接着，设置整数的阈值向量 ，向量的大小等于在BF的位数。每个BF都被扫描；每遇到一个位i，向量 中的相应指数都会递增。在第一遍结束时，向量 中所有大于阈值的整数都被设置为零。剩余的整数作为相关伪独特特征的过滤器。通过计算 + Fi + Fj，可以为每个（i，j）磁盘对创建向量 i，j。
5.3分割RDS
文件哈希为取证调查人员提供了一种消除文件集合中不可能修改的已知文件的有用方法。然而，文件集合可以提供更多的有用信息，不过却很难找到。
我们不是将单一的BF用于所有的RDS，而是将数据集合分割成更小的集合：一个集合包含Windows安装文件，一个包含普通桌面应用程序的文件，一个包含视频应用程序的文件，等等。
将RDS分为两半并将每一半存储在各自的BF中，这样可以减少混叠的机会，从而显著降低误报率。虽然用于搜素BF的时间增加（因为每个BF需要按顺序搜素），但是该方法也有优点：BF可用于表征文件，而非简单地分为已知和未知。这与使用Bloomier过滤器的效果相同[5]。
表4：对布隆过滤器（M= 32，k = 4）的暴力破解攻击的结果。第一行显示了原始JPEG（图5）的SHA1；第二行显示了被附加十六进制字节03 df 91 06的文件的SHA1；其余各行显示了RDS2.19内部导致误报的特定文件和应用的SHA1，其别名用方框标出。
5.4用布隆过滤器进行预过滤
将RDS分割为多个BF的另一种方法是将BF与返回其他信息的较慢的查询服务结合起来。也就是说，不把RDS BF视为将RDS存储于MySQL数据库的替代方法，而是将BF用做数据库的加速器：可以首先检查要查询的哈希值是否存在于BF，如果哈希值存在于RDS，则可以从MySQL数据库获取额外的元数据。
为此，我们的MySQL架构为每个哈希存储了更多信息：我们存储了RDS分布的所有信息，包括文件名、大小、操作系统ID、应用ID、语言，以及RDS发布。这些信息被存储在多对1和多对多SQL表中。可以通过MySQL连接器或基于Web的XMLRPC服务器直接访问这些信息。
6. 结论
通过验证以前研究，我们发现，BF（布隆过滤器）是执行高速哈希匹配的有用工具。但是，我们也发现，BF并不太适合分布“已知的良好文件”的哈希集合，这是因为对手能够访问过滤器或其参数，而且能够相对容易地修改敌对内容以导致误报。防御这种攻击的方法是在现场用随机选择的加密密钥创建布隆过滤器。
通过用各种不同的BF参数测试RDS， 我们发现，有232个1位元素（大小为512 MB）和5个哈希函数的过滤器具备很好的性能。我们在公共域中提供了免费的BF实现下载；任何人都可以出于任何目的地免费使用或修改。最后，我们指出BF如何构建安全关注列表并进行跨磁盘分析。
6.1可用性
6.2未来研究
我们正在评估将BF用于各个文件块或磁盘扇区的哈希集合。
我们正在修改基于Web的哈希查询服务，以便社区成员能够自动地提交新的哈希；我们希望实现一个信誉系统和投票算法，以防止数据库中毒。我们可能会进一步修改系统，使用户能够“实时”下载BF以便基于RDS匹配特定的SQL查询（例如，BF匹配是特定应用程序的一部分）。
我们正在研究BF代码的新版本，这一版本将能够直接打开经ZIP或GZIP算法压缩的BF。由于Java有内存映射文件，而且不断有报告称编写完善的Java代码比C代码的性能好，我们也在编写BF代码兼容的Java实现。
6.3致谢
我们希望向BrianCarrier、Jesse D. Kornblum、Beth Rosenberg以及Vassil Rouss表达诚挚的感谢，他们对本文的研究提供了非常有帮助的反馈意见。我们还要感谢指出并改正本文之前版本中错误，并建议我们探索误报攻击可能性的匿名审稿人。
本研究获得了美国海军研究生院的研究启动计划的支持。本文中所表达的观点属于作者本人，不反映美国国防部、美国国家标准与技术研究所，或美国政府的官方政策或立场。
参考文献
[2] Burton H. Bloom. Space/timetrade-offs in hash coding with allowable errors. Commun. ACM, 13(7):422–426,1970. ISSN 0001-0782. [3] Andrei Broder and MichaelMitzenmacher. Network appli- cations of bloom filters: A survey. InternetMathematics, 1 (4):485–509, May 2004. [5] Bernard Chazelle, Joe Kilian, andRonitt Rubinfeld. The blomier filter: an efficient data structure for static sup- port lookup tables. In Proceedings ofthe Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 30– 39,2004. [7] Peter J. Denning and Stuart C.Schwartz. Properties of the working-set model. Commun. ACM, 15(3):191–198,1972.ISSN 0001-0782. [9] Li Fan, Pei Cao, J. Almeida, and A.Z. Broder. Summary cache: a scalable wide-area web cache sharing protocol.IEEE/ACM Transactions on Networking, 8:281–293, June 2000. [10] Simson Garfinkel. Forensic featureextraction and cross- drive analysis. In Proceedings of the 6th Annual Digi-tal Forensic Research Workshop (DFRWS). Lafayette, Indi- ana, August 2006. http://www.dfrws.org/2006/proceedings/10-Garfinkel.pdf. [14] Panagiotis Manolios. Bloom filtercalculator, 2004. http://www.cc.gatech.edu/˜manolios/bloom-filters/calculator.html. [15] Michael Mitzenmacher. Compressedbloom filters. pages 144–150, 2001. [16] James K. Mullin. A second look atbloom filters. Commun. ACM, 26(8):570–571, 1983. ISSN 0001-0782. [17] Vassil Roussev, Yixin Chen, Timothy Bourg, and Golden G.Richard III. md5bloom: Forensic filesystemhashing re- visited. Digital Investigation, 3(Supplement-1):82–90, 2006. [18] Vassil Roussev, Golden G. RichardIII, and Lodovico Marziale. Multi-resolution similarity hashing. Digital In-vestigation, 4(Supplement-1):105–113, 2007. [20] Douglas White, August 17 2006. http://www.nsrl.nist.gov/RDS/rds_2.13/bloom/.
英文原文报告下载：
Practical Applications of Bloom Filters to the NIST RDS and Hard Drive Triage.pdf
(299.04 KB, 下载次数: 80)
安天公益翻译（非官方中文译文）下载：
布隆过滤器在NIST RDS和硬盘诊断方面的实际应用[非官方中文译文•安天技术公益.pdf
(1.28 MB, 下载次数: 74)
| 
发表于 2015-7-20 15:15
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡