哈希函数是一种将任意长度输入转换为固定长度输出的函数，即 H: {0,1}* → {0,1}^n。它常被视作消息的“指纹”，但数学上无法实现真正的唯一性——输出空间有限而输入无限，碰撞必然存在。本文深入探讨哈希函数的安全性定义、常见构造方法及其实际应用场景。
哈希函数的基本概念
哈希函数的核心在于将变长输入映射到定长输出。虽然理想中的“唯一指纹”函数应是单射的，但受限于输出空间，碰撞（即不同输入产生相同输出的情况）无法避免。密码学关注的是计算难度：若寻找碰撞在计算上不可行，则哈希函数可视为“抗碰撞的”。
碰撞存在的必然性
由于输入空间远大于输出空间，根据鸽巢原理，碰撞必然存在。但若寻找碰撞的计算复杂度超出多项式时间可行范围，则此类函数可满足密码学需求。
抗碰撞性的形式化定义
直接要求“无多项式时间算法能找到碰撞”的定义存在缺陷：任何哈希函数都有硬编码碰撞的敌手。解决方案是引入哈希函数族概念，通过随机选择函数来规避硬编码攻击。
哈希函数族的安全性
哈希函数族 ℋ 包含多个哈希函数，安全性依赖于随机选择函数 H ∈ ℋ。敌手知晓 ℋ 但不知具体选择的 H，这与加密方案中密钥随机选择的安全理念相似。
实用定义框架
采用库交换法定义抗碰撞性：两个库仅在遇到碰撞时行为不同。ℒ_cr-fake 在检测到碰撞时自毁，确保运行中默认无碰撞发生。此定义简化了安全证明过程，无需显式检查碰撞。
抗碰撞性的变体
除了标准抗碰撞性，还有两种常见弱化版本：
- 目标抗碰撞性：给定随机 H 和 H(x)，难以找到任何 x’ 使得 H(x) = H(x’)
- 第二原像抵抗：给定随机 H 和 x，难以找到 x’ ≠ x 使得 H(x) = H(x’)
标准抗碰撞性蕴含这两个属性，因此成为主要研究对象。
哈希然后MAC结构
将哈希函数与消息认证码（MAC）结合，可扩展短输入MAC到任意长度消息。具体构造为：对消息 m 计算 t = MAC(k, H(m))。
安全性证明
通过混合论证验证其安全性：若 ℋ 抗碰撞且 MAC 安全，则 HtM 也是安全 MAC。关键在于，碰撞会破坏论证——敌手可通过碰撞消息伪造 MAC。
Merkle-Damgård构造方法
该构造将压缩函数（定长输入哈希函数）扩展为全功能哈希函数。核心步骤包括：
- 消息分块与填充
- 迭代应用压缩函数
- 添加长度编码块
压缩函数的作用
压缩函数 h: {0,1}^{n+t} → {0,1}^n 将输入“压缩”t 位。Merkle-Damgård 通过迭代方式处理任意长度输入。
安全性保证
若压缩函数族抗碰撞，则其 Merkle-Damgård 变换也是抗碰撞的。证明通过碰撞传递实现：任何 MD_h 碰撞都可转化为 h 的碰撞。
长度扩展攻击及其影响
某些哈希函数构造（如 Merkle-Damgård）易受长度扩展攻击：已知 H(x) 可预测 H(x‖z) 的值，其中 z 为特定填充。这对基于哈希的 MAC 构成威胁。
攻击原理
利用哈希函数的内部状态，攻击者无需知悉密钥即可扩展消息并计算有效 MAC。这揭示了 H(k‖m) 作为 MAC 的不安全性。
实际应用考虑
哈希函数在实际应用中需注意：
- 部分哈希验证可能不够安全
- 自定义构造需谨慎避免固有漏洞
- 结合具体需求选择适当安全属性
常见问题
问：哈希函数与加密函数有何区别？ 答：哈希函数是单向的，无需密钥，将任意输入映射到固定输出；加密函数是双向的，需要密钥，确保数据机密性。
问：抗碰撞性为何重要？ 答：抗碰撞性保证不同输入产生相同输出的计算不可行，这是数字签名、证书验证等应用的安全基础。
问：如何选择哈希函数输出长度？ 答：输出长度应足够长以抵抗暴力攻击，通常建议至少256位，具体取决于安全需求和应用场景。
问：MD5和SHA-1为何被弃用？ 答：这些算法已被发现实际碰撞攻击方法，无法满足现代安全需求，应使用更安全的算法如SHA-256、SHA-3。
问：哈希函数能否用于密码存储？ 答：单纯哈希不足够安全，应使用专门设计的密码哈希函数（如bcrypt、Argon2）并配合盐值使用。
问：长度扩展攻击如何防御？ 答：使用抗长度扩展攻击的哈希函数（如SHA-3），或在消息中包含长度信息后再哈希。
