找到雜湊滿足的明文有多難h(a)⊕h(b)=h(c)H(一種)⊕H(b)=H(C)h(a)oplus h(b)=h(c)?
給定一個密碼散列函式 $ h $ ，例如SHA256，找到明文有多難 $ a,b,c $ 這樣
$$ h(a)\oplus h(b)=h(c) \text? $$
這個部分答案為問題的漸近硬度建立（相當微不足道的）下限和上限，假設 $ h $ 表現得像一個 $ n $ -位寬隨機函式。
如果一個雜湊 $ m $ 消息 $ M $ ，然後計算 $ f(i,j,k)=h(M_i)\oplus h(M_j)\oplus h(M_k) $ 為了 $ (i,j,k)\in\mathbb {Z_m}^3 $ ， 那是 $ m^3 $ 結果，大多數值重複至少 6 次大 $ m $ . 任何人永遠不會達到零的機率 $ f(i,j,k) $ 關於 $ (1-2^{-n})^{m^3/6} $ 對於大 $ m $ , 對於任何選擇 $ M $ 由無法區分的對手 $ h $ 從一個隨機函式。
因此，如果 $ m\approx2^{n/3} $ 已經計算了雜湊值，但對於大參數，這不能導致解決問題的機率超過 16%。
因此，問題中問題的預期難度至少為 $ \mathcal O(2^{n/3}) $ 乘以雜湊的工作量。此外，一個無限強大的對手可能會成功 $ \mathcal O(2^{n/3}) $ 對實現散列的預言機的查詢。
以上導致了一個顯式算法，其成功機率不為零 $ (2^{n/3})^3=2^n $ 的評價 $ f $ ，因此有成本 $ \mathcal O(2^n) $ $ n $ 位操作；這個需要 $ \mathcal O(2^{n/3}) $ $ n $ -位記憶單詞。我們可以做得更好。
一種選擇是修復 $ a $ ，然後找到函式的碰撞 $$ g(x)=\begin{cases}h(x) & \text{if }x\text{ is even}\h(x)\oplus h(a) & \text{if }x\text{ is odd}\end{cases} $$ 這種搜尋可以用成本進行 $ \mathcal O(2^{n/2}) $ 雜湊和適度的記憶體，使用Floyd 的循環查找，或 Paul C. van Oorschot 和 Michael J. Wiener 的Parallel Collision Search with Cryptanalytic Applications（密碼學雜誌，1999 年 1 月，第 12 卷，第 1 期；稍早的免費版本可從第一作者的網站）。
請注意，如果 $ g(b)=g(c) $ 和 $ b\ne c $ ， 然後 $ (a,b,c) $ 是問題的解決方案，如果 $ b $ 和 $ c $ 有不同的奇偶性，其中（對於隨機 $ h $ ) 的賠率約為 $ 1/2 $ 對於每個展示的碰撞。
因此，問題中問題的預期難度最多為 $ \mathcal O(2^{n/2}) $ 乘以雜湊的工作量。
這基本上就是所謂的 3-XOR 問題，並且已經研究了一段時間。
簡而言之，最著名的時間複雜度是 $ 2^{n/2} $ 為了 $ n $ 位雜湊。但是，幼稚的方法需要大量記憶體，並且有一些方法可以降低記憶體複雜性（有時以更多時間為代價）。
詳情見近期工作
$$ 1 $$, 幻燈片也可用。 注意： SHA256 的目前記錄是具有 119 個零位的 3-XOR，使用大量計算得出；）請參閱
$$ 2 $$玩得開心。 $$ 1 $$Bouillaguet 等人。（TOSC 2018 (1)）重新審視和改進 3XOR 問題的算法。 $$ 2 $$蓋坦·勒朗。密碼分析記錄。FSE 2018 臀部會議幻燈片，第 160 頁。https://fse.iacr.org/2018/files/proceedings_rumpsession.pdf