SHA-0破解

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

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

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

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

SHA-1破解破密成果

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

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

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

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

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