Chapter 6:Hash Functions and Applications

# 6.Hash Functions and Applications

在本章中，我们超越了迄今为止所讨论的安全通信问题，转向一个具有许多应用的密码学基元：哈希函数。在最基本的层面上，哈希函数 H 提供了一种将长输入字符串确定性地映射为较短输出字符串（有时称为摘要）的方式。其主要要求是在 H 中找到碰撞（collision）应该是不可行的，即找到两个输入产生相同的摘要。如我们将看到的，抗碰撞（collision-resistant）哈希函数有许多用途，包括另一种被标准化为 HMAC 的方法，用于消息认证码的域扩展。

哈希函数可以被视为位于私钥和公钥密码学之间。一方面，如我们将在第七章看到的，哈希函数（在实践中）是使用对称密钥技术构造的。然而，从理论的角度来看，抗碰撞哈希函数的存在似乎是比其他对称密钥原语存在更强的假设，同时又比公钥加密所需的假设要弱。哈希函数在私钥和公钥设置中都有重要的应用。

哈希函数在密码学中已变得无处不在，并且它们经常用于需要比抗碰撞能力更强的属性的场景。实际上，常常将密码学哈希函数建模为“完全不可预测”（也称为随机神谕），我们将在第6.5节中讨论这个模型及其围绕的争议。在第6.6节中，我们将简要介绍随机神谕的一些应用；在公钥密码学的上下文中，我们将再次遇到随机神谕模型。

# 6.1 定义

哈希函数是一种简单的函数，它将一些长度的输入压缩成短而固定长度的输出。非密码学的经典应用是在数据结构中，用于构建哈希表，在存储一组元素时实现 $O (1)$ 的查找时间。具体而言，如果哈希函数 $H$ 的范围大小为 $N$ ，则元素 $x$ 存储在大小为 $N$ 的表的第 $H (x)$ 行。要检索 $x$ ，只需计算 $H (x)$ 并在表的对应行中查找存储的元素。对于此目的而言，“好”的哈希函数是那些产生少量碰撞的函数，其中碰撞是指对于不同的元素 $x$ 和 $x^{'}$ ，有 $H (x) = H (x^{'})$ ；在这种情况下，我们也说 $x$ 和 $x^{'}$ 发生了碰撞。（当发生碰撞时，两个元素被存储在同一个位置，增加了查找时间。）

抗碰撞（collision-resistant）哈希函数在精神上与此类似；再次，目标是避免碰撞。然而，存在一些根本的不同。首先，在数据结构的设置中，为了避免碰撞，我们希望哈希函数产生少量碰撞，而在密码学的设置中，避免碰撞成为了一个必须要满足的要求。此外，在数据结构的背景下，我们假设被哈希的元素集是独立于 $H$ 而且没有任何意图引起碰撞的。然而，在密码学的背景下，我们面临着一个可能会选择元素以明确引起碰撞的对手。这意味着抗碰撞哈希函数的设计要困难得多。

# 6.1.1 抗碰撞性

非正式地说，一个函数 $H$ 如果对于任何概率多项式时间算法来说在 $H$ 中找到碰撞是不可行的，那么它就是抗碰撞性的。我们只关心域比值域要大的哈希函数。在这种情况下，碰撞肯定存在，但是这样的碰撞应该很难找到。

形式上，我们考虑有密钥的哈希函数。也就是说， $H$ 是一个带有两个输入的函数，输入为密钥 $s$ 和字符串 $x$ ，输出为字符串 $H_{s} (x) = H (s, x)$ 。要求在随机生成的密钥 $s$ 下，很难找到 $H_{s}$ 中的碰撞。我们需要强调现在的密钥与我们之前考虑的密钥有一个主要区别：在当前的情况下，密钥 $s$ （通常）不是保密的，并且即使在对手已知 $s$ 的情况下，依然需要满足抗碰撞性。为了强调密钥可能不是保密的，我们在密钥上加上上标，并写为 $H_{s}$ 而不是 $H^{s}$ 。

定义 6.1： 哈希函数（输出长度为 $n$ ）是一对概率多项式时间算法 $(Gen, H)$ ，满足以下条件：

$Gen$ 是一个概率算法，输入安全参数 $1^{n}$ 并输出一个密钥 $s$ 。我们假设 $n$ 隐含在 $s$ 中。
$H$ 是一个确定性算法，输入密钥 $s$ 和字符串 $x \in {0, 1}^{*}$ ，输出字符串 $H_{s} (x) \in {0, 1}^{n}$ （其中 $n$ 是隐含在 $s$ 中的安全参数的值）。

如果 $H_{s}$ 仅对长度为 $n^{'} > n$ 的输入 $x$ 定义，则我们称 $(Gen, H)$ 是输入长度为 $n^{'}$ 的定长哈希函数。在这种情况下，我们也称 $H$ 为压缩函数。在定长情况下，我们要求 $n^{'}$ 大于 $n$ ，以确保 $H_{s}$ 压缩其输入。在一般情况下，该函数接受任意长度的字符串作为输入，因此它也是压缩函数（但仅对长度大于 $n$ 的输入压缩）。请注意，如果没有压缩，抗碰撞性是平凡的（因为可以简单地取恒等函数 $H_{s} (x) = x$ ）。

接下来我们定义安全性。像往常一样，我们首先为哈希函数 $H = (Gen, H)$ 、对手 $A$ 和安全参数 $n$ 定义实验过程：

碰撞查找实验 ${Hash-coll}_{A, H} (n)$ :

通过运行 $Gen (1^{n})$ 生成密钥 $s$ 。
对手 $A$ 获得密钥 $s$ ，并输出 $x, x_{0}$ 。（如果 $H$ 是输入长度为 $n^{'}$ 的定长哈希函数，则我们要求 $x, x_{0} \in {0, 1}^{n^{'}}$ 。）
实验输出定义为：如果 $x \neq x_{0}$ 且 $H_{s} (x) = H_{s} (x_{0})$ ，则输出为 1。在这种情况下，我们说对手 $A$ 找到了一个碰撞。

抗碰撞性定义说明没有有效的对手能在上述实验中找到碰撞，除非其概率可以忽略。

定义 6.2： 哈希函数 $H = (Gen, H)$ 是抗碰撞性的，如果对于所有概率多项式时间对手 $A$ ，存在一个可忽略函数 negl，使得

P r [{Hash-coll}_{A, H} (n) = 1] \leq negl (n) .

为简单起见，我们有时将 $H$ 或 $H_{s}$ 称为“抗碰撞性哈希函数”，即使严格来说我们只应该说 $H = (Gen, H)$ 是。这不应引起任何混淆。

实际使用的密码学哈希函数都被设计为显式具有抗碰撞性（以及其他性质）。在第 7 章中，我们将讨论一些哈希函数的设计原则以及一些常用的例子。在第 9.4.2 节中，我们将展示如何基于某个数论问题的难度构造具有已证明抗碰撞性的哈希函数。

无密钥哈希函数。实际使用的密码学哈希函数通常是无密钥的，并且具有固定的输出长度（类比于块密码），这意味着哈希函数只是一个固定的确定性函数 $H : {0, 1}^{*} \to {0, 1}^{ℓ}$ 。从理论角度看，这是有问题的，因为对于任何这样的函数，总是存在一个常数时间算法输出哈希函数中的碰撞：该算法仅在算法自身硬编码一个碰撞对 $(x, x_{0})$ 并输出。使用有密钥的哈希函数解决了这个技术问题，因为在合理的内存量下，不可能为每个可能的密钥硬编码一个碰撞

（在渐进的设置下，为每个安全参数的值硬编码一个碰撞也是不可能的）。

尽管如上所述，实际世界中使用的（无密钥）密码学哈希函数在所有实际目的上都是抗碰撞的，因为碰撞对是未知的（且计算上难以找到），即使碰撞必定存在。对于基于抗碰撞性哈希函数的方案，即使使用无密钥哈希函数 $H$ ，安全性证明仍然有意义，只要证明显示任何有效的攻击者“破解”该原语可以被用于高效地找到 $H$ 中的一个碰撞（本书中的所有证明都满足这个条件）。在这种情况下，安全性证明的解释是，如果一个攻击者能够破解该方案，那么可以用于找到一个明确的碰撞，而这被认为是困难的。

在本章和本书的其余部分，当正式证明依赖于抗碰撞性时，我们会考虑有密钥的哈希函数，但通常假设使用无密钥哈希函数。

# 6.1.2 安全性的较弱要求

对于某些应用，不需要具备碰撞抗性这么强的安全要求。以下安全性概念有时会被考虑：

第二原像抗性（Second-preimage resistance）： 非正式地说，如果给定 $s$ 和一个均匀的 $x$ ，那么对于一个多项式时间（ppt）的攻击者来说，找到一个 $x_{0} \neq x$ 使得 $H_{s} (x_{0}) = H_{s} (x)$ 是不可行的。换句话说，对于给定的哈希值 $H_{s} (x)$ ，找到一个不同的输入 $x_{0}$ ，使得它们的哈希值相等是困难的。
原像抗性（Preimage resistance）： 非正式地说，如果给定 $s$ 和 $y = H_{s} (x)$ （其中 $x$ 是均匀的），那么对于一个多项式时间（ppt）的攻击者来说，找到一个 $x_{0}$ （可能等于 $x$ ，也可能不等于 $x$ ），使得 $H_{s} (x_{0}) = y$ 是不可行的。可以预见，这基本上等价于 $H_{s}$ 是单向函数（one-way function）。

很显然，任何具有碰撞抗性的哈希函数也具有第二原像抗性。同样，如果一个哈希函数具有第二原像抗性，那么它也具有原像抗性。虽然我们没有给出上述概念的正式定义或证明这些蕴含关系，因为它们在本书的其余部分没有被使用。你可以在练习 6.1 中对上述内容进行形式化。

# 6.2 域扩展：Merkle–Damgård变换

在前面的章节中，我们讨论了哈希函数的基本概念和抗碰撞特性。现在，让我们来探讨一种重要的技术，即Merkle–Damgård变换，它可以将定长哈希函数转换为全功能的哈希函数。

# 6.2.1 定长哈希函数与全功能哈希函数

在介绍Merkle–Damgård变换之前，我们先回顾一下哈希函数的基本分类。根据输入和输出的长度，哈希函数可以分为两类：定长哈希函数和可变长度（或全功能）哈希函数。

定长哈希函数将输入数据压缩为固定长度的输出。例如，如果输入为任意长度的字符串，定长哈希函数可以将其压缩为128位或256位的摘要。常见的定长哈希函数包括MD5和SHA-256等。

可变长度哈希函数是一种更加灵活的哈希函数，它可以处理任意长度的输入，并将其压缩为固定长度的输出。这种哈希函数常用于处理较长的数据，比如文件或消息。Merkle–Damgård变换就是一种将定长哈希函数转换为全功能哈希函数的技术。

# 6.2.2 Merkle–Damgård变换的原理

Merkle–Damgård变换是由Ralph Merkle和Ivan Damgård在1979年独立提出的。它是一种将定长哈希函数转换为全功能哈希函数的构造方法。

Merkle–Damgård变换的基本思想是将输入数据分块处理，然后依次压缩这些块，最终得到输出。具体步骤如下：

将输入数据分割成多个固定大小的块。每个块的大小通常等于定长哈希函数的输出长度。
初始时，设置一个称为初始向量（IV）的值，作为第一个压缩步骤的输入。
对每个块进行压缩操作。压缩操作使用定长哈希函数来将前一个压缩结果和当前块压缩成一个新的结果。
最后一个块的压缩结果即为全功能哈希函数的输出。

Merkle–Damgård变换的关键在于定长哈希函数的抗碰撞特性。因为定长哈希函数是抗碰撞的，所以在每一步压缩操作中，即使输入数据存在相同的块，也不会导致碰撞。这保证了Merkle–Damgård变换的输出是唯一的，并且具有较高的安全性。

# 6.2.3 Merkle–Damgård变换的示例

为了更好地理解Merkle–Damgård变换的原理，让我们通过一个简单的示例来演示它的过程。

假设我们有一个定长哈希函数H，它将输入压缩为256位的摘要。我们希望将H转换为一个全功能哈希函数，以处理任意长度的输入。

首先，我们将输入数据分割成256位的块。假设我们要处理的输入为"hello, world!"，分割成两个块："hello, "和"world!"。

接下来，我们设置初始向量IV的值。假设IV为全0，即IV = 0x0000000000000000。

现在，我们依次对每个块进行压缩操作。假设第一个块"hello, "的压缩结果为$$H(IV, "hello, ") = 0x7a8f5c67e18c5d64$$。然后，我们将这个压缩结果作为下一个压缩操作的输入，计算第二个块"world!"的压缩结果$$H(0x7a8f5c67e18c5d64, "world!") = 0xf5a3e6c75c89d45b$$。

最后，我们的全功能哈希函数的输出为$$0xf5a3e6c75c89d45b$$。

通过Merkle–Damgård变换，我们成功将定长哈希函数H转换为一个全功能哈希函数，可以处理任意长度的输入数据。这种转换在密码学中有广泛的应用，特别是在设计密码学协议和构造密码学算法时非常有用。

# 6.3 使用哈希函数进行消息认证

在本节中，我们将探讨哈希函数在消息认证中的应用，包括Hash-and-MAC和HMAC两种方式。这些技术可用于验证消息的完整性和真实性，保障通信的安全性。

# 6.3.1 哈希函数与消息认证码（Hash-and-MAC）

# 什么是消息认证码（MAC）？

消息认证码是一种用于验证消息完整性和真实性的技术。它允许发送者对消息进行签名，而接收者可以通过验证签名来确定消息是否被篡改或伪造。MAC算法接受一个密钥和一个消息作为输入，输出一个固定长度的认证码。发送者将消息认证码附加在消息中一起发送。接收者收到消息后，可以使用相同的密钥对收到的消息进行验证，然后再次计算认证码，并与收到的认证码进行比较。如果两者相等，则说明消息没有被篡改或伪造，否则认为消息不可信。

# Hash-and-MAC是什么？

Hash-and-MAC是一种将哈希函数与消息认证码结合使用的技术。具体来说，首先使用哈希函数对消息进行哈希，然后使用一个密钥对哈希值进行签名，生成消息认证码。发送者将消息认证码附加在消息中一起发送。接收者收到消息后，可以使用相同的密钥对收到的消息进行验证，然后再次计算哈希值，并与收到的消息认证码进行比较。如果两者相等，则说明消息没有被篡改或伪造，否则认为消息不可信。

# Hash-and-MAC的特点

简单高效：哈希函数的计算和消息认证码的生成都是高效的操作，不会引入太大的额外开销。
安全可靠：只有知道密钥的合法用户才能正确生成和验证消息认证码，从而保证了消息的完整性和真实性。

# Hash-and-MAC的限制

密钥管理：发送者和接收者必须共享相同的密钥，因此密钥的安全管理和分发是一个重要的问题。
单向性：由于哈希函数是单向的，接收者无法从消息认证码中还原出原始消息。

# 6.3.2 哈希运算消息认证码（HMAC）

# 什么是HMAC？

HMAC是一种特殊的消息认证码构造方式，它将哈希函数与密钥混合使用，增强了消息认证码的安全性和性能。HMAC的全称是Hash-based Message Authentication Code。

# HMAC的构造方式

假设哈希函数为H，密钥为K，消息为M。HMAC的构造方式如下：

对密钥进行预处理，使其与哈希函数的输入长度相同（通常是哈希函数的块长度）。
将经过预处理的密钥与消息进行异或运算，得到新的输入。
对新的输入使用哈希函数进行多轮迭代计算，得到消息认证码。

# HMAC的优点

安全性高：HMAC结合了哈希函数和密钥，增加了攻击者破解的难度，提高了消息认证码的安全性。
灵活性强：可以使用不同的哈希函数和密钥长度来构造HMAC，适应不同的应用场景。

# HMAC的应用

HMAC广泛应用于各种安全协议和系统中，例如TLS、IPsec等。它在保障数据完整性和真实性方面发挥着重要作用，并为网络通信提供了一定程度的安全保障。

总结起来，哈希函数在消息认证中的应用包括Hash-and-MAC和HMAC两种方式。它们都可以用于验证消息的完整性和真实性，保障通信的安全性。在使用哈希函数进行消息认证时，需要注意密钥的安全管理和密钥长度的选择，以及选择合适的哈希函数来满足不同的安全需求。

# 6.4 哈希函数的通用攻击

在前面的章节中，我们介绍了哈希函数的基本定义、碰撞抗性以及在消息认证中的应用。然而，哈希函数并非完美的密码学原语，它们可能受到各种攻击。本节将探讨一些常见的通用攻击方法，如生日攻击和时空折中攻击。

# 6.4.1 生日攻击寻找碰撞

生日攻击是一种旨在寻找哈希函数碰撞的攻击方法。它基于生日悖论，即在一个包含n个不同元素的集合中，只需要大约 $\sqrt{n}$ 次的随机选择，就有很大的概率会出现两个相同的元素。将这个悖论应用到哈希函数中，如果哈希函数的输出长度为n位，则只需要约 $2^{n / 2}$ 次的随机输入，就有很大的概率会得到两个相同的哈希值。

生日攻击的基本思想是利用这种悖论，在有限的计算复杂性下找到两个不同的输入消息，它们产生相同的哈希值。一旦找到这样的碰撞，攻击者就可以伪造消息，绕过哈希函数的完整性保护。

# 6.4.2 小空间生日攻击

小空间生日攻击是一种优化的生日攻击方法，它允许攻击者在较小的计算空间内找到哈希函数的碰撞。传统的生日攻击需要存储大量的哈希值，这在某些情况下可能是不现实的。而小空间生日攻击通过利用内存换取计算复杂性的方式，使得攻击者可以在较小的内存空间中找到碰撞。

具体来说，小空间生日攻击使用时间和内存的折中方法，在有限的内存空间内存储部分哈希值，并利用哈希函数的抗碰撞性质来找到碰撞。虽然小空间生日攻击的计算复杂性较高，但在一些特定的应用场景下，它可以是一种有效的攻击方法。

# 6.4.3 时空折中攻击

时空折中攻击是一种综合利用时间和空间的攻击方法。它通过预先计算并存储一些中间结果，然后在攻击阶段利用这些中间结果来加速碰撞的搜索过程。时空折中攻击在一些特定的哈希函数构造中可能具有较高的效率，但它需要耗费大量的计算和存储资源。

时空折中攻击的基本思想是牺牲一部分计算时间来存储一些中间结果，以便在后续的碰撞搜索中加速计算过程。通过巧妙地选择时间和空间的折中方式，攻击者可以在较小的计算复杂性下找到哈希函数的碰撞。

总结起来，哈希函数虽然在许多应用中发挥着重要的作用，但也不是绝对安全的。在设计和使用哈希函数时，需要注意它们可能面临的各种攻击，并选择合适的构造和参数来增强其安全性。同时，对于攻击者来说，了解哈希函数的弱点和常见攻击方法，有助于发现潜在的漏洞和保护数据的安全性。

# 6.5 随机预言机模型

在密码学中，随机预言机模型（Random-Oracle Model）是一种常用的分析工具，用于研究哈希函数和其他密码学原语的安全性。在随机预言机模型中，我们假设存在一个理想的随机函数，称为随机预言机（Random Oracle）。这个随机预言机能够接收任意长度的输入，并返回一个随机的输出。

# 6.5.1 随机预言机模型的定义

d
具体地说，随机预言机 $R O$ 是一个函数，它接收一个输入 $x$ ，并返回一个输出 $R O (x)$ ，其中 $x$ 可以是任意长度的二进制串，而 $R O (x)$ 是一个随机的二进制串，其长度与输入无关。随机预言机 $R O$ 的输出是不可预测的，并且对于不同的输入 $x$ 和 $x^{'}$ ，它们的输出 $R O (x)$ 和 $R O (x^{'})$ 是不相关的随机串。

在随机预言机模型中，我们假设 $R O$ 是完美的，即它能够提供完美的随机性。这意味着我们可以随机选择输入并获得一个不可预测的输出，并且无论何时查询相同的输入，都会得到相同的输出。

# 6.5.2 随机预言机模型的应用

随机预言机模型在密码学分析中非常有用，它可以帮助我们研究和分析哈希函数的安全性。通过在随机预言机模型中进行分析，我们可以得到一些关键的结论和性质，例如：

在随机预言机模型下，特定构造的哈希函数是碰撞抗性的。
通过随机预言机模型，我们可以证明某些密码学原语的安全性。
随机预言机模型为密码学的研究和应用提供了更强的理论基础。

尽管随机预言机模型可能不完全反映真实世界中的密码学实践，但它仍然是一个有用的工具，能够帮助我们深入理解和分析哈希函数的安全性。通过随机预言机模型，我们能够得到对哈希函数性质的深入认识，为密码学的研究和应用提供更加严谨和可靠的理论基础。

# 6.6 哈希函数的其他用途

哈希函数在密码学和计算机安全领域具有广泛的应用。除了用于保障消息完整性和提供抗碰撞等基本安全性质外，哈希函数还在许多其他领域发挥着重要作用。在本小节中，我们将详细介绍一些哈希函数的其他应用。

# 6.6.1 指纹识别与去重

指纹识别是一种常见的应用，用于快速识别和比较大量数据中的重复项。在指纹识别中，哈希函数用于将数据映射为较短的指纹（哈希值）。由于哈希函数的唯一性特性，相同的数据将产生相同的指纹，不同的数据将产生不同的指纹。通过比较数据的指纹，可以快速确定数据是否重复，从而实现数据去重的目的。指纹识别广泛应用于数据存储系统，例如在云存储中去除重复的文件和数据块，以节省存储空间。

# 6.6.2 Merkle树

Merkle树是一种基于哈希函数的树状数据结构，常用于验证大量数据的完整性。在Merkle树中，每个叶节点都是数据块的哈希值，而每个非叶节点都是其子节点的哈希值的哈希值。通过逐级验证Merkle树中的哈希值，可以高效地验证大量数据的完整性，而无需逐个验证每个数据块。Merkle树被广泛应用于点对点网络传输和分布式存储系统，以确保数据的完整性和可靠性。

# 6.6.3 密码哈希

密码哈希是一种用于存储密码的安全方法。在密码哈希中，哈希函数将用户的密码映射为哈希值，并将哈希值存储在数据库中，而不是直接存储原始密码。这样做的好处是即使数据库泄露，攻击者也无法轻易地获得用户的明文密码。密码哈希通常采用加盐（salting）的方式，即在密码前面加上随机的盐值，增加了破解的难度。哈希函数在密码哈希中的应用保障了用户密码的安全性，防止了明文密码的泄露和攻击者的暴力破解。

# 6.6.4 密钥派生

密钥派生是一种从给定的主密钥派生出一系列派生密钥的技术。在密钥派生中，哈希函数用于生成不同的派生密钥，而这些派生密钥可以用于不同的加密和认证场景。密钥派生常用于安全协议和密钥管理中，用于生成多个相关的密钥，而无需直接使用主密钥。通过哈希函数的高效性，密钥派生可以灵活地生成多个派生密钥，从而支持更复杂的加密方案和协议。

# 6.6.5 承诺方案

承诺方案是一种密码学原语，用于实现在未来公开某些值之前，对该值进行绑定和隐藏。在承诺方案中，哈希函数用于生成承诺值，将承诺值绑定到某个特定的消息，从而确保该消息在未来不能更改。承诺方案在零知识证明、安全多方计算等领域有着重要的应用。通过哈希函数的不可逆性和唯一性，承诺方案实现了对信息的绑定和隐藏，确保了信息的保密性和完整性。

这些是哈希函数的一些其他应用示例，展示了哈希函数在密码学和计算机安全中的多样化应用。哈希函数的高效性、不可逆性和碰撞抗性等特性使其成为许多安全应用和协议的关键组成部分。通过哈希函数的灵活应用，我们能够构建更加安全和高效的密码学系统和安全协议。

编辑

上次更新: 2025/04/03, 09:58:11

← Chapter 5:CCA-Security and Authenticated Encryption Chapter 9:Number Theory and Cryptographic Hardness Assumptions→