📑 本页目录（点开跳转）
09 · 哈希函数
⏱ 26 分钟 ｜ ⭐ 密码学里用得最广的一个工具
🎯 一句话
哈希函数把任意长度的输入压成固定长度的输出， 而且这个过程实质上不可逆、不可碰撞。 它是签名、区块链、密码存储、完整性校验的共同地基。
📐 一、三个安全性质（必须分清）
$$H: \{0,1\}^* \to \{0,1\}^n$$
| 性质 | 给你什么，要你找什么 | 直觉 |
|---|---|---|
| ① 单向性 （原像抗性） |
给 y，找任意 m 使 H(m) = y | 不能反推 |
| ② 二次原像抗性 | 给 m，找 m′ ≠ m 使 H(m′) = H(m) | 不能给指定的东西找替身 |
| ③ 碰撞抗性 | 什么都不给，找任意一对 m ≠ m′ 使 H(m) = H(m′) | 不能造出任何一对双胞胎 ⭐ |
⭐ 三者的强弱关系
碰撞抗性 ⟹ 二次原像抗性
↑ 最强 （反过来不成立）
💡 为什么："能给任意 m 找替身"当然就"能造出一对双胞胎"（随便挑个 m 就行）
但"能造出某一对双胞胎"不代表"能给你指定的 m 找替身"
一个具体的直觉：
二次原像：我指定一个人，你去找一个和他长得一模一样的
碰撞： 你随便找两个长得一样的人（双胞胎就行）⭐
→ 显然后者容易得多
🎂 二、生日悖论：碰撞比你以为的容易得多
问题：一个房间里要有多少人，才有 50% 的概率两人生日相同？
直觉答案：183 人（365 的一半）
实际答案：23 人 ⭐⭐
📐 为什么是 23（想看再点）
算"没有任何两人生日相同"的概率：
$$\Pr[\text{无碰撞}] = \frac{365}{365}\cdot\frac{364}{365}\cdots\frac{365-q+1}{365}$$
$q = 23$ 时这个值约 0.493，所以有碰撞的概率约 50.7%。
关键在于比较的对数：$q$ 个人有 $\binom{q}{2} = q(q-1)/2$ 对。 $q = 23$ 时是 253 对 —— 这就接近 365 了。
一般化：从 $N$ 个值里随机取 $q$ 个，碰撞概率约 $\frac{q^2}{2N}$， 所以 $q \approx \sqrt{N}$ 时碰撞概率就到了常数级。
💥 对哈希函数的直接后果
n bit 输出 ⟹ 2ⁿ 个可能值
找原像（性质①②）：需要 2ⁿ 次
找碰撞（性质③）： 只需要 2^(n/2) 次 ⭐⭐ ← 开平方！
| 哈希 | 输出 | 抗碰撞强度 | 状态 |
|---|---|---|---|
| MD5 | 128 bit | 64 bit（理论） | 💀 实际几秒钟就能造碰撞 |
| SHA-1 | 160 bit | 80 bit | 💀 2017 年 Google 造出真实碰撞（SHAttered） |
| SHA-256 | 256 bit | 128 bit | ✅ 当前默认 |
| SHA-3 / SHA-512 | 256/512 bit | 128/256 bit | ✅ |
| BLAKE3 | 256 bit | 128 bit | ✅ 极快 |
🔑 记住这条换算：要 128-bit 的抗碰撞安全，哈希输出必须 256 bit。 很多人以为 SHA-256 提供 256-bit 安全 —— 抗碰撞只有 128 bit。
💥 真实事故：碰撞不是纸上谈兵
| 事故 | 发生了什么 |
|---|---|
| Flame 恶意软件（2012） | 用 MD5 碰撞伪造了微软的代码签名证书，冒充 Windows 更新 ⭐ |
| SHAttered（2017） | Google 造出两个 SHA-1 相同的 PDF，内容完全不同 |
| 各类文件校验 | "MD5 校验和一致"不再能证明文件没被换过 |
🔨 三、哈希的正确用法与错误用法
✅ 正确用法
| 用途 | 怎么用 |
|---|---|
| 完整性校验 | 比对哈希值（前提：哈希值本身通过可信渠道获得） |
| 数字签名 | 先哈希再签（第 17 章）⭐ |
| 承诺方案 | 先公布 H(值‖随机数)，之后再揭示（第 21 章） |
| Merkle 树 | 第 12 章 |
| PoW | 第 20 章 |
| 密钥派生 | 用 HKDF，不要直接哈希 |
❌ 危险用法 ① 直接哈希存密码
❌ 存 SHA256(password)
为什么不行：
├─ 哈希【太快】了 —— GPU 每秒能算几十亿次
├─ 彩虹表：常见密码的哈希早就被算好了
└─ 相同密码 → 相同哈希，一眼看出哪些用户密码相同 ⭐
# ✅ 正确：用专门的密码哈希函数（慢 + 加盐 + 抗 GPU）
import argon2
ph = argon2.PasswordHasher() # ⭐ 首选
hashed = ph.hash("user_password") # 自动加随机 salt
ph.verify(hashed, "user_password")
# 其他可接受的：bcrypt、scrypt、PBKDF2（迭代次数要够高）
| 要素 | 作用 |
|---|---|
| 盐（salt） | 每个用户不同的随机值 → 彩虹表失效，相同密码哈希也不同 |
| 慢 | 故意设计成慢（可调迭代次数）→ 暴力破解成本上升 |
| 抗 GPU/ASIC | Argon2 需要大量内存 → GPU 的并行优势被抵消 ⭐ |
❌ 危险用法 ② 用哈希做认证
❌ tag = H(secret ‖ message) ← 长度扩展攻击！
⭐ 这是第 10 章的主题，也是一个打穿过很多 API 的真实漏洞
❌ 危险用法 ③ 用普通哈希比对时不用恒定时间
# ❌ 有时间侧信道
if computed_hash == provided_hash: ...
# ✅
import hmac
if hmac.compare_digest(computed_hash, provided_hash): ...
🎲 四、随机预言机模型（了解即可）
很多安全证明会假设"哈希函数表现得像一个【真随机函数】"
—— 对每个新输入返回一个全新的随机值
这叫【随机预言机模型 ROM】
⚠️ 但真实的哈希函数不是随机预言机（它有固定的代码！）
→ 存在人为构造的方案：在 ROM 下可证安全，实例化后却不安全
💡 实践中的态度：ROM 下的证明【比没有证明好得多】，
但它是一个理想化假设，不是铁证
🔗 第 17 章的 FDH-RSA 和 Fiat–Shamir 转换， 它们的安全性证明都依赖 ROM。
🔗 和站内其他章的关系
| 相关的地方 | 和这一章的关系 |
|---|---|
| 第 1 章 完整性 | 哈希是实现它的基础工具 |
| 第 6 章 生日界 | 同一个 √N 现象 ⭐ |
| 第 5 章 nonce 碰撞 | 也是生日界 |
| 第 10 章 | 哈希怎么造出来的，以及它的结构性弱点 |
| 第 12 章 Merkle 树 | 哈希的树状组合 |
| 推荐算法 · 特征工程 | hash(author_id) % 100万 的哈希分桶——同一个碰撞，在那里是可接受的压缩代价，在这里是方案的死因 ⭐ |
| 模型上线之后 · 灰度影子与回滚 | 「带盐的哈希分流」：那边加盐是为了让不同实验互不污染，这里加盐是为了让彩虹表失效——同一个手法，两个目的 |
✅ 检查点
- 哈希的三个安全性质分别是什么？各自"给什么、找什么"？
- 三者的强弱关系是什么？用一个直觉例子说明。
- 生日悖论的答案是多少人？为什么这么少？
- n bit 哈希找原像和找碰撞分别需要多少次？
- SHA-256 提供多少位的抗碰撞安全？
- Flame 恶意软件是怎么利用 MD5 碰撞的？
- 为什么不能直接用 SHA256 存密码？正确做法的三个要素？
- Argon2 相比 PBKDF2 多了什么优势？
- 什么是随机预言机模型？该用什么态度看待它？
👀 答案
- ①单向性：给 y 找任意 m 使 H(m)=y ②二次原像抗性：给 m 找 m′≠m 使哈希相同 ③碰撞抗性：什么都不给，找任意一对 m≠m′ 哈希相同。
- 碰撞抗性 ⟹ 二次原像抗性，反之不成立。直觉：二次原像是"我指定一个人，你找和他长得一样的"；碰撞是"你随便找两个长得一样的人"——后者容易得多。
- 23 人。因为关键是比较的对数：23 人有 253 对，已经接近 365。一般化：从 N 个值取 q 个，碰撞概率约 q²/2N，q ≈ √N 时就到常数级。
- 找原像 2ⁿ 次；找碰撞只需 2^(n/2) 次（开平方）。
- 128 位，不是 256 位。要 128-bit 抗碰撞安全，输出必须 256 bit。
- 用 MD5 碰撞伪造了微软的代码签名证书，从而能冒充 Windows 更新分发恶意软件。
- 因为①哈希太快（GPU 每秒几十亿次）②彩虹表 ③相同密码产生相同哈希，一眼看出哪些用户密码相同。三要素：盐（彩虹表失效+相同密码哈希不同）、慢（可调迭代）、抗 GPU/ASIC。
- Argon2 需要大量内存，抵消了 GPU/ASIC 的并行优势；PBKDF2 只是迭代慢，对专用硬件抵抗力弱。
- 假设哈希表现得像真随机函数（每个新输入返回全新随机值）。态度：真实哈希不是随机预言机（它有固定代码），存在 ROM 下可证安全但实例化后不安全的构造；ROM 下的证明比没有证明好得多，但不是铁证。
🛑 可以停在这里
⚡ 走神救援
哈希把任意长输入压成固定长输出。三性质：①单向性（给y找m）②二次原像抗性（给m找替身）③碰撞抗性（随便找一对双胞胎）；⭐碰撞抗性⟹二次原像抗性，反之不成立（"指定一个人找长得一样的"比"随便找两个长得一样的"难得多）。⭐⭐生日悖论：23 人就有 50% 概率生日相同——因为关键是比较的对数（23人有253对），一般化 q≈√N 时碰撞概率就到常数级。💥直接后果：n bit 哈希找原像要 2ⁿ 次，找碰撞只要 2^(n/2) 次（开平方）→ ⭐SHA-256 的抗碰撞只有 128 bit 不是 256 bit；MD5 和 SHA-1 已死（💥Flame 恶意软件用 MD5 碰撞伪造微软代码签名证书冒充 Windows 更新；2017 Google 造出 SHA-1 碰撞 PDF）。三个危险用法：①⭐直接哈希存密码（哈希太快、彩虹表、相同密码相同哈希）→ 用 Argon2（盐让彩虹表失效、慢、⭐需要大量内存抵消 GPU 并行优势）②用 H(secret‖msg) 做认证（长度扩展攻击，第10章）③比对时不用恒定时间函数。随机预言机模型：假设哈希像真随机函数，很多证明（FDH-RSA、Fiat-Shamir）依赖它；⚠️ 真实哈希不是随机预言机，ROM 下的证明比没有好得多但不是铁证。
下一节 👉 10-哈希构造与长度扩展攻击.md