SHA-1 器件的安全性是否依然足够安全？

　　近来，几名中国学者对安全散列算法(SHA)的强大安全性做出了攻击。本白皮书将讨论这种攻击方式，其结果表明：尽管比起最初的想法, SHA-1 算法在抗碰撞上略有不足，但Dallas Semiconductor/Maxim 的SHA-1 存储器件的安全性并未受到影响。因此，该公司的SHA-1 存储器件(DS1963S、DS1961S、DS2432) 仍可以为附件/外设鉴别及防窜改、存储器认证应用提供低成本、有效的解决方案。
引言

　　Dallas Semiconductor/Maxim 的SHA-1 存储器件将为附件/外设鉴别及防窜改、存储器认证应用提供低成本、高效的解决方案。这些SHA-1 存储器件具有可鉴别特性，特别适合那些要求防范造假的应用，如大批量消耗品、高附加值硬件、硬件许可管理、楼宇进出控制或自动售货机。

　　从根本上讲，这些设备的实用性取决于安全散列算法的坚固性和安全性，这一算法是由美国国家标准技术研究所(NIST 在联邦信息处理标准180-1 (FIPS PUB 180-1) 及ISO/IEC 10118-3 中定义的。近来，几位中国学者攻击了这种算法(见注释一)。本文指出，尽管某些采用SHA-1 算法的应用其安全性有待重新评估，但Dallas Semiconductor/Maxim 的SHA-1 存储器件的安全性不会受这一研究声明的影响。

针对SHA-1 摘要码的攻击

　　FIPS PUB 180-1 标准中规定：SHA-1 能够以安全的方式将数据计算压缩成一段特定的信息。如文档资料中所定义，SHA-1 算法的安全性有两层含义：(1) 由一个给定的信息摘要不可能通过计算导出信息源；(2) 要找到两条不同的信息使之产生相同的摘要在计算上是不可行的。第一条推论表明，由SHA-1 算法所得出的结果并不包含足够的信息，不足以由此推出算法输入中的全部文本信息(也就是说，该算法是不可逆的)；还包括如果仅仅知道摘要(输出)的话，找出对应的原文信息(输入)需要耗费大量的资源和时间。第二条推论表明，发现两个计算结果相同的独一无二的输入信息需要耗费大量的资源和时间(也就是说，该算法具有抗冲撞性)。上述假定并不表明不存在两条摘要相同的信息，只是很难找到而已。

　　从理论上来说，发现一次碰撞(摘要相同的两条信息)最多需要进行280 杂散运算(参见注释2)。学者们近来对于SHA-1 的攻击表明：这一数字已经减小到只需269 次运算。这一新发现削弱了上文关于SHA-1 的第二条结论，因为它有效地将这种“计算上的不可行性”减小了211 级。但这并不意味着“发现信息摘要相同的两条不同的信息”在计算上是可行的，只是相对先前的技术来说稍微易于实现而已。而且，研究人员的此次发现也并不意味着“由一个给定摘要反推出生成摘要的原始信息”在计算上是可行的，因为这次新的攻击是建立在小心仔细地选择两个输入信息基础上的。唯一证明攻击SHA-1 的方法是找到对应于某个给定摘要的一条信息，而没有必要就是原始信息，如果要推出该原始信息，需要采用穷举法进行2160 次搜索运算。

　　虽然有关SHA-1 算法的第二条结论的权威性由于中国学者的研究而被削弱，但没理由怀疑该研究会对SHA-1 的第一条结论产生任何的影响。因此总的来说，SHA-1 仍然是不可逆的，只是或许在碰撞上略有不足。尽管如此，对于那些依赖于数字签名的应用领域(如时间标注的或公证文档来说，此项研究成果仍不失为一记警钟。由于对于应用来说，输入数据中的许多信息是相互关联的，因此，出自中国学者、针对特定应用的攻击是否有效还有待观察。

信息认定码

　　Dallas Semiconductor/Maxim 的SHA-1 存储器件安全性依赖于双向数据通信中的信息认证码(MAC)。计算MAC 仅需要输入公开的字符串(由存储器内容、器件的唯一序列号和随机质询码等组成)，和结合密码字结合在一起，进行SHA-1 运算。以及一个作为SHA-1 算法输入信息的机密密钥。计算出的摘要(或散列)被称为MAC。将MAC 连同信息一起传输，提供了一种安全的方法，验证你是否知道密钥，以及在传输过程中数据未被篡改。在读操作期间，SHA-1 存储器件以MAC 响应，据此验证其是真实可信的，以及主机正确地接收数据。在写操作期间，主机提供MAC，以验证它有权对器件的存储内容进行修改和器件正确地接收到新存储器内容。

　　对基于MAC 的安全系统算法的成功攻击是要找出密钥。对大多数现有的SHA-1 存储器件来说，其密钥长度为64 位，仅能写入(不久将推出新型的、更长的密钥长度器件)。攻击者向器件发出质询码，读入器件生成的MAC 码，接着对全部64 位数执行一次穷举搜索，直到发现相匹配的MAC 码。这一过程需要进行264 次SHA-1 运算，一台64 CPU Cray X1 超级计算机需要花费十多年时间才能计算出(参见注释3)。

　　找到一条与给定摘要相匹配的信息源，需要2160 次运算(远超过找出密钥所需的264 次运算)。由于输入信息的长度被固定为512 位，并且其中448 位是已知的公开数据，因此最直接的方法是寻找剩下64 位的正确值(即密钥)。只要由一个给定的摘要不能反推出生成摘要的原始信息"，那么就不存在比穷举法搜索密钥更成功的攻击方法。

　　注意：尽管为找出机密密钥所进行的264 次运算其复杂程度要小于为发现一对信息发生碰撞需要的269 次运算，但两种攻击方式之间没有可比性。如果研究人员找到一种在250 次运算之内发现SHA-1 碰撞，但仍然需要经过264 次SHA-1 运算才能找到密钥。因此，此次新的攻击虽然在任意两条输入信息之间找到碰撞的新攻击方法，并不能用于为一个确定的输入信息找到碰撞，这是因为需要仔细地选择输入信息。

结束语

　　已有文献记载了对采用SHA-1 存储器件的系统的攻击(参见Whitepaper 3: Why are SHA-1 Devices Secure?)。但是，利用公开可读的MAC 发现被隐藏的密钥是人们所知的唯一攻击方法。就SHA-1 而言，我们知道所定义的SHA-1 算法具有两点安全性：防碰撞和不可逆性。最近的攻击只表明：SHA-1 算法的防碰撞比以前略有下降，但这种攻击不会影响Dallas Semiconductor/Maxim 的SHA-1 存储器件的安全性。

注释:

1. Collision Search Attack on SHA-1 (PDF)

2. 遵循"生日悖论(birthday paradox）”，发现SHA-1 中的一次碰撞最多需要280 次运算。这一观点说明，基本上，如果试图匹配任意两个n 位的输出元数，只须考虑2(n/2)个元数，而并非2(n)个元数，找到匹配的可能性极高。众所周知，所有hash 函数都具有加密特性，该特性仅由输出数据的位数决定。

3. SHA-1 算法在信息单元块之间大约需要进行1740 次基本的算术运算。假定其它操作还需20%的额外开销，完全执行一次算法需2100 个时钟周期。若使用一台含64 位CPU 的Cray X1 超级计算机(目前最大规模的Cray 计算机，单机柜结构)，发挥其每秒819 亿次浮点操作的峰值计算能力，需要连续工作12.4 年才能生成一张完整的查找表。若采用广告中宣称的运算能力最强的Cray X1 型超级计算机(带64 只机柜)，也需耗时两个月。如此巨大的计算量使得此类攻击所需花费的成本高而却步。