SHA1碰撞演示/示例

Question

此问题与this类似，但该问题仅涉及MD5碰撞演示。

到目前为止，是否有任何实际的SHA1冲突对任意消息已知？

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

进行一些Google搜索只会引发这么突出的MD5/SHA0碰撞和一些创建SHA1碰撞的提示，但我无法举出任何示例。

Answer 1

第一个已知的冲突现在已经在https://shattered.it/

Answer 2

在2005年，Wang，Yin和Yu的论文Collision Search Attacks on SHA1中有一个例子，但仅仅是为了削弱58轮版本的SHA-1。 （完整的，官方的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. 

Answer 3

由于2017年2月23日的这个答案已经不再准确。

For more than six years, the SHA1 cryptographic hash function underpinning Internet security has been at death's door. Now it's officially dead, thanks to the submission of the first known instance of a fatal exploit known as a "collision."

没有为SHA-1没有已知的碰撞呢。现在：

• 上有减少版本的SHA-1的一些冲突，用了不到80个回合标准SHA-1。
• 已经描述了一种算法，其中应该通过计算努力获得SHA-1冲突，其计算量大致等于在小消息上调用SHA-1;这比通用算法（平均需要调用2 ）好得多，但仍然相当大，算法尚未运行。

有努力获得通过利用来自谁能有一些空闲的CPU时钟周期捐功率，与BOINC框架来组织整个事情SHA-1碰撞，但没有足够的志愿者和工作去年被放弃。因此没有实际的SHA-1冲突。

理论攻击依赖于一些可能被证明略有错误的假设;例如，对MD5的攻击实际上比预期的要快一些（在某些时候有一个必须满足的特性，其理论概率为2 ^-28，但实际上它更像是2 ^-27.7 ，即攻击速度比预测快20％）。仍然认为理论上的攻击是正确的，复杂性“相当准确”。

Answer 4

谷歌的安全博客描述了第一次公开，故意SHA-1碰撞的位置： https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html

直接链接到2个PDF文件具有相同SHA-1（从site dedicated to this finding）：

• https://shattered.it/static/shattered-1.pdf
• https://shattered.it/static/shattered-2.pdf

再次，马克史蒂文斯与CWI阿姆斯特丹和一些Google员工一起参与其中，但这次是为了在两个构建的PDF上进行全面的SHA-1。

Stevens also notes由于SHA-1的Merkle-Damgård construction，这两个PDF都可以用相同的任意数据扩展（附加），以生成更长版本散列到同一个摘要。

谷歌显然会在90天后（2017年2月23日）发布随附的源代码，为受影响的系统供应商提供一些时间来更新其内容。

GitHub等软件和GitHub等服务提供商将如何处理这个问题，特别是在向后兼容性方面还有待观察。

Linus Torvalds有issued a statement regarding git，并指出他们将以兼容的方式迁移到更新的哈希，但这需要时间。

顺便说一句，在“破灭”碰撞演示不影响git的（修改），因为它使用SHA-1这样的：

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

你可以得到使用git hash-object <file path>，即使git的哈希该文件不在git中。

在related news, Subversion seems to be the first real victim这个证明，导致存储库损坏，从而使所提到的文件的实际利用。

- 以前... -

一个76-round collision被Marc Stevens发现。

密码学家让 - 菲利普Aumasson，的BLAKE和SipHash和Password Hashing Competition (PHC)的引发剂共同创作，猜测上满80发will have been found by 2020的SHA-1碰撞。

据ongoing research by Marc Stevens et al. published in October 2015，

...我们估计SHA-1碰撞花费今天 75K $ 120K和$在租用亚马逊EC2云计算之间（即2015年秋季）几个月。 相比之下，安全专家布鲁斯之前预测的 SHA-1碰撞成本为〜173K $ 2018年

他们还描述了SHA-1的压缩功能的碰撞攻击。

Answer 5

不完全是SHA1冲突， 但存在冲突PBKDF2-HMAC-SHA1消息摘要认证码。

例如，PBKDF2两个密码plnlrtfpijpuhqylxbgqiiyipieyxvfsavzgxbbcfusqkozwpngsyejqlmjsytrmd和eBkXQTfuBqp\'cTcar&g*，盐hunter2，4迭代，（对于为dkLen 2035d1c8f259129dc800ec8e073bb68f995424619c）提供相同的值（SHA1，密码，盐，迭代为dkLen）。

事实上，找到长于64字节的字符串的这种冲突是微不足道的。

另一个碰撞的例子（Python3）：

>>> import hashlib, binascii 
>>> def pbkdf2sha1hex(x, salt, iters): 
...  h = hashlib.pbkdf2_hmac('sha1', x, salt, iters) 
...  return binascii.hexlify(h) 
>>> pbkdf2sha1hex(b'http://stackoverflow.com/questions/3475648/sha1-collision-demo-example/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'http://stackoverflow.com/questions/3475648/sha1-collision-demo-example/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