[Cryptography] stage4_키 교환: Diffie-Hellman 알고리즘

대칭키 암호를 이용하기 위해서는 송/수신자 간 키 공유가 필수적 -> 데이터 교환 이전에 키 교환 절차가 선행되어야 함. 

 

하지만 현대 유무선 환경에서 안전한 키 교환은 어렵다. -> 대칭키 암호가 아무리 안전해도 키 교환 과정이 안전하지 않으면 무슨 소용? -> 공개된 채널을 통해 키를 교환해도 외부인은 키를 알 수 없게 하는 공개 키 교환 알고리즘 고안

 

Diffie-Hellman 키 교환 절차(Diffie-Hellman key exchange protocol)는 최초의 공개 키 교환 알고리즘으로, 지금도 널리 이용되고 있다.

 

 

 

*Diffie-Hellman알고리즘의 수학적 기반원리

 

 

mod연산에서의 거듭제곱: a^k = b (mod m) -> a^2k = b^2k (mod m) 이 성립한다. (생각해보면 당연하다.)

 

이를 이용해 큰 지수에 대한 합동식을 빠르게 연산하는 알고리즘을 square and multiply라고 한다. 

 

Diffie-Hellman 키 교환 알고리즘 이용을 위해서는 2^2048번 가까이 제곱된 어떤 수의 mod값을 구해야 하는데, 위 알고리즘을 이용하면 2048번 정도의 연산으로 해당 값을 구할 수 있다.

 

 

페르마의 소정리(Fermat`s Little Theorem): 소수 p와 정수 a에 대해 a^(p - 1) = 1 (mod p)가 성립한다. 

 

 

이산 로그 문제(Discrete Logarithm Problem): 자연수 a, m, 정수 b에 대해 a^x = b (mod m)을 만족하는 정수 x를 구하는 문제이다. -> 수가 작다면 프로그램을 구현해 금방 찾을 수 있지만, m이 커지면 문제가 매우 어려워진다. -> 현재 알려진 최선의 방법으로도 m^(1/2)회 정도의 연산이 필요하다고 한다.

 

 

Diffie-Hellman 알고리즘의 안정성은 이산 로그 문제의 어려움에 기반한다. 이 키 교환 알고리즘에서 키를 모르는 공격자가 키를 구하기 위해서는 m값이 2^2048정도 되는 이산 로그 문제를 해결해야 한다. -> 현재의 연산 능력으로는 불가능하다.

 

 

 

*키 교환 절차

 

Alice는 Bob과 키를 교환하고자 한다. 소수 p와 1 <= g <= p-1 을 만족하는 g를 정해 Bob에게 전송한다. (p는 보통 2^1024이상의 큰 소수)

 

Alice는 1 <= a <= p-1을 만족하는 적당한 수 a를 정해 A = g^a (mod p)를 Bob에게 전송한다.

 

Bob은 수신한 p와 g로 1 <= b <= p-1 을 만족하는 적당한 수 b를 정한 뒤, B = g^b (mod p)를 Alice에게 전송한다.

 

Alice는 수신한 B로 K = B^a = (g^b)^a = g^(ba) (mod p)를 계산한다.

 

Bob은 K = A^b = (g^a)^b = g^(ab) (mod p)를 계산한다.

 

Alice와 Bob은 각자 계산한 K를 통신키로 사용한다.

 

 

이 과정에서 공격자는 둘 사이 송/수신되는 값인 p, g, g^a (mod p), g^b (mod p) 를 알아낼 수 있다. -> 앞서 언급한 이산 로그 문제의 어려움으로 인해 g^a mod p로부터 a를 알아내거나, g^b mod p로부터 b를 알아내는 것은 불가능 -> K는 구할 수 없다.

 

 

 

*Diffie-Hellman에 대한 중간자 공격

네트워크 통신의 두 주체는 서로의 신원을 확인하기 어렵다는 특성을 이용한 공격이다. 

 

네트워크에서 발생하는 통신은 수동적 공격/능동적 공격으로 나뉜다.

-> 수동적 공격: 공격자가 통신에 개입하지 않음 -> 도청만 가능

-> 능동적 공격: 공격자가 통신에 직접 개입 -> 도청과 데이터 위/변조 가능 -> 중간자 공격은 여기 해당

 

Alice와 Bob이 통신할 때, 공격자는 Alice에게는 자신을 Bob이라고, Bob에게는 자신을 Alice라고 속인다. -> 실제 Alice와 Bob은 통신 상대가 공격자인지 진짜 상대인지 알 수 없다.

 

Alice와 Bob이 키 교환을 시도하면 공격자는 이를 가로채어 모두와 키 교환을 진행한다. -> Alice와는 K1이라는 키를, Bob과는 K2라는 키를 공유한다. -> 진짜 Alice는 Bob과 K1을, 진짜 Bob은 Alice와 K2를 공유했다고 생각 중

 

이후 Alice라 Bob에게 K1으로 암호화된 데이터를 전송하면, 공격자는 이를 복호화한 뒤 K2로 다시 암호화하여 Bob에게 보낸다. -> Bob의 응답에도 동일한 과정을 거친 뒤 Alice에게 전송한다. 

 

공격자는 둘 사이 오가는 정보를 모두 알 수 있게 되고, 필요시 변조까지 가능한 것이다. 

 

->이러한 취약점 때문에 Diffie-Hellman키 교환은 서로의 신원을 확인할 수 있는 추가 메커니즘이 동반되어야 한다.