在本章中，我们将介绍加密哈希函数并探讨它们的一些应用。在最基本的层次上，哈希函数提供了一种将长输入字符串映射到短输出字符串（有时称为摘要）的方法。主要要求是避免冲突，或避免映射到同一摘要的两个输入。抗冲突散列函数有多种用途。我们将在这里看到的一个示例是另一种标准化为HMAC的方法，用于实现消息身份验证代码的域扩展。

除此之外，散列函数在密码学中已变得无处不在，它们通常用于要求比抗冲突性强得多的属性的场景。将加密散列函数建模为“完全不可预测”（也称为随机预言）已变得很常见，我们将在本章后面详细讨论该框架以及围绕该框架的争议。在这里，我们只涉及随机oracle模型的几个应用程序，但当我们转到公钥加密的设置时，将再次遇到它。

散列函数很有趣，因为它们可以被视为介于私钥加密和公钥加密之间。一方面，正如我们将在第6章中看到的，它们（实际上）是使用对称密钥技术构造的，而散列函数的许多规范应用程序都是在对称密钥设置中。然而，从理论角度来看，抗冲突散列函数的存在似乎代表了比伪随机函数的存在更强的定性假设（但比公钥加密的存在更弱的假设）。

5.1 Definitions

散列函数是简单的函数，它接受一定长度的输入并将其压缩成短的、固定长度的输出。散列函数的经典用法是在数据结构中，在数据结构中，它们可以用来构建散列表，从而在存储一组元素时启用O（1）查找时间。具体地说，如果散列函数H的范围大小为N，则元素x存储在大小为N的表的行H（x）中。要检索x，只需为存储在其中的元素计算该表的行H（x）和probeth即可。用于此目的的“良好”散列函数是产生少量冲突的函数，其中冲突是一对不同的项x和x0，其中H（x）=H（x0）；在这种情况下，我们也说x和x0碰撞。（发生冲突时，两个元素最终存储在同一单元格中，从而增加查找时间。）

抗冲突散列函数在精神上类似。同样，目标是避免碰撞。然而，两者之间存在着根本性的差异。首先，在数据结构设置中最小化冲突的愿望成为在加密设置中避免冲突的要求。此外，在数据结构的上下文中，我们可以假设数据元素集是独立于哈希函数选择的，并且没有任何导致冲突的意图。相比之下，在密码学的背景下，我们面临的是一个对手，他选择的元素可能具有导致冲突的明确目标。

这意味着抗冲突散列函数更难设计。

5.1.1 碰撞阻力 Collision Resistance

非正式地说，如果任何概率多项式时间算法都无法在H中找到冲突，则函数H是抗冲突的。我们只对域大于其范围的哈希函数感兴趣。在这种情况下，碰撞必须存在，但这样的碰撞应该很难找到。

形式上，我们考虑键入哈希函数。也就是说，H是一个双输入函数，它接受一个键s和一个字符串x作为输入，并输出一个字符串。要求是，对于随机生成的密钥s，必须很难在 中找到冲突。在此上下文中的键和我们迄今为止使用的键之间至少有两个区别。首先，并非所有字符串都必须对应于有效密钥（即，可能没有为某些密钥定义Hs），因此密钥s通常由算法Gen生成，而不是统一选择。第二，也许更重要的是，这个密钥s（通常）不是保密的，即使对手被赋予了s，也需要抵抗冲突。为了强调这一点，我们在键上加上标并写 而不是。

DEFINITION 5.1 散列函数 A hash function

哈希函数（输出长度为l）是一对概率多项式时间算法（Gen，H），满足以下条件：

•Gen是一种概率算法，输入安全参数 ，输出密钥s。我们假设在s中是隐式的。

•H将一个键s和一个字符串作为输入并输出一个字符串（其中n是s中隐含的安全参数的值）。

如果仅为输入定义了并且l'(n)>l(n)，那么我们说（Gen，H）是长度为l'的输入的固定长度哈希函数。在这种情况下，我们也将H称为压缩函数。

在固定长度的情况下，我们要求l'大于l。这确保函数压缩其输入。在一般情况下，函数将任意长度的字符串作为输入。因此，它也会压缩（尽管只压缩长度大于l（n）的字符串）。请注意，如果没有压缩，碰撞阻力很小（因为可以只取恒等式函数（x）=x）。

碰撞发现实验 The collision-finding experiment

我们现在开始定义安全性。通常，我们首先为哈希函数∏=（Gen，H）、对手a和安全参数n定义一个实验：

碰撞阻力的定义表明，在上述实验中，没有有效的对手能够发现碰撞，除非概率可以忽略不计。

DEFINITION 5.2 抗碰撞 collision resistant

如果对于所有概率多项式时间对手A，存在一个可忽略的函数negl，使得 ，则哈希函数∏=（Gen，H）具有抗冲突性。

为简单起见，我们有时将H或 称为“抗冲突散列函数”，尽管从技术上讲，我们应该只说（Gen，H）是。这不应引起任何混乱。

加密散列函数的设计明确目标是抗冲突（以及其他）。我们将在第6章讨论一些常见的现实世界哈希函数。在第8.4.2节中，我们将看到如何基于对某个数论问题的硬度的假设，构造具有经验证的抗冲突性的哈希函数。

无键哈希函数 Unkeyed hash functions

在实践中使用的加密哈希函数通常具有固定的输出长度（就像块密码具有固定的密钥长度）并且通常是未加密的，这意味着哈希函数只是一个固定函数. 从理论角度来看，这是有问题的，因为对于任何这样的函数，总是有一个常数时间算法将冲突放在H中：该算法只输出一个硬编码到算法本身的冲突对（x，x'）。使用键控哈希函数解决了这一技术问题，因为不可能使用合理的空间量为每个可能的密钥硬编码冲突对（并且在渐进设置中，不可能为安全参数的每个值硬编码冲突对）。

尽管有上述规定，但现实世界中使用的（无眼）加密散列函数在所有实际用途中都是抗冲突的，因为碰撞对是未知的（并且在计算上很难找到），即使它们必须存在。基于哈希函数抗冲突性的某些构造的安全性证明即使在使用无眼哈希函数H时也是有意义的，只要证明任何有效的对手“破坏”原语都可以有效地在H中找到冲突（本书中的所有证明都满足此条件）在这种情况下，对安全性证明的解释是，如果对手可以在实践中破坏该方案，那么它可以用于在实践中发现冲突，我们认为这是很难做到的。

5.1.2 较弱的安全概念 Weaker Notions of Security

在某些应用中，仅依靠弱于抗碰撞的安全要求就足够了。这些措施包括：

•第二个前像或目标碰撞阻力：非正式地说，如果给定s和统一的x，哈希函数是第二个前像阻力。ppt对手不可能找到x'≠x，从而 。

•预映像抵抗：非正式地说，哈希函数是预映像抵抗的，如果给定s和统一y，ppt对手不可能找到值x，从而 （x）=y。（展望第7章，这基本上意味着 是单向的。）

任何抗冲突的散列函数也是抗第二个前映像的。

这是因为，如果给定一个统一的x，对手可以找到x'≠x，其中，那么它可以清楚地找到碰撞对x和x'。

同样，任何抗第二预映像的哈希函数也抗重新映像。这是因为，如果有可能，给定y，找到一个x，使得 （x）=y，那么我们也可以得到一个给定的输入x'，计算y:= （x'），然后得到一个 （x）=y的x。高概率x'≠x（取决于H压缩的事实，因此多个输入映射到相同的输出），在这种情况下，已找到第二个前图像。

我们没有正式定义上述概念或证明上述含义，因为本书其余部分没有使用这些概念。在练习5.1中，要求您将上述内容正式化。

5.2

(b)定类似权利要求是否分别适用于抗第二原像和抗原像。在每种情况下都证明你的答案。

参考答案

5.2 a

5.2 b

5.2 域扩展：Merkle-Damgard变换 Domain Extension: The Merkle-Damg˚ard Transform

哈希函数通常是通过首先设计一个处理固定长度输入的抗冲突压缩函数，然后使用域扩展来处理任意长度的输入来构造的。在本节中，我们将展示一种解决域扩展问题的方法。我们回到第6.3节中设计抗碰撞压缩功能的问题。

Merkle–Damgard变换是将压缩函数扩展为完整哈希函数的常用方法，同时保持前者的抗冲突特性。它在实践中广泛用于哈希函数，包括MD5和SHA系列（参见第6.3节）。这种转换的存在意味着，在设计抗冲突哈希函数时，我们可以将注意力限制在固定长度的情况。这反过来使设计抗冲突散列函数的工作变得更加容易。从理论角度来看，Merkle–Damg˚ard变换也很有趣，因为它意味着单比特压缩与任意量压缩一样容易（或一样难）。

具体而言，假设压缩函数（Gen，h）将其输入压缩一半；假设其输入长度为2n，输出长度为n。（只要h压缩，构造就可以不考虑输入/输出长度。）我们构造了一个抗冲突哈希函数（Gen，h），该函数将任意长度的输入映射到长度为n的输出。（Gen保持不变。）

Merkle–Damgard变换在构造5.3中定义，并在图5.1中描述。构造步骤2中使用的值z0称为初始化向量或IV，是任意的，可以用任何常数替换。

Construction 5.3 The Merkle-Damgard transform

Figure 5.1 The Merkle-Damgard transform

5.6

对于以下对Merkle–Damgard变换（构造5.3）的每个修改，确定结果是否具有抗碰撞能力。如果是，请提供证据；如果没有，演示一次攻击。

(a)修改结构，使输入长度完全不包括在内(假设生成的哈希函数仅为长度为块长度整数倍的输入定义。)

(b)修改结构

参考答案

5.6 a

5.6 b