[Crypto] 디피 헬만 (Diffie-Hellman) 알고리즘과 취약점

Intro

디피 헬만(Diffie-Hellman) 키 교환은 이산 로그(Discrete Log) 문제의 어려움에 기반한 키 교환 방식이다. 이 글에서는 디피 헬만 키 교환의 동작 원리와, 그리고 동작 과정에서 잘못 구현될 수 있는 부분들의 후보를 간략하게 나열함으로서 디피 헬만 알고리즘의 취약점을 공격하려는 초보 크립토그래퍼에게 도움을 주려고 한다.

작동 과정과 원리

디피 헬만 키 교환은 공개된 통신 위에서, 두 사람이 다른 사람은 알지 못하고 둘만이 아는 공유된 정보(Shared Secret)을 갖도록 하는 방법이다. 이 알고리즘을 이해하기 위해서는 간단한 대수적 지식이 필요하다.

기본적으로 덧셈과 곱셈이 정의되었을 때 모듈러 $n$에 대한 수의 집합 $0, 1, 2, \dots , n-1$은 환(Ring)을 이룬다(다시 말해, 덧셈과 곱셈에 대해 닫혀 있다). 이때 디피 헬만 키 교환은 $n$이 소수 $p$인 환 위의 수들을 사용하게 되는데, 이때 모듈러가 소수이면 0을 제외한 환의 모든 수 $x$에 대해서 서로소이기 때문에 $xy=1$을 만족하는 $y$가 존재하고 따라서 곱셈의 역원(multiplicative inverse)가 존재한다고 할 수 있다. 따라서 이 환은 체(Field)이기도 하고, 이를 $F_p$라고 쓴다. 이때 이 체에는 유한개의 원소가 들어있기 때문에 유한 체(Finite Field 혹은 Galois Field)라고 부른다.

이때 $F_p$의 임의의 원소 $g$는 무한히 제곱하면 부분군 $H = {g,g^2,g^3 \dots}$을 이루게 된다. 이런 원소들 중 일부는 $H=F_p$를 만족하는데, 다시 말해 이 경우에는 $F_p$의 임의의 원소를 $g^x \bmod p$로 쓸 수 있다. 이런 원소들을 우리는 원시근(primitive elements)라고 하고, Finite Field의 generator이라고도 한다. 조금 더 생각해보면, 이 경우에 0이 아닌 임의의 수 $t$에 대해 $t=g^x \bmod p$를 만족하게 하는 $x < p$는 유일하다는 것을 알 수 있다. $t$가 주어졌을 때 이 $x$를 구하는 것이 바로 이산 로그 문제이다. 이산 로그 문제를 푸는 방법은 여러 가지가 있지만, 특수한 경우가 아니라면 이산 로그 문제는 Baby Step Giant Step(BSGS) 알고리즘을 활용해서 기껏해야 $O(p^{0.5})$ 시간에나 풀 수 있다.

이 이산 로그 문제는 파라미터를 잘 골랐다는 전제 하에, 굉장히 풀기 어렵다. 따라서 이 문제를 풀기 어렵다는 것을 활용해서 비대칭 암호화를 시도할 수 있다. Alice와 Bob이 공개된 통신을 이용해서 둘만 아는 비밀 수를 하나 정하고 싶다고 하자. 먼저, Alice와 Bob은 상의를 통해 매우 큰 소수 $p$과 $F_p$의 generator인 $g$를 고른다. 원시근은 꽤 많기 때문에, 랜덤으로 수를 계속 정하면서 그 수가 원시근인지 체크해서 $g$를 정할 수 있다. 이 글 아래에서 언급하겠지만, 이 $p$는 일반적으로 역시 매우 큰 소수 $q$에 대해 $2q+1$ 꼴이 되는 것이 안전하다. 이 두 수는 외부에 공개되도 상관없다. 그 다음, Alice와 Bob은 각자 $p$보다 작으면서 적당히 큰 수 $a$과 $b$를 고른다. 이 두 수는 외부에 절대 공개되어서는 안 되며, $a$는 오직 Alice만, $b$는 오직 Bob만이 알고 있어야 한다. Alice는 Bob한테 $A = g^a \bmod p$를 보내고, Bob은 Alice한테 $B = g^b \bmod p$를 보낸다. 그 다음 Alice는 Bob으로부터 받은 $B$를 $a$제곱하여 $(g^b)^a \bmod p = g^{ab} \bmod p$를 만들고, Bob은 Alice로부터 받은 $A$를 $b$제곱하여 $(g^a)^b \bmod p = g^{ab} \bmod p$를 만든다. 그러면 Alice와 Bob 모두 $g^{ab} \bmod p$라는 공통된 수를 얻으며, 우리는 이를 Shared Secret라고 부른다.

그러면 이 과정은 암호학적으로 안전할까? 이 둘의 통신을 감청하고 있는 Eve가 있다고 해보자. Eve는 $p$와 $g$, 그리고 $A$와 $B$를 알고 있다. 그러나 Eve는 $g^{ab}$를 알 수 있는 방법이 전혀 없다. $A$와 $B$만 가지고 복원하는 것은 불가능하고, $g^{ab}$를 알기 위해서는 적어도 $a$를 알거나, $b$를 알아야 한다. 그래야 $A$ 또는 $B$를 그만큼 제곱해서 공유 정보를 얻어낼 수 있다. 그러나 $g^a \bmod p$나 $g^b \bmod p$로부터 $a$나 $b$를 얻어내는 것은 위에서 언급한 대로 $O(p^{0.5})$ 시간 정도가 필요한데, $p$를 2048비트 크기의 소수로 유지하는 것은 어려운 일이 아니므로 현실적으로 이 문제를 해결하는 것은 불가능하다고 할 수 있다. 따라서 디피-헬만 키 교환은 암호학적으로 안전하다. 이렇게 교환한 키를 가지고 나서는 안전성이 검증된 Block Cipher, AES 같은 기법을 사용하여 정보를 서로 교환할 수 있다.

취약점

디피-헬만 키 교환은 중간자 공격(Man In The Middle, MITM) 공격에 취약하다. 예를 들어 Eve가 단순히 통신을 감청하는 것이 아니라, 직접 개입해서 서로 주고받는 정보를 하이재킹할 수 있다고 가정해보자. 그러면 Eve는 Alice와 Bob이 서로 전달하는 $A$와 $B$의 값을 낚아채 둘 모두를 임의의 수 $g^t \bmod p$로 바꿀 수 있다. 그러면 Alice는 $(g^t) ^ a$를 Shared Secret으로, Bob은 $(g^t)^b$를 Shared secret으로 가지게 될 것이다. 이는 각각 $A^t$와 $B^t$와 같으므로, Alice와 Bob은 동일한 Shared Secret을 가지지 못하지만 Eve는 둘의 Shared Secret 값을 모두 알게 된다. 따라서 Eve는 Alice와 Bob이 서로 전달하려고 시도하는 메세지를 직접 해독해서 읽은 다음, 적절히 자신이 원하는 메세지를 만들어서 다른 사람한테 보낼 수 있게 된다.

또 문제에서 자주 등장하는 상황 중 하나는, 이러한 파라미터, 즉 $p$, $g$, $A$, $B$에 대한 적절한 검증이나 상호 협의가 보장되지 않은 경우이다. 간단하게 Bob이 검증 없이 Alice가 요구하는 파라미터 $p$와 $g$를 그대로 수용한다고 하자. 그러면 Eve는 중간자 공격을 통해 위에서 언급한 과정을 거칠 필요조차 없이 Alice가 보내는 $p$ 대신 1을 전달할 수 있고, 이러면 $b$를 알지 못하더라도 너무 쉽게 Shared Secret을 구할 수 있다. 아니면 Alice가 Bob한테 파라미터를 전달하는 과정을 낚아챈 다음 $g$에 $A$를 넣어버림으로서 Bob이 $g^b$를 계산해 $B$로 사용하는 대신 $g^{ab}$를 계산해 $B$로 사용하도록 유도할 수도 있다. 중간자 공격이 동반되는 상황에서는 공격자가 굉장히 많은 것들을 할 수 있다.

제일 중요한 것은 바로 Pohlig-Hellman 알고리즘이다. Pohlig-Hellman 알고리즘은 중국인의 나머지 정리를 바탕으로 cyclic group $G$의 order $n$을 소인수분해한 결과인 $\displaystyle n = \Pi_{i=1}^{r}p_i ^{e_i} $가 있을 때 $O(\sum_i e_i(\log n + \sqrt{p_i}))$ 시간복잡도에 이산 로그 문제를 해결해주는 알고리즘이다. 따라서 $p_i$의 최댓값이 작다면, 즉 $n$이 Smooth Number라면, 이산 로그 문제를 직접 해결함으로서 디피-헬만 키 교환의 안전성을 박살낼 수 있다. 따라서 디피 헬만 키 교환에서는 반드시 안전한 $p$를 사용해야 한다. 구체적으로는, $F_p$의 order은 $p-1$이므로 $p-1$이 smooth하지 않도록 하면 된다. 위에서 $p=2q+1$로 해야 한다는 이유가 바로 이것으로, 이렇게 $p$를 설정했을 때 $F_p$의 order은 $q$-smooth하기 때문에 Pohlig-Hellman 알고리즘에 안전하게 된다.