差分密碼分析

差分密碼分析（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]