Skip to content

MD5

1. MD5 基础理论与特性

  • 基本概念：MD5 是一种单向散列（Hash）函数，它的作用是将明文（plaintext）转换为密文（ciphertext）。具体来说，它将报文（message）转换为报文摘要（digest），这个过程相当于有损压缩。

  • 无需密钥：从报文生成摘要的过程中不需要使用密钥。

  • 长度特性：MD5 算法的输入 message 长度可以是 \([0, n]\) 字节（其中 \(n\) 可以无限大），但输出的 digest 长度固定为 128 位，即 16 个字节。

  • MD5 碰撞（Collision）：假定可以找到两段不同的报文 \(m1\) 及 \(m2\)（\(m1 \neq m2\)），使得 \(md5(m1) == md5(m2)\)，则称发生了 MD5 碰撞。

2. MD5 计算过程中的分块与填充 (Padding)

设文件大小为 \(n\) 字节，MD5 在计算时是分块进行的，每块大小为 64 字节。

当最后一块大小刚好为 64 字节时，该块只能算作倒数第 2 块，必须在其后补充一个大小为 0 字节的块作为真正的最后一块。

最后一块的原始大小为 \([0, 63]\) 字节，需要按以下步骤进行填充，使其凑成 64 字节的一个块，或扩充至 128 字节的两个块：

  1. 数据填充：

    • 情况 A (长度 < 56 字节)：假定该块大小 \(n < 56\) 字节，则在末尾补上 0x80，其后补 0x00，共补 \(56-n\) 个字节。例如 \(n=55\) 时，只需补上 0x80 一个字节。

    • 情况 B (长度在 [56, 63] 字节)：假定该块大小 \(n \in [56, 63]\)，此时空间不足以追加长度信息，必须补至下一个块的末尾，总共需要补上 \(64 - n + 56\) 个字节。例如 \(n=56\) 时，应补上 \(64\) 个字节（即 \(8+56\) 个字节）。

  2. 长度追加：在填充完 0 后，最后补上 8 个字节。这 8 个字节相当于一个 64 位的整数，记录的是 message 原本的总位数（不含填充内容）。

3. MD5 源代码与核心数据结构剖析

MD5 的实现依赖于特定的数据结构和轮函数操作。

3.1 核心数据结构 MD5_CTX

typedef struct _MD5_CTX
{
    ulong32 state[4]; /* 128位摘要 (a, b, c, d) */
    ulong32 count[2]; /* 已处理的报文的二进制位数，最大值为 2^64-1 */
    unsigned char data[64]; /* 64字节的message块缓存 */
} MD5_CTX;

此处 ulong32 被强制定义为 32 位无符号整数。

3.2 算法核心流程

  1. 初始化 (Init_MD5)：

    初始化 count 为 0。

    赋予 4 个链接变量（state）初始值（Magic Numbers）：

    • state[0] = 0x67452301

    • state[1] = 0xEFCDAB89

    • state[2] = 0x98BADCFE

    • state[3] = 0x10325476

  2. 位运算宏定义：算法包含 F, G, H, I 四个基本的按位逻辑函数，以及循环左移宏 ROL(x, n)。利用这些基本函数构成了 FF, GG, HH, II 四种宏操作。

  3. 数据更新 (Update_MD5)：

    • 利用位运算 (count[0] >> 3) & 0x3F 计算当前内部缓冲 data 中剩余未处理的字节数 bytes_left。

    • 如果输入数据填满了 64 字节的缓存块，就调用 Process_One_Block_MD5 对这 64 字节进行压缩计算，并将剩余数据循环存入缓冲。

  4. 单块处理 (Process_One_Block_MD5)：

    • 取出当前的 state 存入局部变量 a, b, c, d 中。

    • 经历 64 步（共 4 轮，每轮 16 步）的复杂变换，分别调用 FF、GG、HH、II 宏，并混入从明文块中取出的数据位和特定的常量 const_sin。

    • 最后将变换后的 a, b, c, d 累加回原 state[0..3] 中。

  5. 收尾填充 (Final_MD5)：

    • 保存最初始的已处理二进制位数 total_bits。

    • 计算出需要填充的长度 pad_len（补全至不足 8 字节满 64 字节的位置），并使用预设好的 pad_stuff（即 0x80 后面跟着一堆 0x00）调用 Update_MD5 进行填充。

    • 最后将 total_bits 调用 Update_MD5 补入末尾。

3.3 正弦常量 (Sine Constants)

64 步操作中每次加入的常量值并非随机，而是通过正弦函数计算得来。计算公式为：

y = floor(fabs(sin(i)) * pow(2,32)) （其中 i 从 1 到 64，单位是弧度）。

4. MD5 的应用与碰撞攻击利用

  • 数字签名结合：MD5 经常与 RSA 等算法结合用于数字签名。

    • 发送方 A 计算摘要 \(m = \operatorname{md5}(\text{letter})\)，随后用自己的私钥对摘要加密得到签名 \(m' = \operatorname{rsa}(m, \text{A 的私钥})\)。

    • 接收方 B 收到后验证：\(\operatorname{rsa}(m', \text{A 的公钥}) = \operatorname{md5}(\text{letter})\)。

  • 碰撞的实际影响：假定构造出两个会发生碰撞的文件 \(m1\) 和 \(m2\)（即 \(md5(m1) == md5(m2)\)），由于此时计算所用的 4 个 state 种子值完全相等，那么在此基础上追加相同内容，其结果依然相等，即：\(md5(letter + m1) == md5(letter + m2)\)。这意味着 \(letter + m1\) 的签名可以被恶意用于 \(letter + m2\)。

5. MD5 破解方法：彩虹表 Rainbow Table

彩虹表是一种用空间换时间的密码破解技术，适用于逆向查找 MD5 对应的明文。

5.1 彩虹表的构建（以 4 个大写字母为例）

  1. 产生一个随机数 \(n_0 \in [0, 26^4-1]\)。

  2. 找出与 \(n_0\) 对应的 4 位字母组合 \(p_0\)，并计算其 MD5 值：\(m_0 = md5(p_0)\)。

  3. 循环运算建立哈希链：执行 100 次循环（\(j=1\) 到 \(100\)）：

    • 消减函数 Reduction function：计算 \(n_j = m_{j-1} \bmod 26^4\)。（把一个明文的 MD5 计算结果映射到另一个明文）

    • 映射出对应的字母组合 \(p_j\)（例如 n=0 时为 "AAAA"，n=26 时为 "AABA"）。

    • 计算新的 MD5：\(m_j = md5(p_j)\)。

  4. 在数据库中仅记录链条的起点 \(n_0\) 和终点 \(m_{100}\)。上述过程完成 SomeBigNumber 次后，得到对应数量的链，每条链隐式包含 101 个 md5 值。

5.2 彩虹表的查询与破解

假设要破解一个已知的 MD5 值 M：

  1. 首先在数据库的终点（\(m_{100}\)）中查找 M。若找到，表示 M 是 \(j=100\) 时算出来的。从数据库取出对应的 \(n_0\)，顺着算法重新计算到第 100 步，得到的 \(p_{100}\) 即为所求明文。

  2. 若数据库中未找到 M，则假设它是链条倒数第二个节点（即设 \(m_{99} = M\)），再次执行消减函数和 MD5 计算得出 \(m_{100}\)（对应推导出的 \(m_{j+1}\)），再到数据库中匹配。

  3. 若匹配成功，表示找到了该链的起点 \(n_0\)。从起点重新推导到 \(j=99\) 时的字母组合 \(p_{99}\)，该组合极有可能满足 \(md5(p_{99}) == M\)。依此类推不断往前倒推验证。

SHA-1

1. 算法核心特征

  • 哈希值长度：160位（20字节），由5个32位（ulong）状态值组成。比MD5多32位。

  • 数据块大小：分块处理，每块64字节（512位）。

  • 填充规则：当最后一块不足64字节时进行填充，机制与MD5相同。数据末尾必须追加8个字节（64位）用于记录原始报文的总位数。

  • 字节序要求：SHA-1 算法严格遵循大端序（Big-Endian）。在小端序（如 Intel CPU）架构下，计算过程中需要对数据块、长度值以及最终的哈希输出进行字节序转换。

2. 核心数据结构 (SHA1_CTX)

上下文结构体用于保存哈希计算的中间状态：

  • state[5]：长度为5的 unsigned long 数组，总计20字节，用于存储160位的中间/最终哈希值。

  • length：包含 hi 和 lo 两个32位整数，组合成一个64位整数，用于累加记录已处理报文的二进制位数。

  • data[64]：内部缓冲区，缓存尚未达到64字节的数据块。

3. 算法执行流程

3.1 初始化 (SHA1_Init)

为5个状态变量赋初始魔数，并将报文长度清零：

  • state[0] = 0x67452301UL

  • state[1] = 0xEFCDAB89UL

  • state[2] = 0x98BADCFEUL

  • state[3] = 0x10325476UL

  • state[4] = 0xC3D2E1F0UL

3.2 数据处理 (SHA1_Update)

将输入报文分批送入内部缓冲区，满64字节即触发一次块处理：

  1. 计算当前缓冲区内已有的剩余字节数。

  2. 更新64位报文长度计数器（处理低32位进位到高32位的逻辑）。

  3. 如果新输入的数据能够填满64字节缓冲区，则调用核心处理函数 Process_One_Block_SHA1。

  4. 若输入数据极长，则通过循环直接以64字节为步长处理数据，省去拷贝到缓冲区的开销。

  5. 将末尾不足64字节的零头存入内部缓冲区等待下次处理。

3.3 填充与结束 (SHA1_Final)

  1. 记录原始长度：提取当前 length 值（64位总位数），后续追加使用。

  2. 填充数据：

    • 首先追加一个 0x80 字节。

    • 随后补 0x00。

    • 长度判定：若缓冲区剩余空间不足以放下8字节的长度信息（即已占用 \(\ge 56\) 字节），则当前块填满 0x00 后先处理一次，然后再开启一个新块填充 0x00 至56字节。

  3. 追加总位数：将步骤1提取的64位总位数转为大端序，填入最后8个字节，触发最后一次块计算。

  4. 输出摘要：提取 state 数组的20字节。在小端序机器上输出时，必须先对每个 ulong 内部的4个字节进行大端序翻转，以确保按字节读取时顺序正确。

4. 单块核心计算 (Process_One_Block_SHA1)

对64字节数据块进行数学运算，更新内部状态：

  1. 数据转换：将输入的64字节（16个 ulong）转为大端序，存入数组 X[0...15]。

  2. 数据扩充：将16个 ulong 扩展为80个 ulong。

    • 扩展公式：X[i] = ROL(X[i-3] ^ X[i-8] ^ X[i-14] ^ X[i-16], 1) （其中 ROL 为循环左移）。

  3. 四轮混合运算（Round）：

    每轮包含20步操作（共80步），分别使用不同的非线性逻辑函数和常数：

    • 第 00-19 步：使用常数 y1 = 0x5A827999，函数 f(u,v,w) = (u & v) | (~u & w)

    • 第 20-39 步：使用常数 y2 = 0x6ED9EBA1，函数 h(u,v,w) = u ^ v ^ w

    • 第 40-59 步：使用常数 y3 = 0x8F1BBCDC，函数 g(u,v,w) = (u & v) | (u & w) | (v & w)

    • 第 60-79 步：使用常数 y4 = 0xCA62C1D6，函数 h(u,v,w) = u ^ v ^ w

  4. 状态叠加：一轮运算结束后，将运算得到的临时状态累加回主状态 state[0...4] 中。