密码学/差分密码分析

差分密码分析是一种通用的密码分析方法，主要适用于分组密码，但也适用于流密码和密码散列函数。从广义上讲，它是研究输入差异如何影响输出结果差异的学科。对于分组密码，它指的是一组用于跟踪网络变换中差异的技术，发现密码在何处表现出非随机行为，并利用这些特性来恢复密钥。

历史

差分密码分析的发现通常归功于埃利·比汉和阿迪·沙米尔，他们在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，奥地利格拉茨