差分密码分析

差分密码分析（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的抗攻击性也不尽人意。相比之下，差分分析在使用247数量级的选择明文后才能破解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）

## 参考[编辑]

1. ^ Biham and Shamir, 1993, pp. 8-9
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" （页面存档备份，存于互联网档案馆）

## 外部链接[编辑]

* 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）.

* 查
* 论
* 编

分组密码

常见加密算法|

* AES
* Blowfish
* DES（内部细节 · 3DES）
* Serpent
* Twofish

次常见加密算法|

* Camellia
* CAST-128（英语：CAST-128）
* IDEA
* RC2（英语：RC2）
* RC5
* SEED（英语：SEED）
* Skipjack（英语：Skipjack）
* TEA
* XTEA

其他加密算法|

* 3-Way（英语：3-Way）
* ABC（英语：ABC (cipher)）
* Akelarre（英语：Akelarre (cipher)）
* Anubis（英语：Anubis (cipher)）
* ARIA（英语：ARIA (cipher)）
* BaseKing（英语：BaseKing）
* BassOmatic（英语：BassOmatic）
* BATON（英语：BATON）
* BEAR and LION（英语：BEAR and LION ciphers）
* CAST-256（英语：CAST-256）
* CIKS-1（英语：CIKS-1）
* CIPHERUNICORN-A（英语：CIPHERUNICORN-A）
* CIPHERUNICORN-E（英语：CIPHERUNICORN-E）
* CLEFIA（英语：CLEFIA）
* CMEA（英语：Cellular Message Encryption Algorithm）
* Cobra（英语：Cobra ciphers）
* COCONUT98（英语：COCONUT98）
* Crab（英语：Crab (cipher)）
* Cryptomeria/C2（英语：Cryptomeria cipher）
* CRYPTON（英语：CRYPTON (cipher)）
* CS-Cipher（英语：CS-Cipher）
* DEAL（英语：DEAL）
* DES-X（英语：DES-X）
* DFC（英语：DFC (cipher)）
* E2（英语：E2 (cipher)）
* FEAL（英语：FEAL）
* FEA-M（英语：FEA-M）
* FROG（英语：FROG）
* G-DES（英语：GDES）
* GOST（英语：GOST (block cipher)）
* Grand Cru（英语：Grand Cru (cipher)）
* Hasty Pudding cipher（英语：Hasty Pudding cipher）
* Hierocrypt（英语：Hierocrypt）
* ICE（英语：ICE (cipher)）
* IDEA NXT（英语：Idea NXT）
* Intel Cascade Cipher（英语：Intel Cascade Cipher）
* Iraqi（英语：Iraqi block cipher）
* KASUMI（英语：KASUMI (block cipher)）
* KeeLoq（英语：KeeLoq）
* KHAZAD（英语：KHAZAD）
* Khufu and Khafre（英语：Khufu and Khafre）
* KN-Cipher（英语：KN-Cipher）
* Ladder-DES（英语：Ladder-DES）
* Libelle（英语：Libelle (cipher)）
* LOKI97（英语：LOKI97）
* LOKI89/91（英语：LOKI）
* Lucifer（英语：Lucifer (cipher)）
* M6（英语：M6 (cipher)）
* M8（英语：M8 (cipher)）
* MacGuffin（英语：MacGuffin (cipher)）
* Madryga（英语：Madryga）
* MAGENTA（英语：MAGENTA）
* MARS（英语：MARS (cipher)）
* Mercy（英语：Mercy (cipher)）
* MESH（英语：MESH (cipher)）
* MISTY1（英语：MISTY1）
* MMB（英语：MMB）
* MULTI2（英语：MULTI2）
* MultiSwap（英语：MultiSwap）
* New Data Seal（英语：New Data Seal）
* NewDES（英语：NewDES）
* Nimbus（英语：Nimbus (cipher)）
* NOEKEON（英语：NOEKEON）
* NUSH（英语：NUSH）
* Q（英语：Q (cipher)）
* RC6
* REDOC（英语：REDOC）
* Red Pike（英语：Red Pike (cipher)）
* S-1（英语：S-1 block cipher）
* SAFER（英语：SAFER）
* SAVILLE（英语：SAVILLE）
* SC2000（英语：SC2000）
* SHACAL（英语：SHACAL）
* SHARK
* SM4
* Speck
* Spectr-H64（英语：Spectr-H64）
* Square（英语：Square (cipher)）
* SXAL/MBAL（英语：SXAL/MBAL）
* Threefish（英语：Threefish）
* Treyfer（英语：Treyfer）
* UES（英语：UES (cipher)）
* Xenon（英语：Xenon (cipher)）
* xmx（英语：xmx）
* XXTEA
* Zodiac（英语：Zodiac (cipher)）

密码设计|

* Feistel网络
* 密钥调度（英语：Key schedule）
* 乘积密码
* S盒
* P盒
* 代换-置换网络
* 混淆與擴散
* 雪崩效应
* 密钥白化
* 密钥长度
* 块大小

攻击（密码分析）|

* 穷举攻击/蛮力攻击（EFF DES破解机）
* 中途相遇攻击（Biclique攻击（英语：Biclique attack） · 三子集中途相遇攻击（英语：Biclique attack））
* 线性密码分析（英语：Linear cryptanalysis）（堆积引理（英语：Piling-up lemma））
* 差分密码分析（不可能差分密码分析（英语：Impossible differential cryptanalysis））
* 截断差分分析（英语：Truncated differential cryptanalysis）
* 高阶差分分析（英语：Higher-order differential cryptanalysis）
* 差分-线性攻击（英语：Differential-linear）
* 区分攻击（英语：Distinguishing attack）（已知密钥区分攻击（英语：Known-key distinguishing attack））
* 积分密码分析（英语：Integral cryptanalysis）
* 回力镖攻击（英语：Boomerang attack）
* 模n密码分析（英语：Mod n cryptanalysis）
* 相关密钥攻击（英语：Related-key attack）
* 滑动攻击（英语：Slide attack）
* 回旋密码分析（英语：Rotational cryptanalysis）
* 計時攻擊（英语：Timing attack）
* XSL攻击（英语：XSL attack）
* 插值攻擊
* Partitioning（英语：Partitioning cryptanalysis）
* 戴维斯攻击（英语：Davies' attack）
* 回弹攻击（英语：Rebound attack）
* 弱密钥（英语：Weak key）
* 肯德尔等级相关系数（英语：Kendall tau rank correlation coefficient）
* 卡方检验
* 时间、内存、数据取舍攻击（英语：Time/memory/data tradeoff attack）

密码标准|

* 高级加密标准（AES）评选过程
* CRYPTREC（英语：CRYPTREC）
* NESSIE（英语：NESSIE）

工作方式|

* 初始向量
* 工作模式
* 填充

* 查
* 论
* 编

密码学

* 密码学历史
* 密码分析
* 密碼學主題列表

* 對稱密鑰加密
* 分组密码
* 流密码
* 公开密钥加密
* 密碼雜湊函數
* 訊息鑑別碼
* 随机数
* 隐写术

* 分类
* 主题
* 专题

*[查]: 查看该模板
*[论]: 讨论该模板
*[编]: 编辑该模板