如何将差分密码分析应用于分组密码？

Question

我读过很多关于块密码的摘要，特别是关于NIST竞赛的摘要，指出减少的圆形块密码(例如)容易受到差分密码分析的影响。

我有一个总体想法，即差分密码分析的应用是查看输入之间的差异；维基百科使这一点相当清楚。但是，对于任何给定的分组密码，我可以接受任意两个输入，而且我非常肯定，我会盯着随机差异。

• 我知道这是一个写得很好的分组密码的想法；然而，假设一个破的或易受攻击的密码(尽管可以提供简单的例子)，我应该如何选择差异来尝试呢？
• 在算法设计中是否有任何线索可以帮助您决定选择哪些值？
• 在野外，易受差分密码分析影响的密码是什么？
• 如果我所有的区别是已知的纯文本和已知的键作为我的分析和捕获的密文作为我的数据可以利用，我能实际推断什么呢？

Answer 1

基本上，它是通过寻找输入数据和输出数据之间的差异来分析密码的。理想情况下，输入数据(明文)的细微差别，即使是一位，也会产生完全不同的文本。然而，如果密码设计不好，可能会观察到这两个结果的密码文本之间的相关性。反过来，这种相关性也可能被用来找出关键。这显然需要选择明文攻击；这意味着攻击者应该能够访问加密机制，从而使用它加密他或她所选择的任意数量的明文。因此，这种攻击通常被应用于那些可以使用但不能掌握钥匙本身的防脾气硬件。

根据AES，请参阅关于差分密码分析的维基百科文章的摘录：

例如，如果1 => 1的微分(暗示输入LSB中的LSB的差异导致LSB中的输出差)发生，则概率为4/256 (例如，用AES密码中的非线性函数可能发生)，那么只有4个值(或2对)的输入是可能的。假设我们有一个非线性函数，其中键在求值之前是XOR‘’ed，允许微分的值是{2,3}和{4,5}。如果攻击者发送的值为{6，7}，并观察到正确的输出差，则意味着密钥为6 xor K=2或6 xor K= 4，这意味着密钥为K= {2,4}。从本质上讲，对于n位非线性函数，人们最理想的是寻求尽可能接近2-(n-1)，以实现微分均匀性。当发生这种情况时，差异攻击所需的确定键的工作量与强制键的蛮力一样多。

以下是热身的几个链接：

• 一种简化的AES算法及其线性和差分密码分析
• 迷你俄歇的不可能差分密码分析
• AES的低复杂度差分密码分析与故障分析

这里有几篇关于这个主题的更好的文章：

• 线性和微分密码分析教程
• 差分侧信道密码分析的随机模型

不是最高质量的链接，特别是不像你所期待的那样以实践为导向，但我认为最后两个可能会让你对这个主题有一点把握。

Answer 2

一个关于差分密码分析的好教程可以在斯丁森的书中找到，他在书中对简化的圆DES进行了不同的攻击。他给出了攻击4轮DES (相对容易)和6轮DES (相当困难)的详细信息，这足以让人直观地知道为什么将攻击扩展到完整的DES (即16轮)需要如此多的PT/CT对和这么多的计算量(最好在这一点上进行彻底的密钥搜索)。

Biham和Shamir关于差分密码分析的原始著作是以一本书的形式出版的；他们破译了几个著名的密码(在写这本书的时候是众所周知的)。然而，上一次我看他们的书是绝版的，只有一大笔钱才能买到。