EN | ZH

中间相遇攻击 - MITM

概述

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

基本原理如下

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

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

P=D_{k_2}(D_{k_1}(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 部分

参考文献


评论