雜湊組合的生日攻擊
對於家庭作業，我必須回答以下問題：
你有一個雜湊算法可以轉換一個 $ 2\cdot n $ 位數到 n 位數。您必須計算多少個雜湊值才能找到衝突 $ h(x) \oplus h(y) = h(r) \oplus h(s) $
我知道你可以找到一個碰撞後 $ 2^{n/2} $ 評價。但我不知道這是如何受到一個事實的影響 $ 2\cdot n $ 位號被散列為 $ n $ 位號和 $ \oplus $ 的雜湊值。
我們首先需要細化問題的定義。
加密上下文中最自然的假設是“你必須計算多少雜湊值”意味著我們考慮了一種最小化該雜湊值的策略。
在理論密碼學中，一個常見的假設是我們被允許任意大量的記憶體，並使用任意的計算能力。我們假設我們使用它來記憶體雜湊計算，但最終會健康地檢查所需的記憶體量和處理器時間，以獲得獎勵積分。
我們還將假設我們實際上被詢問了最佳策略之一所需*的預期雜湊計算數量。*正如密碼學中常見的那樣，我們將滿足於近似值，和/或忽略低 $ n $ ，如果有幫助的話。
我們需要定義“碰撞”。在談論雜湊中的衝突時，可以理解 $ x $ 和 $ y\ne x $ 和 $ h(x)=h(y) $ . 但是這里後面的條件被替換為 $ h(x)\oplus h(y)=h(r)\oplus h(s) $ ，那麼剩下的呢？那可能是：
- $ (x,y)\ne(r,s) $ . 在這種情況下，假設答案為零 $ n>0 $ : 我們取任意兩個不同的 $ x $ 和 $ r $ 我們知道 $ (x,x) $ 和 $ (r,r) $ 是一個解決方案，不做任何雜湊。 $ (x,r) $ 和 $ (r,x) $ 也可以。從現在開始，我們將忽略選項 1。
- 清楚的 $ x $ , $ y $ , $ r $ , $ s $ ; 至少需要四個雜湊。
- $ x $ , $ y $ , $ r $ , $ s $ 這樣無論雜湊算法如何，術語之間可能的相等都不會導致衝突；為了 $ n=3 $ 可以是（以二進制顯示輸入和輸出）
- $ x=\mathtt{000000} $ 和 $ h(x)=\mathtt{010} $
- $ y=\mathtt{000001} $ 和 $ h(y)=\mathtt{001} $
- $ r=\mathtt{000010} $ 和 $ h(r)=\mathtt{010} $
- $ s=y $ ; 這特別有效，因為 $ x=r $ .
選項 2 和 3 不等價；選項 2 錯誤地看起來更簡單（我們稍後會陷入這個陷阱……）。
結果顯然取決於特定的“散列算法”，在加密上下文中假設它是已知的。也許我們可以通過查看這個算法找到答案。但是問題中沒有給出，因此在加密上下文中，我們的預設備份選項是考慮預期的雜湊數是針對隨機函式的 $ h:{0,1}^{2n}\to{0,1}^n $ （該符號僅說明輸入的位大小和輸出 $ h $ ）。有 $ 2^{(n2^{2n})} $ 這樣的功能，因此 $ 2^4=16 $ 為了 $ n=1 $ , $ 2^{32} $ 為了 $ n=2 $ ，還有一聲吶喊 $ 2^{192} $ 為了 $ n=3 $ .
有一種簡單的方法可以合理地證明這一點 $ 2^{n/4+1/2} $ 雜湊允許以公平的機率找到碰撞，除了小 $ n $ . 爭論：
- 評估 $ h(i)=h_i $ 為了 $ 2^{n/4+1/2} $ 的增量值 $ i $ 從…開始 $ 0 $ ，將整數同化為大端二進制中的位串（在密碼學中很常見）；也就是說，對於 $ n=4 $ , $ h_5=8 $ 意思是 $ h(\mathtt{00000101})=\mathtt{0100} $ .
- 對所有人 $ (x,y) $ 和 $ 0\le x<y<2^{n/4+1/2} $ 考慮 $ h’(x|y)\gets h(x)\oplus h(y) $ 並列出幾乎 $ 2^{n/2} $ 價值觀 $ h’(x|y) $ .
- $ h’ $ 不是隨機函式，但如果我們仍然濫用密碼散列的生日問題（密碼學中的常見問題），這告訴我們有接近 40% 的碰撞機率 $ h’ $ 在雜湊的標准定義中。
- 這種碰撞將允許一個 $ h $ 按照要求，始終匹配我們的選項 3。
- 每個選項 2 的碰撞並不總是一個；但是考慮到它只有在我們發現碰撞時才會發生 $ h $ 在雜湊的標准定義中，僅僅經過 $ 2^{n/4+1/2} $ 雜湊。
通過將這種策略轉變為一種尋找碰撞的策略 $ h’ $ 對於增量值 $ i $ （而不是計算所有雜湊 $ h_i $ )，我們可以使生成的策略對選項 3 的幾乎完整子集（包括選項 2）進行優化；見下文。
我們現在繼續推理最佳策略必須做什麼。
它必須只計算不同輸入的雜湊值（否則我們可以設計一個更好的策略）。
並且由於函式 $ h $ 是隨機的，所說的不同輸入與所需的預期雜湊數無關（即，所有可能的雜湊的平均數 $ h $ ）。所以我們可以限制策略總是使用字典順序中的輸入，就像我們在範例 3 中所做的那樣。我們可以安全地聲明“..a $ 2\cdot n $ 位數..”問題的一部分足夠大，以至於該策略不會用完輸入值；如果我們刪除了二的因素，這仍然成立，包括 $ n=1 $ .
計算後 $ h_i $ ，如果計算的雜湊現在允許展示不同的，則該策略必須停止 $ x $ , $ y $ , $ r $ , $ s $ 最多 $ i $ 和 $ h_x\oplus h_y=h_r\oplus h_s $ . 至少其中之一 $ x $ , $ y $ , $ r $ , $ s $ 一定是 $ i $ （否則策略將不是最佳的），並重新排序 $ x $ , $ y $ , $ r $ , $ s $ 以非遞減順序使策略有效且最優。
因此，受限制的最佳策略必須嘗試增加 $ s $ 並準確停止
對於選項 2，當 $ s>2 $ 和 $ h_s $ 剛剛計算和記憶體的匹配 $ h_x\oplus h_y\oplus h_r $ 對於一些 $ x $ , $ y $ , $ r $ 這樣 $ 0\le x<y<r<s $ ; 這種情況下 $ x $ , $ y $ , $ r $ , $ s $ 是碰撞。
對於選項 3，另外
- 什麼時候 $ s\ge2 $ 和 $ h_s $ 剛剛計算過的數學 $ h_r $ 和 $ 0<r<s $ ， 在這種情況下 $ x=0 $ , $ y=0 $ , $ r $ , $ s $ 是非平凡的碰撞；
- 或者什麼時候 $ s>1 $ 和 $ h_s=h_0 $ ， 在這種情況下 $ x=0 $ , $ y=1 $ , $ r=1 $ , $ s $ 是非平凡的碰撞；
- 或者什麼時候 $ s=1 $ 和 $ h_s=h_0 $ ， 在這種情況下 $ x=0 $ , $ y=0 $ , $ r=0 $ , $ s=1 $ 是一次非平凡的碰撞。
選項 2 的一種實現選項是四個嵌套循環 $ s $ 成長始於 $ 0 $ 在外部，計算和記憶體 $ h_s $ ，那麼對於 $ r $ 從 $ 2 $ 至 $ s-1 $ , $ y $ 從 $ 1 $ 至 $ r-1 $ , $ x $ 從 $ 0 $ 至 $ y-1 $ ，如果新計算的則終止 $ h_s=h_x\oplus h_y\oplus h_r $ ， 在這種情況下 $ x $ , $ y $ , $ r $ , $ s $ 是碰撞。
有 $ s(s-1)(s-2)\over6 $ 的組合 $ x $ , $ y $ , $ r $ 對於給定的 $ s $ . 每個對應一些 $ h_x\oplus h_y\oplus h_r $ ，這些不一定不同，並且發現它們之間的衝突本身並不能讓算法停止。我們考慮所有 $ h $ ，因此對於每個新的 $ h_s $ , 賠率 $ p_s $ 該策略停止計算 $ h_s $ 假設它之前沒有停止是（最多） $ \tilde{p_s}={s(s-1)(s-2)\over6},2^{-n} $ . 它認為 $ p_s\lessapprox\tilde{p_s} $ , 當它發生時相等 $ s(s-1)(s-2)\over6 $ 的值 $ h_x\oplus h_y\oplus h_r $ 都是不同的。
在計算之前停止的機率 $ h_j $ （也就是說，已經計算 $ j $ 雜湊或更少）是
$$ q_j;=;1-\prod_{3\le s<j}(1-p_s);\lessapprox;\sum_{3\le s<j}p_s;\lessapprox;\sum_{3\le s<j}\tilde{p_s};\lessapprox;{6\over2^n}\sum_{3\le s<j}(s-1)(i−2)(i−3) $$ 只要這個近似值很緊 $ j\ge4 $ 足夠小 $ q_s $ 仍然很小，並且之間幾乎沒有碰撞 $ (j-1)(j−2)(j−3)\over6 $ 的值 $ h_x\oplus h_y\oplus h_r $ 之前計算的時間 $ h_{j-1} $ 被計算。 此外，歸納表明
$$ \sum_{3\le s<j}(s-1)(i−2)(i−3);=;{j(j-1)(j−2)(j−3)\over4}\lessapprox{j^4\over4} $$ 並且除了小的值之外，該近似值對於所有 $ j $ . 因此停止計算的機率 $ j $ 雜湊或更少是 $ q_j\lessapprox{3\over2}j^4 2^{-n} $ ，並且這個近似值是緊的，只要 $ k $ 不是太小，但足夠小，所述賠率仍然很小，並且很少有碰撞 $ \approx{j^3\over6} $ 的值 $ h_x\oplus h_y\oplus h_r $ 經過考慮的。
因此，選項 2 的最佳算法不能比 $ O(2^{n/4}) $ ; 這表明我們的簡單算法具有正確的漸近性。
而且， $ j\le{1\over\sqrt[4]3}2^{n/4}\implies q_j\le{1\over2} $ 持有。請注意，後面的近似值遠非嚴格：我們預計 $ h_x\oplus h_y\oplus h_r $ （通過濫用密碼散列的生日問題，有意識地忽略了一個事實，即 $ \approx{j^3\over6} $ 值不是獨立的）；並且我們將產品更改為 sum 的近似值不再嚴格。這為任何最佳策略所需的雜湊數的中位數建立了一些上限（不是近似值） ；我們的目標是稍高的均值。
我們幾乎嚴格地證明了最佳策略的預期雜湊數和大 $ n $ 一定是 $ k=O(2^{n/4}) $ 作為 $ n $ 成長；並有合理的論據 $ 2^{n/4+1/2} $ 提供近 40% 的碰撞機率。
因為那個 $ k $ 遠低於生日界限 $ \approx2^{n/2} $ , 對於大 $ n $ 雜湊衝突 $ h $ 單獨到達之前 $ k $ 步驟，以及我們沒有拒絕的“碰撞”的兩個定義之間的區別僅對小問題 $ n $ .
我們知道根據 2 或 3 導致最小散列數的各種策略，似乎在執行 $ O(2^n) $ 時間與 $ O(2^{n/4}) $ 或者 $ O(2^{n/2}) $ 記憶單詞（對於至少有單詞的電腦 $ n $ 位；除此之外，一個乘法因子 $ \log n $ 兩者都適用）。我們可以對非常小的期望值進行精確計算 $ n $ （但這將取決於碰撞的定義）。我們最多可以進行隨機模擬 $ n=32 $ . 尋找需要更少工作的策略（可能以更多記憶體為代價，或者計算比需要更多的雜湊值）以解決更大的問題 $ n $ 是一個有趣的問題。
這個答案是不完整的（我們仍然錯過了一個嚴格而緊密的界限），過於冗長和復雜，可能會令人困惑（尤其是從我們尋求最佳策略的那一刻起），並且破壞了一項有趣的家庭作業（以模糊的方式詢問，但也許這是老師或OP故意的）。我希望至少編輯會有所不同，並且 OP 將進行上述精確和模擬的計算。畢竟，我很可能在某個地方留下了嚴重的錯誤。
