암호통신 : Diffie–Hellman key exchange

버들비·2021년 4월 9일

이때 엘리스(Alice)와 밥(Bob) 사이에서 이브(Eve) 는 메시지를 훔쳐 보려 하고 있다.

이브는 엘리스와 밥의 상상을 뛰어넘는 능력을 갖고 있어서, 아무리 보안에 신경써도 기상천외한 방법으로 메시지를 훔쳐보고 만다(worst case).

이브가 훔쳐보는걸 막을 수 없다면, 훔쳐본다해도 해독할 수 없게끔 메시지를 암호화(encrypt) 해서 보내기로 한다.

암호화된 메시지는 키가 없으면 해독할 수 없으니, 이브가 중간에 메시지를 훔쳐봐도 무용지물이다. 이제 안전하게 메시지를 주고 받으면 된다!

암호화에 쓰인 key 와 해독에 쓰이는 key 가 서로 같기 때문에, 암호화된 메시지와 key를 도둑맞으면 메시지가 노출되는 위험이 남아있다.

엘리스와 밥은 key 를 도둑맞지 않고 안전하게 공유하기 위해 다음과 같은 방식을 사용하기로 한다.

엘리스와 밥은 p, g라는 prime number 두개를 나눠갖는다.
엘리스는 다른 사람한테 알려주지 않고, 어떤 정수 a를 이용해 A = $g^a$ mod p 를 계산한다.
엘리스는 밥에게 A를 건내준다.
밥은 다른 사람한테 알려주지 않고, 어떤 정수 b를 이용해 B = $g^a$ mod p 를 계산한다.
밥은 엘리스에게 B를 건내준다.
엘리스와 밥은 각각 $B^a$ mod p 와 $A^b$ mod p 를 계산한다. 이때 두개의 값은 $B^a$ mod p = $A^b$ mod p 이므로, 이 값을 key 로 사용한다.

이브는 엘리스와 밥이 주고 받은 p, g, A, B 를 모두 훔쳐봤다. 하지만 key 를 알아내려면 a 나 b 를 알아내야 하는데, A = $g^a$ mod p 가 되는 a를 계산하는 것이 매우 어려운 문제이다(discrete logarithm problem).

이브가 엘리스와 밥의 key 를 계산해낼 가능성이 0은 아니지만, 현실적으로 불가능하기에 충분히 안전하다고 볼 수 있다.

이제 key 를 직접적으로 주고 받지 않고도 엘리스와 밥이 서로 공통의 key를 나눠갖게 됐다. 이브는 엘리스와 밥이 key를 주고 받지 않으니 key 를 훔쳐갈 수 없고, 암호화된 메시지를 중간에 훔친다 해도 해독할 수 없다!

디피-헬만 키 교환 방식은 두 사람이 안전하게 키를 나눠가질 수 있음을 보장할 뿐, 엘리스와 밥이 주고받는 메시지가 정말 엘리스와 밥인지를 보장해 주지 않는다.

만약 엘리스와 밥 사이에 누군가, 맬러리가 껴서 주고받는 메시지를 슬쩍할 수 있다면 위와 같은 key 교환방식을 무력화 시킬 수 있다.

엘리스는 밥에게 메시지를 보낸다. key를 만드는데 쓸 p, g를 보내줘!
하지만 엘리스와 밥 사이에는 맬러리가 껴 있어서, 보낸 메시지를 중간에 갈취하고 입맛대로 다시 보낼수 있다. 맬러리는 일단 엘리스가 보낸 메시지를 밥에게 그대로 보낸다.
밥은 엘리스에게 p 와 g를 보내준다.
맬러리는 밥이 보낸 p와 g 를 기억하고, 엘리스에게는 p와 g 대신 p' 과 g', 그리고 B'를 보내준다.
엘리스는 p'와 B'를 통해 key $k_{A}$ 를 만들고, p'와 g'을 이용해 A 를 만들고 밥에게 보낸다.
맬러리는 원래 밥에게 보내질 A를 갈취해서 key $k_{A}$ 를 만든다.
밥에게는 자신이 p와 g로 만든 A' 를 보내준다.
밥은 맬러리에게 받은 A'를, 엘리스가 보내준 것이라 생각하고 key $k_{B}$ 를 만든다.

맬러리는 엘리스와 밥 사이에 껴서 key $k_{A}$ 와 key $k_{B}$ 둘 다를 알고 있다.

하지만 엘리스와 밥은 맬러리의 존재를 알아낼 수 있는 방법이 없다!

결국 Diffie-Hellman 방식은 안전하게 key를 나눠가질 수 있는 방식일뿐, 암호통신 프로토콜이 아니기에 인증(authentication)이나 중간자 공격(Man In The Middel Attack)에 취약하다.

arXiv