MD5算法原理及其碰撞攻击

３ ＭＤ５算法的碰撞攻击
约 定 格 式 、有 语 义 的 信 息 ， 那 么 推 演 出 的 信息Ｂ将不是 一个 符合 约定 格式 、有语 义
ＭＤ５的创始人Ｒｉｖｅｓｔ猜测， ＭＤ５可能是 １２８位的Ｈａｓｈ码中最强的算法， 即Ｈａｓｈ码相 同的两条消息所需的代价为２６４数量级， 找到 给定摘要的消息所需的代价为２１２８数量级。
步数为１６０（ ５轮， 每轮１６步） 。 （ ３） ＭＤ５与ＳＨＡ－ １、ＲＩＰＥＭＤ－ １６０的 比
较 ＭＤ５、ＳＨＡ － １、ＲＩＰＥＭＤ － １６０ 均 基 于
ＭＤ４。 抗穷举攻击的能力： ３种算法都不易
受 到 对 抗 弱 碰 撞 性 的 攻 击 。由 于 ＭＤ５使 用 的是１２８位 的摘 要， 所 以 它 极 易 受 基 于 抗 强 碰 撞 性 的 生 日 攻 击 ， 而 ＳＨＡ － １ 和 ＲＩＰＥＭＤ－ １６０在不 久的 将来 对基 于抗 强碰 撞性的生日攻击是安全的。
（ ２） Ｂｏｅｒ 和 Ｂｏｓｓｅｌａｅｒｓ［２］说 明 了 如 何 找 到消息分组Ｘ和两个有关的链 接变 量使 得
的 信 息 。 比 如 说 ， Ａ是 一 个 符 合Ｘ５０９格 式 的数字证书， 那么 推出 的Ｂ不 可能 刚好 也 是一个符合Ｘ５０９格式， 而 且是 伪造 者希 望 的数字证书。
众所周知， 电子合同需要双方甚至多 方电子签名。对于双方签名， 相当于先产 生Ａ的Ｈａｓｈ值Ｈ１， 然后对Ａ和Ｈ１合起来的 信 息 进 一 步 产 生Ｈａｓｈ值 Ｈ２。目 前 的 研 究 发 现还无法找到一 种方 法推 出一 则信 息Ｂ刚 好产生同样的Ｈ１和Ｈ２。其次， 即使ＭＤ５被 破解， 也 有更 好的 更安 全 的Ｈａｓｈ算 法 。应 该 使 用 Ｈａｓｈ码 更 长 其 抗 密 码 分 析 能 力 更 强 的Ｈａｓｈ函 数 代 替ＭＤ５， 其 中２种 常 用 的 函数是下节中的ＳＨＡ－ １和ＲＩＰＥＭＤ－ １６０。
Ｔ［４］＝Ｃ１ＢＤＣＥＥＥ ………
Ｔ［２０］＝ Ｅ９Ｂ６Ｃ７ＡＡ
………
破， 也就是对于给定的 Ｔ［３６］＝ＦＤＥ５３８０Ｃ Ｔ［５２］＝ＦＣ９３Ａ０３９ 明 文 及 摘 要 ， 能 够 用 数
………
………
学计算的方法， 求出另 一个也能产生出此摘
Ｔ［１６］＝４９Ｂ４０８２１
Ｔ［３２］＝
Ｔ［４８］＝Ｃ４ＡＣ５６６５ Ｔ［６４］＝ＥＢ８６Ｄ３９１ 要 的 等 价 的 明 文 ； 第 ２
抗 密 码 分 析 的 能 力 ： ＭＤ５ 已 经 被 破 解 ， ＲＩＰＥＭＤ－ １６０正 是 为 抗 已 知 密 码 分 析 攻击而设计。虽然对ＳＨＡ－ １的设计原则知 之甚少， 但它抗已知密码分析攻击的能力 很强， 但与ＳＨＡ－ １相 比 ， 对ＲＩＰＥＭＤ－ １６０的 密码分析更加困难。
找到一个碰撞大约需要的消息数如下： ＭＤ５算法： ２６４≈１．８×１０１９ ＳＨＡ－ １算法： ２８０≈１．２×１２２４ ＲＩＰＥＭＤ－ １６０算法： ２８０≈１．２×１０２４ 速 度 ： ３种 算 法 都 是 基 于 模 ２３２加 法 和 简单 的位 逻辑 运算 ， 所以 它 们 在３２位 机 上 执行速度较快。 此外，还有其它一些消息摘要长度更大 的 安 全 Ｈａｓｈ 算 法 ， 例 如 ＳＨＡ－ ２５６、ＳＨＡ－ ３８４、ＳＨＡ－ ５１２。 随着新的攻击方法的提出和计算能 力的不断提高， ＭＤ５ 已经被攻破， 另外一 些 Ｈａｓｈ函 数 如ＳＨＡ－ １也 将 在 今 后 几 年 面 临 严 峻 的 考 验 。因 此 设 计 新 的 高 安 全 度 的 Ｈａｓｈ函 数 的 需 求 越 来 越 迫 切 。基 于 ＭＤ５的 碰撞攻 击， Ｈａｓｈ函 数的 设计 应 该 考 虑 到 如 下２个 方面 ： ①输 出Ｈａｓｈ值 的 长 度 要 提 高 ； ②抵抗差分攻击的能力要强。
它们产生相同的输出， 也就是说， 对一个 ５１２ 位 的 分 组 ， ＭＤ５ 压 缩 函 数 对 缓 冲 区
５ 安全Ｈａｓｈ算法介绍
ＡＢＣＤ的 不同 值产 生相 同的 输出 ， 称 之 为 伪 碰 撞 。目 前 尚 无 法 用 上 述 方 法 成 功 地 攻 击 ＭＤ５算 法 。
（ ３） Ｄｏｂｂｅｒｔｉｎ［３］提出的攻击对ＭＤ５最具 威胁， 它可使ＭＤ５压缩函数产生碰撞。但到 目前为止， 尚不能用Ｄｏｂｂｅｒｔｉｎ提出的方法 对使用初值（ ＩＶ） 的整个消息进行攻击。
第４轮的 输出 与 第１轮 的 输 入 （ ＣＶｑ） 相 加 得到ＣＶｑ＋１， 这里 的加 法是 指缓 冲 区 中 的 ４ 个 字 与 ＣＶｑ中 对 应 的 ４ 个 字 分 别 ２３２模 相 加。
（ ５） 步骤５： 输 出 。所 有Ｌ个５１２位 分 组 处 理完 毕， 最 后的 结 果 就 是１２８位 消 息 摘 要。
８Ｄ２Ａ４Ｃ８Ａ
种是对于给定的明文
Ｘ［ｋ］＝Ｍ［ｑ×１６＋ｋ］＝消 息 第 ｑ个５１２位 分 及摘要 ， 能够 用随 机碰 撞的 方 法 找 到 另 一
组 的 第 ｋ个 ３２位 字 Ｔ ［ｉ］＝矩 阵Ｔ中 的 第ｉ个３２位 字＋＝模２３２
个等价的明文； 第３种也是用随机碰撞的 方法， 找到两个具有相同摘要的不同的明
作者简介：舒畅（ １９８２－ ） ， 女， 湖北黄石人， 广东省清远市公安消防支队助理工程师， 研究方向为网络安全。
软件导刊·２００７·６ 月号 １０３
算法与语言
表 ２ 从正弦函数构造的表 Ｔ
４ ＭＤ５算法的破解
Ｔ［１］＝Ｄ７６ＡＡ４７８ Ｔ［１７］＝Ｆ６１Ｅ２５６２ Ｔ［３３］＝ＦＦＦＡ３９４２ Ｔ［４９］＝Ｆ４２９２２４４ 及其意义 一 种 Ｈａｓｈ 函 数 被
算法与语言
ＭＤ５算法原理及其碰撞攻击
舒畅
（清远市公安消防支队， 广东 清远 ５１１５１５）
摘 要： ＭＤ５作为一种重要的Ｈａｓｈ函数， 被广泛应用于数据完整性和消息认证领域。详细探讨了ＭＤ５算法的
原 理 、ＭＤ ５算 法 的 碰 撞 攻 击 以 及ＭＤ ５算 法 破 解 的 重 要 意 义 。
关键词： 密码学； Ｈａｓｈ函数； ＭＤ５； 碰撞攻击
每一轮 包含 对缓 冲 区ＡＢＣＤ进 行１６步 迭代， 每步迭代形为：
ａ←ｂ（（ａ＋ｇ（ｂ，ｃ，ｄ，）＋Ｘ" ｋ # ＋Ｔ" ｉ $ ）＜＜＜ｓ） 其中 ａ，ｂ，ｃ，ｄ＝缓冲区 的４个 字， 它 按一 定次 序随迭代步变化。 ｇ＝基本逻辑函数Ｆ， Ｇ， Ｈ， Ｉ之一 ＜＜＜ｓ＝３２位 的 变 量 循 环 左 地址字节上） 如下：
字 Ａ： ０１ ２３ ４５ ６７ 字 Ｂ： ８９ ＡＢ ＣＤ ＥＦ 字 Ｃ： ＦＥ ＤＣ ＢＡ ９８ 字Ｄ： ７６ ５４ ３２ １０ （ ４） 步 骤 ４： 以 ５１２位 的 分 组 （ １６个 字 ） 为 单 位 处 理 消 息 。算 法 的 核 心 是 压 缩 函 数 （ ＨＭＤ５） ， 它包括４轮处理。４轮处理具有相 似的结构， 但每次使用不同的基本逻辑函 数， 记为Ｆ、Ｇ、Ｈ、Ｉ， 如表１所示。 每 一 轮 以 当 前 的 ５１２位 分 组 （ Ｙｑ） 和 １２８位缓 冲区ＡＢＣＤ作为 输入 ， 并 修 改 缓 冲 区 的内容 。每 次 使 用６４元 素 表Ｔ［１Ｌ ６４］中 的１／４。 该 Ｔ表 有 ｓｉｎ函 数 构 造 而 成 。Ｔ的 第 ｉ 个 元 素 表 示 为Ｔ［ｉ］， 其 值 等 于２３２×ａｂｓ（ｓｉｎ（ｉ）） 的整数部分， 其中ｉ是弧 度。由 于ａｂｓ（ｓｉｎ（ｉ）） 是 一个０到１之 间 的 数 ， Ｔ的 每 一 个 元 素 是
（ ２） 步骤２： 填充长度。原始消息长度 （ 二 进制 位的 个数 ） 用６４位 表 示 ， 并 附 在 步 骤１的结果后。
由 这２个 步 骤 得 到 长 度 为 ５１２整 数 倍 的 报 文 。 表 示 为Ｌ个５１２位 的 分 组 ： Ｙ０， Ｙ１， … … ＹＬ－ １。其 长 度 为 Ｌ×５１２ｂｉｔｓ。令 Ｎ＝Ｌ×１６， 则长度为Ｎ个３２位的字。令Ｍ×［ＯＬ Ｎ－ １］表
加法 每次循 环进 行１６步 操 作 ， 其 中Ｓ的 值
在４次循环中都有不同的定义， 并且在每 一步的值也不同。
文， 其工作量比第２种情况要小很多。 根据ＭＤ５破 解算 法， 对 一个 消息Ａ及
其Ｈａｓｈ值Ｈ， 有 可 能 推 出 另 一 则 信 息Ｂ， 它 的Ｈａｓｈ值 也 是Ｈ。如 果Ａ是 一 个 符 合 预 先
表 １ 基本逻辑函数的真值表 ｂ ｃ ｄ Ｆ ＧＨＩ ００００００１ ００１１０１０ ０１００１１０ ０１１１００１ １００００１１ １０１０１０１ １１０１１００ １１１１１１０
一个可 以表 示成３２位的 整数 。Ｔ表 提 供 了 随机 化的３２位模 板， 消 除 了 在 输 入 数 据 中 的任何规律性的特征，如表２所示。
Ｔ［２］＝Ｅ８Ｃ７Ｂ７５６ Ｔ［１８］＝Ｃ０４０Ｂ３４０ Ｔ［３４］＝８７７１Ｆ６８１ Ｔ［５０］＝４３２ＡＦＦ９７
Ｔ［１９］＝２６５Ｅ５Ａ５１
Ｔ［３］＝２４２０７０ＤＢ
Ｔ［３５］＝６９９Ｄ６１２２ Ｔ［５１］＝ＡＢ９４２３Ａ７
破解， 通常有３种情况： 第１种 是 函 数 的 单 向 性 被攻破， 即最彻底的攻
示以字为单位的消息表示。 （ ３） 步 骤 ３： 初 始 化 ＭＤ缓 冲 区 。 一 个
１２８ 位 ＭＤ 缓 冲 区 用 以 保 存 中 间 和 最 终 Ｈａｓｈ函数 的结 果。它 可 以 表 示 为４个３２位 的寄存器（ Ａ， Ｂ， Ｃ， Ｄ） 。
寄 存 器 初 始 化 为 以 下 的 １６进 制 值 ： Ａ＝６７４５２３０１ Ｂ＝ＥＦＣＤＡＢ８９ Ｃ＝９８ＢＡＤＣＦＥ Ｄ＝１０３２５４７６
中图分类号： ＴＰ３１２
文献标识码： Ａ
文章编号： １６７２－ ７８００（２００７）０６－ ０１０３－ ０２
１ ＭＤ５消息摘要算法
ＭＤ５ （ ＲＦＣ１３２１） 的 全 称 是 Ｍｅｓｓａｇｅ － Ｄｉｇｅｓｔ Ａｌｇｏｒｔｈｍ ５， 即 将 任 意 长 度 的 “字 节 串”变 换成 一个１２８ｂｉｔ的大 整数 ， 是 一 种 不 可逆的字符串变换算法。通过数学运算， 把 不 同 长 度 的 信 息 转 化 到 １２８位 编 码 中 ， 形 成Ｈａｓｈ值 ， 通过 比较 该数 值 是 否 正 确 ， 来确定通信双方的合法性， 即数字签名功 能 。在数 据传 输后 ， 可以 通 过 比 较Ｈａｓｈ值 来判断信息途中是否被截获修改， 是否由 合法的发送人发送或者合法的接收人接 收等。用这种方法， 可以防止密钥丢失。