SHA-1“SHAttered”的新攻擊是什麼，它是如何工作的？
Google和一些研究人員最近對 SHA-1 發起了一種新的攻擊，名為“SHAttered”。我知道它使用了一些花哨的新技術，但不是細節。
我的問題是：如何？
攻擊是如何工作的（在高層次上）？與之前的攻擊相比如何？
注意：這個問題已經解決了這個問題，所以請不要關注它。
為了在 a 上發生碰撞 $ n $ bit Random Oracle 使用生日悖論，需要 $ \sqrt{\pi / 2} \cdot 2^{n/2} $ 來電。換句話說，在 SHA-1 的 160 個輸出位的情況下，限制為 $ 2^{160/2} = 2^{80} $ .
以前的攻擊
SHA-1（和損壞的 SHA-0）在過去幾年中一直受到以下攻擊：
- Chabaud F., Joux A. 在 SHA-0 中的差異衝突在 SHA-0中存在衝突 $ 2^{61} $ 來電。
- Biham E., Chen R. 在 CRYPTO 2004上的 SHA-0 中的接近碰撞
- SHA-0 和 Round 的碰撞減少了 SHA-1，作者 Biham E.、Chen R.、Joux A.、Carribault P.、Lemuet C.、Jalby W. 在 EUROCRYPT 2005
- Wang 等人在完整的 SHA-1 中查找碰撞。在 CRYPTO 2005
- Pierre Karpman、Thomas Peyrin 和 Marc Stevens 在 CRYPTO 2015上對 76 步 SHA-1 的實用自由啟動碰撞攻擊
- 新的 SHA-1 碰撞攻擊基於Stevens M. 在 EUROCRYPT 2013上的最優聯合局部碰撞分析
第 4 篇論文提出了一種攻擊 $ 2^{69} $ 呼叫顯示 SHA-1 的弱點。第 6 篇論文將是 SHAttered 攻擊的基礎工作。
這些攻擊背後的主要思想依賴於差分密碼分析。你有兩個輸入 $ t_0 $ 和 $ t’_0 $ 有區別 $ \Delta_0 $ . 一旦這兩個輸入通過函式 $ f $ （SHA-1情況下的壓縮函式）你會有所不同 $ \Delta_1 $ 等等（見下圖）…
這裡的目標是找到輸入的差異 $ \Delta_0 $ 這樣經過一些迭代後你得到 $ \Delta_2 = 0 $ ，也就是說沒有區別。
破碎的攻擊
由於 SHA-1 的 Merkle-Damgård 構造，可以選擇更改迭代之間的差異，以改進差異以滿足他的需要。在 SHAttered Attack 的情況下，他們選擇了一個初始前綴 ( $ P $ ），然後在接下來的塊中，他們引入了差異（ $ M^{(1)}_1 $ , $ M^{(2)}_1 $ ) 並刪除它 ( $ M^{(1)}_2 $ 和 $ M^{(2)}_2 $ ）。此時他們已經發生了碰撞。他們只需要繼續執行相同的以下塊（ $ S $ )，導致整個輸入發生衝突。
$ \mathrm{SHA-1}(P||M^{(1)}_1\mathbin\Vert M^{(1)}_2\mathbin\Vert S)=\mathrm{SHA-1}(P||M^{(2)}_1\mathbin\Vert M^{(2)}_2\mathbin\Vert S) $
的價值觀 $ M^{(1)}_1 $ , $ M^{(2)}_1 $ , $ M^{(1)}_2 $ 和 $ M^{(2)}_2 $ 如下面所述：
因此，困難在於找到正確的 $ M_i $ 滿足所選前綴標準的 $ P $ 然後很好地取消自己。這種情況發生的機率非常小，因此需要大量呼叫 SHA-1 壓縮函式 ( $ 2^{63.1} $ ).
對於提供的 PDF，他們還提供了一個很好的資訊圖，解釋了 PDF 中的差異所在：
