差分密碼分析

差分密碼分析（Differential cryptanalysis）是一種密碼分析的方法，主要用於破解分組加密，但也適用於流加密和加密雜湊函數。廣義上講，其研究的是資訊輸入上的差別對輸出結果變化的影響。對於區塊加密法，其指的是利用差異來取得金鑰的技術，包括跟蹤變換網絡中的差異，以及尋找加密中的非隨機行為等。

歷史

1980年代後期，誒利·比哈姆（英語：Eli_Biham）和阿迪·薩莫爾發表了一系列針對多個塊加密和雜湊函數的攻擊，包括對資料加密標準（DES）理論弱點的運用。因此，二者通常被認為是在公開領域中發現差分密碼分析的元勛，然而NSA在更早之前已發現該方法，但並未公開。比哈姆和薩莫爾表示，DES在抗差分密碼分析方面表現意外的好，不過只要對加密演算法稍加修改就能大幅減弱其抗攻擊能力。^[1]

1994年，IBM DES初始團隊的成員唐·庫帕史密斯（英語：Don_Coppersmith）發表論文稱，IBM早在1974年就發現了差分密碼分析法，並早已將抗差分分析納入演算法的設計目標中。^[2]作家史蒂芬·列維表示，IBM的確獨立發現了差分密碼分析方法，顯然NSA也知道這項技術。^[3]對於IBM選擇保密的原因，庫帕史密斯解釋道：「IBM與NSA商討後，認為若公佈加密演算法中抗差分密碼分析的設計，那麼差分密碼分析這種能攻擊多種加密演算法的強力技術就會被暴露，這將削弱美國在密碼學領域的領先優勢。^[2]IBM內部把差分分析稱為「T-attack」^[2]或「Tickle attack」。^[4]

與內建抗差分密碼分析的DES相比，同期其它加密演算法在這方面被證實是脆弱的。FEAL（英語：FEAL）是本分析方法的早期攻擊目標。原始的4輪版本（FEAL-4）可以在僅利用八個選擇明文的情況下被破解，且31輪版本的FEAL的抗攻擊性也不盡人意。相比之下，差分分析在使用2⁴⁷數量級的選擇明文後才能破解DES演算法。

攻擊原理

差分密碼分析通常是選擇明文攻擊，意思是攻擊者可以自行選取一部分明文並取得相應密文。不過，一些擴充也能讓此方法用在已知明文攻擊，甚至是唯密文攻擊上。差分分析的基本方法，是運用若干對有着常數差異的明文；差異可以用數種方法定義，最常見的是邏輯異或（XOR）。然後，攻擊者計算相應密文的差異，嘗試找出差異分佈的統計特徵。明文差異和密文差異所組成的差異對被稱為差分，其統計性質由加密所使用的S盒決定。也就是說，對於S盒子S，攻擊者分析差分(Δ_X, Δ_Y)，其中Δ_Y = S(X ⊕ Δ_X) ⊕ S(X)（⊕表示異或）。在初等攻擊中，攻擊者希望某個密文差異出現的頻率非常高，這樣就能將加密和隨機過程區分開來。更複雜的變體攻擊能做到比窮舉更快地破解出金鑰。

最基本的差分密碼分析金鑰破解形式中，攻擊者首先取得大量明文對的密文，並假設差分在至少r − 1輪後有效，r即加密演算法的總輪數。攻擊者在倒數第二輪與最後一輪之間差異固定的假設下，去推測可能的輪金鑰。如果輪金鑰比較短，那麼只需舉可能的輪金鑰，直到最後一輪運算結果和差異的密文對一致即可。當一個輪金鑰看起來明顯比其他金鑰常出現時，其會被假設是正確的輪金鑰。

針對特定的加密演算法，輸入差異要經過精心挑選才能使攻擊成功。這需要研究演算法的內部過程；標準的方法是在加密的不同階段，跟蹤一個高頻差異經過的路徑，術語上將這點稱為差分特徵。

自從差分密碼分析進入公眾視野，其就成了加密設計者的基本考量。新的加密設計通常需要舉證其演算法可以抗此類攻擊。包括AES在內的許多演算法都被證明在差分分析攻擊下是安全的。^{[來源請求]}

攻擊細則

攻擊主要依賴於一點：給定輸入/輸出，差異特徵僅在特定輸入下出現。這種方法通常用於線性結構組成的加密方式，如差表結構或S盒。給定兩個已知密文或明文後，觀察其輸出差異可猜測金鑰的可能值。

舉個例子，假設有一個差分：輸入的最低位的變化時，引起輸出最低的變化，記作1 => 1（代表輸入的最低有效位元 (LSB) 的差異導致 LSB 的輸出差異）發生的幾率為4/256，（可能在例如AES 密碼中使用非線性函數），則只有4 個值（或2 對）的輸入才可能有差分。假設我們有一個非線性函數，其中密碼在求值之前經過異或運算並允許差分的值為 {2,3} 和 {4,5}。如果攻擊者傳送了 {6, 7} 的值並觀察到正確的輸出差異，則說明金鑰是 6 ⊕ K = 2 或 6 ⊕ K = 4，表示金鑰 K 是 2 或 4。

變體

高階差分分析（英語：Higher-order differential cryptanalysis）
截斷差分分析（英語：Truncated differential cryptanalysis）
不可能差分密碼分析（英語：Impossible differential cryptanalysis）
回力鏢攻擊（英語：Boomerang attack）

另見

密碼學
線性密碼分析（英語：Linear_cryptanalysis）
密文不可區分性（英語：Ciphertext_indistinguishability）

參考

^ Biham and Shamir, 1993, pp. 8-9
^ ^2.0 ^2.1 ^2.2 Coppersmith, Don. The Data Encryption Standard (DES) and its strength against attacks (PDF). IBM Journal of Research and Development. May 1994, 38 (3): 243 [2018-07-15]. doi:10.1147/rd.383.0243. （原始內容存檔 (PDF)於2020-11-14）. (subscription required)
^ Levy, Steven. Crypto: How the Code Rebels Beat the Government — Saving Privacy in the Digital Age. Penguin Books. 2001: 55–56. ISBN 0-14-024432-8.
^ Matt Blaze, sci.crypt（英語：sci.crypt）, 15 August 1996, Re: Reverse engineering and the Clipper chip" （頁面存檔備份，存於互聯網檔案館）

外部連結

A tutorial on differential (and linear) cryptanalysis （頁面存檔備份，存於互聯網檔案館）
Helger Lipmaa's links on differential cryptanalysis
A description of the attack applied to DES. [2018-07-14]. （原始內容存檔於2007-10-19）.

[1] Biham and Shamir, 1993, pp. 8-9

[coppersmith-2] 2.0 ^2.1 ^2.2 Coppersmith, Don. The Data Encryption Standard (DES) and its strength against attacks (PDF). IBM Journal of Research and Development. May 1994, 38 (3): 243 [2018-07-15]. doi:10.1147/rd.383.0243. （原始內容存檔 (PDF)於2020-11-14）. (subscription required)

[3] Levy, Steven. Crypto: How the Code Rebels Beat the Government — Saving Privacy in the Digital Age. Penguin Books. 2001: 55–56. ISBN 0-14-024432-8.

[4] Matt Blaze, sci.crypt（英語：sci.crypt）, 15 August 1996, Re: Reverse engineering and the Clipper chip" （頁面存檔備份，存於互聯網檔案館）

[1]

[2]

[3]

[4]