部分 SHA-256 雜湊 XOR’ed 的抗碰撞性
我的散列算法為 12 個輸入字元串中的每一個計算 SHA-256，並對它們進行異或運算以獲得最終散列。
是否存在攻擊者能夠偽造 2 組產生相同最終雜湊的輸入的風險？
為了避免通過兩次輸入相同的輸入來避免微不足道的攻擊並使這個方案依賴於順序，我在每個輸入前面加上它的索引（二進制 0 到 11）。
對於 256 個輸入的情況，攻擊很容易（因為每個散列可用於使用矩陣演算控制單個輸出位），這讓我想知道是否只有 12 個輸入有類似的攻擊。
我知道有更安全的替代方案，例如 Merkle 樹，但我確實需要最高性能，尤其是在僅修改單個輸入時。
設 tne hashlength 為 $ d $ . 和 $ k=12, $ 這是 $ k- $ 異或問題。使固定 $ k. $ 如果向量是隨機生成的，並且至少大致形成一個大小列表 $ 2^{d/k}, $ 存在一個以遠離零為界的恆定機率的解。這是因為大小列表 $ M $ 包含$$ F:=\binom{M}{k} $$大小子集 $ k, $ 因此作為 $ {x_1,\ldots,x_k} $ 函式在這些子集上的範圍 $ f(x_1,\ldots,x_k):=x_1\oplus \cdots \oplus x_k $ 範圍超過 $ {0,1}^d. $
這是一個 $ F $ 球進 $ 2^d $ 垃圾箱問題，如果 $ F\geq 2^d, $ 的機率 $ f $ 錯過了與給定雜湊值對應的 bin $ h_0 \in {0,1}^d $ 大致是 $ e^{-1}\approx 0.37. $ 服用 $ M=\Omega(k 2^{d/k}) $ 這裡就夠了。然而，找到解決方案的計算成本更高。
Wagner（見這裡）有一個基於遞歸二叉樹的算法 $ k- $ 異或問題$$ x_1\oplus \cdots \oplus x_k=0 \qquad (1) $$和 $ k=2^m, $ 本質上具有時間和記憶體複雜性 $$ O(k 2^{d/(1+m)}). $$(1) 右邊的零向量可以用任何常數向量代替。
讓 $ x_9,\ldots,x_{12}, $ 任意使用瓦格納 $ k=8 $ 解決 $ 8- $ 異或問題
$$ x_1\oplus \cdots \oplus x_8=c, $$ 和 $ c=x_9\oplus x_{10} \oplus x_{11} \oplus x_{12}\oplus h_0. $ 這可以通過複雜性來完成 $$ O(k 2^{d/(m+1)})=O(8 \times 2^{256/4})=O(2^{67}). $$