Collision-Resistance

如果文件被修改,雜湊衝突是否會持續存在?

  • February 13, 2020

假設我使用一種相對不安全的散列算法對契約進行數字簽名。還假設創建具有相同雜湊值的欺詐性合約是可行的。據我了解,為了利用散列衝突,黑帽需要首先將一些人為的資訊引入數據中,以對抗其預期更改的散列影響。

例如,原始合約和雜湊為:

我會付給你 1.00 美元 -> 12345

和欺詐性衝突契約:

我會付給你 1,000,000.00 美元(人為的資訊)-> 12345

我可以在簽名前加入一些我自己的文字來保護自己嗎?

例如:

我會付給你 1.00 美元祝你有美好的一天 -> 67890

攻擊者能否簡單地將相同的文本添加到他們設計的文件中並獲得相同的新雜湊?

我會付給你 1,000,000.00 美元(人為的資訊)祝你有美好的一天 -> 67890

或者附加的文本會改變散列,使文件不再衝突?

我會付給你 1,000,000.00 美元(人為的資訊)祝你有美好的一天 -> 37294

即我添加的資訊會抵消攻擊者的人為資訊嗎?

實際上,與 SHA1 或 MD5 一樣,找到了一種實用的衝突查找方法,使用這種算法比更安全的算法更快。使用一種非常快速的不安全算法與雙方、第三方或隨機自動化系統相結合,在散列之前添加一些新穎的良性資訊是否有意義?這是否增加了足夠的複雜性?

即在 SHA1 和 git 的情況下,攻擊者是否可以提前添加一些模糊的人為資訊(被送出和簽名或其他),然後在時機合適的時候引入惡意程式碼?或者後續的送出會阻礙這個計劃嗎?即有很多貢獻者和來自各地的送出的程式碼倉庫是否比幾乎沒有變化的倉庫更安全?

TL;DR:當使用 SHA-1 或類似的弱散列時,在消息的開頭包含不可預測的數據。


簡而言之,對導致衝突的實際(迭代)雜湊存在三種攻擊,即攻擊者以具有相同雜湊的兩條不同消息(相同長度)結束。從最簡單到最難:

  1. 碰撞攻擊:攻擊者可以為每個操作約束選擇一個有意義的前綴和一個有意義的後綴。消息的形式

I will pay you $1,000,000.00 (Qn47y2NXu49ssmexutgno5!QsmtxG) have a nice day

I will pay you $1,000,000.00 (eCW3Y!=jLJK;q&vM+;gdPZma7JAP4) have a nice day

此類針對 SHA-1 的攻擊的範例已被粉碎。 2. 選擇前綴¹碰撞攻擊:攻擊者可以為每個操作約束選擇兩個有意義的前綴(等長)和一個有意義的後綴。消息的形式

I will pay you $1.00 (G&RyUbpwgnn6dYbkLLnkx2WqMu5RVZ!QsmxyG) have a nice day

I will pay you $1,000,000.00 (KE2nFdwUizu;uo!BKgSB$c&ULEQ!R) have a nice day

對 SHA-1 進行此類攻擊的一個例子是最近的這篇論文。 3. 第二原像攻擊。攻擊者可以根據操作約束選擇兩個消息中的一個完整消息,另一個消息的前綴,並讓兩個消息共享一個後綴。消息的形式

I will pay you $1.00 on presentation of this signed message, have a nice day

I will pay you $1,000,000.00 (48CMWaAb5gt9RopNsgw!W2&o9x54e) have a nice day

沒有針對 SHA-1,甚至針對 MD5 的此類攻擊的範例。

注意:任意部分的最小長度通常為幾個塊(普通雜湊為 32 或 64 字節)。

注意:根據消息的解釋方式,碰撞攻擊 (1) 仍然可以導致兩條消息的外觀完全在對手的控制之下。特別地,有可能具有在後綴中編碼的兩個任意不同外觀之間進行選擇的前綴,其中一個根據任意部分中的一位來顯示。選擇了破碎攻擊的前綴以允許 PDF 文件使用該前綴。這個技巧可以用圖像,可執行程式碼..

攻擊 1 和 2 僅在她/e 可以選擇簽名消息的一部分時對攻擊者有用,例如對於像這樣的消息

I will pay you $1.00 per invoice PkictdyAxvaokEeTtEkVYEG24UYtK4GLiTqCWHtw, have a nice day

我可以在簽名前加入一些我自己的文字來保護自己嗎?

是的,但不完全符合問題中說明的方法。您可以通過在簽名消息的開頭(在第一個塊中)包含一些不可預測的數據來防止衝突攻擊和選擇前綴衝突攻擊(1 和 2) 。例如

My Ref BzCP3dFT. I will pay you $1.00 per invoice PkictdyAxvaokEeTtEkVYEG24UYtK4GLiTqCWHtw

精明的證書頒發機構在生成具有不可預測證書序列號的數字證書時會使用此技術。這可以防止選擇前綴衝突攻擊,其中前綴包括可預測的 CSN 和兩個不同的域名(一個是攻擊者的目標,另一個在攻擊者的控制下),並且一些任意數據屬於公鑰。

攻擊者能否簡單地將相同的文本添加到他們設計的文件中並獲得相同的新雜湊?

是的,攻擊者可以輕鬆添加或更改兩個衝突消息的後綴。這就是為什麼不可預測的數據必須在開始。

我添加的資訊會抵消攻擊者的人為資訊嗎?

僅當消息中的添加足夠早(例如,第一個塊),並且對手無法執行攻擊 3(第二個原像)時。至關重要的是,不可預測的數據必須位於散列消息​​的開頭。在PDF 文件或其他結構化消息的外觀中添加不可預測的數據是沒有意義的。

攻擊者是否可以提前添加一些模糊的人為資訊(被送出和簽名或其他),然後在時機合適的時候引入惡意程式碼?

是的,但前提是攻擊者(能夠執行攻擊 1 或 2)可以預測他/她控制的部分*之前的內容。*這在準備 zip 文件時是可以避免的,然後進行散列(例如,通過散列簽名或引用):zip 創建過程可以添加隨機標頭,從而使攻擊 1 和 2 不可行。當攻擊者可以發布整個文件並且該文件的完整性根據該文件的雜湊值得到保證時,這是無法避免的(攻擊 1 對於包括大多數執行檔在內的許多文件格式來說已經足夠了)。


¹ 通​​常只寫選擇前綴(衝突)。

如果攻擊者在看到您的人為數據後添加他們的人為數據,那沒有任何區別,並且添加的人為數據會對您有好處。

但是,如果攻擊者需要提前做好準備,例如攻擊是計算密集型的,並且他必須在收到有效文件後立即送出偽造的文件,那麼添加不可預測的資訊可能會使攻擊變得不切實際。

如果散列遵循 MD(例如 MD5/SHA1/SHA2)構造,則在開頭添加不可預測(隨機)資訊很重要,因為向此類散列函式添加公共後綴將保留衝突。

如果攻擊者與消息 m 發生衝突。Forged(m),他不太可能僅僅因為他已經有 Forged(m) 就能夠輕鬆地找到修改消息(隨機 || m)的衝突。但是,如果他具有發現碰撞的通用能力並擁有必要的時間/資源,他將能夠創建 Forged(random || m)。

引用自:https://crypto.stackexchange.com/questions/77575