對 GOST 的第二次原像攻擊的複雜度值的解釋？

我一直在閱讀 F. Mendel 等人 (連結)的文章“對 GOST 雜湊函式的 A (second) preimage attack”，我很難掌握攻擊中的一些複雜性/機率值。具體來說：

1. 在第 228 頁，兩對導致對應值的機率如何 $ x_1 $ , $ x_2 $ ， 和 $ x_3 $ 相當於 $ 2^{-192} $ ?
2. 在第 230 頁上，如何 $ 2^{128} $ 用於計算壓縮函式的複雜度？
3. 在第 230 頁，為什麼要建構 $ 2^{32} $ GOST 最後一次迭代的偽原像？
4. 在第 231 頁，找到正確的機率的值是多少 $ M_{257} $ 在列表中 $ L $ 獲得？
5. 最後，在另一個問題上，平方指的是什麼操作 $ \ominus $ 第 231 頁上的符號： $ \Sigma^m = \Sigma^t \ominus M_{257} $ . [我的猜測：減法模 $ 2^{256} $ - 我對嗎？]

非常感謝。

初步：幾乎同一篇文章在不違法的情況下免費提供，也不下載5GB（格式最多移動三分之一頁）。它也是（以及 2000-2011 年 IACR 加密會議的所有其他文章）在IACR Online Proceedings中，特別是在 FSE 2008 部分，但是你需要從問題中引用的頁碼中減去大約 223 以獲得PDF 中的頁碼。出於這個原因，最好使用章節（而不是頁碼）編號來指定文章的章節。

---

我現在已經回答了所有要點（並在此過程中學到了），但仍然歡迎任何人改進這個答案，製作社區 wiki。

1）在第3節中，為什麼兩對導致對應值的機率 $ x_1 $ , $ x_2 $ ， 和 $ x_3 $ 相當於 $ 2^{−192} $ ?

通過施工， $ x_i $ , $ y_i $ , $ z_i $ , $ s_i $ 是 64 位的。我們假設發現每一對的過程獨立於關係 $ x_i=y_i\oplus z_i\oplus s_i $ 為了 $ i\in{1,2,3} $ （僅與該關係有關 $ i=0 $ )，使這些關係中的每一個 $ i\in{1,2,3} $ 真實的可能性約為 $ 2^{-64} $ ; 因此使這三個為真，機率約為 $ 2^{-192} $ （同樣，沒有獨立性證明）。

這在密碼分析中很典型：我們假設 $ a=b $ 勝算 $ 2^{-n} $ 什麼時候 $ a $ 和 $ b $ 是 $ n $ - 具有至少一個由一個過程產生的數量的比特，該過程的設計目的與匹配該關係無關，並且該過程的輸出或其他數量沒有明顯的偏差。該機率將來自假設任一數量是均勻分佈的。

2) 在第 4.1 節中，如何 $ 2^{128} $ 用於計算複雜度？

在第 4.1 節中，它被認為是多重碰撞 $ t=256 $ 消息塊，每個塊都有一對可以互換使用而不改變結果的值 $ H_{256} $ :

對於每個 $ t $ 消息塊，該對是通過對輸出的生日攻擊找到的 $ f $ ， 其中有 $ n=256 $ 位，因此大約 $ 2^{n/2} $ 的評價 $ f $ 使用諸如 Paul C. van Oorschot 和 Michael J. Wiener 的Parallel Collision Search with Cryptanalytic Applications等技術。某物（人）到了 $ 2^{n/2}=2^{128} $ 學期！

發現多重衝突的總成本約為 $ t\cdot2^{n/2}=2^{136} $ . 請注意，這在可預見的未來已經完全不可行：我們正在討論理論上的攻擊

3) 在第 4.2 節中，為什麼要構造 $ 2^{32} $ GOST 最後一次迭代的偽原像？

這是 4.2 中所需工作之間的折衷，它與數量成正比增加 $ w $ 製作的偽原像；以及 4.3 中所需的工作，它與 $ w $ . 因此，這兩個步驟所需的工作總和為 $ a\cdot w+b/w $ , 最小值是 $ w=\sqrt{b/a} $ .

這裡 $ a=2^{192} $ ， 和 $ b=2^{256} $ （除非我錯了，否則不在同一個單位，但由於這是純粹的理論攻擊，這並不重要），它來了 $ w=2^{32} $ 最低限度。

換句話說：一個人可以改變 $ 2^{32} $ 一點點，攻擊仍然（理論上）有效。有了增加的說 $ 2^{33} $ ，4.3 中的預期工作量將減半，但代價是 4.2 中的工作量增加了兩倍，記憶體增加了兩倍。因此，如果我們增加太多，工作將整體提高（以 4.2 為主），如果我們減少太多，工作將整體提高（以 4.3 為主）。價值 $ 2^{32} $ 平衡了 4.2 和 4.3 中的工作，並且處於正確的範圍內以最小化整體攻擊力。

4) 在第 4.3 節中，找到正確的機率是多少 $ M_{257} $ 在列表中 $ L $ 獲得？

名單 $ L $ 包含 $ w=2^{32} $ 對 $ (H,M) $ 和 $ H $ 的 $ n=256 $ 位（自 $ w\ll2^{n/2} $ , 在標准假設下 $ H $ 由於 1) 中討論的原因，它們是隨機的。

我們想找到一個 $ M_{257} $ 這使得 $ H_{258} $ 匹配的 $ H $ 一些中的 $ (H,M) $ 在 $ L $ . $ H_{258} $ 緊挨著均勻分佈（無論我們如何列舉不同的 $ M_{257} $ ，因為這是一個設計目標 $ f $ ) 因此每個嘗試的值都有機率 $ 2^{-n} $ 匹配任何特定的 $ H $ 在列表中，因此賠率（僅略高於） $ 2^{-n}\cdot w=2^{-224} $ 匹配一個 $ H $ 在列表中，這就是我們想要的機率。

預計僅攻擊的那一部分就需要嘗試 $ 2^{224} $ 的值 $ M_{257} $ ， 因此 $ 2^{225} $ 的評價 $ f $ ，這也是攻擊的既定成本：在這種不切實際的情況下，通常會考慮 $ u+v\approx u $ 每當 $ v<u $ 我們只重複這種近似幾次。

5) 指的是什麼操作 $ \boxminus $ 象徵？

確實， $ \boxminus $ （寫$\boxminus$在這個網站上）在本文中用於減法模 $ 2^{256} $ . 鑑於本文第 4.3 節的定義 $ \boxplus $ ( $\boxplus$) 在第 2 節中作為加法模 $ 2^{256} $ . 注意：確定如何在 $ \TeX $ ，我經常嘗試去毒劑，在這種情況下它起作用了。

6）在第 3 節中，為什麼方程組與 $ 5⋅64 $ 方程在 $ 8⋅64 $ 變數導致 $ 2^{192} $ 解決方案？

一個線性系統 $ x $ 中的線性獨立方程 $ y>x $ 變數未確定，並且 $ y-x $ 變數可以固定為任何值。如果這些是二進制變數，則會導致 $ 2^{y-x} $ 解決方案。我們獲得 $ 2^{192} $ 作為 $ 2^{8⋅64-5⋅64} $ .

求解方程組時也會發生同樣的情況 $ 6⋅64 $ 方程在 $ 8⋅64 $ 變數導致 $ 2^{128} $ 解決方案：我們獲得 $ 2^{128} $ 作為 $ 2^{8⋅64-6⋅64} $ .

引用自：https://crypto.stackexchange.com/questions/15157