Diffie-Hellman Key Exchange - 공개된 정보만으로 secret key 만들기

네트워크상의 두 노드가 암호화된 통신을 하기 위해선 먼저 두 노드가 어떤 암호화 방식으로 어떤 키를 이용해서 암호화할지 합의해야 한다. 보통 암호화 방식은 사용하는 애플리케이션에 따라 고정된 방식을 사용하거나 두 노드가 처음 통신을 시작할 때 암호화하지 않은 패킷을 이용해 합의하거나 한다. 이후 패킷은 양쪽 노드밖에 모르는 암호키를 이용해 암호화할 것이기 때문에 암호화 방식은 암호화되지 않은 방식으로 합의를 해도 안전하다. 하지만 어떤 키를 사용할지는 암호화되지 않은 방식으로 합의해선 안 된다. 키가 공개되면, 이 비밀키를 이용해서 제삼자가 패킷을 위조할 수 있기 때문이다. 그렇다면 이 비밀키는 어떻게 안전하게 교환할 수 있을까?

이에 대한 해답으로 나온 것 중 하나가 Diffie-Hellman key exchange(a.k.a. DH)다. 사실 이외에도 다른 방법들이 많이 있지만, 개인적으로 생각하기에 가장 범용적으로 안전하게 사용할 수 있는 것은 DH라고 생각한다. 또한, 이후 이것에 대해 많은 변종이 나왔지만, DH만 이해하면 나머지는 이해하는 데 별문제 되지 않는다. 그렇다면 DH는 어떻게 동작할까?

우선 DH가 성립하기 위해서는 특별한 수학적 성질을 만족하는 generator가 필요하다. 이 generator는 하나의 입력을 받아 하나의 출력을 내뱉는다. 이 generator가 $g$라고 하고, 입력 $x$에 대해서 출력 $Y$를 내뱉는 $Y=g\left(x\right)$가 있을 때, $x$로부터 $Y$를 가지고 오는 것은 빠르고 쉽게 계산할 수 있지만, $Y$로부터 $x$를 가지고 오는 것은 어려운 일이어야 한다. 즉, 수학적으로는 역함수가 없는 함수여야 하고, 결괏값의 스페이스가 매우 커서 brute-force로 찾는 것이 매우 힘들어야 한다. 사실 이외에도 만족해야 할 수학적 성질이 여러 개 있지만 이번 포스팅에서는 그에 대한 설명은 생략하고 넘어가겠다.

DH가 처음으로 제시한 방법은 generator로 modular exponentiation을 사용했다. modular exponentiation에서는 입력을 $x$라고 했을 때, 출력 $Y$를 다음과 같이 계산한다. . 이때 $b$와 $m$은 적절한 수학적 성질을 만족하는 값으로, $b$와 $m$의 pair가 generator $g$가 된다.

이후 여러 변종이 나왔고, 요새 많이 사용되는 것은 elliptic curve를 이용하는 Elliptic-curve Diffie–Hellman(a.k.a. ECDH)이다. 이 경우 사용하는 곡선의 종류가 generator $g$가 된다.

어떤 generator를 사용할지 결정되고 나면 DH는 다음의 과정을 거쳐서 진행된다.

	Alice	Bob	Eve
1	G	G	G
2	a	b
3	A=G(a)	B=G(b)
4	B	A	A, B
5	s=B(a)	s=A(b)

우선 위의 표를 설명하자면, Alice와 Bob은 서로 통신하기 원하는 사용자고, Eve는 Alice와 Bob 사이에 무슨 내용을 통신하는지 알기 원하는 도청자다. Alice와 Bob은 공개된 공간에 있기 때문에 둘 사이의 통신하는 내용은 제삼자인 Eve도 알 수 있다. 그리고 위의 표에서 푸른색으로 표시된 문자는 자신이 생성한 데이터고, 붉은색으로 표시된 문자는 다른 사람이 생성하여 통신을 통해서 듣게 된 데이터다. 또한, 대문자와 소문자도 다른 의미를 가지는데, 대문자는 외부에 공개해도 되는 public 한 데이터고, 소문자는 자신만 알고 있어야 하는 private 한 데이터다. 따라서 붉은색 데이터는 모두 Eve도 알게 되고, 붉은색 데이터와 푸른색 데이터를 조합하여 Alice와 Bob은 알지만, Eve는 모르는 데이터를 만드는 것이 DH의 목적이다.

1

G

G

G

우선 첫 단계는 어떤 generator를 사용할지 결정하는 단계다. generator를 결정하는 단계도 여러 방법으로 구현할 수 있지만 그다지 중요한 내용은 없으니 이번 포스트에서는 결정됐다고 가정하고 넘어가도록 하겠다.

2

a

b

다음 단계에서 Alice와 Bob은 각자 private key를 만든다. 이 private key를 어떻게 만드는가는 DH에서 중요한 요소가 아니지만, replay 공격을 막기 위해 private key는 랜덤하게 생성하는 것이 좋다.

3

A=G(a)

B=G(b)

그리고 Alice와 Bob은 generator $G$를 이용해서 각자 public key를 생성한다. 여기까지 진행되면 Alice와 Bob은 자신의 private key와 public key만 알고 있고, Eve는 아무 키도 모르고 있는 상태가 된다.

4

B

A

A, B

다음 단계는 Alice와 Bob이 각자 자신의 public key를 말하는 단계다. 이 단계를 지나면 Alice와 Bob의 public key 두 개는 Eve를 포함한 모든 사람이 알고 있는 정보가 된다.

5

s=B(a)

s=A(b)

다음 단계에서 Alice는 Bob의 public key를 기반으로 generator를 만들어 자신의 private key를 사용하여 secret key를 만들고, Bob은 Alice의 public key를 기반으로 generator를 만들어 자신의 private key를 사용하여 secret key를 만든다. 이때 public key를 사용해서 generator를 만드는 것은 어떤 generator를 사용하는가에 따라 다르다. modular exponentiation을 사용하는 경우 $m$는 기존의 generator의 $m$을 그대로 사용하고, 새로 받은 public key를 $b$로 사용한다. elliptic curve를 사용하는 경우 타원 곡선은 그대로 사용하고, public key를 시작점으로 계산한다.

어쨌든 전달받은 public key를 기반으로 generator를 만들어 자신의 private key를 input으로 만들면, 그 결과 나온 secret key는 놀랍게도 Alice와 Bob이 같은 값을 가지게 된다. 이는 아까 설명을 생략했던 generator의 몇 가지 수학적 성질 중 하나 덕분에 가능한 것이다. 이 secret key $s$를 알기 위해서는 최소 한 개의 private key가 필요하므로 Eve는 secret key $s$를 알 수 없다. 이제 Alice와 Bob은 공유하지만, Eve는 모르는 값이 생겼으니, 이후 메시지는 전부 secret key s를 이용해서 암호화하면 된다.

이상이 Diffie-Hellman Key Exchange를 이용하여 두 노드가 안전하게 비밀키를 만들어 공유하는 방법을 설명하였다. 사실 DH를 직접 구현해야 할 경우는 거의 없다. 하지만 네트워크 통신의 기본이 되는 내용이고, 많은 프로토콜이 컨넥션을 시작하는 단계에서 DH를 사용하기 때문에 서버 프로그래머라면 알아 두는 것이 좋다.