生日攻擊尋找附近的碰撞
跟進這個問題：關於近碰撞阻力的通用攻擊的效率如何？
讓 $ H:{0,1}^∗→{0,1}^n $ 是一個密碼安全的散列函式。讓 $ k\in \mathbb{N} $ 是 $ 0 \leq k \leq n $ . 沒有更多細節，需要多少努力才能找到兩個字元串 $ x_1,x_2 $ 這樣 $ \Delta(H(x_1),H(x_2))\leq k $ 持有？ $ \Delta(\cdot,\cdot) $ 表示漢明距離。
接受的答案提到它需要 $ \displaystyle \sqrt \frac{1}{p} $ 雜湊在哪裡 $ p=\displaystyle \frac{\sum_{i=0}^{k}{n\choose i}}{2^n} $ 有機率 $ 1/2 $ 獲得一對近碰撞對。這是為什麼？
我試圖用生日悖論來計算數學。我得到一個必須計算的最小雜湊數是這樣的：
$$ \frac{2^{n/2}}{\sqrt{\sum_{i=0}^k{n\choose i}\cdot 2^i}} $$ 我哪裡做錯了 ？
好的，讓我們從頭到尾討論這個問題。
請注意，對於散列函式，我們可以將輸出位建模為獨立的二進制變數，從而應用二項分佈模型來找出有多少位取某個值。所以機率 $ k $ 位不匹配是 $ \binom{n}{k}2^{-(n-k)}2^{-k}=\binom{n}k2^{-n} $ （直覺上，我們在這裡匯總了所有可能允許的不匹配）。現在我們最多想要那個 $ k $ 位不匹配，因此我們可以總結： $ \sum^k_{i=0}\binom{n}i2^{-n} $ . 現在請注意 $ 2^{-n} $ 是一個常數因子，因此 $ p=\sum^k_{i=0}\binom{n}i2^{-n}=2^{-n}\sum^k_{i=0}\binom{n}i=\frac{\sum^k_{i=0}\binom{n}i}{2^n} $ ，現在我們終於可以使用所說的生日參數來找到需要的消息數量 $ \sqrt{\frac1p}=\sqrt{\frac1{\frac{\sum^k_{i=0}\binom{n}i}{2^n}}}=\sqrt{\frac{2^n}{\sum^k_{i=0}\binom{n}i}}=\frac{2^{n/2}}{\sqrt{\sum^k_{i=0}\binom{n}i}} $ 這是預期的結果。
請注意，如本答案中所述，此結果也可以更嚴格地證明，這是由 Mario Lamberger、Florian Mendel、Vincent Rijmen 和 Koen Simoens 在“通過編碼理論實現的無記憶近碰撞”中完成的 (PDF)。