Introduction

抗碰撞的哈希函数

HMAC：基于抗碰撞的哈希函数构建的。

碰撞的哈希函数：一个哈希函数，能将某个信息空间 M 映射到一个标签空间 T （信息空间应当比标签空间大得多），H：M→T (|M| >> |T|)，函数 H 的一个碰撞是一对信息 ($m_0$,$m_1$)， $m_0$ 和 $m_1$ 不同，但应用函数 H 会得到同样的输出。H($m_0$) = H($m_1$) 且 $m_0$ ≠ $m_1$，当应用这个函数时，他们会发生碰撞，即信息空间的 $m_0$ 和 $m_1$ 同被映射到标签空间中的同一个输出（输出空间没有足够的空间来不碰撞地容纳所有信息），则称函数 H 是碰撞的。

抗碰撞的哈希函数：抗碰撞是指 $m_0$ 和 $m_1$ 不同，使得 H($m_0$) = H($m_1$) 是很难找到的。如果有一个能直接找出这些碰撞的有效算法，我们说这个函数是抗碰撞的。如果对所有有效的算法 A ，这些算法都不能输出函数 H 的碰撞，通常，我们用一个算法 A 能够输出一个碰撞的概率来定义这个优势。

简单应用：特别地，给定一个抗碰撞的哈希函数，我们看如何简单地构建一个 MAC 。假设我们对短信息有一个 MAC ，假设我们有一个哈希函数是抗碰撞的，它从一个很大的信息空间里取值，将几个 G 的信息映射到小的信息空间里，我们用哈希函数输出值 MAC 来定义它。我们如何验证它呢？给定一个标签，我们通过重新计算给定信息的哈希值来验证，检查小 MAC 值是否能验证给定的标签。这是一个非常简单的方法来证明，抗碰撞可以取一个原型，这个原型可以处理短输入，把这个原型扩展成一个为非常长的输入而构建的原型。

安全性定理

如果底层 MAC 是安全的，并且 H 是抗碰撞的，那么这个组合可以计算长信息的 MAC ，得到的 MAC 也是安全的。

把这个安全性定理应用到 AES ，在 SHA-256 里，输出 256 位，即 32 字节，我们必须构建一个能处理 32 字节的 MAC ，我们可以应用 16 字节的 AES 把它带入到一个两个分组的 CBC 里，两个分组的 CBC 把 AES 从一个 16 字节的 PRF 扩展成了以一个 32 字节的 PRF ，然后取 SHA-256 的输出，把它带入到两分组的基于 AES 的 CBC 里，然后我们获得了一个非常简单的 MAC ，假设 AES 是个 PRF ，并且 SHA-256 是抗碰撞的，这个 MAC 是安全的。

抗碰撞是这个组合 MAC 的安全性的本质。假设我们使用的哈希函数 H 不是抗碰撞的，换句话说，存在一个算法，可以找到两个不同的信息，它们的 MAC 是一样的，这种情况下，这个组合 MAC 是不安全的，因为攻击者可以简单地使用一个选择信息攻击来获得 $m_0$ 的标签，然后输出 ($m_1$,t) 作为一个伪造，确实，t 是 $m_1$ 的一个有效 MAC 。

抗碰撞被直接应用于信息的完整性

想象我们有想保护的文件，我们把这些文件想象成软件包，我们想把这些软件安装在系统里，如下图有三个不同的软件包，现在用户想下载软件包，他想确保他下载的软件包的版本不是某个被攻击者篡改后的版本，内容被攻击者修改了。那么用户可以参考一个比较小的公共空间，这个公共空间只需保存这些软件包的哈希值，不需要很多这样的空间，公共空间唯一的要求是只读。

换句话说，攻击者无法篡改这个空间里的哈希值，然后，一旦用户参考了公共空间，他可以很容易地计算下载的软件包的哈希值，把结果与公共空间进行比较，如果它们相同，用户就知道他下载的版本是正确的。因为函数 H 是抗碰撞的，攻击者无法找到一个戴帽子的 $F_1$ ，可以让它拥有与 $F_1$ 同样的哈希值，因此攻击者无法修改 $F_1$ ，且不会被发现，因为无法让这个戴帽子的 $F_1$ 拥有与公共空间里一样的哈希值。

我们看一个 MAC 与上述类似的情况，在这个 MAC 的例子里，我们需要一个密钥来验证单个文件的标签，但我们不需要一个只读的公共空间；用抗碰撞的哈希函数，我们就不需要用一个密钥来验证，任何人都可以验证，但是我们需要这个多余的资源，即攻击者不能修改的空间，事实上，我们后面看到数字签名可以在完整性和资源两方面都达到最优，届时我们可以既让公众自行验证，又不需要只读空间。

但目前，只用 MAC 或抗碰撞哈希函数，我们只能达到单方面的要求，事实上，这种机制是非常流行的，实际上，Linux 发行版通常使用公共空间来发布它们软件包的哈希值，任何人在电脑上安装之前，可以确保他们下载了正确的软件包。

Generic birthday attack

针对抗碰撞哈希函数的通用攻击

针对分组密码的通用攻击是穷举攻击，穷举攻击迫使分组密码的密钥大小是 128 位或更多；针对抗碰撞哈希函数的通用攻击是生日攻击，生日攻击迫使抗碰撞的哈希函数的输出必须多于某个下界。

这里我们有抗碰撞的哈希函数，假设它输出 n 位，换句话说，它的输出空间大小大约是 2^n 。现在，信息空间要远远大于 n 位，我们说待哈希的信息可能有 100 个 n 位长。看这样一个算法，可以用大约 2^(n/2) 的时间，找到这个函数 H 的碰撞，这个算法如下工作：

①我们从信息空间里随机选择 2^(n/2) 个信息，即 $m_1$ ，…， $m_2$^(n/2) ，现在因为信息本身远远大于 n 位，它们有上百个 n 位，很有可能这些信息是不相同的，它们互不相同的概率很大。

②但对每一条选中的信息，我们应用哈希函数，获得标签 $t_i$ ，这个 $t_i$ 是 n 位字符串。

③现在我们在 $t_i$ 中寻找一个碰撞，换句话说，我们找一个 i 和 j ，满足 $t_i$ = $t_j$ ，一旦找到了，就等于是发现了碰撞，因为如前所述，以很高的概率，$m_i$ ≠ $m_j$ ，但 $m_i$ 的哈希值等于 $m_j$ 的哈希值，因此，我们找到了函数 H 的碰撞。现在如果我们找遍了这 2^(n/2) 个 $t_i$ 却没有找到碰撞，我们回到第一步尝试另一组 2^(n/2) 个信息。

我们需要迭代这个过程多少次才能发现碰撞？事实上，迭代次数是个非常小的数，意味着这个算法可以以大约正比于 2^(n/2) 的时间找到碰撞。由于每轮迭代会以 1/2 的概率找到碰撞，我们平均需要迭代 2 次，因此这个算法的运行时间是 2^(n/2) 乘以哈希函数的计算时间（这个算法需要大量的空间 O(2^(n/2)) ，但我们先忽略空间的问题）。如果你的哈希函数输出 n 位，总是存在一个攻击算法用 2^(n/2) 的时间发现碰撞，比如：如果我们输出 128 位，在 2^64 的时间里，可以找到一个碰撞，这将不是充分安全的，这就是为什么抗碰撞的哈希函数通常不输出 128 位。

从下面的例子可以看出，分组越大，算法越慢，有一些性能上的亏损，但安全性上有很多好处。

SHA-1 不推荐使用，有一个理论上的碰撞发现算法，需要 2^51 的时间，所以某人发现一个 SHA-1 的碰撞几乎只是时间问题。

生日悖论的证明

为了分析这种攻击，我们引入生日悖论的知识，它之所以称为悖论，是因为平方根函数增长缓慢，与人的直觉相悖。

设想我们有 n 个随机变量 $r_1$ ，$r_2$ ，…，$r_n$ ，取值范围是从 1 到 B 的区间里，我峨嵋你唯一的假设是，这 n 个随机变量是相互独立的，而且它们是同分布的，例如，它们可能都是在从 1 到 B 的区间里均匀分布的，但它们还是独立的均匀分布的变量。但如果我们把 n 设置为 B 的平方根大小，换句话说，如果我们从区间 1 到 B 内取样约 B 的平方根次，精确的说是 1.2 × B^(1/2) ，那么样本中有两个是一样的概率至少是 1/2 ，事实上，均匀分布是生日悖论中最坏的情况，换句话说，如果 $r_i$ 的分布不是均匀的，事实上，需要取样的次数要少于 1.2 × B^(1/2) 。那么，我们证明均匀分布的情况，也就能证明其他分布的情况，但这里给出的证明只对均匀分布成立。

证明过程：我们要求存在一对 i 和 j ，i ≠ j ，满足 $r_i$ = $r_j$ 的概率，我们求互斥事件的概率，就是说我们所求概率为 1 减去对所有 i ≠ j 都有 $r_i$ ≠ $r_j$ 的概率（这意味着我们选择的 n 个样本里没有发生碰撞）。当我们选择 $r_i$ 时，这是我们第一次选择，所以是不会发生任何碰撞的，但当我们取 $r_2$ 时，$r_2$ 不与 $r_1$ 碰撞的概率是 (B-1)/B ，类似的，当我们选择 $r_3$ ，$r_3$ 不与 $r_1$ 或 $r_2$ 碰撞的概率是 (B-2)/B ，…，直到我们获得了最后的 $r_n$，$r_n$ 不与不与之前所有的 $r_i$ 碰撞的概率是 (B- (n-1) )/B ，也就是 (B-n+1)/B ，将这些概率乘起来正是因为这些 $r_i$ 是相互独立的。

The Merkle-Damgard Paradigm

抗碰撞的哈希函数的构建

我们的目标是构建一个抗碰撞的哈希函数，对这些函数，即使找到一个碰撞也是困难的（尽管我们知道有很多碰撞存在），没有有效的算法可以输出哪怕一个碰撞。那么我们要构建这些哈希函数，我们分两步构建这些哈希函数：

①如果给我一个处理短信息的抗碰撞哈希函数，我们可以扩展它来构建一个处理长得多的信息的抗碰撞的哈希函数。

②构建安全压缩函数。

Merkle-Damgard 是一个非常通用的机制，所有的标准哈希函数都遵循这个机制，由一个压缩函数，构建抗碰撞的哈希函数。

Merkle-Damgard 工作过程：这里我们有函数 H ，我们假设 H 是抗碰撞的哈希函数，可以处理短输入，我们使用这个小函数 h ，h 有时叫做压缩函数（从 T 中取元素，正好与哈希函数相反），我们将取长信息 M 把它分成若干分组，然后我们使用一个固定值叫做 IV ，这里 IV 永远是固定的，它内嵌在代码和标准里，只是一个固定的 ID ，是函数的一部分。然后我们对第一个信息分组应用小的压缩函数 h ，一并使用这个 ID ，得到的叫做链接变量，将被交给下一压缩函数来压缩下一分组，一并使用前一链接变量输出下一链接变量，直到我们到达最后分组。在最后分组上，我们要做一个特别的事情，我们必须把补齐分组 PB 附在信息后面，在附上补齐分组之后，我们还是要压缩最后的链接变量与最后的分组，得到的输出就是实际哈希函数的输出。

补齐分组：我们看到，序列 1000 为实际明文分组的结尾，这个分组最重要的部分是我们对信息长度进行的编码，在这个补齐分组里，信息长度域固定为 64 位，所以在所有所有的 SHA 哈希函数中，最大信息长度为 2^64 - 1 ，事实上信息长度应当适应于 64 位分组，2^64 - 1 位的信息长度的上界对应我们能释放的信息来说足够长了。

如果最后一个分组长度是压缩函数分组长度的倍数，我们怎么办？通常，答案是如果在最后分组中没有空间留给补齐分组时，那么我们就必须加另外一个假分组把补齐函数放在那里。当然以正确的方式写 1000… 有一点非常重要，那就是补齐分组包含信息长度。

Constructing Compression Functions

由分组密码构建压缩函数

利用Davies-Meyer构建压缩函数

h 抗碰撞 => H 抗碰撞

我们能否从分组密码来构造压缩函数呢？答案是肯定的。

假设我们这里有一个特定的分组密码，用来处理 n 位分组，输入和输出都是 n 位。有一个经典的机制叫 Davies-Meyer 机制：h(H,m) = E(m,H)⊕H ，给定信息分组和链接变量，我们使用信息分组作为密钥来加密链接变量，然后我们在输出上再做一次异或。信息分组 $m_i$ 完全是在攻击者的控制之下，攻击者试图找到碰撞，这样他可以选择他想要的信息分组，我们把这个信息分组作为一个分组密码的密钥，当 E 是一个理想的密码时，我们可以证明这个机制事实上是抗碰撞的。

定理：如果 E 是一个理想的分组密码，意味着它是一个 {0,1}^n 上的随即置换的集合，如何置换由密钥 K 确定，在这个 E 是理想的分组密码的假设下，事实上，找到这个压缩函数 h 的碰撞需要 2^(n/2) 的时间，特别地，我们可以证明，任何能找到碰撞的人必须至少能花费 2^(n/2) 的时间来加、解密，这意味着，因为这个压缩函数只有 n 位长，总有一个通用的生日攻击可以在 2^(n/2) 的时间里找到碰撞，所以这个定理是说，这个抗碰撞函数确是抗碰撞的，通过生日攻击以在 2^(n/2) 的时间里找到碰撞，但没有算法可以做的比 2^(n/2) 更好。

一个不抗碰撞压缩函数的例子

Davies-Meyer 机制有一些特别的地方使得该机制是抗碰撞的，如果仅仅是猜这个机制，很有可能最终得到的不是抗碰撞的压缩函数，我们看如下问题：

假设我们如下定义了压缩函数，h(H,m) = E(m,H) ，我们使用目前分组作为密钥，加密这个链接变量 H，不同之处在于，我们不做 Davies-Meyer 机制里的异或，我们求证这个压缩函数不是抗碰撞的。

我们试图构建一个碰撞，即一对不同的 m 和 m’ 能在这个函数 H 下发生碰撞，我们怎么构造这个碰撞呢？选择任意的 H，m，和 m’ ，唯一的要求是 m 与 m’ 不同，如何构建 H’ 可以找出碰撞？首先，我们选择一个简单的方法来解释，如下图第一个选项，如果我们使用加密函数对两边进行加密，左边我们得到了 H’ 用 E 和密钥 m’ 加密的结果 E(m',H') ，右边用 m’ 加密，解密操作会被抵消，只剩下 m 的加密结果 E(m,H) ，即为我们想找的碰撞，这里使用了解密函数 D ，容易为压缩函数构建碰撞。

利用Miyaguchi-Preneel构建压缩函数

Miyaguchi-Preneel 方法有 12 种变体，通过玩弄各种异或以及把变量放在不同位置等手段，都可以得到一个抗碰撞的机制，但也有许多类似的变体并不是抗碰撞的

SHA-256

SHA-256 使用了 Merkel-Damgard 机制 和 Davies-Meyer 压缩函数，那么，Davies-Meyer 的底层分组密码是什么？这个分组密码叫做 SHACAL-2 ，它的参数使用了 512 位密钥，密钥是从信息分组里提取的，信息分组是 512 位，一次会处理它的 512 位输入信息，这个分组密码的分组大小是 256 位。

由数论里的困难问题构建压缩函数

我们说这些压缩函数是可证实的，因为如果你可以找到这种压缩函数的碰撞，那么你就可以解决非常困难的理论问题，一般这类问题是难解的。因此，如果数论问题是难解的，得到的压缩函数可被证实是抗碰撞的。

工作过程：我们选取一个非常大的质数，约 700 个十进制数，2000 位二进制数，我们在 1 到 p 之间选择两个随机数 u 和 v ，现在如下定义压缩函数，它在 0 到 p-1 之间取两个数，输出 0 和 p-1 之间的一个数，那么其压缩率为 2:1 ，然后计算双重指数，计算 $u^H$ × $v^m$ ，现在这个定理表述为一个事实，事实上，如果你找到这个压缩函数的一个碰撞，那么你就可以解一个标准的数论难题，叫做离散对数问题。

所有人都相信离散对数问题是难解的，因此这个压缩函数可证实是抗碰撞的。为什么在实际中我们不使用这种压缩函数呢？因为与分组密码相比，这个压缩函数速度太慢了。

HMAC：a MAC from SHA-256

我们能否不依赖 PRF ，直接用大的哈希函数来构建 MAC 呢？

第一个点子

假设给你一个 Merkel-Damgard 哈希函数，注意到它把长信息哈希成短的摘要，我们想把长信息直接转成 MAC ，首先我们想到，我们为什么不计算 MAC 密钥联结上待求 MAC 的信息后的哈希呢？但实际上，这是完全不安全的，因为由于它的密钥扩展，如果我告诉你一个特定信息的标签 H(m) ，攻击者很容易加上另外一个分组，然后再计算一次压缩函数 h ，现在他们可以获得原信息联结上补齐分组的标签，因此，这是个存在性伪造。

HMAC

有一个标准方法可以把一个抗碰撞的哈希函数转成一个 MAC ，这个标准方法叫做 HMAC 。特别地，我们可以使用 SHA-256 这一哈希函数来构建 MAC ，输出 256 位，事实上，人们相信 HMAC 是一个伪随机函数，所以通过 SHA-256 ，我们获得了一个伪随机函数输出 256 位的信息。

工作过程：首先我们取密钥 k ，然后我们在密钥后面联结一个叫做 ipad 的内部密码本，这使它成为Merkel-Damgard 机制的一个分组，比如，对于 SHA-256 来说将是 512 位，我们把得到的分组附在信息 m 前面，然后求哈希，刚刚证明了只做这些是完全不安全的，不过除此之外， HMAC 还取这 256 位输出，计算密钥 k 与外部密码本 opad 异或，把异或结果附在 256 位输出的前面，也会形成 512 位的一个分组，然后 HMAC 取这两个分组的哈希值，最终得到信息 m 的标签。

如果压缩函数 h 是 PRF ，密钥是第一个上面的输入，那么我们计算 PRF h 在固定 IV 处的值，结果是一个随机值，我们记为 $k_1$ ，然后我们应用到 Merkel-Damgard 链，对外部密码本做同样的事情，认为 h 是 PRF ，密钥是上面的输入，我们使用不同的密钥，应用这个 PRF ，计算在固定值 IV 的值，得到另外一个结果 $k_2$ 。现在，当我们使用这些密钥 $k_1$，$k_2$ 来计算 HMAC 时，这看上去非常熟悉，这就是 NMAC 。

为了证明这是 NMAC 机制，我们必须假设这个压缩函数 h 是 PRF ，密钥是下面的函数输入，我们说这些密码本 ipad 和 opad 它们是固定的 512 位的常数。

我们回头看，发现 HMAC 与 NMAC 的主要不同之处是这些密钥 k⊕ipad ，k⊕opad 互相是有关联的，它们只不过是同样的密钥异或上不同的常数。本质上，密钥 $k_1$ 和 $k_2$ 也是互相关联的，因为它们是在同样的固定值 IV 上应用 PRF 计算得到的。

为了证明 $k_1$ 和 $k_2$ 是伪随机且相互独立的，我们必须证明压缩函数不仅当其上面的输入是密钥时，它是 PRF ，而且当使用关联密钥时，它也是 PRF。基于这些假设，应用对 NMAC 一模一样的分析来分析 HMAC ，我们可以证明 HMAC 是安全的 MAC，其安全的界定与 NMAC 一致，换句话说，你不必改变密钥，只要求 MAC 的信息数小于输出标签的一半空间大小（本质上就是生日攻击里的平方根）。对于 HMAC 和 SHA-256 ，输出空间是 2^256 ，平方根是 2^128 ，这意味着你可以使用 HMAC 和 SHA-256 ，想处理多少信息都可以，而且是始终保持安全的。

TLS 要求支持 HMAC 和 SHA-196 ，意味着 HMAC 由 SHA-1 函数构建，并截断到 96 位，SHA-1 输出 160 位。SHA-1 不再被认为是安全的哈希函数，那怎么能在 HMAC 里使用 SHA-1 呢？实际上，这是没问题的，因为 HMAC 的安全性分析不需要 SHA-1 是抗碰撞的，当输入运行是密钥时，只需要压缩函数 SHA-1 是 PRF ，目前我们知道，这对 SHA-1 的底层压缩函数也成立，即使它可能不是抗碰撞的。

Timing attacks on MAC verification

计时攻击

一个特别的 HMAC 验证的实现，这个实现来自 Keyczar 库。输入为密钥、信息和标签，我们的验证方法是重新计算信息的 HMAC ，然后比较得到的 16 字节与实际给的签名 16 字节。事实上很多人已经实现了它，问题是，如果看下图 “==” 的比较是如何实现的，你可能觉得比较应该是逐字节地进行，第一次发现它不相等的话，循环终止，说两字符串不相等，这造成了针对该密码库的一个严重的计时攻击，这是一个非常合理的实现 MAC 验证的程序。

攻击过程：设想你是攻击者，你有信息 m ，你想获得 m 的一个有效标签。现在，你的目标是攻击一个服务器，这个服务器存放着 HMAC 的密钥。这个服务器开放了一个接口，这个接口接收信息与 MAC ，检查这个 MAC 是否有效，如果 MAC 有效，服务器用这个信息进行操作；如果 MAC 无效，服务器拒绝，退回到信息发送方或拒绝这条信息。现在这个攻击者有机会提交大量信息，看看能不能推出特定的攻击信息的标签，我们可以使用计时攻击来做，攻击者提交许多信息询问信息的标签，而信息始终是一样的，但对于标签来说，攻击者尝试很多不同的标签。

①在第一个询问里，攻击者提交目标信息和一个随机标签，然后攻击者测量服务器的反应时间。

②他提交的下一个询问将尝试的第一字节的所有 256 种情况。标签中剩下的字节是任意选取的，它们是什么并不重要，但对于第一个字节，攻击者会提交一个以 0 字节开头的标签，然后他观察服务器是否比之前花稍长一点的时间验证标签。如果服务器花了与第一步严格相同的时间来验证这个标签，那么攻击者会再次尝试，这次以字节 1 开头，如果服务器依然反应迅速，攻击者会尝试以字节 2 开头，直到服务器花了稍微长一点的时间给出反应，就意味着当服务器比较正确的 MAC 和攻击者提交的 MAC 时，在这个字节上，两个 MAC 是一样的，而不一样的是第二个字节。

③攻击者知道第一个字节后，他可以对第二个字节实施一模一样的攻击，直到服务器接受正确的 MAC 。然后我们继续在这个假信息上做手脚，攻击服务器。

防御方法

第一种防御方法

Keyczar 严格地实现了这种防御，首先我们看攻击者提交的签名的字节数是否正确，如果不是，我们就不承认这是个有效的 MAC ，如果签名确实有正确的长度，我们实现比较器，他们总是花相同的时间比较两个字符串。

第二种防御方法

不被广泛实现，这种攻击试图把字符串的比较对攻击者隐藏起来，这里的验证算法取密钥、信息和一个攻击者提供的候选 MAC 作为输入，然后我们进行比较，首先计算信息的正确 MAC ，但然后不直接比较 MAC 和攻击者的签名，我们再取一次哈希值，我们计算 MAC 的哈希值，计算签名的哈希值，让然如果参数一样，它们的哈希也是一样的，所以这个比较会成功。如果签名和 MAC 的第一个字节一样，先不管其他字节的情况，我们再计算一次哈希，很有可能这两个得到的值是完全不一样的，因此，逐字节的比较器会在第一轮就完成输出，这个攻击者将无法知道到底在比较什么字符串，因此不能实施计时攻击。

【DanBoneh】Collision Resistance