[Cryptography] DES筆記: meet in the middle attack

Meet in the middle attack是在cryptography攻擊上很常見的手法，概念上是把一系列的計算分成前半部份和後半部份，利用建立表格的方式，找到前半部份計算與後半部份計算相等的地方。



因為DES採用56 bits的key，因此先建立2⁵⁶種加密的結果，此為前半部份；然後在從2⁵⁶組合的key中來解密，此為後半部份，只要兩者相同，就可以找到所採用在Double DES的兩把keys。

而在花費的時間上，Double DES只要花費約2⁶³，因此被認為是不安全的，因為其結果並非DES的兩倍，並沒有因為採用Dobule DES而增加一倍的Time complexity。

但是在Triple DES，即使是meet in the middle attack，也要花費2¹¹⁸的時間，相較於Double DES，是被認可比較安全的加密方式。

來驗證一下Time complexity，因為是在2⁵⁶的table做sort，因此Time complexity是2⁵⁶ * log(2⁵⁶)。Double DES前半部和後半部都是2⁵⁶ * log(2⁵⁶)；而Triple DES前半部是2⁵⁶ * log(2⁵⁶)，後半部是2¹¹² * log(2¹¹²)，用底下的python來計算：

#!/usr/bin/env python
import math

# Meet in the middle attack
# 1. Double DES
Time_D = 2**56 * math.log(2**56, 2) * 2
Power_D = math.log(Time_D, 2)
print('The time of Double DES is 2^{}'.format(Power_D))

# 2. Triple DES
Time_T = 2**56 * math.log(2**56, 2) + 2**112 * math.log(2**112, 2)
Power_T = math.log(Time_T, 2)
print('The time of Triple DES is 2^{}'.format(Power_T))

可得結果如講義上所示。

而在第五週的作業中，老師也要求利用Meet in the middle的方式來破解Discrete log modulo a prime p。給定p, g, h，找x，最根本的方式就是用x=1, 2, ..., 2⁴⁰的方式，去求各個解。但用meet in the middle可以降低一半的Time complexity。

h = g^x in Z_p, 1 <= x <= 2⁴⁰

利用

x = x₀ * B + x₁, B=2²⁰

所以在計算上就可以轉換成

h = g^x = g^{x₀ * B + x₁} = (g^B)^x₀ * g^x₁ in Z_p

h/g^x₁ = (g^B)^x₀ in Z_p

因此，首先建立左半邊h/g^x₁的表格，x₁從0, 1, ...,2²⁰。

接著計算右半邊，找出與表格中相等，就可以得到x₀和x₁，就可以解出x。如以一來，就可以把Time complexity從2⁴⁰變成2²⁰。