识别相似的文件使用上下文触发模糊哈希外文翻译资料

英语原文共 7 页，剩余内容已隐藏，支付完成后下载完整资料

识别相似的文件使用上下文触发模糊哈希

关键字：记忆分析 取证 视窗 逆向工程 Microsoft

摘要：

同源文件以相同的顺序共享同一顺序序列。 因为这样的文件不完全相同，传统的技术如加密散列不能用于识别它们。 本文介绍了一种通过组合多个传统散列来构造散列签名的新技术，其边界由输入的上下文决定。 即使在新文件中插入，修改或删除数据，这些签名也可用于识别已知文件的修改版本。 该方法的描述之后是对其性能的简要分析以及计算机取证的一些示例应用程序。

1. 介绍

本文介绍了一种使用上下文触发的滚动哈希与传统散列算法相结合的方法，用于识别已插入，修改或删除数据的已知文件。 首先，我们审查员当前如何使用密码散列来区别已知文件，以及这些哈希存在哪些缺陷。 接下来，介绍模糊哈希的概念。 最后，描述仅基于输入的当前上下文产生伪随机输出的滚动哈希算法。 通过使用滚动哈希来设置传统分段哈希的边界，我们创建了一个上下文触发的分段哈希（CTPH）。 即使未知文件是已知文件的修改版本，这种散列也可用于识别未知输入和已知文件之间的有序同源序列。 我们演示了一个CTPH实现的垃圾邮件算法，并使用称为ssdeep的概念验证程序简要分析其性能。

本文剩余部分中解释的算法是由Andrew Tridgell博士撰写的垃圾邮件检测器（Andrew，2002）改编而成。 垃圾邮件可以识别与已知垃圾邮件的标签类似但不完全相同的电子邮件。 垃圾邮件算法又是由Tridgell博士基于rsync校验和（Tridgell，1999）。 虽然这种算法对计算机取证的应用是新的，但作者没有开发垃圾邮件和算法。 本文解释了新的应用，并对其有效性进行了分析.

1. 背景

辩论取证审查员往往不堪重负。 现代硬盘驱动器包含更多的信息，无法在合理的时间段内手动检查，从而需要数据缩减技术。 数据缩减技术旨在使审查员对相关数据的关注，并尽量减少外部数据。 例如，常见的文字处理应用程序不值得检查，但是应该突出显示已知的恶意程序。

迄今为止，辩论取证审查员已经使用加密散列算法，如MD5和SHA-1进行数据简化（White，2005）。这些算法采用任意大小的输入，并产生相应于该输入的固定长度值。密码散列有许多属性，但辩论取证审查员特别利用其中的两个。首先，如果即使输入的一位更改，输出将完全不同。第二，给定一个输入和它的散列，找到另一个产生相同散列的输入是计算上不可行的。

这两个属性可用于识别未知文件集中的已知文件。审查员收集一组已知文件，计算其加密哈希值，并存储这些值。在未来的调查中，审查员可以计算调查中每个文件的哈希值，并将这些哈希值与之前计算的已知值进行比较。如果任何新的哈希值与已知值匹配，调查员几乎肯定会找到已知文件（White，2005）。如果有问题的文件是一个已知的好的文件，该文件可以从消除消除考虑。如果这是一个已知的坏文件，审查员将有一个新的调查结果。

一旦创建了一组散列，就可以从一个调查员传递给另一个。美国国家标准与技术研究所，美国司法部（White，2005）以及一些forensic软件供应商已经为此建立了密码散列的知识库。
然而，恶意用户可能会挫败这种技术，但是通过对已知文件进行一点更改（Foster和Liu，2005）。如上所述，甚至更改输入的单个位改变文件的密码散列。例如，更改在大多数Microsoft Windows程序中找到的字符串，从lsquo;This program cannot be run on DOS modersquo;该程序无法在DOS模式下运行（加重），将彻底改变哈希值那个文件。因此，使用已知密码散列集的系统无法将该文件与原始文件相匹配。
具有一位更改的文件几乎完全相同，并且共享大量有序的同源性。从遗传学借鉴，如果两个染色体具有相同顺序的相同基因序列，那么它们是同源的。类似地，如果两个计算机文件具有相同顺序的相同位的大序列，则可以排列同源序列。除了一组插入，修改和删除数据之外，这两个文件是相同的。

实际上，这些几乎相同的文件可能是Microsoft Word文档和该文档的编辑版本，或JPEG的JPEG和截断版本。 这样的文件将具有不同的加密散列，并且不能使用诸如MD5的算法来识别为同源的。 虽然人眼可以检测到两者之间的相似性，但目前还没有自动化方法。

3.上下文触发的模糊哈希

3.1模糊哈希

最初由Nicholas Harbour为dcfldd开发（Har-bour，2002），分段散列使用任意散列算法为文件创建许多校验和，而不是仅仅一个。不是为整个文件生成单个散列，而是为文件的许多离散固定大小段生成散列。例如，对于前512字节的输入，下一个512字节的另一个散列，等等，生成一个散列。见图 1用于一组样本分段散列。该技术最初是为了减轻法医学成像过程中的错误而开发的。如果发生错误，则只能使一个分段哈希无效。其余的分段散列，因此其余数据的完整性仍然得到保证。
模糊哈希可以使用加密散列算法，例如dcfldd中的MD5或更多传统散列算法，例如Fowler / Noll / Vo（FNV）散列。无论算法如何，为了本文的目的，用于计算分段散列的算法称为传统哈希，以将其与下面描述的滚动哈希值进行区分。

3.2滚动哈希

滚动散列算法仅基于输入的当前上下文产生伪随机值。 滚动哈希的工作原理是仅通过输入的最后几个字节来保持状态。 每个字节被添加到状态，因为它处理并从处理了一定数量的其他字节后的状态中移除。

假设我们输入了n个字符，我们说输入的第i个字节由bi表示。 因此，输入整体由字节b1，b2，...，bn组成。 在输入中的任何位置p，滚动哈希的状态将仅取决于文件的最后s个字节。 因此，滚动散列值r可以表示为最后几个字节的函数如等式（1）。

滚动散列函数F被构造成可以消除其中一个术语的影响。 因此，给定r(p)，可以通过消除作为函数X（b(p-s)）的b(p-s)的影响来计算r(p 1)，并且加上b(p 1)的影响，表示为函数Y（b(p 1)），如图所示在等式（2）和（3）。

3.3组合哈希算法

而目前的分段哈希程序如dcfldd使用固定偏移来确定何时启动和停止传统散列算法，CTPH算法使用滚动哈希。 当滚动哈希的输出产生特定的输出或触发值时，传统的哈希被触发。 也就是说，在处理输入文件时，开始计算文件的传统散列。 同时，还必须计算文件的滚动散列。 当滚动哈希产生触发值时，传统哈希的值被记录在CTPH签名中，传统的哈希被重置。

因此，CTPH签名中的每个记录值仅取决于部分输入，而对输入的更改将仅导致CTPH签名中的本地化更改。 例如，如果输入的字节被改变，最多两个，并且在许多情况下，只有一个传统哈希值将被改变; 大多数CTPH签名将重新统一。 由于大多数签名保持不变，具有修改的文件仍然可以与已知文件的CTPH签名相关联。
本文的其余部分展示了CTPH的一个实现，称为垃圾邮件算法，以纪念其起源。 该算法在程序ssdeep中实现，与本文同时发布http//ssdeep.sourceforge.net/。

1. spamsum算法

spamsum算法使用传统哈希算法的FNV散列（Andrew，2002），为任何输入产生32位输出（Noll，2001）。在垃圾邮件中，Tridgell博士通过仅记录每个散列值的六个最低有效位（LS6B）的base64编码进一步减少FNV散列（Andrew，2002）。

滚动哈希的算法受到Alder32校验和（Andrew，2002）的启发，伪代码如图1所示。原始的垃圾邮件算法有一个额外的逻辑AND，0xffffffff跟随已经被删除的左移。此AND语句最初将算法中的值限制为32位值。因为作者已经明确指出，算法中的所有值都是未签名的32位值，所以AND语句没有任何效果，已被省略。

在处理输入文件之前，我们必须为滚动哈希选择一个触发值。在spamsum算法中，因此对于本文的其余部分，触发值将被称为块大小。使用两个常数，最小块大小，bmin和一个spamsum 长度S来设置n个字节的输入的初始初始块大小。 （4）。在以下定义的某些条件下处理输入后，可以调整块大小。因此，在读取输入之前计算的块大小称为初始块大小（binit）。在处理每个输入字节后，更新滚动散列，并将结果与块大小进行比较。如果滚动哈希生成一个相等的值，则将块大小模数化到块大小减去1，则滚动校验和已经触发了一个触发值。此时，传统哈希的LS6B的base64编码值被附加到最终签名的第一部分。类似地，当滚动校验和产生相等的值，模数为块大小的两倍，为块大小减去1的两倍时，传统散列的LS6B的base64编码值被附加到spamsum散列的第二部分。请注意，维护传统散列的两个独立状态，每个块大小计算一个。

在输入的每个字节已经被处理之后，检查最后的签名。如果在处理所有输入后签名的第一部分不够长，则块大小减半，并再次处理输入。

最终的spamsum签名由块大小，两组LS6B和引号中的输入文件名组成。第一组LS6B以块大小b计算，而另一组2b计算。用于垃圾邮件算法的伪代码如图1所示。图3中示出了一个例子的spamsum签名在图4。

1. 比较spamsum签名

可以比较两个spamsum签名，以确定它们所派生的文件是否是同源的。检查查看块大小，消除消除任何序列，然后计算它们之间的加权编辑距离，如下所定义。编辑距离被缩放以产生在两个文件中找到的有序同源序列的匹配分数或保守加权度量。
因为传统哈希的触发器基于输入文件和块大小，所以只能比较具有相同块大小的签名。垃圾邮件算法基于块大小b和2b为每个输入生成签名，因此如果签名中给出的块大小在2的幂之内，则可以比较两个签名。例如，使用两个签名，第一个具有块大小为bx，第二个签名具有块大小为bx和2bx的CTPH值，第二个为y和2by。如果bx=by，2bx=by或bx=2by，我们可以比较这两个签名

在块大小已解决之后，任何循环序列都被删除。这些序列指示输入文件中的模式，通常不会传达有关文件内容的许多信息（Andrew，2002）。最后，使用动态规划计算两个散列之间的加权编辑距离。给定两个字符串s1和s2，它们之间的编辑距离被定义为“将s1更改为s2”所需的最小点数突变，其中点突变改变，插入或删除一个字母（Allison，1999） 。垃圾邮件算法使用最初为USENET新闻阅读器trn（Andrew，2002）开发的编辑距离公式的加权版本。在该版本中，每个插入或删除被加权为一个差异，但是每个改变以三个加权，并且每个交换（即，正确的字符，但是以相反的顺序）以五加权。为了清楚起见，对于长度为l1和l2的签名s1和s2，该加权编辑距离被称为e（s1，s2），并且在等式（5） - （7）。在这些方程式中，i是插入次数，d是删除次数，c是变更次数，w是互换次数。

然后将编辑距离从0-64重新缩放到0-100并反转，使得零表示不同源，并且100表示几乎相同的文件。 长度为l1和l2的串的最终匹配得分M可以使用公式（8）。 注意，当S = 64，这是默认值，S和64项取消。
匹配分数表示s1和s2是多少顺序同源序列的保守加权百分比。 也就是说，这两个签名中有多少位是相同的，并且顺序相同。 最后得分越高，签名来自一个共同祖先的可能性就越大，这些签名的源文件越有可能来自一个共同的先决条件。 更高的匹配分数表示源文件具有共同的和相同顺序的值的块的可能性更大。

5.1比较相似文件

因为垃圾邮件算法是完全确定的，所以相同的文件将产生相同的垃圾邮件散列。 由于哈希正好匹配，它们将具有0的编辑距离。 当缩放测量时，他们的匹配分数为100 - 完美匹配。

5.2不改变触发

在输入文件中进行更改，使得触发滚动哈希的上下文都不会更改，传统哈希值中的一个仍将被更改。 由于传统哈希只有64个可能的值，所以这个新文件仍将具有与原始文件相同的签名的2^（-6）可能性。 即使签名不同，它们只会有一个字符的差异，因此编辑距离为1。 应用公式 （8），我们可以将这两个文件的最终匹配得分计算为（100（100/（L1 L2）））。

5.3更改触发器

如果在输入文件中进行了修改，使得一个上下文触发器被改变，则最多两个传统散列值将被改变。 首先，滚动哈希将比原始文件更早地触发，改变传统哈希的当前值。 然后，因为传统哈希的下一个值的计算在输入文件的不同点开始，所以传统哈希的下一个值很可能也会被改变。 最后，对于传统散列的每个值，传统哈希的值将是相同的2^（-6）概率，因此，具有影响触发点的修改的文件的几率产生相同的邮件签名 因为原始文件是2^（-12）。
即使两个分段散列值在最终的CTPH签名中不同，这个新的签名将具有距离原始签名的两个编辑距离和（100（98/（L1 L2）））的匹配分数）。

5.4Random文件

如果它们之间的编辑距离足够小，则两个完全随机的文件将匹配。 作者早些时候证明，签名中任何两个字符的几率相同是2^（-6），对于长度为l1和l2的两个签名，其中l = min（l1，l2），匹配得分为100的几率为2^（-6）^l。 在l = 32的情况下，例如，精确匹配的可能性为2^（-192），因此非常不可能。

<l

剩余内容已隐藏，支付完成后下载完整资料

---

资料编号：[141913]，资料为PDF文档或Word文档，PDF文档可免费转换为Word

</l