哈希函数

核心属性

1. 抗碰撞性 (Collision Resistance)：找到 $x\ne x^{\prime }$ 使得 $H(x)=H(x^{\prime })$ 是困难的。
2. 抗第二原像 (Second Pre-image Resistance)：给定 $x$，找到 $x^{\prime }\ne x$ 使得 $H(x)=H(x^{\prime })$ 是困难的。
3. 抗原像 (Pre-image Resistance/One-wayness)：给定 $y$，找到 $x$ 使得 $H(x)=y$ 是困难的。

• 关系：抗碰撞 $⟹$ 抗第二原像 $⟹$ 抗原像。

攻击与结构

• 生日攻击：对于输出长度为 $n$ 的哈希，找到碰撞的复杂度是 $O(2^{n/2})$，而不是 $2^n$。因此 $n$ 至少要是 256 (如 SHA-256)。
• Merkle-Damgård 结构：将压缩函数 $h$ (固定长度输入) 扩展为哈希函数 $H$ (任意长度输入)。MD5, SHA-1, SHA-2 都基于此。
  • 缺陷：易受长度扩展攻击 (Length Extension Attack)。如果 $H(m)$ 已知，敌手可以在不知道 $m$ 的情况下计算 $H(m||padding||extension)$。
• HMAC：$HMAC(k,m)=H((k\oplus opad)||H((k\oplus ipad)||m))$。
  • 嵌套结构是为了抵御长度扩展攻击。