Linear Cryptanalysis(線性密碼分析)


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

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

這種攻擊方法是針對 SBOX :

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

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

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

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

假設有一個 SBOX

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

In\Out 0 1 2 3 4 5 6 7 8 9 A B C D E F
0 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 -2 -2 0 0 -2 6 2 2 0 0 2 2 0 0
2 0 0 -2 -2 0 0 -2 -2 0 0 2 2 0 0 -6 2
3 0 0 0 0 0 0 0 0 2 -6 -2 -2 2 2 -2 -2
4 0 2 0 -2 -2 -4 -2 0 0 -2 0 2 2 -4 2 0
5 0 -2 -2 0 -2 0 4 2 -2 0 -4 2 0 -2 -2 0
6 0 2 -2 4 2 0 0 2 0 -2 2 4 -2 0 0 -2
7 0 -2 0 2 2 -4 2 0 -2 0 2 0 4 2 0 2
8 0 0 0 0 0 0 0 0 -2 2 2 -2 2 -2 -2 -6
9 0 0 -2 -2 0 0 -2 -2 -4 0 -2 2 0 4 2 -2
A 0 4 -2 2 -4 0 2 -2 2 2 0 0 2 2 0 0
B 0 4 0 -4 4 0 4 0 0 0 0 0 0 0 0 0
C 0 -2 4 -2 -2 0 2 0 2 0 2 4 0 2 0 -2
D 0 2 2 0 -2 4 0 2 -4 -2 2 0 2 0 0 2
E 0 2 2 0 -2 -4 0 2 -2 0 0 -2 -4 2 -2 0
F 0 -2 -4 -2 -2 0 2 0 0 -2 4 -2 -2 0 2 0

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

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

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

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

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



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

我們可以簡單地做出 inverse_sboxinverse_pbox

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

那麼,以上圖的路線為例:

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

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

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

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

接下來 U1,5U1,7U1,8U_{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 就消失了,成為完美的 12\frac{1}{2}


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

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

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

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

如果 XOR 錯 Key ,那麼這個 bias 並不存在,所以會回歸 12\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