|
发表于 2007-9-13 02:23:52
|
显示全部楼层
刚刚上了wiki,查了一下,就贴出来吧~~~
SHA-0 的破解
在 CRYPTO 98 上,两位法国研究者提出一种对 SHA-0 的攻击方式 (Chabaud and Joux, 1998): 在 261的计算复杂度之内,就可以发现一次碰撞(即两个不同的讯息对应到相同的讯息摘要);这个数字小于 280 ,也就是说,其安全性不到一个理想的杂凑函数抵抗攻击所应具备的计算复杂度。
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 工时 [1]。
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 年八月 17 的 CRYPTO 会议尾声中王小云、姚期智、姚储枫再度发表更有效率的 SHA-1 攻击法,能在 2^63 个计算复杂度内找到碰撞。
在密码学的学术理论中,任何攻击方式,其计算复杂度若少于暴力搜寻法所需要的计算复杂度,就能被视为针对该密码系统的一种破密法;这并不表示该破密法已经可以进入实际应用的阶段。
就应用层面的考量而言,一种新的破密法出现,暗示著将来可能会出现更有效率、足以实用的改良版本。虽然这些实用的破密法版本根本还没诞生,但确有必要发展更强的杂凑算法来取代旧的算法。在“碰撞”攻击法之外,另有一种反译攻击法,就是由杂凑出的字串反推原本的讯息;反译攻击的严重性更在碰撞攻击之上。 在许多会应用到密码杂凑的情境(如用户密码的存放、文件的数位签章等)中,碰撞攻击的影响并不是很大。举例来说,一个攻击者可能不会只想要伪造一份一模一样的文件,而会想改造原来的文件,再附上合法的签章,来愚弄持有私密金钥的验证者。另一方面,如果可以从密文中反推未加密前的使用者密码,攻击者就能利用得到的密码登入其他使用者的帐户,而这种事在密码系统中是不能被允许的。但若存在反译攻击,只要能得到指定使用者密码杂凑过后的字串(通常存在影档中,而且可能不会透露原密码资讯),就有可能得到该使用者的密码。
2006 年的 CRYPTO 会议上,Christian Rechberger 和 Christophe De Cannière 宣布他们能在容许攻击者决定部分原讯息的条件之下,找到 SHA-1 的一个碰撞。
http://zh.wikipedia.org/w/index.php?title=SHA-1&variant=zh-cn
[ 本帖最后由 fwjmath 于 2007-9-13 13:40 编辑 ] |
|