基於塊的雜湊的抗碰撞證明
我正在設計一個基於 SIMON 密碼的無密鑰雜湊。這是對“這個”問題的跟進。快速總結：我在硬體中有一個 ECC 引擎和 SIMON 密碼，並且它處於一個功率極其受限的環境中。我想要一個雜湊生成器有兩個原因：1）ECC 共享密鑰，2）如果我想驗證一個流。由於硬體限制，我不能使用任何其他雜湊引擎，這主要是因為它們很大並且破壞了我的功率預算，但是因為我已經有一個 SIMON 加密塊，所以我可以以任何我想要的方式對其進行修改。
我從閱讀“ chap9.pdf ”和一堆論文開始；但是，我想在我設計的東西上打個洞。我需要為自己證明我使用它的合理性，因為硬體是如此昂貴的提議。
我採用了 SIMON 128/256 架構，它對 4 個 64 位字進行了密鑰擴展，然後用它創建了一個輸入 128 位並輸出 128 位的東西。只是為了讓這個問題易於解釋，我將從這裡開始使用 SIMON 32/64，因為它有 4 個 8 位字。
基本架構在這裡：
我只是繼續通過 XOR 將內容輸入到較低的兩個單詞中，這遵循 Davies-Meyer 和 Merkle 風格的架構。
為了視覺化這一點，我為一個全 0 的 64 位輸入生成了密鑰擴展，通過雜湊引擎進行了兩次執行：
在上圖中，將 0 流送入雜湊進行兩輪雜湊的結果是 0x5753c0fe。這意味著 32 位最終會產生 32 位，而在我計劃實現 128 位塊的系統中，最終會產生 128 位數字。
現在，我可以說出我所知道的所有問題：
- 我無法指定長度，因為這需要用作流，並且我無法保證有多少塊將通過它。通過它的 2 個街區，我可以找到碰撞。. 這似乎不是問題，因為我使流輸入更長，但我找不到正式的證明。
- 我有一個執行加密硬體的計數器，我可以對高位或低位字進行異或運算，但是對於 2 個塊，我仍然可以找到衝突。
問題： 對於基於塊的無密鑰密碼，是否有正式的流輸入長度和衝突證明？
如果我理解正確，您正在使用 Simon 密鑰擴展過程，因此您的塊的輸入是 256 位 Simon 密鑰，輸出是 256 位最後一輪密鑰（並且您完全忽略了 Simon 加密過程）。
如果是這樣，三個尼特：
我相信您可以在 $ O(2^{64}) $ 壓縮函式評估。發生這種情況是因為密鑰擴展過程是可逆的；也就是說，給定一個 256 位輸出，你可以找到對應的 256 位輸入。所以，攻擊者會做的是假設一個 2 塊消息；他會：
- 產生 $ 2^{64} $ 初始塊，並從中計算中間狀態。
- 產生 $ 2^{64} $ 最終狀態由目標雜湊和 $ 2^{64} $ 不同的 $ K_i, K_{i+1} $ 單詞，併計算逆鍵擴展
- 尋找碰撞 $ K_{i+2}, K_{i+3} $ 字; 如果你找到一個，這意味著一個原像這很容易解決；使變換不可逆。
如果您希望散列函式具有抗衝突性，則需要添加一些無衝突填充機制。
這種架構實際上比 Davies-Meyer 類型的構造更接近 Sponge 雜湊函式（以防萬一你想知道）