Cryptanalysis
對 COCONUT98 的 Boomerang 攻擊的複雜性
我正在嘗試理解David Wagner 的論文 The Boomerang Attack。在關於迴旋鏢攻擊複雜性的第 162 頁上，該論文說：
攻擊需要 $ 8 \cdot 2 \cdot 32 \cdot 2^{32} = 2^{41} $ 的離線計算 $ F $ 功能。
我想我理解攻擊，但我無法理解這些複雜性常量的價值。從做什麼 $ 8 $ 和 $ 2 $ 起源？
您正在尋找的答案在第 161 頁。
- 在分而治之的方法中猜測和檢查每個輪密鑰，所以 $ 2^{32} $ 是猜測單個密鑰的成本。我們需要找到數量 $ F $ 在每個階段呼叫，將它們相乘，最後將每個階段的成本相加。
- 第一階段和最後（第 8 階段）需要相同的 16 個四重奏，這使得 $ 16\cdot 4\cdot 2 $ 打電話給 $ F $ Feistel 網路的功能。
請注意，四重奏包含 $ 4 $ 密文-明文對。
- 第二和第七階段需要 $ 8 $ 四重奏，這使得 $ 8\cdot 4\cdot 2 $
- 第三和第六階段需要 $ 4 $ 四重奏，這使得 $ 4\cdot 4\cdot 2 $
- …
當它進入內部和內部時，攻擊將四重奏的數量減半。
讓我們總結一下
$$ \begin{align} time &= 2^{32}(16\cdot 4\cdot 2) + 2^{32}(8\cdot 4\cdot 2) + 2^{32}(4\cdot 4\cdot 2) + 2^{32}(2\cdot 4\cdot 2) + 2^{32}(1\cdot 4\cdot 2)\ &= 2^{32}(16\cdot 4\cdot 2 + 8\cdot 4\cdot 2 + 4\cdot 4\cdot 2 + 2\cdot 4\cdot 2 + 1\cdot 4\cdot 2)\ & = 2^{32}\cdot 8 \cdot (16+8+4+2+1)\ & \approx 2^{32}\cdot 8 \cdot 32 \end{align} $$