由Feal-4密碼演算法淺談差分攻擊
Feal-4密碼演算法在密碼分析史上有重要的地位，差分分析就是針對該演算法首次提出，是一個很好的學習範例。*ctf2019就有一道相關的問題。可能是由於已經不存在現實應用，探討該問題的中文文件非常少，詳細分析對Feal-4進行差分攻擊的我還沒有看到。因此筆者將自己的分析總結與大家分享。
一、Feal-4 加密演算法
1.1 Feal密碼概述
Fea加密演算法由日本NTT公司於1987年發明，該演算法的全稱是 Fast data Encryption ALgorithm。Feal密碼的最初版本就是Feal-4，後來由陸續推出了Feal-8和Feal-N。該演算法提出後，經過密碼學家的研究，陸續發現了該演算法的一些脆弱性，即使是後續版本也存在一定程度的不安全性。
本文我們主要討論Feal-4，分析該密碼演算法的脆弱性及差分攻擊方法。
Feal-4密碼演算法在密碼學史上有很重要的地位，差分攻擊正是研究者通過對Feal-4的研究首次提出的，之後又拓展到了DES密碼演算法上。自此以後，抗差分分析成了密碼設計的一部分，差分分析成為了密碼分析的基本方法。
由於Feal-4的自身的設計特點，差分攻擊對Feal-4非常有效，不需要大量的選擇明文就可以實現。
關於對Feal-4的差分分析，部落格 http://theamazingking.com/crypto-feal.php 有比較詳細的闡述， 我自己在分析時也參考了該部落格的內容，感謝作者的分享。
通過進一步學習我發現，有比該部落格上的方法更高效的方式進行差分攻擊。第一，該部落格使用的方法，子金鑰列舉空間是2的32次方，如果用Python實現，執行的時間久到無法承受，本文使用的方法列舉空間是2的17次方，能大大節約了破解時間。第二，該部落格中講到，子金鑰K0不能使用差分方法求得，通過測試我發現是可以的，需要稍微改動求解方式，基本與前3輪子金鑰的破解相同。這樣破解K0也能使用列舉2的17次方的方法。
1.2 Feal-4密碼演算法加解密流程
Feal-4屬於分組加密演算法，採用Feistel架構。金鑰長度為8位元組，分組長度也是8位元組。Feal-4密碼演算法對一個分組的加密過程可用下面的圖描述
首先，8位元組的金鑰經過子金鑰生成演算法，擴充套件為6個4位元組的子金鑰 K0 – K5，加密過程使用的就是這樣6個4位元組子金鑰。所以如果能恢復出子金鑰，不需要恢復原始金鑰，就能完成對Feal-4的解密，下文的差分攻擊也正是這樣做的。
分組加密過程中，首先8位元組明文分組被分成左右兩個部分，左半部與子金鑰K4異或，右半部與子金鑰K5異或。兩個半部再異或作為右半部。接著進入4輪輪函式。每一輪裡，右半部直接成為下一輪的左半部。
第一輪裡，右半部與K0異或，然後進入F函式，F函式實現非線性部分，F函式的結果與左半部進行異或，成為下一輪的右半部。後3輪同理，依次使用子金鑰 K1 K2 K3。
4輪操作完成後，左半部就是密文分組的左半部，左半部與右半部異或後，成為密文分組的右半部。這就是一個分組的加密過程。解密過程就是上述過程的逆過程。
1.3 輪函式
下面我們來看F函式。Feal-4的脆弱性就在F函式中。輪函式F將32位元對映為32位元。輪函式中使用了一個名為G函式的操作，G函式有兩個定義如下
G0和G1，接收兩個引數 a 和 b，將a+b的值加0或加1，模256後（避免超出一個位元組的長度），進行迴圈左移位，移2位。定義完G函式，輪函式F可用下圖描述
如果說輪函式F是Feal-4的核心，G函式就是F函式的核心。
二、對 Feal-4 進行差分攻擊
接下來我們開始對Feal-4進行差分攻擊。差分分析的目標是獲得加密的子金鑰。
差分分析最早由Murphy於1990年，針對Feal4密碼提出，隨後 Biham 和 Shamir 又在一系列研究裡對該技術進行了發展，屬於選擇明文攻擊，適用於過度使用異或操作的分組密碼演算法。
所謂差分分析，是指追蹤明文對的“差異”的傳播。這裡的“差異”由我們根據目標進行定義，可以是異或值，也可以是其它。針對Feal-4，我們使用的就是異或值定義“差異”，或者稱之為“距離”。有些地方也稱為“特徵”（characteristic）
比如說，選定明文分組P1，分組之間的“差值”（differential）為δ，於是另一個明文分組就是P1+δ，明文P1對應的密文分組時C1，明文 P1+δ 對應的密文與C1的“距離”是 ε
如果 δ 以一定的概率對應著 ε ，就稱 δ 是一個差分特徵。
其實這個過程我們主要關注的是非線性部分F函式，所以也可以用下面的圖描述這個過程，右側可認為是一種簡要描述
在Feal-4密碼裡，有這樣兩個有用的“特徵”，第一個，同樣的輸入經過輪函式F一定產生同樣的輸出，即，當輪函式的輸入差值為0x00000000時，輪函式的輸出差值一定時0x00000000，概率為1。第二個，當輪函式的輸入差值為0x80800000時，輪函式的輸出差值一定時0x02000000，概率為1。
基於這樣一個事實，我們來追蹤差分特徵0x8080000080800000在Feal-4加密過程的傳播。
我們可以任意選擇一個明文分組P0，然後與0x8080000080800000異或，得到明文分組P1，P0與P1構成一個明文對，差值為0x8080000080800000 對應的密文分組分別是C0和C1，記
追蹤差分特徵 P’ 在Feal-4中的傳播，過程如下
上述差值進入Feal-4後，我們可以追蹤差值到第3輪，此後由於差值0x02000000對應的輪函式差值不確定，才中斷。但是，密文分組我們是知道的（選擇明文攻擊），因此，L’ 和 R’ 是已知的，我們可以從密文倒推，看倒推到差值追蹤中斷的地方
Y' = L' ^ R' Z' = 0x02000000 ^ L' X' = 0x80800000 ^ Y'
由上面三行，我們已經倒推到X’了，於是整個流程裡的差分值，我們都是清楚的。L’ R’ X’ Y’ Z’ 都是已知的。
請注意輪函式的輸出差值Z’，馬上就要用到。
結合實際加密流程圖，我們還可以通過猜解K3，計算實際的Z0和Z1，從而獲得實際的 Z0 ^ Z1
Y0 = L0 ^ R0 Y1 = L1 ^ R1 Z0 = F(Y0 ^ K3) Z1 = F(Y1 ^ K3)
所以現在我們有了一個K3的方程，
差分分析得到實際的 Z’ = 0x02000000 ^ L’
猜解K3得到可能的 Z’ = Z0 ^ Z1 = F(Y0 ^ K3) ^ F(Y1 ^ K3)
如果猜解的K3正確，那麼這兩個值應該相等，由此我們就可以爆破出K3，爆破需要列舉的空間是4個位元組，即2的32次方。爆破出K3後，使用K3以及 L、R，可以恢復出第四輪加密前的資料，即第三輪加密的結果
L3 = Y R3 = L4 ^ F(Y ^ K3)
使用L3和R3繼續上面的過程，可以猜解出K2。這個過程需要改變的是使用的差分特徵，猜解K3時使用的差分特徵是0x8080000080800000，猜解K2時使用差分特徵 0x0000000080800000，可以像K3那樣構建方程
由於K3已知，可以算出此時的Y0和Y1
Y0 = L ^ F(K3 ^ R0 ^ L0)
Y1 = L ^ F(K3 ^ R1 ^ L1)
同理可以由差分資料流得到Z’
Z’ = L3’ ^ 0x02000000
其中 L3’ = R4’ = L’ ^ R’
此時猜解K2，構建Z’的等式
Z’ = F(Y0 ^ K2) ^ F(Y1 ^ K2)
Z’ = L3’ ^ 0x02000000
得到K2
同理，用差分特徵0x00000000 02000000 可以求解出K1
那麼如何求解K0和K4、K5呢？theamazingking 部落格上講到，無法使用差分方法求解K0，只能直接猜解K0，然後求出對應的K4和K5，然後使用其他選擇明文分組驗證猜解的K0 K4 K5 正確性。經過測試我發現其實是可以使用差分的方式求K0的。
還是使用差分特徵0x0000000002000000，此時構建K0的方程針對 X’ 構建。有了K3 K2 K1後，我們就有了第一輪加密的左右輸出，從而有了L1’ 和 R1’，於是
X' = L1' ^ 0x00000000 = L1'
另一方面，猜解K0，得到
X0 = F(R1_0 ^ K0) X1 = F(R1_1 ^ K0) X' = X0 ^ X1
我們同樣可以得到K0的等式。
提高破解速度
上述過程已經可以實現子金鑰的恢復，但是列舉空間是2的32次方，theamazingking的 C demo 程式就是使用的這種演算法。C程式的執行時間已經較慢了，使用Python實現破解程式，速度慢到無法承受。得益於Feal-4輪函式的設計，我們還能以更快的速度找到子金鑰，方法如下
首先定義M函式，針對4位元組輸入產生4位元組輸出，如下
其中z表示zero,0x00
然後對所有可能的四位元組序列，計算 Q0 和 Q1
此時有這樣的結論：如果A恰好等於M(K3)，那麼下面的式子成立
將式子展開，就能看到等式左右兩邊相等
基於這種方式，我們可以將猜解子金鑰的過程分為兩步。
第一步，猜解16位的M(K3)，即 M(K3) = (0, a0, a1, 0) ，猜解的空間是2的16次方
通過上述步驟得到 Q0 和 Q1，然後與 Z’ 建立方程，
Q0 ^ Q1 = F[ M(Y0) ^ (0, a0, a1, 0) ] ^ F[ M(Y1) ^ (0, a0, a1, 0) ] Z' = L' ^ 0x02000000 Q0 ^ Q1 的8-23位 = Z' 的8-23位
通過上述三行式子，列舉全部的 M(K3)，得到所有可能的 M(K3)
第二步，根據 K3 = (c0, c0^a0, c1^a1, c1) ，繼續猜解 c0 c1兩個位元組，猜解方式依然是基於Z’構建等式，猜解的空間是2的16次方，就可以得到完整的子金鑰 K3。
通過這種子金鑰求解方式，兩次2的16次方的列舉，共2的17次方的列舉次數，就可以求解出子金鑰K3，K2 K1 K0的求解方式一樣。實際測試中，效率提升非常明顯。
以上就是對Feal-4的差分攻擊過程。上述分析過程仍然有可以改進的地方，比如選擇明文的數量。以及使用破解K0的方式，用同一組選擇明文破解K3 和 K2，第二組選擇明文破解K1 和 K0，這樣需要的選擇明文數更少。由於時間原因我沒有再做測試。
三、例項
*ctf 2019 的 notfeal 問題就是這樣一個使用差分方式攻擊Feal密碼的例子。不過該程式對原始Feal-4進行了改動。有以下兩點
第一，F函式的輸出被逆序了。
第二，Feistel架構左右顛倒了。
只要理解了差分攻擊的過程，不難調整差分過程，完成攻擊。
由於輸出逆序，三輪使用的差分特徵要調整為
1.0×0000000080800000
2.0×8080000080800000
3.0×0000000200000002
該問題限定的選擇明文數量是50組，實際上使用36組就可以成功。
程式碼很亂就不放了。可參考 sixstar 在github上的官方 writeup（該wp使用的就是theamazingking的C程式碼）
值得一提的是，差分攻擊得到的子金鑰組不唯一，但是都可以正確解密。