视频

杂凑函数基础

杂凑函数（aka 哈希函数、报文摘要函数、散列函数等），是将任意长度的报文 $m$ 压缩成固定长度的报文摘要 $H(m)$ 的函数。

有两种杂凑函数，不带密钥的（MDC）、带密钥的（MAC）。

特性

1. 单向性（求第一原像不可行）。$H(m) = z$ 可求，反之计算不可行。
2. 弱无碰撞性（求第二原像不可行）。任意给定报文 $m_1$ 找出另一个不同报文 $m_2$ 使得 $H(m_1) = H(m_2)$ 计算不可行。
3. 强无碰撞性。任意两份报文杂凑值不同。

应用

1. 完整性检验。
2. 数字签名。
3. 密钥推导。
4. 伪随机数生成。

自由起始碰撞攻击

目的是找到两个不同的 $m_1, m_2$ 使得 $H(m_1) = H(m_2)$。

步骤

1. 随机选取 $N$ 个不同报文 $m_1, m_2, m_3, ..., m_N$
2. 计算这 $N$ 个报文的杂凑值，得到集合 $$S = \{ (m_k, H(m_k)): k = 1, 2, ..., N \}$$
3. 根据 $H(m_k)$ 的大小，对集合 $S$ 快速排序
4. 若过程中找到两个不同消息使 $H(m_k) = H(m_t)$ 就成功停止，否则失败停止

指标分析

所需存储量：表 $S$ 的规模 $O(N)$

所需计算量：

1. 生成集合 $S$ 的计算量为计算 $N$ 次杂凑函数
2. 快速排序并找出碰撞的计算量为 $|N| \log_2 |N|$ 次比较

成功率：

定理1

设杂凑值为 $n$ bit 且 $N$ 远小于 $2^n$，则碰撞攻击的成功率近似为

$$1 - e^{-\frac{N^2}{2^{n+1}}}$$

特别地，当 $N = \sqrt{2^n}$ 时，碰撞成功率近似为

$$1 - e^{-0.5} \approx 1 - \frac{1}{\sqrt{2.718}} \approx 0.393$$

特别地，当 $N = \sqrt{2^n+1}$ 时，碰撞成功率近似为

$$1 - e^1 \approx 1 - \frac{1}{2.718} \approx 0.632$$

对该定理的推导

所有 $H(m_k)$ 都不相同，完全没有碰撞的概率为

$$(1 - \frac{1}{2^n}) (1 - \frac{2}{2^n}) ... (1 - \frac{N - 1}{2^n}) = \prod^{N-1}_{i=1}(1 - \frac{i}{2^n})$$

由 $1 - x \approx e^{-x}$ 有（没有学过数分不懂，只能记结论）

$$\prod^{N-1}_{i=1}(1 - \frac{i}{2^n}) \approx \prod^{N-1}_{i=1}e^{\frac{i}{2^n}} = e^{\frac{-N (N - 1)}{2^{n+1}}} \approx e^{\frac{-N^2}{2^{n+1}}}$$

结论

假设能对抗穷举攻击的密钥长度安全界限为 $n$，能够对抗碰撞攻击的杂凑函数安全界限为 $2n$。

基于分组密码的杂凑函数

Merkle-Damaard 强化技术

将消息 $M = (M_1, M_2, ..., M_n)$ 的最后一个分组 $M_n$ 设置为原始消息长度。

这样，$H(0) \neq H(00)$。

基于分组密码设计杂凑函数的一般方法

消息 $M = (M_1, M_2, ..., M_n)$，初始值 $H_0$，$H_i = E(H_{i-1}, M_i), i = 1, 2, ..., n$，最后得到 $H_n$ 就是消息的杂凑值。也就是不断 update 初值至完整消息。

常见的杂凑函数设计如下

MD5

由 MD4 改进，产生 128 位输出，一个主循环处理 512 bit（长度 $L$，执行次数 $t = L / 512$）

初始化

1. 原始消息二进制后填一个 1，然后在最低 64 bit 填入原始消息长度的二进制，中间全部补 0，填充后长度为 512 bit 整数倍。长于 $2^{64}$时，模 $2^{64}$ 直接填入后 64 bit。
2. 将填充后结果 $x$ 分为 $t$ 个 512 bit 块 $x_0, x_1, ..., x_{t-1}$
3. 将每个块 $x_i(i = 0, 1, ..., t - 1)$ 再划分为 16 个 32 bit 的子块，记为 $M[16i]M[16i+1]...M[16i+16]$

初始向量

• A = 0x01234567
• B = 0x89abcdef
• C = 0xfedcba98
• D = 0x76543210

基本函数

$$\begin{array}{l} F(X,Y,Z) = (X \wedge Y) \vee (\overline{X} \wedge Z) \\ G(X,Y,Z) = (X \wedge Z) \vee (Y \wedge \overline{Z}) \\ H(X,Y,Z) = X \oplus Y \oplus Z \\ I(X,Y,Z) = Y \oplus (X \vee \overline{Z}) \end{array}$$

过程

1. 将 16 个子块放入缓存 $X[j]$
2. 保存初始值为 $AA,BB,CC,DD$
3. 数据块与 $ABCD$ 刷新多轮
4. 结果与原始值模 $2^{32}$ 加（如 $A' = A + AA \mod 2^{32}$）

连接最后输出就是结果。

$$a \leftarrow (b + [a + f(b, c, d) + x[i] + t] <<< s)$$

第二轮也是类似，将 $f$ 变为 $g$。之后每一轮也是更换一个函数。

安全性

MD5 算法已被证明是不安全的。

SHA-2

以 SHA-512 为例。

初始化

1. 原始消息二进制后填一个 1，然后在最低 128 bit 填入原始消息长度的二进制，中间全部补 0，使得填充后长度是 1024 整数倍。长于 $2^{128}$时，模 $2^{128}$ 直接填入后 128 bit。
2. 将填充结果分为 8 个 64 bit 块。

也有很多很多的初始向量，记忆这些东西没有意义，略过。

基本函数

$$CH( x, y, z) = (x \vee y) \otimes ( (\neg x) \vee z) \\ MAJ( x, y, z) = (x \vee y) \otimes (x \vee z) \otimes (y \vee z) \\ BSIG0(x) = ROTR^{28}(x) \otimes ROTR^{34}(x) \otimes ROTR^{39}(x) \\ BSIG1(x) = ROTR^{14}(x) \otimes ROTR^{18}(x) \otimes ROTR^{41}(x) \\ SSIG0(x) = ROTR^{1}(x) \otimes ROTR^{8}(x) \otimes SHR^{7}(x) \\ SSIG1(x) = ROTR^{19}(x) \otimes ROTR^{61}(x) \otimes SHR^{6}(x)$$

过程

$$T_1 = h + BSIG1(e) + CH(e,f,g) + K_t + W_t \\ T_2 = BSIG0(a) + MAJ(a,b,c) \\ h = g \\ g = f \\ f = e \\ e = d + T_1 \\ d = c \\ c = b \\ b = a \\ a = T_1 + T_2$$

计算最终结果

$$H_{i, 0} = a + H_{i - 1, 0} \\ H_{i, 1} = b + H_{i - 1, 1} \\ H_{i, 2} = c + H_{i - 1, 2} \\ H_{i, 3} = d + H_{i - 1, 3} \\ H_{i, 4} = e + H_{i - 1, 4} \\ H_{i, 5} = f + H_{i - 1, 5} \\ H_{i, 6} = g + H_{i - 1, 6} \\ H_{i, 7} = h + H_{i - 1, 7} \\$$

拼接 $H_{N, 0}, H_{N, 1}, ..., H_{N,7}$

SHA-3

基于海绵函数，我搞不懂。

基于杂凑函数的消息认证码

基于杂凑函数的 HMAC 消息认证码

有密钥 $k$ 函数 $H$，两个包含 $k$ 信息的数字串 $k_1, k_2$，计算消息 $m$ 的认证码：$HMAC(m) = H_{k_2}(H_{k_1}(m))$

ref

博客园文章