MITM variant No.OnE (partial matching)
在进行经典 MITM 时,大多数情况不能在中间匹配到等于分组长度的状态,即 往往不能满足。
所以更多情况下,往往只对分组长的部分比特进行匹配,也即部分匹配。
这是一种匹配的技巧,在中间相遇攻击中都会用到,如经典 MITM 的 MITM stage 中,步骤 2. 的得到的 的长度往往比分组长度小,但这样部分匹配也引发了一定的问题:
见经典 MITM NOTE 1. 匹配到的概率会变小,如果状态长度为 那么匹配到的概率就是 ,留下的密钥数量就是 ,在后面测试阶段就需要更多的明密文对来筛选候选密钥集。当然也可以利用并行搜索的办法,减少留下的候选密钥数量,并行 个明密文对来进行 MITM ,留下的密钥数量就是 ,MITM 阶段和测试阶段的操作没有实质性的变换,但复杂度需要重新考虑:
复杂度分析:
时间复杂度:并行 N 个明密文对,所以时间复杂度变为:
空间复杂度:同样的,并行 N 个明密文对,所以空间复杂度变为:
数据复杂度:MITM 阶段和测试阶段都使用了多个明密文对,取较大的作为数据复杂度量级: