對 3 輪 SIMON 分組密碼的已知明文攻擊
我正在嘗試編寫一個程序來對 SIMON 分組密碼的縮減輪次版本執行線性逼近攻擊，但我被困在如何實際應用線性逼近來獲取每一輪的子密鑰。我找到了這篇論文，其中列出了以下高偏差線性近似值：
P[ F(X)_i = X_(i-2) ] = 3/4 P[ F(X)_i = X_(i-2) ^ X_(i-1) ] = 3/4 P[ F(X)_i = X_(i-2) ^ X_(i-8) ] = 3/4 P[ F(X)_i = X_(i-2) ^ X_(i-1) ^ X_(i-8) ] = 1/4其中 F(X) 是 SIMON 算法中的非線性函式，F(X)_i 是所述函式輸出的第 i 位，X_n 是函式輸入的第 n 位。這一切對我來說都很有意義。然而，我被困在如何利用這些線性近似來推導每一輪的子密鑰。如何從線性逼近到找到子鍵的程序？如果有人可以幫助我縮小理解上的差距，或者至少為我指明正確的方向，我將不勝感激。非常感謝！
編輯：最初發佈在 Stack Overflow
該論文還討論了多輪的線性特徵：
我們提出了幾種產生 SIMON32/64 線性特性的方法，並提出了 11 輪 SIMON 32/64 的最著名線性特性，偏置為 $ 2^{-16} $ . 然後，我們將此特徵擴展到 13 輪密碼。
我們提出了幾種為 SIMON32/64 生成 LC 的方法，作為案例研究，並介紹了該密碼的最著名的 11 輪 LC，其偏差為 $ 2^{-16} $ （可消耗 13 輪密碼）。
您列出的線性近似值似乎來自等式 3。 SIMON 是Feistel 密碼。通過結合描述一輪Feistel的方程，該論文的作者得到了整輪的以下線性表達式：
$$ (P_R)_2 \oplus (K^1)_2 \oplus (X^1_L)_2 = (P_L)_0, $$
這很可能成立 $ 3/4 $ . 這裡 $ X^1 = X^1_L || X^1_R $ 是第一輪的輸出，並且 $ P = P_L || P_R $ 是明文。符號 $ (X)_i $ 用於 $ i $ 第一點 $ X $ . 請注意，這裡的表達式是針對第一輪編寫的，但它同樣適用於任何一輪 $ i $ ，當寫成以下形式時：
$$ (X^{i-1}_R)_2 \oplus (K^i)_2 \oplus (X^i_L)_2 = (X^{i - 1}_L)_0, $$
我們更換的地方 $ P $ 經過 $ X^{i - 1} $ 和 $ X^1 $ 經過 $ X^i $ . 這當然也可以寫成
$$ (X^{i-1}_R)_2 \oplus (K^i)_2 \oplus (X^{i - 1}_L)_0 = (X^i_L)_2. $$
這仍然是正確的機率 $ 3/4 $ .
如果我們將最後一個方程“代入”（堆積）成一個 3 輪 Feistel 網路（如論文中的圖 3 所示），我們得到：
$$ (X^{i - 1}_R)_2 \oplus (K^i)_2 \oplus (X_L^{i -1})_0 = (X^{i + 2}_R)_0 \oplus (K^{i + 2})_2 \oplus (X_L^{i + 1})_2, $$
或者：
$$ \Sigma_K \oplus (X^{i - 1}_R)_2 \oplus (X_L^{i -1})_0 \oplus (X^{i + 2}_R)_0 \oplus (X_L^{i + 1})_2 = 0, $$
和 $ \Sigma_K = (K^i)_2 \oplus (K^{i + 2})_2 $ .
論文繼續使用這個表達式進行更多輪次，但我們可以在這裡停下來。上述表達式是 3 輪密碼的線性特徵。因為我們知道上面的表達式以何種機率成立（取決於奇偶性 $ \Sigma_K $ )，我們就可以開始獲取密鑰位了。 本文件很好地解釋了該部分：
隨後的過程涉及部分解密最後一輪密碼。具體地，對於目標部分子密鑰的所有可能值，將對應的密文比特與目標部分子密鑰的比特進行異或，並將結果反向執行對應的S-box。這是針對所有已知的明文/密文樣本完成的，並為目標部分子密鑰的每個值保留一個計數。當線性表達式對於進入最後一輪的 S 盒（由部分解密確定）和已知明文位中的位成立時，特定目標部分子密鑰值的計數會增加。假定具有與明文/密文樣本數的一半不同的最大計數的目標部分子密鑰值表示目標部分子密鑰位的正確值。這是有效的，因為假設正確的部分子鍵值將導致線性近似保持的機率顯著不同於 1/2。（它是高於還是低於 1/2 取決於線性或仿射表達式是否是最佳近似值，這取決於隱含線上性表達式中的子密鑰位的未知值。）假設不正確的子密鑰會導致對進入最後一輪 S-box 的比特進行相對隨機的猜測，結果，線性表達式將以接近 1/2 的機率成立。這是有效的，因為假設正確的部分子鍵值將導致線性近似保持的機率顯著不同於 1/2。（它是高於還是低於 1/2 取決於線性或仿射表達式是否是最佳近似值，這取決於隱含線上性表達式中的子密鑰位的未知值。）假設不正確的子密鑰會導致對進入最後一輪 S-box 的比特進行相對隨機的猜測，結果，線性表達式將以接近 1/2 的機率成立。這是有效的，因為假設正確的部分子鍵值將導致線性近似保持的機率顯著不同於 1/2。（它是高於還是低於 1/2 取決於線性或仿射表達式是否是最佳近似值，這取決於隱含線上性表達式中的子密鑰位的未知值。）假設不正確的子密鑰會導致對進入最後一輪 S-box 的比特進行相對隨機的猜測，結果，線性表達式將以接近 1/2 的機率成立。
以上適用於 SPN，但對於 Feistel 網路，原理是相同的。