這是一個針對 SPN 結構的攻擊手法

那 SPN 是由 SBox 和 PBox 結合成的網路所以叫做 SPN

這種攻擊方法是針對 SBOX :

我們希望每個地方進去的 bit 其 0,1 的分佈必須是 $\frac{1}{2}$

那麼 SBOX 這個結構，就沒辦法了，他一定存在著 bias

若你把輸入中某些位置的 bit 和輸出的某些位置的 bit 全部 XOR 起來

計算完所有的可能後，結果他的分佈不是 $\frac{1}{2}$ ，那麼這個與 $\frac{1}{2}$ 的距離就是其 bias

假設有一個 SBOX

1

SBox = [0xE, 4, 0xD, 1, 2, 0xF, 0xB, 8, 3, 0xA, 6, 0xC, 5, 9, 0, 7,]

我們可以暴力搜尋 SBOX，把 SBOX 的哪裡進去和哪裡出來會產生多少的 bias 做成一個表，那就是 Linear Approximation Table (LAT)

Linear Approximation Table

由上表我們可以看到，最大的 bias 是 6/16

所以，由於 SPN 是由一堆 SBOX, PBOX 組合起來的網路

那麼如果餵足夠亂的亂數給他，並盯著加密前的某些 bit 和加密後的結果，會發現有些 1 的分佈不一定會等於 0.5 而會是 0.5 + bias

這樣我們也就可以透過計算這個 bias 還原出他用了什麼 key

舉個例子：以下是一個簡單的 SPN 架構

由於 Sbox, Pbox 是可以逆著算回來的

我們可以簡單地做出 inverse_sbox 和 inverse_pbox

所以我們無法反推的其實只有 Key 與他生成的 Sub_key 而已

那麼，以上圖的路線為例：

我們在最上方，也就是鎖定了明文的第 5,7,8 個 bit

那麼其實 $K_{1,5}, K_{1,7}, K_{1,8}$ 是什麼並不重要

因為我們對 bias 的計算是全部 XOR 起來，那 $K_{1,5}, K_{1,7}, K_{1,8}$ 的結果必定是 0, 1 而且從不改變，所以我們直接略過他就好

於是我們的 bias 從 $P_5 \oplus P_7 \oplus P_8 \oplus K_{1,5} \oplus K_{1,7} \oplus K_{1,8}$ 成為了 $U_{1,5} \oplus U_{1,7} \oplus U_{1,8}$

接下來 $U_{1,5} \oplus U_{1,7} \oplus U_{1,8}$ 遇到了 SBOX，挑一個輸出 bit 比較少而 bias 不錯的大路線給他

因為輸出 bit 如果太多，稍後遇到 PBOX 會分佈到很多個區塊，會使 bias 驟降。

所以我們選 1011 -> 0100 bias 為 4/16 的路線

那要注意的是如果其中一個 SBOX 選擇了 bias 為 0 的路線

那他們相乘的結果必定會 = 0

bias 就消失了，成為完美的 $\frac{1}{2}$

…

經過一系列的選擇 到了最後 $U_{4,6},U_{4,8},U_{4,14},U_{4,16}$

我們決定卡在這裡與密文相遇

我們從後方的密文回來，由於不知道他 XOR 了什麼樣的 Key 所以我們亂猜

會影響我們的 bias 的只有第二和第四把 Key 所以我們暴力搜尋這兩把 KEY

如果 XOR 錯 Key ，那麼這個 bias 並不存在，所以會回歸 $\frac{1}{2}$

如果猜對這兩把 Key，那麼 bias 就會是我們計算出來的結果

透過這個方法，我們可以輕鬆的找出半把 Key

那麼破解加密的 Key 的難度，比起暴力搜尋，直接減半了。

接著如果他生成 Key 的 Key_Schedule 是可逆的話，找出最後一把 SubKey 就能算出所有的 SubKey 了

如果不幸是不可逆的，那就只能 1 Round， 1 Round 推回去了 ˊˋ

參考資料：https://www.engr.mun.ca/~howard/PAPERS/ldc_tutorial.pdf