【密码学】（九）消息认证与杂凑函数

一、 认证与安全的必要性

在信息安全中，我们不仅要防止信息被偷看，还要防止==信息被篡改或伪造==。
总结起来就是：==确保收到的文件（明文或者密文皆可）是真实的、没有被改动的==

[!note] 注意和数字签名区分

1. 信息安全的三大目标与机制：

• 保密性 (Confidentiality)：不希望他人知道消息的内容。通常采用 加密机制 。
• 完整性 (Integrity)：保证消息内容未被篡改，且是真实的。通常采用 消息认证机制 。
• 真实性 (Authenticity)：保证消息来源的真实性和实体身份的真实性。通常采用 身份认证机制。

2. 为什么简单的加密不能代替认证： 在1970年代末之前，人们错误地认为：只要信息加密了，且解密后有意义，就证明信息是真实的。但实际上， 保证真实性不仅要求加密算法安全，还取决于加密模式。

• 流密码的反例：主动攻击者可以直接翻转密文中的某些比特。因为流密码是按位解密的，密文比特的改变会直接导致解密后的明文发生对应比特的改变，接收方却无法察觉。
• 分组密码（ECB模式）的反例：攻击者可以直接打乱或替换密文分组的顺序（如记录过去的密文分组来替代现在的），只要明文分组间不相关，接收方完全无法检测到攻击。

二、 杂凑（Hash）函数的核心概念

为了实现信息的完整性和真实性认证，密码学引入了Hash函数。

1. 杂凑函数的定义与映射： Hash函数（记为 ）的作用是==将 任意有限长度 的消息 （即原像空间 ${0,1}^$ ），变换成 *固定长度 的Hash值（即像空间 ）==。 Hash函数又称为改动检测码MDC、散列函数、消息摘要等。

2. 强单向函数的数学要求： 一个函数 $f: {0,1}^ \rightarrow {0,1}^$ 若被称为强单向函数，必须满足：

• 正向计算容易：计算 是多项式时间可计算的。
• 逆向反推困难：计算 是困难的。即对每一多项式时间概率算法 、每一多项式 和充分大的 ，有： $Pr{M(f(U_n)) \in f^{-1}(f(U_n))} < 1/p(n)$
  3. Hash函数的抗碰撞性分类： Hash函数不仅要求计算快、具有完全单向性，还要求有 雪崩效应 （输入极其微小的变动会导致输出极大的变化）。基于抗碰撞的强度，分为以下两类：
• 弱无碰撞（OWHF，单向杂凑函数）： 已知输入 ，想找出另一个 ( ) 使得 在计算上是不可行的。用于抵抗第二类生日攻击。
• 强无碰撞（CRHF，抗碰撞杂凑函数）： 没有任何已知输入 ，凭空寻找任意两个不同的消息 和 ( )，使得 在计算上是不可行的。用于抵抗第一类生日攻击。

三、 消息认证的核心工具：MDC 与 MAC

根据是否引入密钥，消息认证分为两类。

1. ==操作检测码 MDC (Manipulation Detection Code)：== MDC的计算 没有密钥参与 ，即 。

[!NOTE] 这个中的是原始消息
具体流程是A发送消息给B，B用接收到的消息（不一定是原来的）验证

• 局限性：因为没有密钥，任何拿到消息的人都能重新计算MDC。所以，发送者必须通过一个 绝对安全的信道 （如当面确认或电话确认）将MDC值单独传递给接收方，接收方自己算一遍并比对。
• 密码学中的组合应用方案： 由于单纯传递MDC需要安全信道，实际中常将MDC与加密或签名结合使用：
  • 方案1（保密+认证）： 。先算Hash并拼接在明文后， 整体加密。
  • 方案2（仅认证）： 。明文公开， 只对Hash值加密。
  • 方案3（认证+数字签名）： 。明文公开，用私钥 对Hash值进行 数字签名。
  • 方案4（保密+认证+签名）： $EK[M || S{Ks}[H(M)]]$ 。先签名，再拼接，最后 整体加密。

2. ==消息认证码 MAC (Message Authentication Code)：== MAC的计算 有通信双方共享密钥 的参与 ，即 。

• 优势：由于攻击者没有密钥 ，即使他篡改了消息，也无法算出合法的MAC值。这直接把对消息真实性的保护，转化为了==双方安全共享密钥==的问题， 不再需要额外的安全信道来传递MAC。
• MAC的应用组合方案：
  • 方案1（仅消息认证）：直接发送 。
  • 方案2（认证+保密：先MAC后加密）： $E{K2}[M || C{K1}(M)]K_1K2$ 对整体进行加密。 （注：这是实际中最常用的认证方式）。
  • 方案3（认证+保密：先加密后MAC）： $C{K1}[E{K2}(M)] || E_{K2}(M)$ 。先对消息加密，再对密文算MAC。

四、 Hash函数的底层构造

如何把任意长度的信息变成固定长度？常用的构造方法有两种：

1. 迭代Hash函数（Merkle-Damgård 结构）： 这是MD系列、SHA系列和SM3的基础。

• 首先将信息 填充（padding）后，分成 个固定长度的分组： 。
• 设定初始变量 。
• 执行迭代计算： $Hi = f(X_i, H{i-1})f$ 为轮函数。
• 最后，经过输出变换 ，得到 。

2. 基于分组密码的构造方法： 使用[[（四）分组密码的五大工作模式#二、密文分组链接模式（CBC）]] 。输入初始变量 和对称密钥 ，对明文分组 逐个进行加密操作。将输出的 最后一个密文分组 直接作为Hash函数的输出值 。

3.直接构造Hash函数： 见下段

五、 主流Hash算法详解（SHA-256 与 SM3）

这里深入讲解基于迭代结构的两种主流算法。

1. SHA-256 算法的流程： SHA-256最终输出256位（32字节）的摘要。

• （1）消息填充： 目的是让输入消息长度变成512的整数倍。对于长度为 的消息： 首先在末尾添加一个比特“1”；然后添加 个“0”，使得满足方程： （即填充到距离512倍数还差64位的位置）；最后在这64位中，填入原始消息长度 的二进制表示。
  
• （2）消息编排（扩展）： 将每一个512位的信息块划分为16个32位的字（ $M0M{15}$ ）。然后扩展为 64个32位的字 $W0W{63}Wt = M_tW_t = \sigma_1^{(256)}(W{t-2}) + W{t-7} + \sigma_0^{(256)}(W{t-15}) + W_{t-16}$ （涉及循环右移和异或）。
  
  
• （3）缓冲区初始化与压缩处理： 准备8个32位寄存器 （初始值为前8个素数平方根小数部分）。 对扩展出的64个字执行 64轮迭代 。每轮使用复杂的逻辑函数（如选择函数 、多数表决函数 ）和轮常数 。 经过64轮后，将得出的新 与进入这64轮之前的旧 进行模 的加法操作，作为下一个512位块的初始输入。所有块处理完毕后，拼接 到 即为最终结果。

2. SM3 算法的流程（国密标准）： SM3由王小云院士团队研发，抗碰撞强度达到 ，输出同样为256位。

• （1）消息填充与分组： 填充规则与SHA-256完全相同，同样按512位为一个分组 。
• （2）极其复杂的消息扩展： SM3不仅仅将16个字扩展为64个字，它总共会产生 132个32位的字 ！ 首先产生68个字 $W0, …, W{67}P1W_k = P_1(W{k-16} \oplus W{k-9} \oplus (W{k-3} \lll 15)) \dotsW’0, …, W’{63}W’k = W_k \oplus W{k+4}$。
• （3）迭代压缩： 同样初始化8个寄存器 ，执行 64轮非线性变换 。
  • 混淆作用：通过布尔函数 和 （前16轮为异或，后48轮为选择/多数表决）实现。
  • 扩散作用：通过置换函数 和 实现。 64轮结束后，同样将结果与本轮初始的 异或，作为下一分组的输入。

六、 针对Hash函数的攻击原理

衡量一个Hash算法好坏的标准，就是看攻击者找到碰撞所需花费的代价有多大。

1. 生日攻击 (Birthday Attack)： 生日攻击的数学原理来源于概率论中的“生日悖论”：在365天的取值中，要使得房间里至少有两个人生日相同的概率大于50%，只需要 23人 即可。 推导公式： 个数据项中任意两个取值不相同的概率为 。当 时， 。

将此结论推广到输出长度为 n = 2^m$ ）的Hash函数：

• 第一类生日攻击（寻找任意两个碰撞，测试CRHF）： 假设攻击者随机输入 个值，要使其中发生碰撞的概率大于0.5，所需次数 。 这说明： 要攻破一个256位的Hash函数，不需要尝试 次，仅仅需要尝试大约 次即可！ 这就是为什么SHA-256和SM3的抗碰撞强度标称为 。
• 第二类生日攻击（给定一个特定输出，找另一个输入与其碰撞，测试OWHF）： 要找到特定输出的碰撞，其概率计算不同，要达到0.5的概率，所需的尝试次数约为 。这比第一类攻击困难得多。

2. 中间相遇攻击： 这是一种专门针对分组链接迭代结构（如Merkle-Damgård）的攻击方法。 攻击者选出若干消息分组分为两部分：第一部分从初始值 正向迭代 到中间某一步；第二部分从预期的目标Hash摘要值 逆向反推 回这一步。如果在这中间步骤发现有一对输出相等，就可以“拼接”出一条能够产生同样Hash值的“碰撞消息”。

[!faq]- 课后作业

参考回答：

1. 杂凑函数在消息认证中的用途是什么？
杂凑函数在消息认证中主要用于生成一个能够代表原始消息的固定长度的特征值。通过对任意长度的消息进行运算，杂凑函数可以将其转化为一个唯一的、不可逆的摘要，这个摘要常与对称密钥、数字签名或加密技术结合使用，从而在保证计算效率的前提下，使接收方能够验证消息在传输过程中是否被篡改。

2. 消息认证的目的是什么？
消息认证的核心目的在于确保网络通信的安全与可靠，它主要用来验证信息的完整性和来源的真实性。具体而言，它不仅要确保接收到的消息在传输过程中没有被恶意篡改、删除或插入，还要证实消息确实是由声称的发送方所发出，而不是由攻击者冒充或伪造的。

3. 请对比分析先计算MAC,后加密和先加密后计算MAC有什么不同？
先计算MAC后加密的方法是将明文输入MAC函数生成认证码，然后将明文和认证码拼接在一起整体进行加密传输。这种方式的特点是能够保护认证码的机密性，防止攻击者了解MAC的结构，但其缺点在于接收方在进行完整性校验之前必须先执行解密操作，这意味着如果遇到拒绝服务攻击，系统即使面对无效的密文也需要消耗高昂的计算资源去解密。
与之相反，先加密后计算MAC的方法是先将明文加密生成密文，随后对生成的密文计算MAC，并将密文和MAC一起发送。这种方式提供了更高的安全性，因为接收方在收到数据后可以立刻利用共享密钥对密文进行MAC校验，如果校验失败则直接丢弃数据，无需执行解密操作，从而能够有效抵御针对解密过程的攻击，这也是目前现代密码学标准和安全协议中更为推荐的构造方式。