密码学/中间相遇攻击

一种极其专业的攻击，中间相遇攻击是一种已知明文攻击，它只影响特定类型的加密方法 - 那些通过使用一个或多个“轮次”的普通对称加密算法来实现更高安全性的方法。 3DES 就是这种复合系统的一个例子。

但是，为了解释这种攻击，让我们从一个更简单的系统开始，定义如下：两个密码系统，分别表示为 $encrypt_{\alpha }$ 和 $encrypt_{\beta }$（其逆函数分别为 $decrypt_{\alpha }$ 和 $decrypt_{\beta }$）被简单地组合起来（通过先应用一个，然后应用另一个）来形成一个复合密码系统。 每个系统都接受一个 64 位密钥（用于从 0 到 18446744073709551615 的值），我们可以称之为 $key_{\alpha }$ 或 $key_{\beta }$，具体情况视情况而定。

所以，对于给定的明文，我们可以计算出密文，如下所示：

$cryptotext=encrypt_{\beta }(key_{\beta },encrypt_{\alpha }(key_{\alpha },plaintext))$

相应地：

$plaintext=decrypt_{\alpha }(key_{\alpha },decrypt_{\beta }(key_{\beta },cryptotext))$

现在，鉴于每个系统都有一个 64 位密钥，用于加密或解密所需的密钥量为 128 位，因此简单的分析将假设这与 128 位密码相同。

但是，如果拥有足够的存储空间，可以将这种有效密钥强度降低到比所使用的两个密钥中的较大密钥大几位，如下所示。

1. 给定明文/密文对，将 $encrypt_{\alpha }$ 应用于明文，并依次使用每个可能的密钥，生成 $2^{64}$ 个中间密文 $cryptotext_{1}$$\rightarrow$$cryptotext_{n}$，其中 $n=2^{64}$
2. 将每个 $n$ 密文存储在哈希表中，以便可以通过其密文引用每个密文，并给出用于生成该密文的密钥。
3. 将 $decrypt_{\beta }$ 应用于密文，依次尝试每个可能的密钥，并将中间明文与之前计算的哈希表进行比较。这将得到一对密钥（用于两种算法中的每一种，$\alpha$ 和 $\beta$）。
4. 使用第三阶段的两个密钥，针对第二对明文/密文测试每个密钥。如果也匹配，则极有可能拥有消息的有效密钥对 - 并非在 $2^{128}$ 次操作中，而是在“仅仅” $2x2^{64}$ 次操作中（尽管由于哈希表操作，这些操作明显更长，但并没有增加任务复杂度超过几个额外的位）。

这种方法的缺点是存储空间。假设使用64位密钥，那么至少需要 $2^{64}$ 个存储单位 - 其中每个单位是单个哈希记录所占用的存储空间。即使使用最小的实现（例如，密钥 64 位加上 4 位哈希冲突开销），如果使用 160GB 硬盘来实现这样的系统，也需要近十亿个硬盘来存储哈希表本身。