散列上的很多迭代：它不會減少熵嗎？

Question

我看到這個技術在很多地方推薦使用（包括堆棧），我不能擺脫我的頭腦，這會減少熵！畢竟，你再次哈希了一些已經被哈希並碰撞的機會。碰撞機會不會碰撞機會導致更多的碰撞機會？經過研究，似乎我錯了，但爲什麼？

Answer 1

既然您標記了md5，我將以此爲例。從wikipedia：

如果用相同的哈希兩個前綴可以構造一個共同的後綴可以添加到既要使碰撞更容易被接受爲使用它的應用程序的有效數據。此外，當前的碰撞查找技術允許指定任意前綴：攻擊者可以創建兩個相同的內容開始的衝突文件。所有攻擊者需要生成兩個碰撞文件，它是一個帶128字節數據塊的模板文件，在64字節的邊界上對齊，可以通過碰撞尋找算法自由更改。一個MD5衝突的例子，其中兩個消息有6位不同，它們是：

然後他們給出的例子明文是256字節長。由於衝突攻擊依賴於一個數據塊，並且散列摘要只有128位位，所以在第一次迭代之後確實沒有增加碰撞攻擊的風險 - 也就是說你不能真正影響超出第一個散列的碰撞可能性。

還要考慮散列的熵是前述的128位。即使考慮到總碰撞機會僅爲2^20.96（再次來自wikipedia），需要大量的迭代纔會導致兩個輸入發生碰撞。我認爲自己成爲受害者的第一眼推理是：

• 任意兩個任意輸入都有碰撞機率x％。
• 第一個散列的輸出本身就是兩個這樣的輸入。
• 因此，每次迭代都會增加碰撞機率x％。

這很容易被反例所證實。再考慮MD5：

• 的兩個輸入碰撞的機會是1：2^21（考慮最壞的情況下，從MD5的維基百科的密碼分析）
• 哈希再次引起衝突的可能性相等機會複合，因此在第二輪碰撞的機會是1：2^20
• 因此，對於任何兩個輸入散列多次等於摘要的熵保證衝突。

MD5任意兩個輸入連續128次，你會發現這是不正確的。你可能不會在它們之間找到一個重複的散列 - 畢竟，你只創建了256個可能的2^128散列值，留下了2^120個可能性。每輪比賽的碰撞概率爲independent。

有兩種方法可以理解爲什麼會這樣。首先是每次迭代本質上都試圖擊中一個移動目標。我認爲你可以根據生日悖論構建一個證明，其中有一個令人驚訝的低數量的哈希迭代，你可能會看到一個輸入的哈希摘要匹配不同輸入的哈希摘要。但他們幾乎肯定會發生在迭代的不同步驟。一旦發生這種情況，它們在相同的迭代中永遠不會有相同的輸出，因爲散列算法本身是確定性的。

另一種方法是認識到哈希函數在運行時實際上增加了熵。考慮一個空字符串與其他輸入一樣有一個128位摘要;這在算法步驟中沒有添加熵的情況下不會發生。這實際上是密碼散列函數的必要組成部分：必須銷燬數據或者可以從摘要中恢復輸入。對於比摘要更長的輸入，是的，熵總體上失去了;它必須是爲了適應摘要長度。但是也增加了一些熵。

我沒有其他散列算法的確切數字，但我認爲所有的觀點已經概括爲其他散列函數和單向/映射函數。

Answer 2

它減少了熵。

在由Flajolet和奧德里茲科，一個定理（定理2）命名爲Random Mapping Statistics紙表明：

「如果一個Ñ比特被重複ķ倍，圖像點的期望的數量隨機函數是（1 - t_k）* 2^N（用於大ñ），其中t_k滿足遞推關係T_0 = 0和T_ {K + 1} = E^{ - 1 + t_k}。從這一點可以看出，圖像點的期望的數量是2^{N-1 + 1}時的隨機函數進行迭代K = 2^I次。」

更多參考如如下：。

• Gligoroski，D和克利馬，五，2010年9月ICT創新的理想隨機函數的窄管哈希設計像差的實際後果在國際會議（第81- 93）Springer Berlin Heidelberg

• Bhaum Ik，R.，Dutta，A.，Guo，J.，Jean，J.，Mouha，N.andNikolić，I.，2015. More Rounds, Less Security?

• Dinur，I.和Leurent，G.，八月。改進了對基於哈希的MAC和HAIFA的通用攻擊。在國際密碼學會議（pp.149-168）中。施普林格柏林海德堡。

從最後一個引用文件，人們會發現以下兩個引理： Two lemmas on entropy loss。因此，如果使用獨立的隨機函數，而不是一次迭代k次的隨機函數，那麼關於熵損失的觀察也成立。