中间相遇攻击 - MITM

概述

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

基本原理如下

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

$C=E_{k_2}(E_{k_1}(P))$

$P=D_{k_1}(D_{k_2}(C))$

则我们可以推出

$E_{k_1}(P)=D_{k_2}(C)$

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

1. 攻击者可以枚举所有的 k1，将 P 所有加密后的结果存储起来，并按照密文的大小进行排序。

2. 攻击者进一步枚举所有的k2，将密文 C 进行解密得到 C1，在第一步加密后的结果中搜索 C1，如果搜索到，则我们在一定程度上可以认为我们找到了正确的 k1 和 k2。

3. 如果觉得第二步中得到的结果不保险，则我们还可以再找一些明密文对进行验证。

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

这与 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