Diffie Hellman 키 교환 알고리즘

AES와 같은 대칭키 암호는 암호화와 복호화에 사용되는 키가 같으므로 송신자와 수신자 모두 암호를 주고받기 전에 같은 키를 공유해야 한다. 따라서 데이터를 교환하기 전에 키 교환이 먼저 이루어져야 하는데 키 교환 과정에서 통신이 도청당하면 대칭키 암호는 무력화 된다. Diffie Hellman 키 교환 알고리즘은 통신이 도청당할 수 있는 공개된 환경에서도 키를 안전하게 교환할 수 있는 알고리즘이다.


Diffie Hellman은 이산 로그 문제를 이용한 알고리즘이다. 이산 로그 문제란 자연수 $a$, $m$, 정수 $b$에 대해서 $a^x \equiv b \pmod p$를 만족하는 정수 x를 구하는 문제이다. $p = 2^{127} - 1$이라 치면 $a$, $x$, $p$가 주어진 상태로 $b$를 구하라고 하면 단순히 $a^x \pmod p$를 계산하면 되고 임의의 합동 항등식에서 양변에 같은 값을 곱해도 식은 성립하기 때문에 square and multiply알고리즘을 이용해서 대략 $\log_2{x}$번 정도의 곱셈 연산만 하면 되지만 $b$값이 아닌 $x$의 값을 구하는 이산 로그 문제의 경우 현재까지 알려진 최선의 방법으로도 $\sqrt{p}$ 번 정도의 연산을 해야 하고 이정도 수치는 현대 컴퓨터로는 불가능한 수치이다.


Alice와 Bob이 서로 키를 교환한다고 하면 Diffie Helman의 키 교환 과정은

1. 먼저 공개키 $p$, $g$를 설정한다. ($p$는 소수이고 $1 \le g \le p-1$)

2. Alice는 $1 \le a \le p-1$을 만족하는 적당한 수 $a$를 정해서 $A = g^a \pmod p$를 Bob에게 전송한다.

3. Bob은 $1 \le b \le p-1$을 만족하는 적당한 수 $b$를 정해서 $B = g^b \pmod p$를 Alice에게 전송한다.

4. Alice는 Bob에게 받은 $B$를 이용해서 $B^a \pmod p$를 계산하고 Bob은 Alice에게 받은 $A$를 이용해서 $A^b \pmod p$를 계산한다.

5. $B^a \pmod p = (g^b \pmod p)^a \pmod p = g^{ab} \pmod p$이고 $A^b \pmod p = (g^a \pmod p)^b \pmod p = g^{ab} \pmod p$이므로 Alice와 Bob은 $g^{ab} \pmod p$을 키로 사용하게 된다.


이렇게 Diffie Hellman알고리즘을 이용해서 키를 교환하면 중간에 통신을 도청당하더라도 공개키인 $p$, $g$와 서로 통신이 오갔던 $A$, $B$까지만 알 수 있게 된다. $p$, $g$, $A$, $B$만 알고 있는 상황에서 $g^{ab} \pmod p$를 구하기 위해서는 비밀키 $a$, $b$중에 하나를 알고있어야 하고 비밀키를 얻으려면 $g^a \equiv A \pmod p$와 같은 이산 로그 문제를 풀어야 한다. 따라서 공격자는 키 교환 과정을 도청해도 키를 알아낼 수 없다.


이렇게 공개된 채널에서도 안전하게 키 교환을 할 수 있는 Diffie Hellman은 중간자 공격(Meet In The Middle Attack)에 취약하다. 중간자 공격은 줄여서 MITM이라고 부른다. Diffie Hellman은 단순히 도청만 한다면 안전한 알고리즘이지만 중간에 통신을 가로채서 변조할 수 있다면 얘기가 달라진다. Alice와 Bob에게 전달되는 $A$, $B$를 맘대로 조작할 수 있게 되니까 그냥 뚫리게 된다.

Diffie Hellman이 MITM으로 어떻게 뚫리는지는 아래 문제들을 풀어보면 바로 깨닫게 될 것이다.

https://dreamhack.io/wargame/challenges/120/

Textbook-DH

Cryptohack - Parameter Injection
Cryptohack - Static Client