SHA-0破解

在CRYPTO 98上，兩位法國(guó)研究者提出一種對(duì)SHA-0的攻擊方式：在261的計(jì)算復(fù)雜度之內(nèi)，就可以發(fā)現(xiàn)一次碰撞(即兩個(gè)不同的訊息對(duì)應(yīng)到相同的訊息摘要);這個(gè)數(shù)字小于生日攻擊法所需的2的80次方，也就是說(shuō)，存在一種算法，使其安全性不到一個(gè)理想的雜湊函數(shù)抵抗攻擊所應(yīng)具備的計(jì)算復(fù)雜度。

2004年時(shí)，Biham和 Chen也發(fā)現(xiàn)了SHA-0的近似碰撞，也就是兩個(gè)訊息可以雜湊出幾乎相同的數(shù)值;其中162位元中有142位元相同。他們也發(fā)現(xiàn)了SHA-0的完整碰撞(相對(duì)于近似碰撞)，將本來(lái)需要80次方的復(fù)雜度降低到62次方。

2004年8月12日，Joux, Carribault, Lemuet和Jalby宣布找到SHA-0算法的完整碰撞的方法，這是歸納Chabaud和Joux的攻擊所完成的結(jié)果。發(fā)現(xiàn)一個(gè)完整碰撞只需要251的計(jì)算復(fù)雜度。他們使用的是一臺(tái)有256顆Itanium2處理器的超級(jí)電腦，約耗80,000 CPU工時(shí)。

2004年8月17日，在CRYPTO 2004的Rump會(huì)議上，王小云，馮登國(guó)、來(lái)學(xué)嘉，和于紅波宣布了攻擊MD5、SHA-0 和其他雜湊函數(shù)的初步結(jié)果。他們攻擊SHA-0的計(jì)算復(fù)雜度是2的40次方，這意味著他們的攻擊成果比Joux還有其他人所做的更好。請(qǐng)參見(jiàn)MD5 安全性。2005年二月，王小云和殷益群、于紅波再度發(fā)表了對(duì)SHA-0破密的算法，可在2的39次方的計(jì)算復(fù)雜度內(nèi)就找到碰撞。

SHA-1破解破密成果

鑒于SHA-0的破密成果，專(zhuān)家們建議那些計(jì)劃利用SHA-1實(shí)作密碼系統(tǒng)的人們也應(yīng)重新考慮。在2004年CRYPTO會(huì)議結(jié)果公布之后，NIST即宣布他們將逐漸減少使用SHA-1，改以SHA-2取而代之。

2005年，Rijmen和Oswald發(fā)表了對(duì)SHA-1較弱版本(53次的加密循環(huán)而非80次)的攻擊：在2的80次方的計(jì)算復(fù)雜度之內(nèi)找到碰撞。

2005年二月，王小云、殷益群及于紅波發(fā)表了對(duì)完整版SHA-1的攻擊，只需少于2的69次方的計(jì)算復(fù)雜度，就能找到一組碰撞。(利用生日攻擊法找到碰撞需要2的80次方的計(jì)算復(fù)雜度。)

這篇論文的作者們寫(xiě)道;“我們的破密分析是以對(duì)付SHA-0的差分攻擊、近似碰撞、多區(qū)塊碰撞技術(shù)、以及從MD5算法中尋找碰撞的訊息更改技術(shù)為基礎(chǔ)。沒(méi)有這些強(qiáng)力的分析工具，SHA-1就無(wú)法破解。”此外，作者還展示了一次對(duì)58次加密循環(huán)SHA-1的破密，在2的33次方個(gè)單位操作內(nèi)就找到一組碰撞。完整攻擊方法的論文發(fā)表在2005年八月的CRYPTO會(huì)議中。

殷益群在一次面談中如此陳述：“大致上來(lái)說(shuō)，我們找到了兩個(gè)弱點(diǎn)：其一是前置處理不夠復(fù)雜;其二是前20個(gè)循環(huán)中的某些數(shù)學(xué)運(yùn)算會(huì)造成不可預(yù)期的安全性問(wèn)題。”