SHA1碰撞演示/示例

Question

SHA1碰撞演示/示例

hashsha1

31

这个问题类似于这个问题，但那个只提到了MD5碰撞演示。

到目前为止，是否已知任意消息的SHA1碰撞对？

我想用它们来测试各种软件产品（包括我自己的和一些第三方产品）如何处理它。

进行一些谷歌搜索只能找到一些关于如何创建SHA1碰撞的提示，以及非常突出的MD5/SHA0碰撞，但我无法获取任何实际的SHA1碰撞示例。

- Arc

5个回答

18

现在已经发布了第一个已知的碰撞结果，请访问https://shattered.it/

$ curl -sSO https://shattered.it/static/shattered-1.pdf
$ curl -sSO https://shattered.it/static/shattered-2.pdf

$ sha1sum *.pdf
38762cf7f55934b34d179ae6a4c80cadccbb7f0a  shattered-1.pdf
38762cf7f55934b34d179ae6a4c80cadccbb7f0a  shattered-2.pdf

$ sha256sum *.pdf
2bb787a73e37352f92383abe7e2902936d1059ad9f1ba6daaa9c1e58ee6970d0  shattered-1.pdf
d4488775d29bdef7993367d541064dbdda50d383f89f0aa13a6ff2e0894ba5ff  shattered-2.pdf

- Dave L.

1

大多数来源都指向shattered.io - 但是对于我来说，这两个域名显示相同的内容并且实际上解析到相同的IP地址集。 - Palec

第二个公开已知的SHA-1碰撞信息，包括文件本身，可以在sha-mbles.github.io找到。 - Nnnes

11

谷歌安全博客在此处介绍了首次公开的有意SHA-1碰撞: https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html

两个具有相同SHA-1的PDF文件的直接链接（来自专门针对此发现的网站）：

再次，Marc Stevens与CWI Amsterdam和一些谷歌员工一起参与了此次全轮SHA-1的两个构建PDF的工作。

Stevens还指出，由于SHA-1的Merkle-Damgård结构，这2个PDF可以用相同的任意数据进行扩展（附加），以产生散列为相同摘要的更长版本。

谷歌将在90天内（2017年2月23日）发布相关源代码，给受影响的系统供应商一些时间来更新他们的东西。

现在还不清楚像git和GitHub这样的软件和服务提供商将如何处理这个问题，特别是在向后兼容方面。

Linus Torvalds就git 发表了一份声明，指出他们将以兼容的方式迁移到新的哈希算法，但这需要时间。

顺便说一下，“破碎”碰撞演示不会影响git（没有修改），因为它使用SHA-1，如下所示：

sha1("blob " + <size in octets as text> + "\0" + <contents>)

你可以使用git hash-object <文件路径>获取git哈希，即使该文件不在git中。

在相关新闻中，Subversion似乎是第一个真正的受害者，导致仓库损坏，从而使上述文件成为实际的漏洞利用。 -- 以前... -- 马克·斯蒂文斯发现了76轮碰撞。

密码学家Jean-Philippe Aumasson是BLAKE和SipHash的共同创造者，也是Password Hashing Competition (PHC)的发起人。他猜测，到2020年, 在完整的80轮中将会发现SHA-1碰撞。

根据Marc Stevens等人于2015年10月发布的持续研究，

... 我们估计在今天（即2015年秋季），使用Amazon EC2云计算租赁几个月的成本为75K$至120K$。与此相比，安全专家Bruce Schneier先前预测到，到2018年，SHA-1碰撞的成本将达到约173K$。

他们还描述了针对SHA-1压缩函数的碰撞攻击。

- Arc

4

2005年，王小云、殷勇和于泽江在Collision Search Attacks on SHA1一文中给出了一个例子，但仅适用于弱化的SHA-1（58轮版本）。（完整的官方SHA-1执行80轮。）

3 A collision example for 58-step SHA1

         h₁ = compress(h₀,M₀) = compress(h₀,M'₀)
 _____________________________________________________
   h₀:  67452301 efcdab89 98badcfe 10325476 c3d2e1f0
 _____________________________________________________
   M₀:  132b5ab6 a115775f 5bfddd6b 4dc470eb
        0637938a 6cceb733 0c86a386 68080139
        534047a4 a42fc29a 06085121 a3131f73
        ad5da5cf 13375402 40bdc7c2 d5a839e2
 _____________________________________________________
   M'₀: 332b5ab6 c115776d 3bfddd28 6dc470ab
        e63793c8 0cceb731 8c86a387 68080119
        534047a7 e42fc2c8 46085161 43131f21
        0d5da5cf 93375442 60bdc7c3 f5a83982
 _____________________________________________________
   h₁:  9768e739 b662af82 a0137d3e 918747cf c8ceb7d4
 _____________________________________________________

Table 2: A collision of SHA1 reduced to 58 steps. The two
messages that collide are M₀ and M'₀. Note that padding
rules were not applied to the messages.

- Ben Robinson

存档网站链接，指向我发布链接时的页面。https://web.archive.org/web/20090830220227/http://cryptome.org/sha1-attacks.htm - Ben Robinson

2

并非SHA1碰撞，但存在PBKDF2-HMAC-SHA1消息摘要认证代码的碰撞。

例如，两个密码plnlrtfpijpuhqylxbgqiiyipieyxvfsavzgxbbcfusqkozwpngsyejqlmjsytrmd和eBkXQTfuBqp\'cTcar&g*，盐值为hunter2，迭代次数为4，使用PBKDF2(SHA1, password, salt, iterations, dkLen)提供相同的值（对于dkLen 20，值为35d1c8f259129dc800ec8e073bb68f995424619c）。

事实上，对于长度大于64个字节的字符串，找到这样的碰撞是微不足道的。

另一个碰撞示例（Python3）：

>>> import hashlib, binascii
>>> def pbkdf2sha1hex(x, salt, iters):
...     h = hashlib.pbkdf2_hmac('sha1', x, salt, iters)
...     return binascii.hexlify(h)
>>> pbkdf2sha1hex(b'https://dev59.com/AXA75IYBdhLWcg3wGVCI#31136714', b'NaCl', 1000000)
b'20177527e04e05d5e7b448c1ab2b872f86831d0b'
>>> pbkdf2sha1hex(b'\x8c\xbf8\x94\xbc\xf4\xbe\x90xT,r\xbc\x03\xd1\xed\xd9\xea\xfb\x9f', b'NaCl', 1000000)
b'20177527e04e05d5e7b448c1ab2b872f86831d0b'

请注意，PBKDF2-HMAC-SHA256也存在同样的“问题”：

>>> h1 = pbkdf2_hmac('sha256', b'https://dev59.com/AXA75IYBdhLWcg3wGVCI#31136714', b'NaCl', 1000000)
b"\xcf\xc5\xee\x15=\r\x0b\x0e\x89r\x9b\xe1\xb7'+\xa4'o\x98kn++u\x12\xec\xd9\xec\xea\xebL\xb7"
>>> h2 = pbkdf2_hmac('sha256', b'.\x83\xb0D\x93D\x9f\x162\xf3\xd4x\xb6\x1a\x9f-\x1f\xdb\xdc\xa4\x8f\xb3\x95Y5\xea\x99*\x97\x00V\x81', b'NaCl', 1000000)
>>> h1 == h2
True

这一切都发生在 PBKDF2 定义中，对于长字符串，它成立：
PBKDF2(hashalgo, s, ...) == PBKDF2(hashalgo, hashalgo(s), ...).

更多信息请参见：https://mathiasbynens.be/notes/pbkdf2-hmac

- mykhal

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Thomas Pornin · Accepted Answer

2017年2月23日的最新回答

互联网安全基础中的SHA1加密哈希函数已经于六年多来一直处于崩溃边缘。现在，由于首个已知的致命“碰撞”漏洞被提交，它正式宣告死亡。

以前的回答（不再准确）

目前尚未发现SHA-1的碰撞。当前：

有一些关于SHA-1 简化版 的碰撞，它们使用的轮数少于标准SHA-1的80轮。
已经描述了一种算法，可以以大约等于对小型消息进行2⁶³次SHA-1调用的计算工作量来获得SHA-1碰撞；这比通用算法要好得多（平均需要2⁸⁰次调用），但仍然相当庞大，而且该算法尚未运行。

曾经试图利用那些有一些多余CPU时钟周期可供捐赠的人的力量来获得SHA-1的碰撞，使用BOINC框架组织整个过程，但志愿者不够，该工作于去年被放弃。因此目前还没有实际的SHA-1碰撞。

理论攻击依赖于一些可能会被证明略微错误的假设；例如，对MD5的攻击实际上比预期要快一点（在某些点上必须满足一个性质，并具有2^-28的理论概率，但在实践中它更接近于2^-27.7，即攻击比预测的快20%）。仍然认为理论攻击是正确的，复杂度“相当准确”。