密码学专题 - 单向散列函数

散列函数是一类将任意长度的输入位 (或字节) 串转换为固定长度的输出的函数。散列函数的一个典型应用是数字签名。给定一个消息 $m$ ，当然可以对这个消息本身进行签名。然而，大多数数字签名方案所采用的公钥运算的运算很大，直接对消息本身签名非常不经济。因此不会直接对 $m$ 进行签名，而是应用散列函数 $h$ ，对 $h(m)$ 进行签名。相对于成千上万位长度的消息而言，散列函数的输出一般在 128 位到 1024 位之间。对 $h(m)$ 的签名比对消息 $m$ 的签名要快得多。为保证采取这种方法构造的签名是安全的，必须要求散列函数 $h$ 满足以一条件：很难构造两个消息 $m_1$ 和 $m_2$ ，使得 $h(m_1)=h(m_2)$ 。下面将详细讨论散列函数的安全性质。

散列函数有时又称为消息摘要函数，其散列结果也称作摘要或者指纹。

散列函数在密码学中有很多应用，它在密码系统中的各个不同部分之间建立紧密的联系。当输入是变长的值时，可以使用散列函数映射为固定长度的值。散列函数可以作为密码学中的伪随机数生成器，从一个共享密钥生成几个密钥。它所具有的单向性也可以起到隔离系统不同部分的作用，以保证即使攻击者得到了其中某个值，也不能获得其他值。

7.1 散列函数的安全性

如上文所述散列函数将任意长度的消息 $m$ 映射为固定长度的输出 $h(m)$ ， $h(m)$ 的长度一般在 128 位到 1024 位之间。可能会对输入的长度有所限制，但对所有实用的目的而言输入都可以是任意长度的。散列函数要满足几个要求，其中最基本的要求是它必须是单向函数：即对给定的消息 $m$ ，计算 $h(m)$ 很容易；而对于给定的 $x$ ，不可能求出满足 $x=h(m)$ 的 $m$ 。换句话说，单向函数是计算容易但求逆困难的函数，单向函数也因此得名。

在散列函数的所有性质中，最常提到的是它的抗碰撞性。一对碰撞是指两个不同的输入 $m_1$ 和 $m_2$ 使得 $h(m_1)=h(m_2)$ 。任意一个散列函数都会有无穷多个这样的碰撞 (因为有无限个可能输入值，有限个可能输出值)。因此，散列函数不可能是无碰撞的。抗碰撞性是要求虽然碰撞存在，但很难被找到。

7.2 实际的散列函数

好的散列函数并不多。目前主要从 SHA 系统中选择：SHA-1、SHA-224、SHA-256 和 SHA-512。当然，还有 SHA-3。

几乎所有实际使用的散列函数都是迭代的散列函数，这里我们也只讨论这一类的散列函数。迭代的散列函数首先将输入分成固定长度的分组序列 $m_1,...,m_k$ ，最后一个分组要进行填充以使其达到固定的长度，分组的长度一般为 512 位，最后一个分组通常包含一个表示输入长度的位串。然后使用一个压缩函数和固定大小的中间状态对这些消息分组按顺序进行处理，这个过程由固定的值 $H_0$ 开始，随后计算 $H_i=h'(H_{i-1},m_i)$ ，最后一个值 $H_k$ 便为散列函数的输出。

散列函数的这种迭代设计有应用上的优势。首先，与直接处理可变长度的位输入相比，这样的迭代运算易于规定和实现；其次，这种结构使得我们可以在得到消息的第一部分时就开始计算，在实际应用中对一个数据计算散列值时，可以实时地进行散列，而无须存储这些数据。

7.2.1 一种简单但不安全的散列函数

在讨论实际使用的散列函数之前，以一个不安全的迭代散列函数的例子来开始，这个例子会帮助该读者理解针对散列函数的通用攻击的定义。该散列函数基于 256 位密钥的 AES 算法来构造，将 256 位密钥 $K$ 设定为全 0。如果对消息 $m$ 进行散列运算，首先将消息进行填充然后每 128 位一组分成 $k$ 个分组，分别为 $m_1,...,m_k$ 。具体的填充细节这里不详述，也不重要。令 $H_0$ 的 128 位都为 0。然后根据 $H_i=AES(H_{i-1} \bigoplus m_i)$ 进行计算， $H_k$ 为散列函数的输出结果。

接下来给出一种非通用攻击。取一条消息 $m$ 经过填充后可以分为两个分组 $m_1$ 和 $m_2$ ，将这两个明文分别用散列函数进行迭代得到 $H_1$ 和 $H_2$ ， $H_2$ 也是该散列函数的输出值。现在构造消息 $m_1'=m_2 \bigoplus H_1$ 和 $m_2'=H_2 \bigoplus m_2 \bigoplus H_1$ ， $m_1'$ 和 $m_2'$ 合并构成一段消息，进行填充得到 $m'$ 。根据散列函数构造的性质可知 $m'$ 经过散列后的结果仍然是 $H_2$ 。以较高的概率， $m$ 和 $m'$ 为不同的位串。也就是两个不同的消息 $m$ 和 $m'$ 的散列值相同，即产生了碰撞。

证明：
$H_1 = AES(H_0 \bigoplus m_1) = AES(m_1)$

$H_2 = AES(H_1 \bigoplus m_2)$

$H_1' = AES(H_0 \bigoplus m_1') = AES(m_1') = AES(m_2 \bigoplus H_1)$

$H_2' = AES(H_1' \bigoplus m_2')$

$= AES(AES(m_2 \bigoplus H_1) \bigoplus (H_2 \bigoplus m_2 \bigoplus H_1))$

$= AES(AES(H_2))$

$= H_2$

也就是说，这个证明需要 $K = 0, H_0 = 0$ 。那这个前提条件也太特殊了？

7.2.2 MD5

MD5 是由 Ron Rivest 设计的一个 128 位的散列函数。MD5 在 MD4 的基础上强化了抗攻击能力，MD4 的运算非常快，但是非常脆弱。现在也同样发现了 MD5 的弱点，但是，MD5 仍然应用于很多实际系统中。

计算 MD5 的第一步是将消息分为 512 位的序列分组，对最后一个分组要进行填充，消息的长度信息也在其中。MD5 有 128 位的状态变量，它们被分为 4 个 32 位的字。压缩函数 $h'$ 共有 4 轮，在每一轮中，消息分组和状态变量进行混合，这种混合运算由 32 位的字上的加法、异或、与、或、轮转运算组合而成。每一轮中将整个消息分组都混合在状态变量中，因此每个消息字都使用了 4 次。在 4 轮的压缩 $h'$ 完成之后，将结果与输入状态相加得到 $h'$ 的输出。

这种在 32 位字上运算的结构在 32 位 CPU 的机器上特别有效，这种结构首先由 MD4 采用，现已成为很多密码学原主的一个基本特性。

对于大多数应用来说，MD5 的 128 位散列长度是不够的。由生日悖论可知，对 128 位散列函数大约进行 $2^{64}$ 次计算就可以找到一个碰撞。这也就是说通过 $2^{64}$ 个 MD5 的计算就可以发现碰撞，这对现在的密码系统来说是不够的。

MD5 算法的问题还更糟。MD5 的内部结构设计也会使很多更有效的攻击成为可能。迭代散列函数设计背后的基本思想之一是如果 $h'$ 是抗碰撞的，那么由 $h'$ 所构成的散列函数 $h$ 也是抗碰撞的。也就是说， $h$ 中的任何碰撞都是由迭代函数 $h'$ 的碰撞所导致的。这些年来 MD5 算法的迭代压缩函数 $h'$ 已经被证明可以产生碰撞，虽然 $h'$ 的碰撞不能完全意味着是 MD5 算法的碰撞。但最近的密码分析进展表明 (由 Wang 和 Yu 的工作突破) 已经可以通过少于 $2^{64}$ 步的计算找到针对 MD5 算法的碰撞。虽然这种攻击并不能攻破 MD5 算法的所有用法，但是可以说 MD5 是脆弱的，因此不宜再使用了。

7.2.3 SHA-1

安全散列算法由 NSA 设计并由 NIST 进行标准化。最早的版本被称为 SHA (现称为 SHA-0)，这个算法有一个缺陷，NSA 发现并修复了这个缺陷，NIST 公布了改进后的版本，称为 SHA-1。

SHA-1 是 160 位的散列函数，与 MD5 一样也是基于 MD4 的，因此与 MD5 有很多共同的特性，但它的设计更加保守，要慢于 MD5。尽管如此，SHA-1 算法仍然是不安全的。

SHA-1 算法的每一个 160 位的状态是由 5 个 32 位的字组成。与 MD5 算法类似，SHA-1 算法总共也有 4 轮，每一轮都由定义在 32 位字长上的基本运算混合而成。所不同的是，MD5 对每个消息分组进行 4 次处理，而 SHA-1 用线性递归的方法将 16 个字长的消息分组扩展为它所需要的 80 个字长。这是对 MD4 技术的一种推广。在 MD5 中，消息的每一位在混合函数中都被使用 4 次，而 SHA-1 的线性递归保证了消息的每一位都至少影响混合函数 12 次。有趣的是，从 SHA-0 到 SHA-1 的唯一改变是对线性递归增加了 1 位的轮转。

SHA-1 的主要问题不是内部缺陷，而是输出为 160 位的长度。进行 $2^{80}$ 步运算就可以使用 160 位的散列函数产生碰撞，这个安全等级低于我们对于分组密码密钥长度为 128 ~ 256 位的要求，当然也不符合对于分组密码 128 位的设计安全等级。虽然进行 SHA-1 运算要比 MD5 花费更多的时间，但是已经可以证明采用少于 $2^{80}$ 步的运算就可以使用 SHA-1 产生碰撞。

3.3 SHA-2

在 2001 年，NIST 公共的标准草案包含了 3 个新的散列函数，后于 2004 年又修订了该规范，增加了一个新的散列函数。这些散列函数都属于 SHA-2 系统，分别有 224 位、256 位、384 位、512 位的输出，设计用于与密钥长度为 128 位、192 位、256 位的 AES 算法以及 112 位的 3DES 算法一起使用。这些算法的结构与 SHA-1 非常类似。

SHA-256 比 SHA-1 慢得多。

有一些针对 SHA-2 系列迭代散列函数其他缺陷的修复方案：截断输出。如果散列函数是 $n$ 位输出，那么只取其前面的 $n->s$ ( $s$ 为某个正整数) 作为散列值。事实上，SHA-224 和 SHA-384 算法都是如此设计的，SHA-224 是将 SHA-256 丢弃了 32 位输出，而 SHA-384 是将 SHA-512 丢弃了 128 位位输出。为了满足 128 位的安全要求，需要采用 SHA-512 算法，然后丢弃 256 位输出，返回剩余的 256 位作为截断散列函数的输出结果。由于生日攻击，这个 256 位的散列函数可以满足 128 位的安全性设计目标。