位翻轉時 SHA512 雜湊的最小漢明距離
為了 $ n\in\mathbb{N} $ 讓 $ {0,1}^n $ 表示集合 $ {0,1} $ -長度向量 $ n $ . 讓 $ {0,1}^* = \bigcup_{n\in\mathbb{N}}{0,1}^n $ 表示所有有限長度的集合 $ {0,1} $ -字元串。
如果 $ x,y\in {0,1}^n $ 對於一些 $ n\in\mathbb{N} $ ，我們讓$$ d_H(x,y) = \big|\big{ i\in {0,\ldots,n-1}:x_i \neq y_i\big}\big| ;;\in {0,\ldots,n} $$ 表示之間的漢明距離 $ x, y $ .
讓 $ h:{0,1}^* \to {0,1}^{512} $ 表示密碼散列函式 $ {\sf SHA512} $ .
**問題。**是否知道$$ m_0 = \min{d_H(h(x),h(y)): (\exists n\in\mathbb{N}(x,y\in {0,1}^n)) \land (d_H(x,y)=1)} $$ 是積極的？是一個下界 $ \geq 2 $ 為了 $ m_0 $ 知道嗎？
我們強烈希望 $ m_0=0 $ 因為我們希望 SHA512 壓縮函式作為隨機預言機執行。例如，如果我們要選擇一個 $ 2^{521} $ 長串 $ s $ 有 $ 2^{521} $ 其他字元串的漢明距離 $ s $ 是 1。優惠券收集估計將返回所有可能的輸出以高機率返回，包括匹配的值 $ \mathrm{SHA512}(s) $ . 因此，對於任何固定的、非常長的字元串，我們希望您可以翻轉一個不會改變最終值的位。
我們強烈希望不能建設性地證明 $ m_0=0 $ 因為這將是雜湊衝突的一個例子。為了證明 $ m_0=0 $ 非建設性的似乎需要比其設計中提供的更多的數學結構。
有趣的是，相關值 $$ m_1=\mathrm{min}{d_H(h(x),h(y)):(\exists n\in\mathbb N,(x,y\in {0,1}^n))\wedge (d_H(x,y)=2)} $$ 可以用鴿子洞原理證明為零。我們挑一串長度 $ 2^{512}+1 $ 併計算其一位翻轉的雜湊值。其中兩個必須匹配，並且是一對漢明距離為 2 的字元串。
ETA：@poncho 指出 SHA512 最多只能輸入長度 $ 2^{128}-1 $ (!) 所以這些長字元串參數不適用於標準版本的 SHA512，僅適用於問題的抽象。對於標準化版本的機率參數，我們改為考慮所有長度為 522 的字元串並修復這些提供的一些位位置 $ 2^{521} $ 在該位位置不同並且其差異應該在統計上獨立的對。我們應該預料到包括 0 在內的一整套差異。
雖然鴿巢原理不再有效 $ m_1 $ 它確實提供了 10 次輸入翻轉的上限以產生匹配的輸出。我們考慮一個長度的字元串 $ 2^{127} $ 以及 5 次翻轉產生的一組輸入。有超過 $ 2^{512}+1 $ 在這些等等中，必須有兩個具有相同的值。根據應用於漢明度量的三角不等式，這對之間的漢明距離最多為 10。