Bytes Dif(int x, Bytes d){ int kflag[64] = {0}; for (int i = 0; i < 64; i++) { kflag[i] = 1; } int cnt = 64; std::independent_bits_engine<std::default_random_engine, 64, Bytes> engine;
while (cnt > 1) { ... }
for (int i = 0; i < 64; i++) { if (kflag[i]) { return i; } } return-1; }
参数 x 表示现在对第几个 S 盒进行分析，d 则表示选定的输入差分。kflag 表示密钥空间，kflag[i] == 0 表示密钥 i 被排除，cnt 表示密钥空间的大小。此外我们还需要一个随机数发生器，这里我选择 independent_bits_engine 。
接下來来写每一轮迭代时对 S 盒的分析：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Bytes m1 = engine(); Bytes m2 = m1 ^ d; Bytes c1 = IP(Encrypt(FP(m1), 5)); Bytes c2 = IP(Encrypt(FP(m2), 5)); Bytes e = c1 ^ c2; Bytes L = d >> 32; Bytes l = e >> 32; Bytes r = e ^ l << 32; Bytes a1 = Block(Expand(c1 & ((1ULL << 32) - 1)), 6, x); Analyse(x, Block(Expand(r), 6, x), Block(ReP(l ^ L), 4, x), mflag); for (int i = 0; i < 64; i++) { if (kflag[i] && !mflag[a1 ^ i]) { kflag[i] = 0; cnt--; } }
这里边出现了几个函数，其中 engine 是调用随机数生成器生成一个 64 bit 的随机串；Encrypt 是一个自带密钥且只管加密的 DES ，参数 5 则表示进行 5 轮；Block 表示取某个 S 盒对应的块；Expand 是轮函数中的明文扩展算法；ReP 是 逆 P 盒；Analyse 则是对 S 盒的差分分析。它们的代码如下：
Bytes Block(Bytes a, int b, int x){ return a >> (7 - x) * b & ((1 << b) - 1); }
voidAnalyse(int x, Bytes a, Bytes b, int flag[]){ for (int i = 0; i < 64; i++) { if ((S(x, i) ^ S(x, i ^ a)) == b) { flag[i] = 1; } else { flag[i] = 0; } } }
其中 ReBox 是求逆盒数组的；Permutate 是位置换操作，具体代码可以在上一篇介绍 DES 的博客找到；Analyse 中的 flag 参数是数组引用，对它的任何修改都会反映到调用处的实参，也就是 mflag 上，我通过这种方式来在 c++ 中返回一个数组；Block 中则有大量位运算，不熟悉优先级的读者建议多查查优先级表。
聪明的读者们一定注意到了，DES 的有效密钥长度有 56 bit ，怎么才求出 48 bit 呢。这是因为密钥扩展算法将 56 bit 密钥分配到了每一轮 48 bit 的轮密钥里，因此我们还需要暴力枚举剩下的 8 bit 才能还原出所有密钥。我的做法是根据密钥扩展算法中 PC2 的盒，求出最后一轮密钥舍弃了哪 8 bit ，并用一个字节串 mask 表示。如果有一位弃掉了，就让 mask 这一位置 1 。然后 mask 和轮密钥同步逆序执行密钥扩展算法的过程。最后暴力枚举 0 到 255 ，把这些字节分配到 mask 所指示的字节，并与轮密钥或起来，就可以枚举缺失的 8 bit 密钥了。把使用这个密钥的 DES 和要进行破解的 DES 的加密结果比较就可以判断是否正确。
Bytes Distribute(Bytes a, int b[], int m, int n){ Bytes c = 0; for (int i = m - 1; i >= 0; i--) { c = c | ((a & 1) << (n - b[i] - 1)); a >>= 1; } return c; }
Bytes ReKeygen(Bytes final_key, int round){ final_key = RePC2(final_key); int loss[8] = {8, 17, 21, 24, 34, 37, 42, 53}; Bytes mask = 0; for (int i = 0; i < 8; i++) { mask = mask | 1ULL << (55 - loss[i]); } Bytes l = final_key >> 28; Bytes r = final_key ^ l << 28; Bytes mask_l = mask >> 28; Bytes mask_r = mask ^ mask_l << 28; int offset[16] = { 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1 }; for (int i = round - 1; i >= 0; i--) { l = Rotate(l, 28 - offset[i]); r = Rotate(r, 28 - offset[i]); mask_l = Rotate(mask_l, 28 - offset[i]); mask_r = Rotate(mask_r, 28 - offset[i]); } Bytes key = RePC1(l, r); mask = RePC1(mask_l, mask_r); int mask_list[8] = {0}; for (int i = 63, j = 0; i >= 0; i--) { if (mask & 1){ mask_list[j] = i; j++; } mask >>= 1; } Bytes guess_key = 0; for (int i = 0; i < 1 << 8; i++) { guess_key = Distribute(i, mask_list, 8, 64) | key; if (Encrypt(0x1234567890abcdefULL, 5) == DES(0x1234567890abcdefULL, guess_key, 0, 5)) { printf("Ye!\n"); printf("Key: %016llx\n", guess_key); return guess_key; } } return0; }
其中 Distribute 就是将猜测的 8 bit 密钥分配到 mask 指示的位置的；RePC1 和 RePC2 的写法和 ReP 一致；Rotate 是密钥扩展算法中的循环左移过程，代码可以在我上一篇讲 DES 的文章找到。
像这种在 r−1 轮差分区别器后再加一轮的攻击称为 1-R 攻击。如果在区别器后添加 t 轮进行攻击则叫做 t-R 攻击。
这里可能会有几个问题：
(1) 如何根据 β 确定有那些密钥可以破解呢？这个问题的思路和 5 轮攻击的思路是一样的，在对输出做逆 P 盒、对输入做明文扩展算法之后，每一个 S 盒的输入、输出以及对应的密钥都是相互独立的。如果 β 中有某一块差分可以确定（在正确对中），那么就能破解这一个 S 盒的密钥。利用这个特点也可以通过对 S 盒的差分分析来过滤错误对。
信躁比越大，正确密钥被统计的次数越多，这样就更能与其他密钥区分开，需要选择的明文数量就会变小。从公式中可以看出一个非常有用的信息，那就是提高攻击的信躁比的方法：提高攻击猜测的密钥量 l 、寻找更高概率的差分、以及降低 λ⋅ν （强度的定义是值越高，剩下的差分对越多）。至于明文对的数量，Biham 和 Shamir 在对 DES 进行大量分析后总结出如下结论：
当 S/N=1∼2 时，c 取 20∼40 。
当 S/N 取较大值，c 取 3∼4 。
当 S/N 取较小值，c 需要取更大值。
差分攻击还有许多理论上的细节，同样推荐想了解更多细节的读者阅读《分组密码的攻击方法与实例分析》。但现在我们已经知道了差分攻击的基本原理，可以尝试破解 8 轮 DES 了。
六、8 轮 DES 的差分攻击
对 8 轮 DES 的攻击也从选择差分路径开始。这次我们选择 (405C0000x,04000000x) 作为输入差分。它的差分路径和差分特征概率如图：
第一个问题是每次猜测 30 bit 的密钥量太大了，需要的储存空间约为 230⋅4Byte=4GB 。一个折中的方案是每次只猜 18 bit ，相应地提高选择的明文个数。我的实践经验是 218 个明文可以得到满意的结果。
第二个问题是每次枚举一整个密钥再解密，实际上有很多运算是浪费的。这是因为每一个 S 盒的加密都是独立的，一个 S 盒的加密结果和其他 S 盒组合多次之后就要重复计算多次。我的解决方案是先计算出每个 S 盒的加密结果，求出每个 S 盒的哪些密钥是满足要求的，然后再用 DFS 把满足要求的所有情况组合起来，并让计数器加 1 。
第三个问题是还原出 30 bit 密钥之后还需要再暴力枚举 18 bit 密钥才能得到 48 bit 轮密钥，然后再执行反密钥扩展算法枚举剩下的 8 bit 。这里每一次暴力枚举都是相互独立的，因此有多线程计算的优化空间。我的代码中使用了 8 线程，效果显著，并且可以根据处理器核心数手动调整。
voidDFS(int x, Bytes key, Bytes mask1, int block_cnt[8][64], int cnt[]){ if (x == 8) { cnt[key]++; return ; } if (!Block(mask1, 6, x)) { DFS(x + 1, key, mask1, block_cnt, cnt); return ; } for (int i = 0; i < 64; i++) { if (block_cnt[x][i]){ DFS(x + 1, key << 6 | i, mask1, block_cnt, cnt); } } }
Bytes Dif(Bytes d, Bytes D, Bytes mask, Bytes mask1){ int m_cnt = 1 << 18; int mask_cnt = 0; for (int i = 0; i < 8; i++) { if (Block(mask1, 6, i)) { mask_cnt+=6; } } int cnt[1 << mask_cnt] = {0}; std::independent_bits_engine<std::default_random_engine, 64, Bytes> engine; while(m_cnt --> 0) { Bytes m1 = engine(); Bytes m2 = m1 ^ d; Bytes c1 = IP(Encrypt(FP(m1), 8)); Bytes c2 = IP(Encrypt(FP(m2), 8)); Bytes e = c1 ^ c2; Bytes l = e >> 32; Bytes r = e ^ l << 32; Bytes b = ReP(l ^ D); Bytes a = Expand(r); if (!Check1(a, b, mask)) { m_cnt++; continue; } Bytes a1 = Expand(c1 & ((1ULL << 32) - 1)); Bytes a2 = Expand(c2 & ((1ULL << 32) - 1)); int block_cnt[8][64] = {0}; for (int i = 0; i < 8; i++) { if (!Block(mask1, 6, i)) { continue; } for (int j = 0; j < 64; j++) { if (!(S(i, Block(a1, 6, i) ^ j) ^ S(i, Block(a2, 6, i) ^ j) ^ Block(b, 4, i))) { block_cnt[i][j]++; } } } DFS(0, 0, mask1, block_cnt, cnt); } double ave = 0; for (int i = 0; i < 1 << mask_cnt; i++) { ave += cnt[i]; } ave /= 1 << mask_cnt; printf("Averange: %.3lf\n", ave); int mx = 0; for (int i = 0; i < 1 << mask_cnt; i++) { if (cnt[i] > cnt[mx]) { mx = i; } } for (int i = 0; i < 1 << mask_cnt; i++) { if (cnt[i] > cnt[mx] * 0.8) { printf("%d: %d\n", i, cnt[i]); } } returnMaskPermutate(mx, mask1, mask_cnt, 48); }
参数 d 表示 Feistel 结构的输入差分；参数 D 是差分路径中第 5 轮输出的右半部分，用来求出最后一轮的 S 盒输出差分；参数 mask 表示总共有哪些密钥比特需要破解，用法和反密钥扩展算法中的一样，如果第 i 个比特需要破解，那么 mask 的第 i 位就为 1 ；参数 mask1 则是本次运行所求的密钥比特。
函数中求最后一轮 S 盒差分对的代码和 5 轮攻击基本一致。接着只需用一个 block_cnt 来表示每个 S 盒中的哪些密钥符合要求。Block 函数的在这里的作用则是把 mask 对应位置的 bit 提取出来，来判断当前 S 盒是否需要分析。求得 block_cnt 后执行 DFS 函数组合所有可能的情况，并让计数器加 1 。最后还需要用一个标准来找出数量有明显优势的密钥。我的策略是找出计数器最大值，如果其它所有计数器都没有超过它的 80% ，那么就找到了密钥。
