sha2编年史

安全散列算法编年史

了解数字摘要的本质

         现在我们假设这么一个情况，如果有个游戏客户端有20G大小，文件上传下载的大小有限制，所以分开为8段5G的来下载，下载完了之后，安装过程中提示安装出错。于是问题来了，要重新把8段下下来呢，还是单独下在出错的。结果显然是只要下载出错的那段就可以了，但是如何来判断这哪段没下载完整呢。这里就可以用数字摘要来解决这个问题，官方可以用一种指定的方法，把5G的大小的数据，通过某种方法得到一串较短的数据，这段新数据的特点包括：新数据较短，易读取识别；原数据任意修改都使其有巨大变化，原数据推得新数据，反之不行；新数据不容易产生相同的。这样，安装发生错误时，可以通过相同的方法来分别演算这8段大数据，再把演算得到的小数据和官方通过演算给出的小数据进行比较，如果一致的话，则说明这段大数据是完整的，无需重新下载；而不一致，则就是我到的不完整文件。

         上文中通过原数据生成小数据的方法就是数字摘要算法。

         摘要算法是一种能计算出一个数字消息所对应到的，长度固定的字符串的算法。它们对应到不同字符串的机率很高。摘要算法有很多，md数字摘要，sha安全算列等。其中SHA是FIPS所认证的五种安全散列算法。这些算法之所以称作“安全”是基于以下两点（根据官方标准的描述）：

l  由消息摘要反推原输入消息，从计算理论上来说是很困难的。

l  想要找到两组不同的消息对应到相同的消息摘要，从计算理论上来说也是很困难的。任何对输入消息的变动，都有很高的机率导致其产生的消息摘要迥异。

SHA家族成员

         SHA家族的五个算法，分别是SHA-1、SHA-224、SHA-256、SHA-384，和SHA-512，由美国国家安全局（NSA）所设计，并由美国国家标准与技术研究院（NIST）发布；是美国的政府标准。后四者有时并称为SHA-2。SHA-1在许多安全协议中广为使用，包括TLS和SSL、PGP、SSH、S/MIME和IPsec，曾被视为是MD5（更早之前被广为使用的散列函数）的后继者。但SHA-1的安全性如今被密码学家严重质疑；虽然至今尚未出现对SHA-2有效的攻击，它的算法跟SHA-1基本上仍然相似；因此有些人开始发展其他替代的散列算法。缘于最近对SHA-1的种种攻击发表，“美国国家标准与技术研究院（NIST）开始设法经由公开竞争管道（类似高级加密标准AES的发展经过），发展一个或多个新的散列算法。”

         2012年10月2日，Keccak被选为NIST散列函数竞赛的胜利者,成为SHA-3。 SHA-3并不是要取代SHA-2，因为SHA-2目前并没有出现明显的弱点。由于对MD5出现成功的破解，以及对SHA-0和SHA-1出现理论上破解的方法，NIST感觉需要一个与之前算法不同的，可替换的加密散列算法，也就是现在的SHA-3。设计者宣称在Intel Core 2的CPU上面，此算法的性能是12.5cpb（每字节周期数，cycles per byte）。不过，在硬件实做上面，这个算法比起其他算法明显的快上很多。

SHA-0与SHA-1

          最初载明的算法于1993年发布，称做安全散列标准（Secure Hash Standard），FIPS PUB 180。这个版本现在常被称为SHA-0。它在发布之后很快就被NSA撤回，并且由1995年发布的修订版本FIPS PUB 180-1（通常称为SHA-1）取代。SHA-1和SHA-0的算法只在压缩函数的消息转换部份差了一个比特的循环位移。根据NSA的说法，它修正了一个在原始算法中会降低散列安全性的弱点。然而NSA并没有提供任何进一步的解释或证明该弱点已被修正。而后SHA-0和SHA-1的弱点相继被攻破，SHA-1似乎是显得比SHA-0有抵抗性，这多少证实了NSA当初修正算法以增进安全性的声明。

           SHA-0和SHA-1可将一个最大2^64比特的消息，转换成一串160位的消息摘要；其设计原理相似于MIT教授Ronald L. Rivest所设计的密码学散列算法MD4和MD5。

SHA-0的破解

         在CRYPTO 98上，两位法国研究者提出一种对SHA-0的攻击方式：在2^61的计算复杂度之内，就可以发现一次碰撞（即两个不同的消息对应到相同的消息摘要）；这个数字小于生日攻击法所需的2^80，也就是说，存在一种算法，使其安全性不到一个理想的散列函数抵抗攻击所应具备的计算复杂度。

         2004年时，Biham和Chen也发现了SHA-0的近似碰撞，也就是两个消息可以散列出几乎相同的数值；其中162比特中有142比特相同。他们也发现了SHA-0的完整碰撞（相对于近似碰撞），将本来需要80次方的复杂度降低到62次方。

          2004年8月12日，Joux, Carribault, Lemuet和Jalby宣布找到SHA-0算法的完整碰撞的方法，这是归纳Chabaud和Joux的攻击所完成的结果。发现一个完整碰撞只需要2^51的计算复杂度。他们使用的是一台有256颗Itanium2处理器的超级电脑，约耗80,000 CPU工时。

          2004年8月17日，在CRYPTO 2004的Rump会议上，王小云，冯登国（Feng）、来学嘉（Lai），和于红波（Yu）宣布了攻击MD5、SHA-0和其他散列函数的初步结果。他们攻击SHA-0的计算复杂度是2^40，这意谓的他们的攻击成果比Joux还有其他人所做的更好。请参见MD5安全性。2005年二月，王小云和殷益群、于红波再度发表了对SHA-0破密的算法，可在2^39的计算复杂度内就找到碰撞。

SHA-1的破解

           鉴于SHA-0的破密成果，专家们建议那些计划利用SHA-1实现密码系统的人们也应重新考虑。在2004年CRYPTO会议结果公布之后，NIST即宣布他们将逐渐减少使用SHA-1，改以SHA-2取而代之。

           2005年，Rijmen和Oswald发表了对SHA-1较弱版本（53次的加密循环而非80次）的攻击：在2^80的计算复杂度之内找到碰撞。

           2005年二月，王小云、殷益群及于红波发表了对完整版SHA-1的攻击，只需少于2^69的计算复杂度，就能找到一组碰撞。（利用生日攻击法找到碰撞需要2^80的计算复杂度。）

           这篇论文的作者们写道；“我们的破密分析是以对付SHA-0的差分攻击、近似碰撞、多区块碰撞技术、以及从MD5算法中查找碰撞的消息更改技术为基础。没有这些强力的分析工具，SHA-1就无法破解。”此外，作者还展示了一次对58次加密循环SHA-1的破密，在2^33个单位操作内就找到一组碰撞。完整攻击方法的论文发表在2005年八月的CRYPTO会议中。

            殷益群在一次面谈中如此陈述：“大致上来说，我们找到了两个弱点：其一是前置处理不够复杂；其二是前20个循环中的某些数学运算会造成不可预期的安全性问题。”

            2005年8月17日的CRYPTO会议尾声中王小云、姚期智、姚储枫再度发表更有效率的SHA-1攻击法，能在2^63个计算复杂度内找到碰撞。

            2006年的CRYPTO会议上，Christian Rechberger和Christophe De Cannière宣布他们能在容许攻击者决定部分原消息的条件之下，找到SHA-1的一个碰撞。

            在密码学的学术理论中，任何攻击方式，其计算复杂度若少于暴力搜索法所需要的计算复杂度，就能被视为针对该密码系统的一种破密法；但这并不表示该破密法已经可以进入实际应用的阶段。

           就应用层面的考量而言，一种新的破密法出现，暗示着将来可能会出现更有效率、足以实用的改良版本。虽然这些实用的破密法版本根本还没诞生，但确有必要发展更强的散列算法来取代旧的算法。在“碰撞”攻击法之外，另有一种反译攻击法（Pre-image attack），就是由散列出的字符串反推原本的消息；反译攻击的严重性更在碰撞攻击之上，但也更困难。在许多会应用到密码散列的情境（如用户密码的存放、文件的数字签章等）中，碰撞攻击的影响并不是很大。举例来说，一个攻击者可能不会只想要伪造一份一模一样的文件，而会想改造原来的文件，再附上合法的签章，来愚弄持有私密密钥的验证者。另一方面，如果可以从密文中反推未加密前的用户密码，攻击者就能利用得到的密码登录其他用户的账户，而这种事在密码系统中是不能被允许的。但若存在反译攻击，只要能得到指定用户密码散列过后的字符串（通常存在影文件中，而且可能不会透露原密码信息），就有可能得到该用户的密码。

SHA2步入视野

            NIST发布了三个额外的SHA变体，这三个函数都将消息对应到更长的消息摘要。以它们的摘要长度（以比特计算）加在原名后面来命名：SHA-256，SHA-384和SHA-512。它们发布于2001年的FIPS PUB 180-2草稿中，随即通过审查和评论。包含SHA-1的FIPS PUB 180-2，于2002年以官方标准发布。2004年2月，发布了一次FIPS PUB 180-2的变更通知，加入了一个额外的变种SHA-224"，这是为了符合双密钥3DES所需的密钥长度而定义。

           SHA-256和SHA-512是很新的散列函数，前者以定义一个word为32位，后者则定义一个word为64位。它们分别使用了不同的偏移量，或用不同的常数，然而，实际上二者结构是相同的，只在循环运行的次数上有所差异。SHA-224以及SHA-384则是前述二种散列函数的截短版，利用不同的初始值做计算。

           这些新的散列函数并没有接受像SHA-1一样的公众密码社区做详细的检验，所以它们的密码安全性还不被大家广泛的信任。Gilbert和Handschuh在2003年曾对这些新变种作过一些研究，声称他们没有找到弱点。

SHA所定义的长度

下面是sha一些相关参数。

SHA-1的攻击的代价

            在2005年，密码学家证明SHA-1的破解速度比预期提高了2000倍。但是破解仍然是极其困难和昂贵的。但是随着计算机变得越来越快和越来越廉价，在互联网上停止使用SHA-1算法只是时间的问题。

           后来，互联网继续使用SHA-1。在2012年，Jesse Walker写了一份评估报告，关于伪造一个SHA-1证书所花费的成本。该评估参照亚马逊Web服务的价格和摩尔定律。

           当时沃克预计一个SHA-1的碰撞在2012年需花费2,000,000美元，在2015年需花费700,000美元，在2018年需花费173,000美元，在2021年需花费43,000美元。基于这些数字，施奈尔暗示到2018年就会有犯罪集团能够伪造证书，到2021年就会有科研院校具备这种能力。

            在有关更替SHA-1的规划和争论中，沃克的评估和施奈尔的推断被广泛的引用。一个由主流CA组成的组织：CA安全理事会（CA Security Council），近来使用沃克和施奈尔的结论来抱怨谷歌的时间表。CA把评估结果当作反驳的利器，认为 “等到2018年这种攻击才会实际出现”。