雜湊函式和雪崩效應

非正式地，雪崩效應表示，當通過雜湊函式饋送時，兩個相似但不相同的輸入應該產生完全不同的輸出。

我至少已經看到了效果的兩個正式定義。第一個是如果我們翻轉輸入的一位，兩個各自的結果通常應該是非常不同的，並且可以保證它們不一樣。另一個定義是，如果我們翻轉輸入的一位，則結果在統計上是獨立的。我覺得這很混亂：這兩個定義是矛盾的。

正確的定義是什麼？實際上，像 sha256 這樣的現代雜湊函式是否具有此屬性？

設定想法。讓 $ H(\cdot) $ 是一些雜湊函式 $ N $ 可能的輸出。讓 $ X_1 $ 是一個（整數）隨機變數，在某個區間上均勻分佈。（假使，假設 $ \Pr(H(X_1) = x) = N^{-1} $ 對於每個 $ x $ 。） 讓 $ X_2 $ 是一個 RV，使得它相對於第一個 RV 完全不同（即，之間的漢明距離 $ X_1 $ 和 $ X_2 $ 正好是一個）。雪崩效應說明了什麼 $ \Pr(H(X_2) = H(X_1),|, H(X_1)) $ ?

第一個定義說 $ \Pr(H(X_2) = H(X_1),|, H(X_1)) = 0 $ . 第二個說 $ \Pr(H(X_2) = H(X_1),|, H(X_1)) = N^{-1} $ . 顯然，兩者都不可能是真的。

雪崩效應的正確定義在Webster 的論文“關於 S 盒的設計”中定義。密碼學進展 - Crypto ‘85 as :

對於展示雪崩效應的給定變換，每當一個輸入位被補碼時，平均一半的輸出位應該改變。

**如果您更改輸入的 1 位，**則還可以看到每個位應該有 50% 的機會發生更改。

這基本上意味著為了測試雪崩效應，您必須應用類似於以下的算法。

# result array
array res[n] = {0, ..., 0}

# compute all inputs
for each inputs x of size n
  ref_val = H ( x )

  # compute all possible 1 bit change
  for i in 0..n-1
     test_val = H ( X ^ (1 << i) )

     # compute statistics per bit
     for j in 0 .. n-1
        res[j] += ((test_val ^ ref_val) >> j) & 1


# in the end forall k, res[k] / (n * 2**n) should be around 50%.

由於輸入的大小，您可以使用相對精度進行測試，無論是否 $ \operatorname{SHA256} $ 確實有嚴格的雪崩效應。但是通過對大量輸入進行採樣，將每個位翻轉一次，就可以進行測量。但是在大多數情況下，我們通常會分析基元的組件，以斷言是否尊重雪崩效應。

引用自：https://crypto.stackexchange.com/questions/40268