From Collisions to Chosen-Prefix Collisions - Application to Full SHA-1
From Collisions to Chosen-Prefix Collisions - Application to Full SHA-1
复制标题
DOI：
10.1007/978-3-030-17659-4_18
复制
发表时间：
2019-05
期刊：
影响因子：
--
通讯作者：
G. Leurent;Thomas Peyrin
中科院分区：
文献类型：
--
作者：
G. Leurent;Thomas Peyrin
选择前缀冲突攻击是冲突攻击的更强变体，其中任意一对质询前缀都会变成冲突。选择前缀冲突通常比（相同前缀）冲突更难产生，但这种攻击的实际影响要大得多。虽然许多密码结构依赖于抗碰撞性来进行安全证明，但碰撞攻击很难转化为具体协议的破坏，因为对手对碰撞消息的控制有限。另一方面，选择前缀冲突已被证明可以破坏证书（通过创建恶意 CA）和许多互联网协议（TLS、SSH、IPsec）。在本文中，我们提出了将冲突攻击转变为选择前缀冲突攻击的新技术。我们的策略由两个阶段组成：首先是生日搜索，旨在将随机链接变量差异（由于选择的前缀模型）与一组预定义的目标差异相结合。然后，使用多块方法，仔细分析聚类效果，我们使用为碰撞攻击开发的技术将这个新的链接变量差异映射到一对碰撞状态。我们将这些技术应用于 MD5 和 SHA-1，并获得改进的攻击。特别是，我们对 SHA-1 进行了选择前缀碰撞攻击，其复杂性介于 和 之间（取决于关于查找接近碰撞块的成本的假设），而最著名的攻击具有复杂性。这只是 SHA-1 经典碰撞攻击复杂性的一小部分（估计为）。这再次警告行业和用户必须尽快放弃使用 SHA-1。
A chosen-prefix collision attack is a stronger variant of a collision attack, where an arbitrary pair of challenge prefixes are turned into a collision. Chosen-prefix collisions are usually significantly harder to produce than (identical-prefix) collisions, but the practical impact of such an attack is much larger. While many cryptographic constructions rely on collision-resistance for their security proofs, collision attacks are hard to turn into break of concrete protocols, because the adversary has a limited control over the colliding messages. On the other hand, chosen-prefix collisions have been shown to break certificates (by creating a rogue CA) and many internet protocols (TLS, SSH, IPsec).In this article, we propose new techniques to turn collision attacks into chosen-prefix collision attacks. Our strategy is composed of two phases: first a birthday search that aims at taking the random chaining variable difference (due to the chosen-prefix model) to a set of pre-defined target differences. Then, using a multi-block approach, carefully analysing the clustering effect, we map this new chaining variable difference to a colliding pair of states using techniques developed for collision attacks.We apply those techniques toMD5andSHA-1, and obtain improved attacks. In particular, we have a chosen-prefix collision attack againstSHA-1with complexity betweenand(depending on assumptions about the cost of finding near-collision blocks), while the best-known attack has complexity. This is within a small factor of the complexity of the classical collision attack onSHA-1(estimated as). This represents yet another warning that industries and users have to move away from usingSHA-1as soon as possible.