针对SHA-1的选择前缀碰撞攻击

SHA-1（Secure Hash Algorithm 1，安全散列算法1）是一种密码散列函数，由美国国家安全局设计，并由美国国家标准技术研究所（NIST）发布为联邦数据处理标准（FIPS）。SHA-1可以生成一个被称为消息摘要的160位（20字节）散列值，散列值通常的呈现形式为40位的十六进制数。

来自法国Inria和新加坡南洋理工大学的的研究人员研究发现了首个针对SHA-1的选择前缀碰撞，这也是一种对SHA-1哈希函数的完整和现实攻击，同时也会PGP/GnuPG伪装攻击的现实安全带来巨大威胁。

选择前缀碰撞

对哈希函数H来说经典的选择前缀碰撞就是两个不同的消息M和M’计算得到的哈希值相同：H(M) = H(M’)。虽然这在密码学中是一个基本的安全假设，但利用经典碰撞攻击发起攻击在实践中是非常困难的。

选择前缀碰撞是一种受限的碰撞类型，给定攻击者两个消息前缀P和P’，攻击者的目标就是计算两个消息M和M’，使得H(P || M) = H(P’ || M’)。

因此，攻击者就可以在即使前缀随机选择的情况下获得碰撞。哈希函数是数字签名中常用的方法，因此这种攻击带来的潜在影响很大。

SHA-1使用情况

近年来SHA-1的使用已经明显减少了，尤其是web浏览器已经拒绝用SHA-1签名的证书。但SHA-1签名仍然支持大量的应用。SHA-1是大量GnuPG子系列认证PGP密钥的默认哈希函数。许多非web的TLS客户端也接受SHA-1证书，而且SHA-1在TLS和SSH中的协议内签名也是允许的。虽然实际使用量很少，但由于满足中间人攻击的情况，因此SHA-1会带来很大的潜在安全威胁。而且有很多的专用协议仍然在使用SHA-1，这些是很难评估的。

受影响的用户

研究人员分析发现了一些直接受到选择前缀碰撞的设置，包括：

· 如果第三方生成SHA-1密钥证书时可以伪装PGP密钥

· 如果CA发布了可预测序列号的SHA-1证书，那么X.509证书可能会被攻破

经典碰撞和选择碰撞并不会威胁SHA-1的使用。尤其是HMAC-SHA-1仍然是安全的，SHA-1的抗原像性(pre-image resistance)仍然没有被攻破。

攻击成本

研究人员租用了在线GPU集群，整个SHA-1选择前缀碰撞攻击的成本为7.5万美元。从计算的时间来看，研究人员的实现方式并不是最优的。此外，随着计算资源的价格降低，研究人员估算当前攻击成本为4.5万美元，研究人员预计2025年发起针对SHA-1的选择前缀碰撞攻击的成本不会高于1万美元。

针对SHA-1的攻击

针对SHA-1的碰撞攻击

早在2017年底，就有了针对SHA-1的经典碰撞攻击。但这与选择前缀碰撞是不同的，因为前缀对对碰撞来说是一个挑战，因此在实际应用中会带来更大的安全威胁。

针对SHA-1的选择前缀碰撞攻击

2019年研究人员发布了针对SHA-1的选择前缀碰撞攻击，成果（From Collisions to Chosen-Prefix Collisions - Application to Full SHA-1）发布了Eurocrypt 2019大会上，具体参见https://eprint.iacr.org/2019/459.pdf。

选择前缀攻击实例

研究人员创建了前缀为99040d047fe81780012000和 99030d047fe81780011800（十六进制）的选择前缀碰撞。

更多参见https://sha-mbles.github.io

建议

研究人员建议用户尽可能地移除产品中的SHA-1，并使用SHA-256或SHA-3来替代。SHA-1已经被攻破15年了，因此没有理由再在现在的安全产品中再使用SHA-1哈希函数。