搜索

[26105] 2017-02-25_密码学大事件！研究人员公布第一例SHA-1哈希碰撞实例

文档创建者：s7ckTeam
浏览次数：27
最后更新：2025-01-19
2017-02-25_密码学大事件！研究人员公布第一例SHA-1哈希碰撞实例 - -   R o m a n G o l   L i a r o d 1 5 % 3 1 % 6 8 % 密 码 学 大 事 件 ！ 研 究 人 员 公 布 第 一 例   S H A - 1   哈 希 碰 撞 实 例 R o m a n G o l   L i a r o d   L i n u x 中 国   2 0 1 7 - 0 2 - 2 5 在 经 过 两 年 的 联 合 研 究 和 花 费 了 巨 大 的 计 算 机 时 间 之 后 ， 研 究 人 员 在 他 们 的 研 究 网 站   S H A t t e r e d   上 给 出 了 两 个 内 容 不 同 ， 但 是 具 有 相 同   S H A - 1   消 息 摘 要 的   P D F   文 件 。 本 文 导 航 - 相 关 背 景 - 攻 击 历 程 - 安 全 建 议 转 载 自 ： 知 乎   h t t p s : / / z h u a n l a n . z h i h u . c o m / p / 2 5 4 0 1 3 8 3   作 者 ：   R o m a n G o l   L i a r o d 2 0 1 7 年 2 月 2 3 日 ， 荷 兰 阿 姆 斯 特 丹   C e n t r u m   W i s k u n d e   &   I n f o r m a t i c a   ( C W I )   研 究 所 和   G o o g l e   公 司 的 研 究 人 员   [ M a r c   S t e v e n s   ( C W I A m s t e r d a m ) ,   E l i e   B u r s z t e i n   ( G o o g l e ) ,   P i e r r e   K a r p m a n   ( C W I   A m s t e r d a m ) ,   A n g e   A l b e r t i n i   ( G o o g l e ) ,   Y a r i k   M a r k o v   ( G o o g l e ) ,   A l e x   P e t i t B i a n c o   ( G o o g l e ) ,   C l e m e n t   B a i s s e   ( G o o g l e ) ]   在 谷 歌 安 全 博 客 [ 1 ] 上 发 布 了 世 界 上 第 一 例 公 开 的   S H A - 1   哈 希 碰 撞 实 例 ！ 在 经 过 两 年 的 联 合 研 究 和 花 费 了 巨 大 的 计 算 机 时 间 之 后 ， 研 究 人 员 在 他 们 的 研 究 网 站   S H A t t e r e d [ 2 ]   上 给 出 了 两 个 内 容 不 同 ， 但 是 具 有 相 同   S H A - 1   消 息 摘 要 的   P D F   文 件 （ P D F   1 [ 3 ] 、   P D F   2 [ 4 ] ） ， 这 就 意 味 着 在 理 论 研 究 长 期 以 来 警 示   S H A - 1   算 法 存 在 风 险 之 后 ， S H A - 1   算 法 的 实 际 攻 击 案 例 也 浮 出 水 面 ， 同 时 也 标 志 着   S H A - 1   算 法 终 于 走 向 了 生 命 的 末 期 。
相 关 背 景 M D - S H A   系 列   H a s h   函 数 家 族 是 最 为 知 名 的   H a s h   函 数 家 族 ， M D 5 ， S H A - 1   和   S H A - 2   都 被 广 泛 的 使 用 过 。 1 9 9 0   年   M D 4   算 法 被 提 出 ， 但 是 被 很 快 发 现 了 严 重 的 安 全 问 题 ， 在   1 9 9 2   年 被   M D 5   算 法 取 代 。 M D 5   算 法 在 之 后 的 十 几 年 内 被 软 件 行 业 广 泛 使 用 ， 直 到   2 0 0 4   年 我 国 密 码 学 家 王 小 云 在 国 际 密 码 讨 论 年 会 （ C R Y P T O ） 上 展 示 了   M D 5   算 法 的 碰 撞 并 给 出 了 第 一 个 实 例 （ 《 C o l l i s i o n s   f o r   h a s h   f u n c t i o n s   M D 4 ,   M D 5 ,   H A V A L - 1 2 8   a n d   R I P E M D ， r u m p   s e s s i o n   o f   C R Y P T O   2 0 0 4 ， H o w   t o   B r e a k   M D 5   a n d O t h e r   H a s h   F u n c t i o n s ， E u r o C r y p t   2 0 0 5 》 ） 。 该 攻 击 复 杂 度 很 低 ， 在 普 通 计 算 机 上 只 需 要 几 秒 钟 的 时 间 。 在   2 0 0 5   年 王 小 云 教 授 与 其 同 事 又 提 出 了 对   S H A - 1   算 法 的 碰 撞 算 法 （ 《 F i n d i n g   C o l l i s i o n s   i n   t h e   F u l l   S H A - 1 ，   C R Y P T O   2 0 0 5 》 ） ， 不 过 计 算 复 杂 度 为   2   的   6 9   次 方 ， 在 实 际 情 况 下 难 以 实 现 。 在 现 实 世 界 中 ， 利 用   H a s h   碰 撞 的 真 实 案 例 确 确 实 实 发 生 在 我 们 身 边 ： 2 0 0 8   年 的   C h a o s   C o m m u n i c a t i o n   C o n g r e s s   大 会 上 ， 研 究 人 员 展 示 了 利 用   M D 5   碰 撞 来 伪 造 合 法   C A   证 书 ， 从 而 攻 破   H T T P S   的 安 全 体 系 。 2 0 1 2   年 在 中 东 大 范 围 爆 发 的 F l a m e 火 焰 病 毒 ， 包 含 了 一 个 伪 造 的 数 字 签 名 ， 就 是 利 用   M D 5   碰 撞 伪 造 了 合 法 的 微 软 签 名 来 逃 避 杀 毒 软 件 的 查 杀 。 攻 击 历 程 本 次 攻 击 的 关 键 先 生 是 荷 兰 阿 姆 斯 特 丹   C W I   研 究 所 的   M a r c   S t e v e n s ， 他 自   2 0 0 6   年 以 来 一 直 在   H a s h   算 法 的 研 究 领 域 发 表 了 大 量 令 人 艳 羡 的 成 果 ， 包 括 一 系 列 关 于   M D 5   算 法 的 攻 击 。 2 0 0 9   年 他 作 为 一 作 的 论 文   《 S h o r t   c h o s e n - p r e f i x   c o l l i s i o n s   f o r   M D 5 a n d   t h e   c r e a t i o n   o f   a   r o g u e   C A   c e r t i f i c a t e   》 在 当 年 的   C R Y P T O   上 获 得 了 最 佳 论 文 奖 ， 在   2 0 1 3   年 的   E u r o c r y p t   上 ， 他 发 表 了 一 篇 论 文 — — 《 N e w   c o l l i s i o n   a t t a c k s   o n   S H A - 1   b a s e d   o n   o p t i m a l   j o i n t   l o c a l - c o l l i s i o n   a n a l y s i s [ 5 ] 》 ， 提 出 了 构 造   S H A - 1   碰 撞 的 一 种 新 的 攻 击 方 法 （ 攻 击 复 杂 度 为   2   的   6 1   次 方 ， 随 后 又 提 出 了 基 于   G P U   的 高 效 实 现 方 法 ） ， 随 后 数 年 不 断 提 出 了 新 的 改 进 方 法 ， 在   2 0 1 6   年 他 给 出 了 关 于   S H A - 1   算 法 的   F r e e s t a r t   c o l l i s i o n ， 也 就 是 找 到 了   S H A - 1   算 法 内 部 的 核 心 组 件   i n t e r n a l   c o m p r e s s i o n f u n c t i o n   的 一 个 碰 撞 实 例 （ 6 4   G P U   集 群 ， 1 0   天 计 算 量 ） ， 这 就 已 经 吹 响 了 攻 克   S H A - 1   完 全 实 际 碰 撞 攻 击 的 决 战 号 角 。 终
于 ， 在   G o o g l e   公 司 强 有 力 的 计 算 资 源 支 持 之 下 ， 在   2 0 1 7   年   2   月   2 3   日 ， S H A - 1   算 法 的 碰 撞 实 例 出 现 在 我 们 面 前 ！ 此 次 攻 击 到 底 使 用 了 多 强 的 计 算 资 源 ， 我 们 可 以 看 一 下 谷 歌 安 全 博 客 [ 6 ] 给 出 的 原 始 数 据 ： N i n e   q u i n t i l l i o n   ( 9 , 2 2 3 , 3 7 2 , 0 3 6 , 8 5 4 , 7 7 5 , 8 0 8 )   S H A 1   c o m p u t a t i o n s   i n   t o t a l 6 , 5 0 0   y e a r s   o f   C P U   c o m p u t a t i o n   t o   c o m p l e t e   t h e   a t t a c k   f i r s t   p h a s e 1 1 0   y e a r s   o f   G P U   c o m p u t a t i o n   t o   c o m p l e t e   t h e   s e c o n d   p h a s e 可 以 看 到 ， 这 样 如 此 强 劲 的 计 算 能 力 几 乎 是 历 史 上 最 大 规 模 的 一 次 计 算   H a s h   碰 撞 的 实 验 。 谷 歌 安 全 博 客 [ 7 ] 还 专 门 配 了 一 幅 图 来 比 较 ， 如 果 使 用 暴 力 搜 索 ， 使 用 的 计 算 资 源 即 使 是   G o o g l e   也 无 法 承 担 ， 而 在 人 类 智 慧 的 研 究 之 下 ， 改 进 的   S h a t t e r e d 算 法 只 需 要   1 1 0   个   G P U   年 就 可 以 完 成 第 二 阶 段 的 搜 索 任 务 。 关 于 攻 击 的 更 多 细 节 ， 可 以 参 考 论 文 — — 《 T h e   f i r s t   c o l l i s i o n   f o r   f u l l   S H A - 1 [ 8 ] 》 。 关 于 这 篇 论 文 ， 还 有 很 多 幕 后 的 八 卦 ， L o C C S   实 验 室 理 论 密 码 研 究 组 [ 9 ] 长 期 从 事 分 组 加 密 算 法 研 究 的 王 磊 研 究 员 曾 与   M a r c   S t e v e n s   合 家 聚 餐 ， 亲 切 交 谈 ， 并 与 本 次 工 作 的 作 者 之 一   P i e r r e   K a r p m a n   长 期 合 作 交 流 ， 王 磊 老 师 告 诉 我 们 ， 他 目 睹 了 这 个 密 码 学 历 史 性 事 件 的 诸 多 进 展 ， 这 个 轰 动 性 结 果 甚 至 让 今 年 某 顶 级 学 术 会 议 的   D e a d l i n e   为 之 延 期 ！ ！ ！
安 全 建 议 我 们 指 出 ， S H A - 1   碰 撞 攻 击 影 响 了 大 量 现 有 的 安 全 应 用 。 目 前 许 多 部 署 的   S S L / T L S   服 务 连 接 中 均 使 用 了   S H A - 1   算 法 作 为 消 息 验 证 的 基 本 密 码 学 原 语 ， 因 此 受 到 该 攻 击 的 影 响 ； 流 行 的 源 代 码 管 理 系 统   G i t   直 到 目 前 依 然 使 用   S H A - 1   作 为 文 件 的 消 息 “ 指 纹 ” 。 另 外 一 个 广 泛 受 到 影 响 的 场 景 是   A n d r o i d   系 统 中 应 用 、 升 级 包 、 B o o t l o a d e r   等 模 块 的 签 名 机 制 （ R S A   +   S H A - 1 ） ， 虽 然 A n d r o i d   7 . 0   给 出 的 全 新 的 签 名 方 案   A P K   S i g n a t u r e   S c h e m e   v 2   中 支 持   S H A - 2   家 族 的   S H A - 2 5 6   和   S H A - 5 1 2 ， 但 经 过 我 们 的 验 证 ， 目 前 大 量 设 备 仍 然 在 使 用   s h a 1 w i t h R S A   的 签 名 验 证 。 在 碰 撞 攻 击 的 影 响 下 ， 攻 击 者 能 够 构 造 出 内 容 篡 改 但 是 签 名 一 致 的 文 件 绕 过 验 证 。 尽 管 计 算 量 巨 大 且 对 内 容 的 控 制 存 在 一 定 的 困 难 ， 但 是 我 们 认 为 这 类 安 全 机 制 已 经 不 再 可 信 。 G o o g l e   公 司 和 诸 多   I T   安 全 研 究 人 员 均 在 过 去 几 年 呼 唤 开 发 者 尽 快 更 换   S H A - 1   算 法 ， 早 在   2 0 1 4   年 ， C h r o m e   团 队 就 已 经 宣 布
了 淘 汰   S H A - 1   算 法 的 时 间 表 ， 本 次 碰 撞 实 例 的 发 布 ， 也 给 所 有 还 在 持 观 望 和 犹 豫 态 度 的 人 敲 响 了 警 钟 ： 赶 紧 为 安 全 的 系 统 启 用 新 的   H a s h   算 法 ！ 事 实 上 ， S H A - 1   算 法 的 后 继 算 法 早 就 已 经 被 研 究 人 员 设 计 和 推 广 ， S H A - 2   算 法 家 族 （ 包 括 六 种   H a s h   函 数 ： S H A - 2 2 4 、 S H A - 2 5 6 、 S H A - 3 8 4 、 S H A - 5 1 2 、 S H A - 5 1 2 / 2 2 4 、 S H A - 5 1 2 / 2 5 6 ） 在   2 0 0 1   年 就 已 经 公 布 ， 而   N I S T   在 经 过 多 年 的   S H A - 3   设 计 竞 赛 后 ， 在   2 0 1 5   年 正 式 推 荐 由 著 名 的 密 码 学 研 究 人 员   G u i d o   B e r t o n i ,   J o a n   D a e m e n ,   M i c h a ë l   P e e t e r s   和   G i l l e s   V a n   A s s c h e   共 同 设 计 的   K e e c a k   算 法 家 族 作 为   S H A - 3   的 候 选 算 法 。 更 为 值 得 注 意 的 是 ， 中 国 国 家 密 码 管 理 局 同 样 在   2 0 1 0   年 底 发 布 了 我 国 自 主 的 国 密   S M 3   消 息 摘 要 （ 密 码 杂 凑 ） 算 法 。 这 些 算 法 的 安 全 性 在 目 前 经 受 住 了 广 泛 的 测 试 和 分 析 ， 是 值 得 信 赖 的 。 所 以 ， 文 章 的 最 后 ， G o S S I P   小 组 建 议 大 家 ： 任 何 以   S H A - 1   作 为 消 息 摘 要 算 法 的 安 全 产 品 应 该 尽 快 更 换 至 这 些 更 为 安 全 的   H a s h   算 法 。 上 海 交 通 大 学 密 码 与 计 算 机 安 全 实 验 室 （ L o C C S [ 1 0 ] ） 软 件 安 全 小 组 （ G o S S I P [ 1 1 ] ） 版 权 所 有 ， 转 载 请 与 作 者 取 得 联 系 ！ 本 文 已 获 授 权 转 载 。 本 文 使 用 的 图 片 来 自 谷 歌 安 全 博 客 [ 1 2 ] 。 相 关 阅 读 [ 1 ] :   谷 歌 安 全 博 客   -   h t t p s : / / s e c u r i t y . g o o g l e b l o g . c o m / 2 0 1 7 / 0 2 / a n n o u n c i n g - f i r s t - s h a 1 - c o l l i s i o n . h t m l [ 2 ] :   S H A t t e r e d   -   h t t p s : / / s h a t t e r e d . i t / [ 3 ] :   P D F   1   -   h t t p s : / / s h a t t e r e d . i t / s t a t i c / s h a t t e r e d - 1 . p d f [ 4 ] :   P D F   2   -   h t t p s : / / s h a t t e r e d . i t / s t a t i c / s h a t t e r e d - 2 . p d f [ 5 ] :   N e w   c o l l i s i o n   a t t a c k s   o n   S H A - 1   b a s e d   o n   o p t i m a l   j o i n t   l o c a l - c o l l i s i o n   a n a l y s i s   -   h t t p s : / / m a r c - s t e v e n s . n l / r e s e a r c h / p a p e r s / E C 1 3 - S . p d f [ 6 ] :   谷 歌 安 全 博 客   -   h t t p s : / / s e c u r i t y . g o o g l e b l o g . c o m / 2 0 1 7 / 0 2 / a n n o u n c i n g - f i r s t - s h a 1 - c o l l i s i o n . h t m l [ 7 ] :   谷 歌 安 全 博 客   -   h t t p s : / / s e c u r i t y . g o o g l e b l o g . c o m / 2 0 1 7 / 0 2 / a n n o u n c i n g - f i r s t - s h a 1 - c o l l i s i o n . h t m l [ 8 ] :   T h e   f i r s t   c o l l i s i o n   f o r   f u l l   S H A - 1   -   h t t p s : / / m a r c - s t e v e n s . n l / r e s e a r c h / p a p e r s / S B K A M 1 7 - S H A t t e r e d . p d f [ 9 ] :   L o C C S   实 验 室 理 论 密 码 研 究 组   -   h t t p s : / / l o c c s . s j t u . e d u . c n / s k c / L o C C S _ C R Y P T O - T e a m - H o m e . h t m l [ 1 0 ] :   L o C C S   -   h t t p s : / / l o c c s . s j t u . e d u . c n / m a i n / [ 1 1 ] :   G o S S I P   -   h t t p s : / / l o c c s . s j t u . e d u . c n / g o s s i p [ 1 2 ] :   谷 歌 安 全 博 客   -   h t t p s : / / s e c u r i t y . g o o g l e b l o g . c o m / 2 0 1 7 / 0 2 / a n n o u n c i n g - f i r s t - s h a 1 - c o l l i s i o n . h t m l 推 荐 文 章 <   左 右 滑 动 查 看 相 关 文 章   > 输 入 文 章   I D   或 长 按 二 维 码 直 达 阅 读 原 文
回复

举报

高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

使用Markdown编辑器编辑 使用富文本编辑器编辑

Archiver| 手机版| 小黑屋|
Powered by Discuz! X3.4 Copyright © 2001-2020, Tencent Cloud. 商业源码建议获取授权，如侵犯您的权益，请联系客服处理