概述?

中间相遇攻击是一种以空间换取时间的一种攻击方法，1977 年由 Diffie 与 Hellman 提出。从个人角度看，者更多地指一种思想，不仅仅适用于密码学攻击，也适用于其他方面，可以降低算法的复杂度。

基本原理如下

假设 E 和 D 分别是加密函数和解密函数，k1 和 k2 分别是两次加密使用的密钥，则我们有

C=Ek2(Ek1(P))C=Ek2(Ek1(P))

P=Dk1(Dk2(C))P=Dk1(Dk2(C))

则我们可以推出

Ek1(P)=Dk2(C)Ek1(P)=Dk2(C)

那么，当用户知道一对明文和密文时

1. 攻击者可以枚举所有的 k1，将 P 所有加密后的结果存储起来，并按照密文的大小进行排序。
2. 攻击者进一步枚举所有的 k2，将密文 C 进行解密得到 C1，在第一步加密后的结果中搜索 C1，如果搜索到，则我们在一定程度上可以认为我们找到了正确的 k1 和 k2。
3. 如果觉得第二步中得到的结果不保险，则我们还可以再找一些明密文对进行验证。

假设 k1 和 k2 的密钥长度都为 n，则原先我们暴力枚举需要 O(n2)O(n2)，现在我们只需要 O(nlog2n)O(nlog2n)。

这与 2DES 的中间相遇攻击类似。

题目?

• 2018 国赛 Crackmec，参见 Wiki AES 部分
• 2018 Plaid CTF Transducipher，参见比特攻击部分的原理。
• 2018 国赛 Crackme java，参见 Wiki 整数域上的离散对数部分
• 2018 WCTF RSA，参见 wiki RSA Complex 部分

参考文献?

• https://zh.wikipedia.org/wiki/%E4%B8%AD%E9%80%94%E7%9B%B8%E9%81%87%E6%94%BB%E6%93%8A