是否有基於衝突的指標來比較不良雜湊函式？
壞散列函式並不像“一般碰撞機率” 假設中那樣完美……而且“抗碰撞”的一般概念不需要散列函式和样本集之間的獨立性約束。
讓 $ H $ 是一個帶有摘要的雜湊函式 $ k $ 位，和 $ S $ 具有大小的輸入樣本集 $ s=|S| $ .
$ H $ 如果“很難找到”散列到相同輸出的兩個輸入，則它是抗碰撞的，
$ \exists x\ne y\in S|H(x)=H(y) $但是“難找”並不是一個好的定義：比較兩個雜湊函式的性能 $ H_1 $ 和 $ H_2 $ 我們需要一個精確的指標……維基百科使用 $ Pr[H] $ ，定義這個度量的機率概念……但是，在現實生活中的測試或基準測試中，我們只有碰撞次數 $ c $ , 和一個大的標準偏差來比較 $ c $ 改變時的值 $ S $ 或者 $ H $ .
換句話說：
有一個“標準的方式”來獲得現實生活 $ Pr[H] $ 壞散列函式？語境。讓我成為一名購買低質量專有軟體的程序員，這些軟體實現了奇異的散列函式：散列函式 $ H $ 對我來說是一個黑匣子，我需要測試它。
所以，如果這個功能的賣家說它是抗性的，我需要通過實驗和對實驗結果的一些統計分析來檢查它。
回到問題……如果這個標準存在，我假設那是一種機率定義，那麼，會有點像（是嗎？只需要檢查數字 $ c $ 碰撞）
$$ PrH=\frac{c}{|S|}=\frac{c}{s} $$ 錯誤的散列函式（範例）具有以下特徵值 $ Pr $ 這不僅取決於 $ |S| $ … 我們可以用 $ c $ 將壞雜湊與其他雜湊的效率進行比較。我在想像我可以使用 $ c $ 或平均 $ \overline{c} $ 基於許多 $ c_i $ 測試作為碰撞率的度量。
筆記
讓 $ c_1 $ 中的碰撞次數 $ H_1(S) $ 和 $ c_2 $ 中的碰撞次數 $ H_2(S) $ ，我們可以比較兩個雜湊函式。
為了避免偏差，我們可以對許多樣本集進行平均 $ S_1 $ , $ S_2 $ 等。所以有平均 $ \overline{c}_1 $ 和 $ \overline{c}_2 $ 作為好的估計者。
理論上我們也可以估計最小值 $ \overline{c} $ 具有摘要的雜湊函式 $ k $ 位由
$$ {Pr}_{min}H ~=~ 1 - \frac{2^k!}{(2^k)^s (2^k - s)!} ~\approx~ 1 - exp({-s^2/2^{k + 1}}) $$ 結論，比較雜湊函式的好分數是
$$ q ~=~ PrH - Pr_{min}H ~\approx~ \frac{\overline{c}}{s} -1+exp({-s^2/2^{k + 1}}) $$ 什麼時候 $ q=0 $ 我們有“完美的散列函式”，它有一個關於碰撞的預期行為……想像像 SHA1 這樣的散列總是完美的，因為不可能計算 $ \overline{c} $ , 但截斷的 SHA1 或“壞雜湊”可以測試大 $ S $ 樣品。
PS：否定 $ q $ 是可能的 $ H $ 和 $ S $ 不是獨立的。我的興趣是這些截斷或錯誤雜湊的行為，並比較它們。
有一些與散列函式族相關的標準量 $ H_k\colon {0,1}^m \to {0,1}^h $ 對於一個統一的隨機密鑰 $ k $ . 你可以稱它們為指標。它們在Carter 和 Wegman 的通用雜湊族研究計劃（免付費牆）中聲名顯赫，儘管它們在Gilbert、MacWilliams 和 Sloane的一次性身份驗證器的密碼學中首次使用（免付費牆）早於 Carter-Wegman計劃幾年。
- 上界 $ \Pr[H_k(x) = u] $ 對於任何 $ x \in {0,1}^m $ 和 $ u \in {0,1}^h $ . 如果是 $ 1/2^h $ ，那麼我們說家庭是平均分配的。
- 上界 $ \Pr[H_k(x) = H_k(y)] $ 對於任何不同的 $ x, y \in {0,1}^m $ . 例如，如果最多 $ 1/2^h $ ，我們說家庭是萬能的；如果最多 $ \varepsilon = O(1/2^h) $ ，我們說它是 $ \varepsilon $ - 幾乎是通用的。數量 $ \Pr[H_k(x) = H_k(y)] $ 有時也稱為碰撞機率。
- 上界 $ \Pr[H_k(x) \oplus H_k(y) = u] $ 對於任何不同的 $ x, y, \in {0,1}^m $ 和任何 $ u \in {0,1}^h $ . 如果最多 $ \varepsilon = O(1/2^h) $ ，我們說它是 $ \varepsilon $ -幾乎異或通用。
- 上界 $ \Pr[H_k(x) = u, H_k(y) = v] $ 對於任何不同的 $ x, y \in {0,1}^m $ 和任何 $ u, v \in {0,1}^h $ . 如果最多 $ \varepsilon = O(1/2^{2h}) $ ，我們說它是 $ \varepsilon $ - 幾乎是強烈普遍的或 $ \varepsilon $ - 幾乎成對獨立。
- 上界 $ \Pr[H_k(x_1) = u_1, \dots, H_k(x_n) = u_n] $ 對於任何不同的 $ x_i \in {0,1}^m $ 和任何 $ u_i \in {0,1}^h $ . 如果最多 $ \varepsilon = O(1/2^{nh}) $ ，我們說它是 $ \varepsilon $ -幾乎 $ n $ -獨立或 $ n $ -通用。
有一些標準可證明的函式範例可以達到上述界限的最優或接近最優值。在密碼學中，這些界限與Poly1305和GHASH等一次性身份驗證器相關，它們基於等分佈 $ \varepsilon $ - 幾乎異或通用雜湊族 $ \varepsilon \approx \lceil m/128\rceil/2^{128} $ ，以及其他應用程序，例如具有非自適應對手的雜湊表。數量 $ \Pr[H_k(m’) = a’ \mathrel| H_k(m) = a] $ 為了 $ m’ \ne m $ 有時稱為偽造機率。
一個 $ n $ - 獨立雜湊族具有碰撞機率的屬性 $ H_k(x) = H_k(y) $ 對於不同的 $ x, y \in S $ 在一個子集中 $ S \subseteq {0,1}^m $ 的 $ n $ 元素是$$ 1 - \frac{2^h!}{(2^h)^n (2^h - n)!} \approx 1 - e^{-n^2/2^{h + 1}}. $$ 但是，要保證這一點，密鑰必須很大。此外，這些界限都不能保證故意計算知道 key 的碰撞的難度。
您可能得到的不是未知鍵的碰撞機率，而是雜湊族的抗碰撞性：
- 上界 $ \Pr[x \ne y, H_k(x) = H_k(y)] $ 在哪裡 $ (x, y) = A(k) $ 和 $ A $ 是任何隨機算法。如果這可以忽略不計，當預期成本 $ A $ 在下面 $ \sqrt{2^h} = 2^{h/2} $ ，我們說家庭是防撞的。
特別是，如果 $ B_t(f) $ 是一種隨機算法，將生日悖論應用於 $ t $ 均勻隨機輸入 $ f\colon {0,1}^m \to {0,1}^h $ 作為一個預言機並返回一個碰撞如果有一個（例如，使用van Oorschot 和 Wiener 的並行碰撞搜尋機），那麼對於任何等分佈的 $ f $ ,$$ \Pr[x \ne y, f(x) = f(y)] = 1 - \frac{2^h!}{(2^h)^t (2^h - t)!} \approx 1 - e^{-t^2/2^{h + 1}}, $$在哪裡 $ (x, y) = B_t(f) $ . 什麼時候 $ t^2 \lll 2^h $ ， 以便 $ t \lll \sqrt{2^h} = 2^{h/2} $ , 這在 $ h $ . 最好的通用攻擊 $ H_k $ 有成本 $ t $ 是 $ A(k) = B_t(H_k) $ ; 如果沒有比這更好的已知攻擊，我們會說 $ H_k $ 是抗碰撞的。
我們不知道如何為所有隨機算法證明這一點 $ A $ ，但是，所以這個屬性只能推測出我們還沒有找到更便宜的碰撞搜尋算法的雜湊族。例如，我們很有信心 Poly1305 或 GHASH 不耐碰撞；用一個欄位乘法和一個欄位加法計算任何鍵下的兩塊碰撞是微不足道的。我們推測鍵控 BLAKE2 是抗碰撞的，因為沒有人知道如何讓它發生碰撞。
通過對通用散列函式的輸出進行採樣來經驗性地研究抗碰撞性幾乎沒有用。 如果您嘗試在 Poly1305 或 GHASH 上使用通用生日算法，它不會比在鍵控 BLAKE2 上做得更好。但是密碼分析家的天才並不需要立即認識到有一種簡單的算法可以找到 Poly1305 和 GHASH 衝突，給定密鑰，比通用生日算法 快得多。我們能做的最好的事情就是通過抽樣算法來尋找碰撞來進行實證研究——讓許多聰明的密碼分析者嘗試去思考它們。 到目前為止，根據經驗，沒有人想出一種在鍵控 BLAKE2 中找到衝突的方法。
由於採樣輸出對於研究抗碰撞性沒有用處，因此在研究雜湊族的簡化版本時，我們通常不會研究截斷輸出大小的進展。相反，我們建構雜湊族以迭代一些內部加擾函式以獲得可變的輪數，並研究輪數的進展。例如，最著名的對 BLAKE 減少輪次版本的碰撞攻擊僅適用於 5 輪，這就是為什麼 BLAKE2 設計者認為只推薦 10 輪很舒服。
鬆散地說，我們有時也會選擇一個固定的雜湊函式，例如 SHA3-256，並說如果沒有人找到在該固定雜湊函式下計算碰撞的方法，它是**抗碰撞的。**當然，如果 $ h \leq m $ ，我們保證存在碰撞，因此必須存在一個成本可忽略不計的簡單隨機算法來計算它：即一種簡單地返回碰撞而不進行任何計算的算法。
所以沒有很好的方法來正式化它，但在實踐中，這似乎很難。20 年前，人們推測 SHA-1 在這種鬆散的意義上是抗碰撞的，直到 2004 年有人想出了一種以比通用攻擊更低的成本計算 SHA-1 碰撞的方法，然後有人最後發布了一個實際的碰撞年。時至今日，仍然推測 SHA-256 在這種鬆散的意義上仍然是抗碰撞的。