最小差異碰撞度量
取一個雜湊函式 $ H $ .
會有相同長度的消息對 $ M,M’ $ 為此 $ M\ne M’,H(M)=H(M’) $ .
讓 $ P(x) $ 是一個函式計算的數量 $ 1 $ 輸入 $ x $ . $ d=P(M\oplus M’) $ ，或者用文字來說， $ d $ 是位數，其中 $ M $ 和 $ M’ $ 不同。
讓 $ T(H) $ 是最小值 $ d $ 為了 $ H $ . 這是指標。它沒有說明實際找到這些衝突消息的難度，只是說必須改變一定的最小位數才能產生衝突。
這個指標真的有用嗎？可以嗎 $ T(H) $ 小，只要實際上找到這樣的碰撞是不可行的，或者做一個小 $ T(H) $ 意味著 $ H $ 弱？
是否有界限 $ T(H) $ 對於任何流行的雜湊函式？（SHA2 系列、SHA3 系列、BLAKE2 及其變體）
可以嗎 $ T(H) $ 小，只要實際上找到這樣的碰撞是不可行的，或者做一個小 $ T(H) $ 意味著 $ H $ 弱？
如果 $ H $ 是一個隨機函式，它接受大尺寸的輸入，並產生一個固定尺寸的輸出，然後 $ T(H) = 1 $ 以極高的機率。
讓我們呼叫固定大小的輸出 $ H $ $ n $ 位。
然後，對於任何一對不同的消息 $ M, M’ $ , 他有機率 $ H(M) = H(M’) $ 作為 $ 2^{-n} $ （作為 $ H $ 假設是一個隨機函式）。
現在，如果我們有 $ m > n $ , 並考慮所有可能的 $ m $ 位對 $ M, M’ $ 有一點不同，我們有 $ m2^{m-1} $ 這樣的對。
沒有這樣的對碰撞的機率是 $ (1 - 2^{-n})^{m2^{m-1}} \approx e^{-m 2^{m-n-1}} $ ， 作為 $ m2^{m-n-1} $ 很大，這個機率很小，因此很有可能會發生至少一個相差一位的衝突。
由於碰撞必須至少相差一位，我們有 $ T(H) = 1 $ （再次，很有可能）。
這個指標真的有用嗎？
似乎不是；我們沒有任何計算方式 $ T(H) $ 對於任何強雜湊函式，所以它在實際意義上沒有用。而且，從理論上講，對於任何像隨機函式一樣起作用的東西，它都是 1，所以我看不到那裡有任何直接用途。