[대칭키 암호 공격] Meet-In-The-Middle Attack

▶ 3중 DES의 등장

DES 암호가 등장한 이후, 3중 DES가 등장했다. 2개의 키를 갖는 3중 DES, 3개의 키를 갖는 3중 DES 두가지 버전이 있다(DES-EDE2, DES-EDE3). 3중 DES는 암호화, 복호화, 암호화 순서를 거친다. k1,k2,k3 키를 총 3개를 넣을 경우의 3중 DES의 구조는 아래 그림과 같다.

 

3중 DES의 구조

 

키를 2개넣는 경우는 간단히 k1,k2,k1 순으로 넣는다. 참고로 Feistel 구조의 암호는 암호화과정과 복호화 과정이 같다.

설계 상으로는 키를 2개 사용하는 DES는 brute force 공격 시 경우의 수는 2^2n(키의 길이)이다. 하지만, Meet-in-the-Middle Attack을 적용하면 경우의 수가 2^(n+1)로 확연하게 줄어버린다.

 

---

 

▶ Meet-in-the-Middle Attack

분류 상 Meet-in-the-Middle Attack은 기지평문공격(Known Plaintext Attack : KPA)에 속한다. 공격자는 평문과 암호문의 쌍들을 알고 있어야 공격을 행할 수 있다. 같은 알고리즘과 두개 이상의 키를 사용하는 암호를 공격할 때 활용할 수 있다. 그 대표적인 예가 3DES, 즉, 3중 DES이다. 

해당 공격을 수행할 수 있는 대표적인 두가지 암/복호화 알고리즘을 보면 다음과 같다.

    C = Eb(kb, Ea(ka, P))
    P = Da(ka, Db(kb, C))

이러한 암/복호화 알고리즘에서 다음과 같은 수식이 성립한다:

   Db(kb, C) = Ea(ka, P)

여기서 C,P 쌍은 이미 공격자가 알고 있다는 상황에서 시작한다(기지 평문 공격). 즉, 공격자는 b알고리즘으로 복호화하는 암호문과, a알고리즘으로 암호화하는 평문을 이미 알고 있다. 

공격에서 첫번째로 할 일은 수식의 한쪽에서 가능한 모든 값을 테이블로 구성하는 것이다. 즉, 한쪽에서는 기지평문(P)을 통해서 Ea(ka, P) 수식으로 만들어질 암호문의 모든 값을 계산한다. 따라서, Table의 row 수는 가능한 키값의 경우의 수가 된다. 

두번째로 할 일은 반대쪽 수식의 가능한 모든 값을 테이블로 구성하는 것이다. 즉, 반대쪽의 암호문(C)을 통해서 Db(kb, C) 수식으로 만들어질 평문의 모든 값을 계산한다. 그리고 이전에 구성한 Table의 값과 비교한다. 그렇게 공격자는 해당 공격을 통해 Ea(ka, P) 수식과 Db(kb, C) 수식의 ka,kb 쌍을 찾게 된다.

 

출처 : http://www.crypto-it.net/eng/attacks/meet-in-the-middle.html

 

즉, DES-EDE2에서 Brute force attack을 수행할 때, 경우의 수가 2^2n이 아닌, 2^(n+1)이 되는 이유는 Meet-in-the-Middle Attack 으로 경우의 수가 확연히 줄 수 있어서 그렇다. 

원본글을 보면 조금 더 자세히 (심지어 해당 알고리즘의 복잡도까지) 설명해놨으니, 원본을 참고하면 더 자세히 알 수 있을 것 같다.

 

 

 

출처 : http://www.crypto-it.net/eng/attacks/meet-in-the-middle.html