Meet In The Middle(MITM)

1. Meet In The Middle

중간에서 만나기는 공간복잡도와 시간복잡도를 교환하는 여타 다른 알고리즘과 비슷한 구조를 가지는 알고리즘으로 첫 시작은 암호 bruteforcing을 위해 만들어진 알고리즘이다. ( 영문 위키에서는 MITM attack으로 소개하고 있다.) 이는 다음과 같은 과정으로 시간적 측면에서 보다 더 효율적인 brute force 공격을 가능하게 한다.

키 길이가 $n$, $m$인 키로 이중으로 암호화된 암호 $C$가 존재할 때, 한 번에 $n$, $m$키 모두를 찾아 복호화하는 것은  $O(2^{n + m})$의 시간이 걸리게 된다. 하지만, 각 키를 따로 계산한다면 각 과정에서의 시간 복잡도는 $O(2^n)$, $O(2^m)$의 시간이 걸리므로 기존의 시간보다 많이 단축된다. 이것이 가능한 이유는 $D_{K_i}$를 키 $K_i$로 복호화를 진행하는 함수라 하고, $E_{K_i}$를 키$K_i$로 암호화를 진행하는 함수라고 할 때, 평문(암호화되지 않은 문장) $P$와 암호문 $C$에 대해 위 상황에서의 관계는 다음과 같이 나타낼 수 있다. $C = E_{K_n}(E_{K_m}(P))$ 이때, 암호화와 복호화는 1 대 1 대응이므로 $D_{K_n}(C) = E_{K_m}(P)$가 성립하게 되어 암호문과 평문의 대응을 알고 있는 경우, 키 값을 알기 위해 $K_n$과 $K_m$모두를 한 번에 구하는$O(2^{n + m})$의 연산을 진행하는 것보다 $K_n$과 $K_m$에 따른 키와 해당하는 암호문 값을 저장하며 각각 따로 계산하는 것이 더욱 시간적으로 효과적이게 된다. 그렇다면 메모리에는 어떤 형태로 키와 암호문의 대응값을 저장하는지 궁금할 수 있다. 이때는 hash table을 이용해 연산된 값 $D_{K_n}(C) = E_{K_m}(P)$ 을 키로 하고 $K_n$ 또는 $K_m$를 대응되는 값으로 저장하여 같은 문장이 나온 경우, 바로 해당되는 키 값들을 알 수 있게 된다.

2. 활용?

사실 이 방식은 다른 영역에서도 유용하게 활용될 수 있다! brute force를 좀 더 효과적으로 = 완전탐색을 좀 더 효과적으로 진행할 수 있게 만들어진 알고리즘이기 때문에,  모든 경우의 수를 계산하되 조건에 맞는 경우만 추려야 하는 문제에 효과적으로 사용될 수 있다. 물론, 검색을 진행한 뒤에 두 집단을 다시 순차적으로 검색하는 것은 시간 복잡도를 다시 $O(2^{n + m})$이 되게 하는 방법이며 오히려 실제 실행시간이 더 늘어나게 되므로 주의해야 한다. 

3. 여담

사실 brute force 방식으로 해결하는 경우는 생각보다 많이 드물다고 할 수 있다. 이러한 알고리즘은 특정한 상황에서만 효과적으로 사용될 수 있기 때문에 문제를 이 방식으로 해결할 수 있다고 해도 시간과 공간을 고려하여 좀 더 효과적인 방법이 있는지를 찾는 것이 중요할 것이다.