密碼學/差分密碼分析

差分密碼分析是一種通用的密碼分析方法，主要適用於分組密碼，但也適用於流密碼和密碼雜湊函式。從廣義上講，它是研究輸入差異如何影響輸出結果差異的學科。對於分組密碼，它指的是一組用於跟蹤網路變換中差異的技術，發現密碼在何處表現出非隨機行為，並利用這些特性來恢復金鑰。

歷史

差分密碼分析的發現通常歸功於埃利·比漢和阿迪·沙米爾，他們在20世紀80年代後期發表了針對各種分組密碼和雜湊函式的攻擊，包括資料加密標準（DES）的理論弱點。Bamford 在《謎宮》中指出，DES 對差分密碼分析具有驚人的抵抗力，因為即使對演算法進行微小的修改也會使其更容易受到攻擊。

1994年，IBM DES 團隊的原始成員唐·科珀史密斯發表了一篇論文，指出IBM早在1974年就瞭解差分密碼分析，並且抵禦差分密碼分析一直是設計目標。 根據作家史蒂文·萊維的說法，IBM 自己發現了差分密碼分析，而國家安全域性顯然也意識到了這種技術。 IBM 保留了一些秘密，正如科珀史密斯解釋的那樣：“在與國家安全域性討論後，我們決定不公開設計考慮因素，因為這會洩露差分密碼分析技術，這是一種可以針對許多密碼使用的強大技術。這反過來會削弱美國在密碼學領域相對於其他國家的競爭優勢。” 在IBM內部，差分密碼分析被稱為“T攻擊”或“撓動攻擊”。

雖然DES的設計考慮了對差分密碼分析的抵抗力，但其他同時代的密碼被證明容易受到攻擊。FEAL 分組密碼是該攻擊的早期目標。最初提出的四輪版本（FEAL-4）可以使用僅八個選定的明文進行破解，即使是 31 輪版本的 FEAL 也容易受到攻擊。

攻擊機制

差分密碼分析通常是一種選擇明文攻擊，這意味著攻擊者必須能夠獲得他選擇的某些明文集的加密密文。該方案可以成功地用大約 2⁴⁷ 個選定的明文來對 DES 進行密碼分析。但是，也有一些擴充套件可以允許已知明文甚至僅密文攻擊。基本方法使用由常數差值相關的明文對；差值可以透過多種方式定義，但異或 (XOR) 運算很常見。然後攻擊者計算相應密文的差值，希望檢測其分佈中的統計模式。得到的差值對稱為差分。它們的統計特性取決於用於加密的 S 盒的性質，因此攻擊者分析差分 $(\Delta _{X},\Delta _{Y})$，其中 $\Delta _{Y}=S(X)\oplus S(X\oplus \Delta _{X})$（並且 $\oplus$表示異或）對於每個這樣的 S 盒 $S$。在基本攻擊中，預期一個特定的密文差異特別頻繁；透過這種方式，可以將密碼與隨機性區分開來。更復雜的變體允許以比窮舉搜尋更快的速度恢復金鑰。

在透過差分密碼分析恢復金鑰的最基本形式中，攻擊者請求大量明文對的密文，然後假設差分至少對 r-1 輪有效，其中 r 是總輪數。然後攻擊者推斷出哪些輪金鑰（對於最後一輪）在假設最後一輪之前的塊之間的差異是固定的情況下是可能的。當輪金鑰較短時，這可以透過簡單地用每個可能的輪金鑰對密文對進行一輪窮舉解密來實現。當一個輪金鑰被認為是潛在的輪金鑰的次數明顯多於任何其他金鑰時，則假設它是正確的輪金鑰。

對於任何特定密碼，如果攻擊要成功，必須仔細選擇輸入差異。對演算法的內部進行分析；標準方法是跟蹤透過加密各個階段的高機率差異路徑，稱為差分特徵。

自從差分密碼分析成為公開知識以來，它已成為密碼設計人員的基本關注點。預期新設計會伴隨著證明演算法對這種攻擊具有抵抗力的證據，並且許多演算法，包括高階加密標準，都已被證明對這種攻擊具有安全性。

參考文獻

• 埃利·比漢，阿迪·沙米爾，資料加密標準的差分密碼分析，施普林格出版社，1993年。 ISBN 0-387-97930-1，ISBN 3-540-97930-1。
• 比漢，E. 和沙米爾，A. (1990)。DES 類密碼系統的差分密碼分析。密碼學進展——CRYPTO '90。施普林格出版社。2–21。
• 埃利·比漢，阿迪·沙米爾，“完整16輪DES的差分密碼分析”，CS 708，CRYPTO '92 論文集，計算機科學講義第740卷，1991年12月。 (Postscript)
• 埃利·比漢，來自“如何產生差異：差分密碼分析的早期歷史”PDF (850 KB)，2006年3月16日，FSE 2006，奧地利格拉茨