SHA-1 衝突——實際攻擊呢？

我理解雜湊衝突的理論問題，但在實踐中，我感到非常困惑。

假設攻擊者想使用雜湊衝突偽造證書（或任何類型的結構化文件），我想知道如何找到衝突（已經不太可能），而且，這種衝突是從相關的結構化輸入中“找到”的字節（日期、通用名稱、dns 攻擊者）。

這對我來說聽起來很奇怪，我無法理解如何找到有助於攻擊的雜湊衝突，我只能考慮可以生成相同雜湊的隨機原始字節，但它不會被解析（例如：攻擊者發現 x509 證書雜湊衝突，但 x509 惡意內容是瀏覽器無法理解的隨機字節）。

該問題詢問諸如 SHA-1 之類的散列中的衝突如何成為實際問題，重點是 X.509 等公鑰證書的情況。

---

我將首先給出一個涉及可執行程式碼簽名的範例。我將假設攻擊者能夠編寫引導程式碼（例如，開發工具鏈的供應商，或破壞該工具鏈的人），並且有足夠的資源來執行一次攻擊，在 SHA 上找到兩條不同的 128 字節衝突消息- 1 有一個小的變化：（任意）160 位初始化值的值。後者是可能的

• 通過蠻力與預期的努力小於 $ 2^{81} $ 使用Paul C. van Oorschot和 Michael J. Wiener 的Parallel Collision Search with Cryptanalytic Applications（密碼學雜誌，1999 年 1 月，第 12 卷，第 1 期；免費稍早的版本可從第一作者的網站獲得）；

• 或者使用複雜的專門方法利用 SHA-1 壓縮功能的弱點以更少的努力，估計的努力相當於

  • $ 2^{69} $ hashes, per Xiaoyun Wang, Yiqun Lisa Yin, Hongbo Yu: Finding Collisions in the Full SHA-1 , in proccedings of Crypto 2005),
  • $ 2^{63} $ 雜湊，作者 Xiaoyun Wang、Andrew C Yao、Frances Yao：SHA-1 密碼分析，Crypto 2005 的臀部會議；另見 Martin Cochran：關於 Wang 等人的註釋。 $ 2^{63} $ SHA-1 差分路徑，在 IACR eprint 檔案中，2007），
  • $ 2^{61} $ 雜湊，根據 Marc Stevens：基於最佳聯合局部碰撞分析的 SHA-1 新碰撞攻擊（在 Eurocrypt 2013 的會議記錄中，也可從作者的網站免費獲得）。

假設一個執行檔格式包括

1. : 4 字節魔法值 0x4D6F4546 (我自己的可執行格式)
2. : 4 字節長度的引導程式碼，允許定位第 4 節
3. : 入口點位於偏移量 8 的引導程式碼
4. : 第 5 節的 4 字節長度，允許定位簽名
5. ： （任何事物）
6. ：1-2-3-4-5 的 SHA-1 雜湊的 PKCS#1v2 RSA-4096 簽名。

攻擊者編寫或修改引導程式碼 3，以便執行檔

1. : 4 字節魔法值 0x4D6F4546 (我自己的可執行格式)

2. : 4 字節長度的引導程式碼，允許定位第 4 節

3. : 入口點位於偏移量 8 的引導程式碼

4. ：獲取值的程式碼 $ k $ 從 3.4 節，然後根據 if 跳轉到 3.6 節或 3.5 節 $ k^\text{th} $ 第 3.3 節的位是 0 或 1

5. : 填充數據，以便 3.3 對齊到 64 字節邊界

6. ：128字節數據塊

7. : 4 字節 $ k<1024 $ 使得第 3.3 節的兩個值在 $ k^\text{th} $ 少量

8. : 執行攻擊者想要執行的任何程式碼

9. ：執行引導程序應該執行的任何程式碼

10. : 第 5 節的 4 字節長度，允許定位簽名

11. ： （任何事物）

12. : PKCS#1v2 RSA-2048 簽名，使用 1 / 2 / 3 / 4 / 5 的 SHA-1 雜湊。

對手需要

• 開始攻擊時知道1 / 2 / 3.1 / 3.2
• 應用足夠多輪的 SHA-1 以在散列 1 / 2 / 3.1 / 3.2 後推導出 160 位 SHA-1 狀態，從而給出被攻擊的 SHA-1 變體的 160 位初始化值
• 執行本節開頭的代價高昂的攻擊之一
• 找到兩個 128 字節的衝突數據塊，確定位索引 $ k $ 它們不同的地方，並根據 if 標記碰撞塊 A 和 B $ k^\text{th} $ 塊的位是 0 或 1
• 建構引導程式碼 3 的兩個版本 3A 和 3B，不同之處僅在於在第 3.3 節中包含塊 A 或 B；請注意，可以更改 3.5 和 3.6，而無需再次執行代價高昂的攻擊；
• 工廠版本 3A 的 boostrap，按預期執行
• 讓毫無戒心的開發人員使用 bootstrap 3A 創建一個應用程序，並對其進行簽名；
• 取得該簽署的原件；
• 通過將第 3.3 節更改為塊 B 來創建偽造，以便引導程序的版本 3B 就位；
• 利用應用程序開發人員的聲譽，安排在目標機器上使用偽造品。

偽造通過簽名驗證是因為 1 / 2 / 3 / 4 / 5 的 SHA-1 雜湊值未更改，但在啟動時執行第 3.5 節的程式碼執行攻擊者想要執行的任何操作，而簽名的原件沒有執行。

此外，可以使用第 3.4 節的塊作為密鑰來加密第 3.5 節的程式碼，從而無法從引導程序 3A 的知識中分析引導程序 3B 的確切行為。並且第 3.1 節的程式碼可以採用 decipher-then-execute 的形式，這樣意圖就不那麼明顯了。

可以使用一些偽裝成執行檔的“數據”格式來實現類似的技巧；例如，這個技巧已經用postcript 和 MD5拉開了。

---

回到類似 X.509 格式的證書：考慮一個簡化的證書格式

1. : 證書持有者的身份，以 ASCII 格式，44 字節右側用空格填充
2. : 公共模數 $ N $ 2048 位 RSA 密鑰，256 字節 ( big-endian )
3. :（其他證書數據，包括公共指數、屬性..）
4. : PKCS#1v2 RSA-2048 簽名使用 1 / 2 / 3 的 SHA-1 雜湊

和兩個相關的攻擊模型之一

• 攻擊者合法地從誠實的證書頒發機構購買具有她的身份 Alice 和公共模數的證書 $ N_a $ , 修改成具有 Bob 身份和公共模數的證書 $ N_b $ , 並持有私鑰 $ d_a $ 和 $ d_b $ 對應於 $ N_a $ 和 $ N_b $ ( $ d_a $ 是獲得證書所必需的； $ d_b $ 允許 Alice 冒充 Bob）；
• 流氓證書頒發機構故意向 Alice 提供具有 Bob 身份和公共模數的證書 $ N $ 使用 Alice 已知的因式分解（並且可能具有相對容易找到的素因數，使得上述攻擊發生的可能性更大），允許 Alice 冒充 Bob；如果有消息洩露 Alice 使用該機構頒發的證書冒充 Bob，則假裝它已陷入上述攻擊。

注意：根據此處給出的證據，基於 MD5 的 X.509 證書實際上已經發生了接近上述情況之一的情況。這已在 2009 年左右公開描述。

為了實際執行攻擊，Alice

• 搜尋兩個 64 字節數據塊之間的一次 SHA-1 衝突 $ M_a=I_a|J_a $ 和 $ M_b=I_b|J_b $ 前 44 個字節 $ I_a $ 和 $ I_b $ 對應於 Alice 和 Bob 的身份；和其他 20 個字節 $ J_a $ 和 $ J_b $ 任意，除了設置第一位

  • 前面提到的蠻力並行碰撞搜尋允許預期的努力少於 $ 2^{82} $ 散列：迭代的函式可以將一個 160 位的值映射到一個 64 字節的塊，其中包含 Alice 或 Bob 的身份 $ I $ 根據一位；並將其他 159 位映射到 $ J $ ; 當發現碰撞時，有 50% 的機率會在不同身份的 64 字節塊之間，因此可用；
  • 可以想像利用一些專門的方法來利用 SHA-1 壓縮功能中的弱點（特別是前面引用的 Marc Steven 的出版物描述了一種選擇前綴衝突攻擊，其預期努力約為 $ 2^{77.1} $ 雜湊）；

• 找到一個 236 字節的值 $ K $ 以便 $ N_a=J_a|K $ 和 $ N_b=J_b|K $ (big-endian) 是具有已知因式分解、 squarefree和奇數的 2048 位整數（如果需要，使用 $ N_a $ 通過認證機構可能執行的任何其他測試，以及 $ N_b $ 通過任何其他測試，Alice 想要將自己代表為 Bob 的實體可能執行的任何其他測試）；鑑於我們的消息格式，甚至可以（儘管不是必需的）確保兩者 $ N_a $ 和 $ N_b $ 正好有兩個大素數因子：我們可以選擇 $ p_a $ 和 $ p_b $ 900位左右的任意素數，然後系統地構造和探索 $ K $ 這樣 $ p_a $ 劃分 $ N_a $ 和 $ p_b $ 劃分 $ N_b $ , 直到兩者 $ N_a/p_a $ 和 $ N_b/p_b $ 是素數。

• 找到一個公共指數 $ e $ 雙方都可以接受 $ N_a $ 和 $ N_b $ （有一個公平的機會，常見的 $ e=2^{16}+1 $ 會做）併計算PKCS#1中定義的每個 RSA 的私有指數，如 $ d_a=e^{-1}\bmod\lambda(N_a) $ 和 $ d_b=e^{-1}\bmod\lambda(N_b) $ ，這很容易知道的因式分解 $ N_a $ 和 $ N_b $ ;

• 合法獲取具有身份的證書 $ I_a $ , 公共模數 $ N_a $ , 公共指數 $ e $ （這通常需要使用 $ d_a $ );

• 改變 $ I_a $ 到 $ I_b $ 和 $ N_a $ 到 $ N_b $ 在證書中（這不會改變 SHA-1 雜湊，因此偽造是通過驗證程序的證書）；

• 使用偽造的證書冒充 Bob 並且 $ d_b $ .

一種對策是認證服務強制在認證數據的開頭插入一些不可預測的數據。

引用自：https://crypto.stackexchange.com/questions/20649