(Dreamhack) 암호학 - 키 교환: Diffie-Hellman 알고리즘

*intro

대칭키 암호는 임의의 데이터를 안전하게 암호화할 수 있는 암호 기술이다.

하지만 송신자와 수신자가 같은 key를 가지고 있어야 하므로 key 교환이 있어야 한다.

key 교환 과정 도중 제 3자가 통신을 도청하면 해당 키를 알 수 있다.

 

이러한 키 분실을 방지하기 위해 네트워크 같은 공개된 채널을 통해 키를 교환해도 외부인은 키를 알 수 없게 하는 공개 키 교환 알고리즘을 고안했다.

 

공개 키 교환 알고리즘인 Diffie-Hellman 키 교환 절차에 대해 살펴보자.

 

*main

-모듈러 합동식에 대해 알아보겠다.

≡는 항등식을 표현한다.

a ≡ b(mod n) 은 a와 b는 n으로 나눈 나머지가 같다는 뜻이다.

1 ≡ 7(mod 2)

 

+예시1

지금이 9시인데, 5시간 후에는 몇 시인가?

   14시가 아닌 2시라고 한다.

   9+5 ≡ 2 (mod 12)

   이것이 합동식 개념

 

+예시2

 

다음과 같은 정리를 사용하면 Diffie-Hellman 키 교환 알고리즘을 사용하려면 2048번 가까이 제곱된 어떤 수의 모듈러 값을 구해야 하는데, 이 방법을 사용하면 2048번 정도만 연산해도 그 값을 구할 수 있다.

 

-페르마의 소정리

: 소수 p와 정수 a에 대해 a^(p-1) ≡ 1(mod p)이 성립한다는 정리이다.

 

+예시

소수 37과 2, 3, 17은 페르마의 소정리에 따라

2^36 ≡3^36 ≡ 17^36 ≡ 1(mod 37)을만족한다.

 

-이상 로그 문제

: 자연수 a, m, 정수 b에 대해 a^x  ≡ b (mod m) ax ≡ b(mod m)을 만족하는 정수x를 구하는문제이다.

 

이 문제의 어려움을 설명하기 위해 5^x ≡ 52(mod 61)을 만족하는 x를 구한다고 생각해보자.

쉽게 떠올릴 수 있는 방법 중 하나는 5를 여러번 곱해가며 5^x (mod 61)을 계산하고, 이 값을 52와 비교하는 것이다.

프로그램으로 구현해서 실행하면 이를 만족하는 x가 21임을 알 수있다.

 

이번에는 m=2^127 - 1, a=2에 대해 a^x ≡ 274877906944 (mod m)을 만족하는 x를 구한다고 생각해보자.

앞에서와 달리 m이 매우 크므로 식이 성립하는 x를 무차별 대입으로 찾기에는 현재까지 알려진 방법으론 어렵다.

최선의 방법은 루트 m번 정도의 연산을 하는 방법이다.

 

 

---

지금까지는 Diffie-Hellman키 교환 절차를 이해하기 위한 개념이였다.

이제 본론으로 가보자.

Diffie-Helloman 키 교환에서 통신을 진행하는 엘리스와 밥이 있다고 하다.

 

키를 교환하기 위해 엘리스는 소수 p와 1<=g<=p-1을 만족하는 적당한 수 g를 정해 밥에게 전송한다.

p는 보통 2^1024이상의 큰 소수로 설정한다.

 

다시 엘리스는 1<=a<=p-1을 만족하는 적당한 수 a를 정해 A=(g^a)*mod p 를 밥에게 전송한다.

 

엘리스로부터 g와 p를 받은 밥은 1<=b<=p-1을 만족하는 적당한 수 b를 정해 B=(g^b)*mod p을 엘리스에게 전송한다.

 

엘리스는 밥이 보낸 B를 a제곱하여 K ≡ B^a ≡ ((g^b)mod p)^a  ≡ (g^(b*a))mod p를 계산하고,

밥은 엘리스가 보낸 A를 b제곱하여 K ≡ A^b ≡ ((g^a)mod p)^b ≡ (g^(a*b))mod p를 계산한다.

a와 b의 값이 매우 크지만, 앞에서 소개한 square-and-multiply를 이용하면 쉽게 K의 값을 구할 수 있다.

 

엘리스와 밥은 계산한 K를 통신의 키로 사용하게 된다,

공격자는 둘 사이의 통신을 도청하여 p, g, (g^a)mod p, (g^b)mod p 를 알아낼 수 있다.

그러나 이산 로그 문제의 어려움으로 인해 (g^a)mod p로 부터 a를 알아내거나 (g^b)mod p로부터 b를 알아내는 것은 불가능하며, 결과적으로 K = ≡ (g^(a*b))mod p 를 구할 수 없다.

 

이 알고리즘을 이용하면 엘리스와 밥 모두에게 공개된 통신 채널을 이용하여도 서로 안전하게 키를 교환할 수 있다.

---

Diffie-Hellman에 대한 중간자 공격

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

일반적으로 네트워크에서 발생하는 공격은 공격자가 통신에 개입하지 않으면 수동적 공격으로, 직접 개입하면 능동적 공격으로 구분된다.

 

수동적 공격자: 공격자가 통신에 개입하지 않는다. 둘 사이의 통신을 도청만 할 수 있다.

능동적 공격자: 공격자가 통신에 직접 개입한다. 통신을 도청하며 데이터를 변조할 수 있다.

중간자 공격은 후자에 속한다.

 

Diffie-Hellman 키 교환은 다음과 같은 중간자 공격에 취약하다.

먼저, 엘리스와 밥이 통신할 때, 공격자는 엘리스에게 자신을 밥이라고, 밥에게는 자신을 엘리스라고 속인다.

엘리스와 밥은 통신하는 상대방이 공격자인지, 신뢰하는 상대방인지 알 수 없다.

 

엘리스가 밥에게 키 교환을 시도하면, 공격자는 이를 가로채어 둘 모두와 키 교환을 진행한다.

그 결과로 엘리스에게는 K1 키를, 밥에게는 K2 키를 공유한다. 

공격자에세 속은 엘리스는 밥과 K1을, 밥에게는 K2를 공유했다고 믿는다.

 

이후 엘리스가 밥에게 K1으로 암호화된 데이터를 전송하면, 공격자는 이를 복호화한 뒤, K2로 다시 암호화해서 밥에게 보낸다. 그리고 밥이 응답하면 같은 방법으로 엘리스에게 재전송한다.

이 과정에서 공격자는 둘 사이에 오가는 정보를 모두 알 수 있으며, 필요하면 이를 변조할 수도 있다.

K1과 K2는 다른 값이지만 엘리스가 공개키로 알고있는 값 K1과 밥이 공개키로 알고있는 값 K2를 중간자가 알아낼 수 있고, 서로에게 공개키로 암호화 한 데이터를 전송한다면 엘리스가 전송한 값은 K1 공개키로 복호화해서 원본 데이터를 알아낼 수 있고, 밥이 암호화한 데이터는 K2로 복호화해서 원본데이터를 알아낼 수 있다.

 

이런 취약점으로 인해 Diffie-Hellman 키 교환은 서로의 신원을 확인할 수 있는 추가적인 메커니즘이 동반되어야 안전하게 이루어질 수 있다.

---

-헷갈리는 부분

K ≡ B^a ≡ ((g^b)mod p)^a  ≡ (g^(b*a))mod p    

K ≡ A^b ≡ ((g^a)mod p)^b  ≡ (g^(a*b))mod p

빨간 부분에서 좌변이 어떻게 우변이 되는 거지지지지?

문자로 표기해서 햇갈림.

엘리스 밥 그림에서는 대문자K와 소문자 k로 되어있는데 이거 잘못된 듯