一个玩具算法的差分攻击
算法概述
用流程图的形式来表示的话，看起来像这个样子（图中共有5轮）。
$m$ 作为明文，${k_0, k_1, \dots, k_n}$ 构成密钥。对于每一轮都通过三个操作来实现加密，分别为S盒混淆，置换混淆，轮密钥加。从算法来看，这样的确能够起到混淆的作用。不考虑明文分组只有 16 bits 的话，整个算法结构在初看之下坚不可摧。
但是事实真的是这样吗？突破口在哪呢？
第一点，像本文之前提到的，这个算法的明文分组只有 16 bits ，所以我们有一种最朴实的攻击思路， 穷举。所有明文的可能只有 $2^{16}$ 种，也就是说，我们可以在不超过一秒钟内，得到说有的明文-密文对，还需要密钥做什么。当然本文这里讲的是差分攻击，所以这一点我们默认没看到。
第二点，如果你的老板说不把密钥恢复出来就别想拿到这个月的工资，那又该怎么办呢？这就是差分攻击的 Show time 了。
差分攻击
概述
差分攻击广泛应用于破解密码算法，利用差分攻击，恢复 8 轮 DES 的密钥，只需要在普通 PC 上跑 2 分钟。差分攻击课堂上讲得很详细，互联网上也有很多文章，期中大部分在大中华局域网内也能访问到。所以我们不再赘述。（参考资料 [1] 中有师兄们很详细的介绍）
S盒特征
先来看看S盒的差分输入输出特征，行坐标是S盒的输入差分，列坐标是S盒的输出差分。
可以看到，输入差分-输出差分的分布并不均匀。例如，当输入差分为 0xf 时，输出差分为 0xd 的概率为 $10/16$。这就是差分攻击的突破点。
差分路径
当明文差分为 diff 时，第 r-1 轮结束后的中间结果差分为 guess_diff , 如果在密钥独立分布的情况下，对于某个 guess_diff_i 条件概率P(guess_diff_i | diff)足够大，那么 diff 和 guess_diff 就是一对好的差分起点和差分终点。为什么不说 diff 和 guess_diff 是一对好的差分对呢？因为起点和终点中间有不同的路径，我们关心的不是中间每一条路径的概率是多少，而是所有这些路径加起来的概率和是多少。
举个例子，对于上述算法，在 diff 为 (0 0 2 0) 的情况下，4轮之后 guess_diff为 (0 0 2 0) 最少有4条路径。
其中每一条的概率都是 ${(\frac{6}{16})}^4=\frac{81}{4096}$ ，四条路径的概率就是 $\frac{81}{1024} > \frac{1}{16}$。 所以我们设定 diff 为 (0 0 2 0)，guess_diff 也为 (0 0 2 0) 来恢复最后一轮的密钥。
但是，这样一条路径却只能恢复 4 bits 密钥，因为只有最后一轮密钥的第5~8位才对guess_diff有影响。所以，需要找到更多概率大于$\frac{1}{16}$的差分起点和终点。
怎么找呢？
活跃S盒
对于一个S盒，其输入差分为0，输出差分必为0。如果差分路径中出现这样的S盒(输入差分为0)，那么称之为“不活跃S盒”；反之(输入差分不为0)，称之为“活跃S盒”。对于一个差分路径，活跃S盒的数量越少，其差分概率越大。本文并不准备证明这一点。
所以我们把穷搜 diff 的时间复杂度从 $2^{16}$ 降到了 $C_{16}^{1} + C_{16}^{2}$ (即 $m$ 的输入差分最多只有 2 bits 为 1，其他位为 0)
攻击
投票
简述一下投票的过程：
对于一个固定的 diff 穷举所有可能的 $m_1$ 和 $m_2$ ( 使得 $m_1 \oplus m_2==diff$ )，这个过程的复杂度是$2^{16}$。
分别计算这些 $m_1$ 和 $m_2$ 的密文 $c_1$ 和 $c_2$ 。
猜测 guess_diff，这一步骤的复杂度在下文解释。
穷举最后一轮的密钥 key_guess，由于我们一次恢复 4 bits 密钥，所以这一步骤的复杂度是 $2^4$
对所有的 $c_1$ 和 $c_2$ ，用 key_guess 解密(一轮)，如果他们解密后的差分就是 diff_guess，则 $m_1$ (或 $m_2$)给 key_guess投一票
赢得最多票数的key_guess赢得选举成为总统 (雾
所以，恢复密钥最关键的步骤就是找到/猜到合适的 diff - guess_diff 对。
找 diff - guess_diff 对
寻找差分路径是差分攻击中最困难的事情，如果我们通过计算概率，来找概率最大的 diff - guess_diff ，这几乎是不可能的。因为种算法的复杂度随着层数指数增长，因此，我们不如试一试穷举。
对于每一轮，首先通过有先验知识得穷举 diff ，遍历 diff 有1~2个位为1其他位为0的所有情况 ( 正如在活跃S盒一节中提到的 )，找到合适的 diff - guess_diff 对。顺便一说，这个过程也是需要投票的，判断一个 diff - guess_diff 对是不是“好的”的唯一方法就是判断能不能通过这个对恢复出正确密钥。所以，我们对每一个 diff - guess_diff 对进行“选举”。一次投票的复杂度是 $$2^{16} * 2^4$$ ,对所有 diff - guess_diff 对投票的复杂度是
$$2^{4} * (C_{16}^{1} + C_{16}^{2}) * 2^{16} * 2^4$$
其中 $2^4$是 guess_diff 的穷举复杂度。这个复杂度是可以接受的，只需要几秒钟即可完成。甚至 ，我们只需要找到一组就可以停止搜索。
找到了 diff - guess_diff 对后，按照投票的思路就可以恢复最后一层密钥了。找到最后一层密钥，重复上述过程，即可恢复出除了 $k_0$ 以外的所有密钥。至于最后的 $k_0$ ，穷举一下就结束了。
攻击的攻击的完整复杂度是: $$(C_{16}^{1} + C_{16}^{2}) * 2^{16} * 2^4 * 2^2 * r$$ , r是轮数。
代码实现
https://github.com/Roarcannotprogramming/crypto_class/tree/master
参考资料
[1] https://blog.csdn.net/weixin_43255133/article/details/83719380