【密码学】6. 消息认证和哈希函数

消息认证和哈希函数

消息认证

1. 基本概念
   • 消息认证（Message Authentication）：验证消息的真实性（来自合法发送者）和完整性（未被篡改），还可验证消息的顺序和及时性。
   • 核心三元组：（K, T, V），其中 K 为密钥生成算法，T 为标签算法（生成认证标识），V 为验证算法。
2. 认证函数分类
   认证函数分为三类：
   • 消息加密函数：用完整密文作为认证标识（加密同时实现认证）。
   • 消息认证码（MAC）：由密钥控制的公开函数，对消息生成固定长度的认证码（非加密，不可逆）。
   • 散列函数（Hash Function）：公开函数，将任意长消息映射为固定长度散列值（无需密钥）。
3. 消息认证码（MAC）
   • 定义：由密钥 k 和消息 m 生成的定长数据（$MAC=C(k,m)）$，通信双方共享 k，发送方附加 MAC，接收方重算比对。
   • 性质：多对一映射（可能存在碰撞，但构造碰撞困难）；无需可逆性；不提供保密性。
   • 使用方式：
     • 仅认证：发送 $m||MAC$；
     • 认证 + 保密（绑定明文）：加密 $m||MAC$；
     • 认证 + 保密（绑定密文）：加密 m 后附加 MAC。
   • 应用场合：非秘密消息广播、高速传输随机认证、程序防篡改、需隐藏明文的认证等（分离认证与保密性，便于层次化设计）。
   • 攻击方式：
     • 穷举攻击：若密钥长 k > MAC 长 n，需多轮验证（如 $2^{k-n}$ 个候选密钥）；若 k < n，可能一次尝试找到密钥。
     • 消息构造攻击：例：若 MAC 算法为 $\Delta (m)=X_1\oplus X_2\oplus \dots \oplus X_m$，$MAC=E(k,\Delta (m))$，攻击者可构造 $m^{\prime }=Y_1||\dots ||Y_m$，使 $Ym=Y_1\oplus \dots \oplus Y_{m-1}\oplus \Delta (m)$，导致 MAC 相同。
   • 要求：已知 m 和 MAC 时，构造同 MAC 的新 m 不可行；MAC 均匀分布；抗选择明文穷举攻击；充分利用消息所有比特。
4. MAC 相关算法
   • 数据认证算法（FIPS PUB 113）：基于 CBC 模式 DES，消息分 64 比特块，初始向量为 0，计算 $O_N=E_K(D_N\oplus O_{N-1})$，MAC 取 $O_N$ 或其前 M 比特（16≤M≤64）。
   • 128-EIA3（基于祖冲之密码）：
     • 输入：消息、完整性密钥 IK、COUNT、BEARER、DIRECTION 等；输出：32 比特 MAC。
     • 步骤：初始化（生成 ZUC 算法的密钥和初始向量 IV）→ 产生密钥字流→ 累加计算 MAC（消息比特控制密钥字流累加）。

哈希函数

1. 定义与分类
   • 哈希函数 H：将任意长消息 M 映射为固定长散列值 H (M) 的单向函数（难以从 H (M) 反推 M）。
   • 分类：带密钥（MAC）和不带密钥（MDC，消息摘要码）。
2. 基本用法
   • 结合单钥加密：加密 $m||H(m)$（认证 + 保密）；
   • 加密哈希值：单钥加密 $H(m)$（仅认证）或公钥加密 $H(m)$（数字签名）；
   • 共享秘密值：计算 $H(m||S)$（S 为秘密值，仅认证）；
   • 组合方式：加密 $m||H(m||S)$（认证 + 保密）。
3. 应满足的条件
   1. 输入任意长，输出固定长；
   2. 已知 x，计算 H (x) 容易；
   3. 已知 h，求 $H(x)=h$ 的 x 不可行（单向性）；
   4. 已知 x，找 $y\ne x$ 使 $H(y)=H(x)$ 不可行（弱抗碰撞性）；
   5. 找任意 $x\ne y$ 使 $H(x)=H(y)$ 不可行（强抗碰撞性）。
4. 生日攻击
   • 第 I 类：找 y 使 $H(y)=H(x)$，概率 0.5 时需 $k\approx n/2$ 次尝试（n 为可能输出数）。
   • 第 II 类：找任意 $x\ne y$ 使 $H(x)=H(y)$，基于生日悖论，概率 0.5 时需 $k\approx 2^{n/2}$ 次尝试（如 64 比特哈希需 $2^{32}$ 次）。
   • 生日悖论：23 人中有两人生日相同的概率 > 0.5，推广到哈希函数即第 II 类攻击的理论基础。
5. 迭代型哈希函数的一般结构（Merkle, 1989）
   • 步骤：
     1. 消息分块：M 分为 L 个 b 比特块 $Y_0,Y_1,\dots ,Y_{L-1}$（最后一块填充并含消息长度）；
     2. 初始化：设初始向量 $I_V=C_{V_0}$；
     3. 迭代压缩：$C_{V_i}=f(C_{V_{i-1}},Y_{i-1})$（f 为压缩函数，b→n 比特，n 为哈希长度）；
     4. 输出：$C_{V_L}$ 为最终哈希值。
   • 核心：设计无碰撞压缩函数 f。

MD5 哈希算法

1. 概述：由 Ron Rivest 设计，MD4 改进版，输出 128 比特摘要，RFC 1321 定义。
2. 处理过程
   • 填充：消息长度调整为 512×L - 64 比特（填充 1 个 “1”+ 若干 “0”）；
   • 附加长度：添加 64 比特消息原始长度（小端方式）；
   • 初始化缓冲区：128 比特缓冲区（A,B,C,D），初值（小端）：
     A=01234567→67452301，B=89ABCDEF→EFCDAB89，
     C=FEDCBA98→98BADCFE，D=76543210→10325476；
   • 分组处理：每 512 比特块经压缩函数处理，更新缓冲区；
   • 输出：最后一个缓冲区值为 MD5 摘要。
3. 压缩函数
   • 4 轮处理，每轮 16 步，每步运算：$a=b+{\text{CLS}}_s\left(a+g(b,c,d)+X[k]+T[i]\right)$ ，其中：
     • g 为逻辑函数（$F:(b\wedge c)\vee (\neg b\wedge d)；G:(b\wedge d)\vee (c\wedge \neg d)；H:b\oplus c\oplus d；I:c\oplus (b\vee \neg d)$）；
     • $CL{S}_s$ 为左循环移位 s 位（移位值见表 6-2）；
     • $T[i]=2^{32}\times |sin(i)|$ 的整数部分（i=1~64）；
     • $X[k]$ 为当前块的第 k 个字，轮 2-4 使用置换后的字序（$\rho 2(i)=(1+5i)mod16$ 等）。
4. 安全性：2004 年王小云等找到碰撞（1024 比特消息，1 小时内），安全性被攻破。

安全哈希算法（SHA）

1. 概述：NIST 设计，SHA-1 为 SHA-0 改进版，输出 160 比特摘要，基于 MD4。
2. 处理过程
   • 填充与附加长度：同 MD5，长度以大端方式存储；
   • 初始化缓冲区：160 比特（A,B,C,D,E），初值（大端）：
     A=67452301，B=EFCDAB89，C=98BADCFB，D=10325476，E=C3D2E1F0；
   • 分组处理：每 512 比特块经压缩函数处理，4 轮（每轮 20 步），更新缓冲区；
   • 输出：最后缓冲区值为 SHA-1 摘要。
3. 压缩函数
   • 每步运算：$A,B,C,D,E=(E+f_t(B,C,D)+CL{S}_5(A)+Wt+Kt),A,CL{S}_{3}0(B),C,D$，其中：
     • $f_t$ 为逻辑函数$（0-19:(B\wedge C)\vee (\neg B\wedge D)；20-39:B\oplus C\oplus D；40-59:(B\wedge C)\vee (B\wedge D)\vee (C\wedge D)；60-79:B\oplus C\oplus D）$；
     • Kt 为常量（0-19: 5A827999；20-39: 6ED9EBA1；40-59: 8F1BBCDC；60-79: CA62C1D6）；
     • Wt：16 字扩展为 80 字（$Wt=CL{S}_1(Wt-3\oplus Wt-8\oplus Wt-14\oplus Wt-16)，t\ge 16$）。
4. SHA 与 MD5 对比
   • 抗攻击：SHA-1（160 比特）抗穷举攻击优于 MD5（128 比特），生日攻击复杂度分别为 $2^{80}$ 和 $2^{64}$；
   • 速度：SHA-1 迭代步数（80）多于 MD5（64），速度较慢；
   • 存储：SHA-1 用大端，MD5 用小端。
5. 安全性：SHA-0 被 Joux 找到碰撞（$2^{51}$ 次运算）；王小云等提出 SHA-1 碰撞攻击（80 步需 < $2^{69}$ 次运算）。

基于离散对数的散列函数

• 算法：设 p 为大素数，$q=(p-1)/2$ 为素数，α 为 $F_p$ 本原元，$\beta ={\alpha }^{\lambda }$（λ 保密，λ 与 p-1 互素），散列函数 $h(x_1,x_2)={\alpha }^{x_1}{\beta }^{x_2}modp$。
• 强无碰撞性证明：若存在碰撞 $h(x_1,x_2)=h(x_3,x_4)$，则 ${\alpha }^{x_1-x_3}={\beta }^{x_4-x_2}$，可推导出 $\lambda =lo{g}_{\alpha }\beta$（离散对数），因离散对数问题难解，故 h 强无碰撞。

HMAC 算法

1. 设计目标：使用现有哈希函数（如 MD5、SHA），易替换，保持性能，简单处理密钥，安全性可分析。
2. 算法描述
   • 输入：密钥 K、消息 M，哈希函数 H（分组长 b，输出长 n）；
   • 步骤：
     1. 密钥处理：K 填充为 b 比特（K+），若 $|K|>b$ 则 $K=H(K)$；
     2. 计算：$HMA{C}_K(M)=H[(K+\oplus Opad)||H[(K+\oplus Ipad)||M]]$，其中 Ipad=00110110（b/8 个），Opad=01011010（b/8 个）。
3. 安全性：攻击 HMAC 等价于以下两种攻击之一：
   • 计算随机秘密 IV 下的压缩函数输出；
   • 找到随机秘密 IV 下的哈希碰撞。

SM3 哈希算法

1. 概述：中国国家标准，输出 256 比特摘要，输入长度 < $2^{64}$ 比特。
2. 常量与函数
   • 初始 IV：7380166F 4914B2B9 172442D7 DA8A0600 A96F30BC 163138AA E38DEE4D B0F80E4E；
   • 布尔函数：$F{F}_j(X,Y,Z)（0-15:(X\wedge Y)\vee (X\wedge Z)\vee (Y\wedge Z)；16-63:X\oplus Y\oplus Z）；G{G}_j(X,Y,Z)（0-15:同FF；16-63:X\oplus Y\oplus Z）$；
   • 置换函数：$P_0(X)=X\oplus (X<<<9)\oplus (X<<<17)；P_1(X)=X\oplus (X<<<15)\oplus (X<<<23)$。
3. 处理过程
   • 填充：同 MD5，长度调整为 512×L - 64 比特；
   • 消息扩展：512 比特块分为 16 字 $W_0-W_{15}$，扩展为 $W_0-W_{67}$（$W_j=P_1(W_j-16\oplus W_j-9\oplus (W_j-3<<<15))\oplus (W_j-13<<<7)\oplus W_j-6$）和 $W_0^{\prime }-W_{63}^{\prime }$（$W_j^{\prime }=W_j\oplus W_j+4$）；
   • 压缩函数 CF：64 步迭代，更新 8 个寄存器（A-H），每步计算 SS1、SS2、TT1、TT2，结合 $W_j$ 和 $W_j^{\prime }$，最终输出 V (L)=ABCDEFGH。
4. 安全性：压缩函数通过布尔函数（混淆）和置换函数（扩散）确保安全性，抗碰撞性强。