Diffie-Hellman 키 교환

〈컴퓨터정보보안〉 수업 노트

Diffie-Hellman 알고리즘은 GCHQ의 Williamson이, 그리고 스탠포드의 Diffie와 Hellman이 개발한 알고리즘(GCHQ와 스탠포드가 독립적으로 개발)이다. 주로 키 교환에 사용된다.

이 알고리즘은 이산 로그 문제에 기반한다.

• 주어짐: $g$, $p$, $g^k \mod p$
• 찾기: $k$

$p$ 는 소수 값이고, $g$ 는 키 생성자로서 다룬다. ${1, 2, …, p-1}$ 범위의 어떤 값 $x$ 에 대해서 $x = g^n \mod p$ 를 만족하는 $n$ 이 존재한다. 이때 $n$ 은 $x$ 의 이산 로그라고 부른다. 이 $n$ 을 찾는 것은 어렵다.

이 알고리즘에서는 키 교환 당사자 A, B가 각각 비밀키 $a$, $b$를 가지고 키교환을 시작한다.

• A는 B 편에 자신의 비밀키로 생성한 $g^a \mod p$ 를 보낸다.
• B는 A 편에 자신의 비밀키로 생성한 $g^b \mod p$ 를 보낸다.
• 양 측은 각각 자신의 비밀키를 수신한 값에 적용해 공유되는 키를 생성한다.

\[g^{ab} \mod p = (g^a \mod p)^b \mod p = (g^b \mod p)^a \mod p\]

키는 $g^{ab} \mod p$ 이다. A, B는 서로의 비밀키를 알지 못하지만, 공유되는 키를 생성할 수 있다.

MiM (Man-in-the-Middle) Attack

이 알고리즘은 키 교환에 관한 것만 고려하므로, 알고리즘 차원에서 중간자 공격을 막을 수는 없다.

• A는 B에게 $g^a \mod p$ 를 보낸다.
• 공격자 M은 A와 B 사이에 위치해, A에게 $g^m \mod p$ 를 보내고, B에게 $g^m \mod p$ 를 보낸다.
• A는 M에게서 $g^m \mod p$ 를 수신하고, B는 M에게서 $g^m \mod p$ 를 수신한다.

공격자 M은 A와 B 사이를 중계하면서 자신이 생성한 키를 이용해 A와 B 사이의 통신을 가로챈다. A와 B는 중간자 공격이 발생했는지 알지 못한다.

이 공격에 대한 대책은 몇 가지 고려할 수 있다.

• 이 교환을 Symmetric Key로 암호화한다.
• 이 교환을 Public Key로 암호화한다.
• 이 교환을 서명한다.

다른 키를 사용하는 것은 이미 키가 교환된 상태에서 사용 가능하므로, 경우에 따라서는 부적절할 수 있다.