【技術分享】密碼學學習筆記之差分分析入門篇——四輪DES - 網安

前言

密碼學學習筆記斷更快半年了，最近又重新拾起了對密碼學的學習，以一篇對四輪DES的差分分析“復出”。

對于差分密碼分析的學習，參考《分組密碼的攻擊方法與實例分析》

這里就不重新介紹一遍DES的算法流程了，網上一大把。我們研究對DES算法的分析時，由于DES的初始置換及其逆置換均以公開，故在安全性分析時就可以將其忽略。另外我們這里暫且只分析四輪DES，所以有很多概率相關的概念也可以暫時不用涉及。

DES差分分析的關鍵就在于其S盒差分分布的不均勻特性，何為不均勻特性，即相同的差分進入S盒，輸出的差分是不均勻分布的。

不過在詳細介紹之前，還是先聲明一些概念比較好。

基礎概念

迭代分組密碼的加密流程

（由于網站對latax語法不太支持，為了讀者更好的”視覺體驗“，這里我用截圖了）

4輪 DES算法的差分分析

流程圖如下

我們記：

明文對和相應的差分記為(P,P*) 和 P’
密文對和相應的差分記為 (T,T*) 和 T’
明文左半部分、右半部分及其差分記為 (L,R) 和 (L’,R’)
密文左半部分、右半部分及其差分記為 (l,r) 和 (l’,r’)
第1、2、3、4輪函數的輸入和輸入差分依次記為 a,b,c,d 和 a’, b’,c’,d’
第1、2、3、4輪函數的輸出和輸出差分依次記為 A,B,C,D 和 A’, B’,C’,D’

4輪DES的差分分析本質上仍然是對S和的差分分析，

1.首先我們由密文對 T = (l,r), T* = (l*, r*),可以獲得第4輪輪函數的輸入對(r,r*)，進而也可以獲得8個 S 盒的輸入對（密鑰加之前的數據）為 (E(r),E(r*)); 簡單分析 S 盒針對差分的擴散特性以及拓展變換 E 的性質可知，第 4 輪輪函數的輸入差分 r’ 也即 d’ 經過拓展變換 E 后（成為 S 盒的輸入差分)，E(r’) 幾乎會讓 8 個 S 盒都活躍，即這個 8 個 S 盒的輸入差分都非0。

2.第 4 輪輪函數的輸出差分為 D’ = l’ ⊕ c’ = l’ ⊕ a’ ⊕ B’ ,其中 l’ = l ⊕ l*，已知。a’ = 00000000，B’ = P(*0000000)，其中 * 為未知的 4 比特向量，表示當第 2 輪輪函數中第一個 S 盒 S_1 的輸入差分為 04（由于拓展變換）時可能的輸出差分，未知。從而，第4輪輪函數中 8 個 S 盒的輸出差分為 P^{-1}(D’)=P^{-1}(l’ ⊕ P(*0000000)) = P^{-1}(l’) ⊕ (*0000000)，可求。故第四輪中S2,S3,S4, S5, S6, S7, S8 共 7 個S 盒的輸出差分均可求。

3.由上述兩個步驟我們可以建立對7個S 盒的差分分析模型，通過對S 盒的差分分析，我們可以恢復 7 × 6 = 42 bit 的輪密鑰，由密鑰拓展算法，其他 14 bit 的密鑰可通過窮盡搜索恢復。

上述攻擊中我們未能恢復第 4 輪中進入第一個 S 盒的密鑰，是因為它的輸出差分未知，因此我們可以選擇另外的明文差分，讓第二輪的輸入差分經過拓展變換后導致第 1 個 S 盒不活躍，即輸入差分為0，這樣我們就可求得第四輪中第 1 個 S 盒得差分輸出了。進而只用再窮盡搜索其他 8bit 密鑰。

好的，上面大部分是《分組密碼的攻擊方法與實例分析》書中的原話。現在，我再用通俗易懂的話來翻譯翻譯。（也就是講的再細一點啦）

筆者的“翻譯”

我們看到，首先我們構造差分 L’為 20000000 ，R’ 為 00000000，這沒什么問題，右下角的x腳標說明這是個十六進制表示，不過注意這里的L’,R’已經是IP 置換過后的了，不是明文差分 X’ 的左右兩部分哦，是IP(X’)的左右兩部分。

然后我們這些個差分進入第一輪，右邊的a’=00000000 進到 F 輪函數，由于是00000000，怎么線性非線性變換都沒所謂，先E 盒拓展，再輪密鑰加，最后出了S 盒也還是 00000000，再走一個P盒置換P(00000000)也還是 00000000。所以第一輪走完，左邊差分等于 A’ ⊕ L’=00000000 ⊕ 20000000=20000000，右邊還是原來的 a’=00000000

到了第二輪，這個輪函數的輸入是 b’ = A’ ⊕ L’=20000000，先先E 盒拓展，變成40000000，然后分為八組進入S 盒，顯然后面 7 組都是0，不會激活 S 盒，那出來還是0。（可能會突然疑惑，輪密鑰加呢？看到最上面的差分經過 F 函數各個組件的性質第一條，差分不受輪密鑰加的影響，所以后面也都不管它了）但是第一組是以差分為 4 進入 S 盒的，由于性質第三條，S 盒的輸出差分不確定，這與輸出差分有關，也與具體的輸出有關。所以，這一輪 S 盒的輸出差分為 *0000000，之后還得 P 盒置換，所以B’ = P(*0000000)。那么第二輪走完，左邊等于B’ ⊕ R’ = P(*0000000) ⊕ 00000000=P(*0000000)，右邊等于b’ = 20000000

開始第三輪，這一輪開始就要亂起來了。首先這個輪函數的輸入是 c’ = B’ ⊕ R’= P(*00000000)，我們看一下具體的 P 盒，

這里我們不確定的前四個bit被擴散到了第3，5，6，8組，也就是說現在我們的c’ = 00*0**0*，然后這里還要先E 盒拓展，看看 E 盒

那么進入S 盒前

可以看到，幾乎每一組都被”污染了“，只剩第5組還是 0 那么 C’ = ****0***，然后這里還有一個 P 盒置換，那么第三輪走完，左邊等于C’ ⊕ b’ = 20000000 ⊕ P(****0***)，右邊等于c’ = ****0***（注，這里 * 為不確定的意思，進入S 盒前的 * 大概率不等于出 S 盒后的 *）

到最后的第四輪了，此時進入 S 盒的是d’ = C’ ⊕ b’,萬幸只有四輪，所以d’ = r’,由于r’ 是可由最后的輸出密文右半部分求一個IP 逆置換而來，因此，d’ 已知。

我們直接計算d’ 可以發現 d’幾乎不會有 0 bit，也可以推一下，因為 d’ = P(****0***) ⊕ 20000000，而由于這個P 盒置換，第5組最終也會被”污染“，那么可以預見，每一組進入 S 盒的差分都被”污染“了，也就是說每一個 S 盒都會被激活。這也就是書中所說的簡單分析 S 盒針對差分的擴散特性以及拓展變換 E 的性質可知，第 4 輪輪函數的輸入差分 r’ 也即 d’ 經過拓展變換 E 后（成為 S 盒的輸入差分)，E(r’) 幾乎會讓 8 個 S 盒都活躍，即這個 8 個 S 盒的輸入差分都非0。

那么到此四輪DES分析完畢。其實也就說明了一個問題，進入第四輪的 S 盒的輸入會激活所有的 S 盒，然后進入第四輪 S 盒的輸入差分已知，從第四輪后面7個 S 盒出來的輸出差分可求，由此我們可以建立對這7個S 盒的差分分析模型以求出第四輪的輪密鑰。

接下來簡單講講具體怎么求。

首先拿到最后的輸出明文差分 Y’,首先對右半邊求 IP 逆置換得到 d’=r’，然后對其用 E盒做拓展置換。先打住，我們去求一下第四輪 S 盒的輸出差分P^{-1}(D’)

我們拿到輸出明文差分Y’,對做半邊求 IP 逆置換得到 l’ = c’ ⊕ D’,這個c’ = a’ ⊕ B’ = 00000000 ⊕ P(*00000000) ，

第四輪的輪密鑰會分為8組，分別和經過 E 盒拓展置換的 8 組輸入異或后最終進入 S 盒。這8組輸入差分在與輪密鑰異或前后是不會變的，但是我們再次強調前面提到過的第三條性質：S 盒：S(x) ⊕ S(x*) = y ⊕ y*，結果不確定，不僅與x ⊕ x* 有關，還與 x 有關。輸入的差分沒變，但是兩次輸入的具體值因為輪密鑰的異或，會發生變化。因此改變這里的輪密鑰，是會使得 S 盒的輸出差分受影響的。

但是呢，但是呢，我們不是已經知道輸出差分了么？啊哈，那么很顯然了，我們只要不斷地嘗試每個 S 盒那一組的輪密鑰——輪密鑰加，再 S 盒輸出差分，然后對比我們已知的輸出差分，如果匹配，則該輪密鑰放入待選集合。由于每個 S 盒只用到 6bit 輪密鑰，因此窮舉復雜度只有 7× 2^6，完全可以接受。然后會出現多解的情況。換一組具有相同差分（非必須，差分為40000000 00000000也可）的明文輸入，得到一個新的解集，再取交集即可。根據實際情況，一般取四對差分明文就能有很大概率解出 42 bit的輪密鑰。

然后現在有兩個選擇，一個是選擇復雜度為 2^{14} 窮舉，另一個是換一下差分，不要激活到第一個 S 盒就行。這樣就能恢復全部的48 bit密鑰，然后再進行復雜度為 2^8 的窮舉，兩種復雜度倒也都是能接受的。

有了48bit的輪密鑰后，我們知道密鑰拓展用的壓縮 P 盒

1.所以我們先根據 P 盒將 48 bit 的密鑰位置先還原，

2.剩下的空位再直接窮舉，最后得到56bit的輪密鑰，

3.然后根據輪密鑰生成的方式，將第四輪輪密鑰還原成最初的密鑰，

4.然后我們選取一對服務端生成的明文密文對，用我們的密鑰對明文進行加密，

5.觀察得到的密文是否與服務端生成的密文一致，若一致則得到正確密鑰，否則回到第二步。

至此，4輪DES差分就到此結束了。可以看到，還沒有用到概率論的知識，這是因為輪次比較少，前面我們分析的每一輪都是確定的，而等輪次增大到8輪以后就要開始引入統計分析與概率論了，取尋找概率較大的差分路徑，這才是差分分析的完全體。

Remark：前面我們提到，DES差分分析的關鍵就在于其S盒差分分布的不均勻特性，何為不均勻特性，即相同的差分進入S盒，輸出的差分是不均勻分布的。現在回頭來看看這句話應該就能理解了，如果S盒差分分布均勻，相同地輸入差分能夠得到相同的輸出差分，那么，我們就沒辦法去窮舉驗證我們的輪密鑰了，因為我們沒有了標準去區分密鑰的正確與否。

結語

差分分析入門篇到此告一段落，希望接下來能有進階篇叭，如果我學的會，能夠理解的話哈哈哈哈哈哈哈哈哈哈哈哈哈。