第5章 消息认证与哈希函数¶

消息认证与哈希函数是现代密码学中的重要组成部分，它们解决了数据完整性验证和身份认证的问题。与加密技术主要关注数据的机密性不同，消息认证技术专注于确保数据的完整性和真实性。哈希函数作为消息认证的核心工具，在数字签名、消息认证码、密钥派生等多个领域发挥着关键作用。

5.1 消息认证基础¶

5.1.1 消息认证的概念¶

消息认证（Message Authentication）是验证消息完整性和来源真实性的过程。它要解决以下几个关键问题：

• 完整性（Integrity）：确保消息在传输或存储过程中未被篡改
• 认证性（Authentication）：确认消息确实来自声称的发送方
• 不可否认性（Non-repudiation）：防止发送方否认已发送的消息

5.1.2 威胁模型¶

消息认证需要防范的主要攻击包括：

• 被动攻击：窃听者截获消息但不修改
• 主动攻击：攻击者修改、删除、重放或伪造消息
• 中间人攻击：攻击者拦截并可能修改通信双方的消息
• 重放攻击：攻击者重新发送之前截获的有效消息

5.1.3 消息认证的方法¶

主要的消息认证方法包括：

1. 消息认证码（MAC）：使用共享密钥生成认证标签
2. 数字签名：使用公钥密码学提供认证和不可否认性
3. 哈希函数：提供数据完整性检查的基础工具

5.2 哈希函数¶

5.2.1 哈希函数的定义¶

哈希函数（Hash Function）是一个将任意长度的输入映射为固定长度输出的函数：

\(H: \{0,1\}^* \rightarrow \{0,1\}^n\)

其中：

• 输入可以是任意长度的比特串
• 输出是固定长度 \(n\) 比特的哈希值（也称为消息摘要或指纹）

5.2.2 密码学哈希函数的性质¶

一个安全的密码学哈希函数必须满足以下性质：

1. 单向性（One-wayness）/ 抗原像攻击（Preimage Resistance）

• 给定哈希值 \(h\)，在计算上不可行找到消息 \(m\) 使得 \(H(m) = h\)
• 即从哈希值反推原始消息是困难的

2. 弱抗碰撞性（Weak Collision Resistance）/ 抗第二原像攻击（Second Preimage Resistance）

• 给定消息 \(m_1\)，在计算上不可行找到不同的消息 \(m_2\) 使得 \(H(m_1) = H(m_2)\)
• 即给定一个消息，找到另一个具有相同哈希值的消息是困难的

3. 强抗碰撞性（Strong Collision Resistance）/ 抗碰撞攻击（Collision Resistance）

• 在计算上不可行找到任意两个不同的消息 \(m_1 \neq m_2\) 使得 \(H(m_1) = H(m_2)\)
• 即找到任意一对具有相同哈希值的消息是困难的

性质关系：

强抗碰撞性 \(\Rightarrow\) 弱抗碰撞性 \(\Rightarrow\) 单向性

5.2.3 生日攻击与哈希长度¶

生日悖论表明，在一个有 \(N\) 个可能值的集合中，只需要大约 \(\sqrt{N}\) 次随机选择就有50%的概率出现重复。

对于 \(n\) 比特的哈希函数：

• 暴力破解单向性需要 \(2^n\) 次操作
• 暴力破解抗碰撞性只需要 \(2^{n/2}\) 次操作

因此，为了提供 \(k\) 比特的安全强度：

• 哈希函数的输出长度应至少为 \(2k\) 比特
• 例如，128比特安全强度需要至少256比特的哈希输出

5.2.4 Merkle-Damgård构造¶

大多数经典哈希函数采用Merkle-Damgård构造：

1. 填充（Padding）：将消息填充到块长度的整数倍
2. 分块处理：将填充后的消息分成固定长度的块
3. 迭代压缩：使用压缩函数逐块处理

构造过程：

1
2
3
4

M = M₁ || M₂ || ... || Mₖ  (分块后的消息)
H₀ = IV  (初始化向量)
Hᵢ = f(Hᵢ₋₁, Mᵢ)  for i = 1, 2, ..., k
H(M) = Hₖ

其中 \(f\) 是压缩函数，将 \((n+b)\) 比特输入压缩为 \(n\) 比特输出。

5.3 常见哈希算法¶

5.3.1 MD5（Message Digest 5）¶

基本参数：

• 输出长度：128比特
• 块大小：512比特
• 轮数：64轮（4组，每组16轮）

算法结构：

MD5使用Merkle-Damgård构造，压缩函数基于四个非线性函数：

• F(x,y,z) = (x ∧ y) ∨ (¬x ∧ z)
• G(x,y,z) = (x ∧ z) ∨ (y ∧ ¬z)
• H(x,y,z) = x ⊕ y ⊕ z
• I(x,y,z) = y ⊕ (x ∨ ¬z)

安全性状况：

• 1996年：发现弱点
• 2004年：王小云等人发现实用的碰撞攻击
• 2008年：可在几秒内找到碰撞
• 现状：已被认为不安全，不推荐使用

5.3.2 SHA-1（Secure Hash Algorithm 1）¶

基本参数：

• 输出长度：160比特
• 块大小：512比特
• 轮数：80轮

算法特点：

• 使用5个32比特的链接变量
• 每轮使用不同的非线性函数和常数
• 消息扩展：将16个32比特字扩展为80个字

安全性状况：

• 2005年：王小云等人发现理论碰撞攻击
• 2017年：Google实现首个实际SHA-1碰撞（SHAttered攻击）
• 现状：已被弃用，被SHA-2和SHA-3取代

5.3.3 SHA-2家族¶

SHA-2包括多个变种，基于相同的设计原理但参数不同：

SHA-256算法流程：

1. 预处理：
2. 填充消息使其长度 ≡ 448 (mod 512)

3. 附加64比特的原始消息长度

4. 初始化：8个32比特哈希值（前8个质数的平方根小数部分）

5. 主循环：对每个512比特块进行64轮处理

6. 消息调度：生成64个32比特字

7. 压缩函数：更新8个工作变量

8. 输出：连接最终的哈希值

关键函数：

• Ch(x,y,z) = (x ∧ y) ⊕ (¬x ∧ z)
• Maj(x,y,z) = (x ∧ y) ⊕ (x ∧ z) ⊕ (y ∧ z)
• Σ₀(x) = ROTR²(x) ⊕ ROTR¹³(x) ⊕ ROTR²²(x)
• Σ₁(x) = ROTR⁶(x) ⊕ ROTR¹¹(x) ⊕ ROTR²⁵(x)

5.3.4 SHA-3（Keccak）¶

设计背景：

• 2007年NIST启动SHA-3竞赛
• 2012年Keccak算法胜出
• 2015年正式标准化为SHA-3

核心创新：

• 海绵构造（Sponge Construction）：替代Merkle-Damgård构造
• Keccak-f置换：基于置换的设计而非压缩函数

海绵构造原理：

1
2
3
4
5

状态 = 速率部分(r比特) || 容量部分(c比特)
总状态大小 = r + c = 1600比特

吸收阶段：将输入数据逐块异或到速率部分
挤压阶段：从速率部分提取输出数据

SHA-3变种：

优势：

• 抗长度扩展攻击
• 更强的安全性证明
• 支持可变长度输出（SHAKE函数）

5.4 消息认证码（MAC）¶

5.4.1 MAC的定义与性质¶

消息认证码（Message Authentication Code, MAC）是一个三元组算法 \((Gen, Mac, Vrfy)\)：

• Gen(): 密钥生成算法，输出密钥 \(k\)
• Mac(k, m): 认证算法，输入密钥 \(k\) 和消息 \(m\)，输出认证标签 \(t\)
• Vrfy(k, m, t): 验证算法，输入密钥 \(k\)、消息 \(m\) 和标签 \(t\)，输出接受/拒绝

安全性要求：

• 不可伪造性：没有密钥的攻击者无法为新消息生成有效的MAC
• 抗选择消息攻击：即使攻击者能获得一些消息-MAC对，也无法伪造新的MAC

5.4.2 基于哈希函数的MAC（HMAC）¶

HMAC构造是最广泛使用的MAC算法，定义为：

1

HMAC(K, M) = H((K ⊕ opad) || H((K ⊕ ipad) || M))

其中：

• H：底层哈希函数
• K：密钥（如果长度不足则填充零，如果过长则先哈希）
• opad：外部填充（0x5C重复B次，B为哈希函数块大小）
• ipad：内部填充（0x36重复B次）
• ||：连接操作

HMAC的优势：

• 基于哈希函数的安全性
• 不需要修改底层哈希函数
• 抗长度扩展攻击
• 高效实现
• 有严格的安全性证明

HMAC安全性：

HMAC的安全性基于以下假设： - 底层哈希函数的抗碰撞性 - 底层压缩函数作为伪随机函数的安全性

即使底层哈希函数不完全安全，HMAC仍可能保持安全性。

常见HMAC变种：

• HMAC-MD5：基于MD5（已不推荐）
• HMAC-SHA1：基于SHA-1（逐步淘汰）
• HMAC-SHA256：基于SHA-256（推荐）
• HMAC-SHA3：基于SHA-3

5.4.3 基于分组密码的MAC¶

1. CBC-MAC

使用分组密码的CBC模式构造MAC：

1
2
3

C₀ = 0
Cᵢ = E_K(Cᵢ₋₁ ⊕ Mᵢ)  for i = 1, 2, ..., n
MAC = Cₙ

安全性考虑：

• 仅对固定长度消息安全
• 需要特殊处理可变长度消息

2. CMAC（Cipher-based MAC）

CMAC是CBC-MAC的改进版本，支持可变长度消息：

• 使用子密钥处理最后一个块
• 根据最后一个块是否完整选择不同的子密钥

3. GMAC（Galois MAC）

基于GCM模式的认证部分：

• 使用有限域上的多项式运算
• 支持并行计算
• 常与AES-GCM一起使用

5.4.4 通用哈希函数与MAC¶

通用哈希函数是一类特殊的哈希函数族，具有良好的统计性质：

对于哈希函数族 \(\mathcal{H} = \{h_k : k \in \mathcal{K}\}\)，如果对于任意不同的 \(x, y\)：

则称 \(\mathcal{H}\) 为通用哈希函数族。

Wegman-Carter构造：

1

MAC_k₁,k₂(m) = h_k₁(m) ⊕ k₂

其中 \(h_{k₁}\) 是通用哈希函数，\(k₂\) 是一次性密钥。

5.5 数字签名与哈希¶

5.5.1 哈希函数在数字签名中的作用¶

数字签名通常不直接对消息签名，而是对消息的哈希值签名：

1
2

签名生成：σ = Sign_sk(H(m))
签名验证：Verify_pk(H(m), σ)

使用哈希的原因：

• 效率：哈希值长度固定且较短，签名操作更快
• 安全性：避免某些针对直接签名的攻击
• 标准化：统一的消息表示格式

5.5.2 哈希函数的安全要求¶

在数字签名中，哈希函数必须满足：

• 抗碰撞性：防止攻击者找到两个具有相同哈希值的消息
• 抗第二原像攻击：防止攻击者为已签名消息找到替代消息

5.5.3 签名方案中的哈希选择¶

RSA签名中的哈希：

• PKCS#1 v1.5：使用特定的填充格式
• PSS（Probabilistic Signature Scheme）：更安全的填充方案

DSA/ECDSA中的哈希：

• 哈希输出长度应匹配签名参数
• SHA-256通常与256比特椭圆曲线配对

5.6 密钥派生函数（KDF）¶

5.6.1 KDF的概念与需求¶

密钥派生函数（Key Derivation Function, KDF）从一个或多个输入值派生出一个或多个密钥：

1

K₁, K₂, ..., Kₙ = KDF(source_key, salt, info, length)

应用场景：

• 从主密钥派生多个子密钥
• 从密码派生加密密钥
• 密钥协商后的密钥确认
• 会话密钥生成

5.6.2 基于哈希的KDF（HKDF）¶

HKDF算法分为两个阶段：

1. 提取阶段（Extract）：

1

PRK = HMAC(salt, IKM)

• IKM：输入密钥材料
• salt：可选的随机值
• PRK：伪随机密钥

2. 扩展阶段（Expand）：

1
2
3
4
5

T(1) = HMAC(PRK, info || 0x01)
T(2) = HMAC(PRK, T(1) || info || 0x02)
...
T(N) = HMAC(PRK, T(N-1) || info || N)
OKM = T(1) || T(2) || ... || T(N)[0..L-1]

5.6.3 基于密码的KDF（PBKDF）¶

PBKDF2算法用于从密码派生密钥：

1

DK = PBKDF2(Password, Salt, c, dkLen)

算法步骤：

1. 将所需输出分成多个块
2. 对每个块应用PRF（通常是HMAC）
3. 进行c次迭代增加计算成本
4. 连接所有块得到最终密钥

参数选择：

• 迭代次数c：足够大以抵抗暴力攻击（推荐≥10,000）
• 盐值：随机生成，防止彩虹表攻击
• 输出长度：根据应用需求确定

5.6.4 现代KDF算法¶

scrypt：

• 内存困难函数，抵抗ASIC攻击
• 参数：N（CPU/内存成本），r（块大小），p（并行度）

Argon2：

• 2015年密码哈希竞赛获胜者
• 三个变种：Argon2d、Argon2i、Argon2id
• 可调节时间成本、内存成本和并行度

5.7 哈希函数的应用¶

5.7.1 数据完整性检查¶

文件校验和：

• MD5校验和（已不安全，仅用于错误检测）
• SHA-256校验和（推荐用于安全应用）
• 软件分发中的完整性验证

区块链中的应用：

• 区块哈希：每个区块包含前一个区块的哈希，形成不可篡改的链式结构
• 交易哈希：每笔交易都有唯一的哈希标识，用于快速查找和验证
• Merkle树：高效验证大量交易的完整性，支持轻节点验证
• 工作量证明（PoW）：比特币等使用SHA-256进行挖矿计算
• 地址生成：从公钥生成钱包地址通常涉及多次哈希运算

5.7.2 密码存储¶

密码哈希存储：

1

stored_hash = hash(password || salt)

现代密码存储方案：

1
2
3
4
5

// PBKDF2示例
stored_hash = PBKDF2(password, salt, iterations, key_length)

// Argon2示例  
stored_hash = Argon2id(password, salt, time_cost, memory_cost, parallelism)

安全考虑：

• 避免快速哈希：不要使用SHA-256等快速哈希函数直接存储密码
• 使用专门的密码哈希函数：PBKDF2、scrypt、Argon2等
• 添加随机盐值：防止彩虹表攻击，每个密码使用唯一盐值
• 适当的计算成本：平衡安全性和性能，定期调整参数
• 考虑硬件攻击：scrypt和Argon2提供内存困难性，抵抗ASIC攻击

5.7.3 数字取证¶

证据完整性：

• 对数字证据计算哈希值
• 建立证据链保证完整性
• 法庭上证明证据未被篡改

5.7.4 随机数生成¶

确定性随机比特生成器（DRBG）：

• 使用哈希函数作为熵提取器
• 从熵源生成伪随机数
• NIST SP 800-90A标准

5.8 攻击方法与防护¶

5.8.1 哈希函数攻击¶

1. 暴力攻击

• 原像攻击：尝试所有可能输入
• 碰撞攻击：生日攻击，复杂度O(2^(n/2))

2. 密码分析攻击

• 差分攻击：分析输入差异对输出的影响
• 线性攻击：寻找输入输出间的线性关系
• 王小云的攻击：针对MD5和SHA-1的创新攻击

3. 长度扩展攻击

• 针对Merkle-Damgård构造
• 攻击者可以在不知道密钥的情况下扩展消息
• HMAC设计专门防范此类攻击

5.8.2 MAC攻击¶

1. 伪造攻击

• 存在性伪造：为任意消息生成有效MAC
• 选择性伪造：为特定消息生成有效MAC

2. 重放攻击

• 攻击者重新发送之前的有效消息-MAC对
• 防护：使用时间戳、序列号或一次性数字

3. 时间攻击

• 通过分析MAC验证时间推断信息
• 防护：使用常数时间比较算法

5.8.3 防护措施¶

1. 算法选择

• 使用经过充分分析的标准算法
• 及时更新到更安全的算法版本
• 关注密码学社区的安全公告

2. 实现安全

• 使用经过验证的密码学库
• 避免侧信道攻击
• 正确处理错误情况

3. 协议设计

• 结合多种安全机制
• 考虑攻击者的能力模型
• 定期进行安全评估

5.9 标准与实践¶

5.9.1 国际标准¶

NIST标准：

• FIPS 180-4：安全哈希标准（SHA-1、SHA-2、SHA-3）
• FIPS 198-1：基于密钥的哈希消息认证码
• SP 800-107：使用哈希函数的建议
• SP 800-108：使用伪随机函数的密钥派生

ISO/IEC标准：

• ISO/IEC 10118：哈希函数标准
• ISO/IEC 9797：消息认证码标准

5.9.2 最佳实践¶

哈希函数选择：

• 新应用推荐使用SHA-256或SHA-3
• 逐步淘汰MD5和SHA-1
• 考虑性能和安全性的平衡

MAC实现建议：

• 优先使用HMAC而非自定义MAC
• 密钥长度至少等于哈希输出长度
• 使用安全的密钥管理机制

密码存储最佳实践：

• 使用专门的密码哈希函数（Argon2、scrypt、PBKDF2）
• 每个密码使用唯一的随机盐
• 定期评估和调整安全参数

5.9.3 性能考虑¶

哈希函数性能对比：

优化策略：

• 硬件加速：使用CPU的哈希指令集
• 并行处理：利用多核处理器
• 缓存优化：减少内存访问延迟

结论¶

消息认证与哈希函数是现代密码学的重要基石，为数据完整性和身份认证提供了可靠的技术手段。从早期的MD5到现代的SHA-3，哈希函数技术不断发展以应对新的安全威胁。消息认证码作为对称密码学中的重要工具，与数字签名一起构成了完整的消息认证体系。

随着量子计算威胁的临近，密码学界正在研究后量子安全的哈希函数和认证方案。同时，新的应用场景如区块链、物联网等也对哈希函数提出了新的需求和挑战。

在实际应用中，选择合适的哈希函数和认证机制需要综合考虑安全性、性能和兼容性等因素。遵循最佳实践，使用标准化的算法和实现，定期更新安全策略，是确保系统安全的关键。

哈希函数发展时间线¶

算法安全性对比¶

引文¶

• NIST FIPS 180-4: Secure Hash Standard (SHS)
• NIST FIPS 198-1: The Keyed-Hash Message Authentication Code (HMAC)
• RFC 2104: HMAC: Keyed-Hashing for Message Authentication
• RFC 5869: HMAC-based Extract-and-Expand Key Derivation Function (HKDF)
• Keccak Team: The Keccak SHA-3 submission
• Wang, X., et al.: Finding Collisions in the Full SHA-1