選擇一個哈希函數

Question

我想知道：什麼是最大數量的字節，可以安全地散列，同時保持散列函數的預期衝突計數？

對於md5，sha- *，甚至可能是crc32或adler32。

Answer 1

您的問題不清楚。 「最大字節數」是指「最大數量的項目」？被哈希的文件的大小與碰撞次數沒有關係（當然，假設所有文件都不相同）。

你是什麼意思「維護預期的碰撞計數」？從字面上看，答案是「無限的」，但是在一定數量之後，你會像預期的那樣發生碰撞。

而對於問題的回答「有多少項目，而保持在X％碰撞的概率我可以哈希？」，看看下錶爲：

http://en.wikipedia.org/wiki/Birthday_problem#Probability_table

從鏈接：

爲了比較，10^-18到10^-15是典型硬盤的不可糾正誤碼率[2]。理論上，MD5,128位應該保持在該範圍內，直到820億個文檔，即使其可能的輸出更多。

這裏假定輸出均勻分佈的散列函數。假設有足夠的項目需要散列和加密散列函數（如md5和sha）或好的散列（如Murmur3，Jenkins，City和Spooky Hash）。

也假定沒有惡意對手積極製造衝突。那麼你真的需要一個安全的加密散列函數，如SHA-2。

注意：CRC和Adler是校驗和，旨在檢測數據損壞，而不是最小化預期的衝突。它們具有諸如「檢測大小爲< X或大於Z千字節的輸入的所有比特歸零」的特性，但不具有良好的統計特性。

編輯：不要忘記這是所有關於概率。完全可以只散列兩個小於0.5kb的文件，並得到相同的SHA-512，儘管極不可能（例如no collision has ever been found for SHA hashes till this date）。

Answer 2

你基本上看着生日悖論，只看着真正的大數字。 考慮到數據的正常「分佈」，我認爲在遇到問題之前可以將約5-10％的可能性排除在外，儘管沒有任何保證。

只要走得足夠長的散列，不會遇到問題;）