맨위로가기

디피-헬먼 키 교환

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

디피-헬먼 키 교환은 두 당사자가 공개된 통신 채널을 통해 비밀 키를 안전하게 공유할 수 있도록 하는 암호화 프로토콜이다. 이 방식은 소수 p와 정수 g를 사용하여 작동하며, 각 당사자는 자신의 비밀 값을 가지고 이를 이용하여 상대방과 공유할 값을 계산하고, 서로 교환된 값을 통해 공통의 비밀 키를 생성한다. 디피-헬먼은 엘가말 암호화와 같은 공개 키 암호 방식의 기반 기술로 활용되며, 전방 보안 및 비밀번호 인증 키 교환에도 사용된다. 그러나 중간자 공격에 취약하며, 안전한 매개변수 선택과 구현에 주의를 기울여야 한다.

더 읽어볼만한 페이지

  • 공개 키 암호 - 공개 키 기반 구조
    공개 키 기반 구조(PKI)는 공개 키 암호화를 기반으로 안전한 통신과 개체 식별을 가능하게 하는 기술로서, 디지털 인증서를 통해 공개 키를 특정 개체에 연결하고 인증서를 관리하며, 인증 기관(CA), 등록 기관(RA) 등 다양한 구성 요소로 이루어져 인증서 발급, 관리, 배포, 사용 및 폐기와 관련된 역할, 정책, 하드웨어, 소프트웨어 및 절차의 집합을 포함한다.
  • 공개 키 암호 - DNSSEC
    DNSSEC는 DNS의 보안 취약점을 개선하기 위해 도메인 정보에 디지털 서명을 추가하여 응답 레코드의 무결성을 보장하고 DNS 위장 공격을 막는 기술로, RRSIG, DNSKEY 등 다양한 리소스 레코드 유형을 사용하여 인증 체인을 구성하며 공개 키 암호 방식을 활용한다.
  • 암호 프로토콜 - HTTPS
    HTTPS는 HTTP에 보안 기능이 더해진 통신 규약으로, 웹 브라우저와 서버 간 통신을 암호화하여 보안을 강화하지만, 인증서 비용, 서버 부하, 혼합 콘텐츠 문제 등의 단점도 존재한다.
  • 암호 프로토콜 - IPsec
    IPsec은 IP 네트워크에서 보안 통신을 제공하기 위한 프로토콜 스위트로서, 전송 모드와 터널 모드를 지원하며, AH, ESP 등의 프로토콜을 사용하여 데이터 무결성, 인증, 기밀성을 제공하고, IKE 프로토콜을 통해 보안 연결을 설정 및 키를 교환하는 개방형 표준이다.
디피-헬먼 키 교환
개요
이름디피-헬먼 키 교환
로마자 표기Dipi-Helmeon Ki Gyohwan
영문명Diffie–Hellman key exchange
일본어명ディフィー・ヘルマン鍵共有 (Difi Heruman Kagi Kyōyū)
종류암호 프로토콜
목적안전하지 않은 통신 채널을 통해 암호 키를 교환
특징키 교환 후의 통신은 별도의 암호화 방식 필요
역사
최초 발표1976년
고안자휘트필드 디피
마틴 헬먼
선행 연구랠프 머클의 "머클 퍼즐" (1974)
특허미국 특허 4200770
영국 정보부 (GCHQ)제임스 H. 엘리스 (1970년)
맬컴 윌리엄슨 (1973년)
클리포드 콕스 (1973년)
보안
중간자 공격취약 (디피-헬먼-머클 인증 필요)
양자 컴퓨터취약 (쇼어 알고리즘으로 계산 가능)
응용
예시인터넷 프로토콜 보안 (IPsec)
보안 셸 (SSH)
TLS/SSL
기밀 메시지 (OTR)
전거래비밀성 (PFS)
참고
관련 개념타원 곡선 디피-헬먼 (ECDH)

2. 역사

1976년 스탠퍼드 대학교의 휘트필드 디피와 마틴 헬만공개 키 암호 방식의 개념을 제안하고, 그 구체적인 방식 중 하나로 디피-헬만 키 교환(DH 키 교환) 프로토콜을 발표했다. 이 키 교환 방식은 대칭키 암호 방식에서 키 전달을 안전하게 수행하기 위해 제안되었다.[8]

이 프로토콜은 통신을 원하는 두 당사자가 각각 공개 키와 비밀 키(사설 키라고도 함)를 준비하고, 공개 키만을 상대방에게 전송하여, 각자 자신의 비밀 키와 수신한 공개 키로부터 공통 키를 생성할 수 있는 방법이다. 설령 송수신되는 데이터(즉, 두 사람의 공개 키)를 제3자가 모두 도청하더라도, 여기에서 (계산량적으로) 사설 키나 공통 키를 생성할 수 없는 점이 특징이다.[8]

미국캐나다에서 특허를 취득했으며, 양국에서 알고리즘의 특허 기간은 1997년 4월 29일에 만료되어 현재는 누구나 자유롭게 이용할 수 있다.[8]

3. 작동 방식

디피-헬먼 키 교환의 작동 방식은 다음과 같다. 앨리스와 밥이 공개된 통신망에서 키를 교환하기 위해 다음과 같은 절차를 거친다.[3]

디피-헬먼 키 교환의 개념도


간단한 비유를 통해 작동 방식을 설명하면 다음과 같다.

1. 앨리스와 밥은 서로 공유할 색(예: 노란색)을 정한다. 이 색은 공개되어도 상관없다.

2. 앨리스와 밥은 각자 비밀 색(예: 앨리스는 빨간색, 밥은 시안색)을 선택한다. 이 색은 외부에 알려져서는 안 된다.

3. 앨리스와 밥은 각자 자신의 비밀 색과 공유하기로 한 색을 섞는다. (앨리스: 주황색-황갈색, 밥: 밝은 파란색)

4. 앨리스와 밥은 섞은 색을 서로 교환한다.

5. 앨리스와 밥은 상대방에게서 받은 색과 자신의 비밀 색을 섞는다.

6. 결과적으로 앨리스와 밥은 같은 색(노란색-갈색)을 공유하게 된다.

이 비유에서 색깔 대신 큰 숫자를 사용하면, 제3자는 원래의 비밀 색(비밀 키)을 알아내기 매우 어렵다. 실제로는 슈퍼컴퓨터로도 계산이 불가능할 정도로 큰 숫자를 사용한다.

앨리스와 밥은 이렇게 공유된 비밀 키를 바탕으로 대칭 키 암호를 이용해 통신을 암호화할 수 있다.

하지만, 사용되는 소수나 정수가 너무 작을 경우, 도청자는 모든 경우의 수를 계산하여 비밀 키를 알아낼 수 있다. 따라서 실제 통신에는 충분히 큰 소수를 사용해야 한다. 만약 p가 최소 300자리의 소수이고, a와 b가 각각 100자리 이상의 정수라면, 현재 인류가 보유한 모든 컴퓨터를 동원해도 공개된 정보로부터 비밀 키를 알아낼 수 없는 것으로 알려져 있다.[9] 이러한 문제를 이산 로그 문제라고 한다.[23]

디피-헬먼 키 교환은 정수 곱셈군뿐만 아니라 유한 순환군에서도 작동하도록 일반화될 수 있다.[10] 타원 곡선 디피-헬만 프로토콜은 ''G''의 원소를 ''n''을 법으로 하는 정수가 아닌 타원 곡선 위의 점으로 나타내는 변형이다.[11]

3. 1. 기본 원리

앨리스와 밥이 공개된 통신망에서 디피-헬먼 키 교환을 하기 위해서는 다음과 같은 절차를 거친다.[3]

1. 앨리스가 소수 p1부터 p-1까지의 정수 g를 선택하여 사전에 밥과 공유한다.

2. 앨리스가 정수 a를 선택한다. 이 정수는 외부에 공개되지 않으며, 밥 또한 알 수 없다.

3. 앨리스가 A = g^a \text{ mod }p, 즉 g^ap로 나눈 나머지를 계산한다.

4. 밥이 마찬가지로 정수 b를 선택하여 B = g^b \text{ mod }p를 계산한다.

5. 앨리스와 밥이 서로에게 AB를 전송한다.

6. 앨리스가 B^a \text{ mod }p를, 밥이 A^b \text{ mod }p를 계산한다.

마지막 단계에서 B^a \text{ mod }p = (g^b)^a \text{ mod }p= g^{ab}\text{ mod }p, A^b\text{ mod }p = (g^a)^b\text{ mod }p = g^{ab}\text{ mod }p이며 따라서 앨리스와 밥은 g^{ab} \text{ mod }p라는 공통의 비밀 키를 공유하게 된다. 앨리스와 밥 이외의 인물은 a와 b를 알 수 없으며, g, p, g^a \text{ mod }p, g^b \text{ mod }p를 알 수 있다.

1976년에 스탠퍼드 대학교의 연구원인 휘트필드 디피와 마틴 헬만공개 키 암호 방식의 개념을 제안하고, 그 구체적인 방식 중 하나로 디피-헬먼 키 교환(DH 키 교환) 프로토콜을 제안했다. 이 키 교환 방식은 대칭 키 암호 방식에서의 키 전달을 안전하게 수행하기 위해 제안된 방식이다.

이 프로토콜은 통신을 원하는 두 당사자가 각각 공개 키와 비밀 키(사설 키라고도 함)를 준비하고, 공개 키만을 상대방에게 전송하며, 각자 자신의 비밀 키와 수신한 공개 키로부터 공통 키를 생성할 수 있는 방법이다. 설령 송수신되는 데이터(즉, 두 사람의 공개 키)를 제3자가 모두 도청하더라도, 여기에서 (계산량적으로) 사설 키도 공통 키도 생성할 수 없는 점이 특징이다.[24]

미국캐나다에서 특허를 취득했다. 양국에서의 알고리즘의 특허 기간은 이미 1997년 4월 29일에 만료되었으므로, 현재는 누구나 자유롭게 이용할 수 있다.

'''예시'''

가장 단순하고 최초의 구현 방식은 다음과 같다.[9]

1. 앨리스와 밥은 모듈러스 ''p'' = 23과 밑 ''g'' = 5(이는 23을 법으로 하는 원시근이다)를 사용하기로 공개적으로 합의한다.

2. 앨리스는 비밀 정수 '''''a''''' = 4를 선택한 다음, 밥에게 ''A'' = ''g'''a''''' mod ''p''를 보낸다.

  • ''A'' = 5'''4''' mod 23 = 4

3. 밥은 비밀 정수 '''''b''''' = 3을 선택한 다음, 앨리스에게 ''B'' = ''g'''b''''' mod ''p''를 보낸다.

  • ''B'' = 5'''3''' mod 23 = 10

4. 앨리스는 '''''s''''' = ''B'''a''''' mod ''p''를 계산한다.

  • '''''s''''' = 10'''4''' mod 23 = 18

5. 밥은 '''''s''''' = ''A'''b''''' mod ''p''를 계산한다.

  • '''''s''''' = 4'''3''' mod 23 = 18

6. 앨리스와 밥은 이제 비밀(숫자 18)을 공유한다.

앨리스와 밥은 모두 mod p에서 다음이 성립하기 때문에 동일한 값에 도달했다.

:{\color{Blue}A}^{\color{Red}b}\bmod {\color{Blue}p} = {\color{Blue}g}^{\color{Red}ab}\bmod {\color{Blue}p} = {\color{Blue}g}^{\color{Red}ba}\bmod {\color{Blue}p} = {\color{Blue}B}^{\color{Red}a}\bmod {\color{Blue}p}

더 구체적으로,

:({\color{Blue}g}^{\color{Red}a}\bmod {\color{Blue}p})^{\color{Red}b}\bmod {\color{Blue}p} = ({\color{Blue}g}^{\color{Red}b}\bmod {\color{Blue}p})^{\color{Red}a}\bmod {\color{Blue}p}

''a''와 ''b''만 비밀로 유지된다. 다른 모든 값들 – ''p'', ''g'', ''ga'' mod ''p'', ''gb'' mod ''p'' –은 공개적으로 전송된다. 이 방식의 강점은 ''gab'' mod ''p'' = ''gba'' mod ''p''가 ''p'', ''g'', ''ga'' mod ''p'', ''gb'' mod ''p''의 지식만으로는 알려진 어떤 알고리즘으로도 계산하는 데 극도로 오랜 시간이 걸린다는 사실에서 비롯된다. 계산하기는 쉽지만 역을 구하기 어려운 이러한 함수를 일방향 함수라고 한다. 앨리스와 밥이 공유 비밀을 계산하면, 그들은 동일한 개방형 통신 채널을 통해 메시지를 보내기 위해 자신들만 아는 암호화 키로 사용할 수 있다.

물론, 이 예시를 안전하게 만들려면 ''a'', ''b'', ''p''의 훨씬 더 큰 값이 필요할 것이다. 왜냐하면 ''n'' mod 23의 가능한 결과는 23개밖에 없기 때문이다. 그러나 ''p''가 600자리 이상의 소수라면, 가장 빠르고 알려진 알고리즘을 사용하는 최신 컴퓨터조차도 ''g'', ''p'' 및 ''ga'' mod ''p''만으로는 ''a''를 찾을 수 없다. 이러한 문제를 이산 로그 문제라고 한다.[23] ''ga'' mod ''p''의 계산은 모듈러 지수 계산이라고 하며, 큰 숫자에도 효율적으로 수행할 수 있다. ''g''는 전혀 클 필요가 없으며, 실제로 작은 정수(2, 3 등)인 경우가 많다.

3. 2. 예제

앨리스와 밥이 디피-헬먼 키 교환을 수행하는 구체적인 예시는 다음과 같다. 여기서는 설명을 위해 작은 크기의 소수를 사용하지만, 실제로는 안전을 위해 매우 큰 소수를 사용한다. 공개된 정보는 파란색, 비밀 정보는 붉은색 굵은 글씨로 표시하였다.

1. 앨리스와 밥은 소수 ''p''=23, 그리고 원시근 ''g''=5를 사용하기로 합의한다.

2. 앨리스는 비밀키 '''''a'''''=6을 선택하고, 밥에게 ''A'' = ''g'''''''a''''''' mod ''p''를 계산하여 전송한다.

  • ''A'' = 5'''''6''''' mod 23 = 8

3. 밥은 비밀키 '''''b'''''=15를 선택하고, 앨리스에게 ''B'' = ''g'''''''b''''''' mod ''p''를 계산하여 전송한다.

  • ''B'' = 5'''''15''''' mod 23 = 19

4. 앨리스는 밥에게서 받은 ''B''를 바탕으로 '''''s''''' = ''B'''''''a''''''' mod ''p''를 계산한다.

  • '''''s''''' = 19'''''6''''' mod 23 = '''2'''

5. 밥은 앨리스에게서 받은 ''A''를 바탕으로 '''''s''''' = ''A'''''''b''''''' mod ''p''를 계산한다.

  • '''''s''''' = 8'''''15''''' mod 23 = '''2'''

6. 앨리스와 밥은 비밀 키 '''''s''''' = '''2'''를 공유하게 되었다.

이 예제에서 ''p''가 충분히 크다면, 외부 도청자 이브는 ''g'''''''a'''''''나 ''g'''''''b'''''''로부터 비밀키 '''''s'''''를 알아낼 수 없다. 앨리스와 밥은 이제 두 사람만이 아는 비밀 키 '''''s'''''를 사용하여 대칭 키 암호 방식으로 통신을 암호화할 수 있다.

하지만, ''p'', ''a'', ''b''가 너무 작으면 도청자는 가능한 모든 조합을 계산하여 '''''s'''''를 알아낼 수 있다. 따라서 실제 통신에는 충분히 큰 소수를 사용해야 한다. ''p''가 최소 300자리 소수이고, ''a''와 ''b''가 각각 100자리 이상의 정수라면, 현재 인류가 가진 모든 컴퓨터를 동원해도 공개된 정보로부터 비밀 키를 알아낼 수 없는 것으로 알려져 있다.

다음은 누가 무엇을 알고 있는지 보여주는 표이다. 파란색은 공개된 값이고, 붉은색 굵은 글씨는 비밀 값이다.

등장인물 별 정보
앨리스이브


3. 3. 유한 순환군으로의 일반화

디피-헬만 키 교환은 정수 곱셈군뿐만 아니라 유한 순환군에서도 작동하도록 일반화될 수 있다.[10]

# 앨리스와 밥은 자연수 ''n''과 ''n''차 유한 순환군 ''G''의 생성 원소 ''g''에 동의한다. (''g''와 ''n''은 모든 공격자에게 알려져 있다고 가정한다.) 군 ''G''는 곱셈으로 표기한다.

# 앨리스는 1 < ''a'' < ''n''인 임의의 자연수 ''a''를 선택하고, ''G''의 원소 ''ga''를 밥에게 보낸다.

# 밥은 1 < ''b'' < ''n''인 임의의 자연수 ''b''를 선택하고, ''G''의 원소 ''gb''를 앨리스에게 보낸다.

# 앨리스는 ''G''의 원소 (''gb'')''a'' = ''gba''를 계산한다.

# 밥은 ''G''의 원소 (''ga'')''b'' = ''gab''를 계산한다.

앨리스와 밥은 이제 공유 비밀 키로 사용할 수 있는 군 원소 ''gab'' = ''gba''를 모두 갖게 된다. 군 ''G''는 ''g'', ''ga'', ''gb''가 주어졌을 때 ''gab''를 결정하는 효율적인 알고리즘이 없는 한 안전한 통신에 필요한 조건을 만족한다.

예를 들어, 타원 곡선 디피-헬만 프로토콜은 ''G''의 원소를 ''n''을 법으로 하는 정수가 아닌 타원 곡선 위의 점으로 나타내는 변형이다. 초타원 곡선을 사용하는 변형도 제안되었다. 초특이 아이소제니 키 교환은 양자 컴퓨터에 안전하도록 설계된 디피-헬만 변형이지만 2022년 7월에 깨졌다.[11]

4. 안전성

디피-헬먼 키 교환의 안전성은 이산 로그 문제의 어려움에 기반한다. 도청자는 앨리스와 밥 사이의 통신에서 g^a \bmod pg^b \bmod p를 얻을 수 있지만, g^{ab} \bmod p를 효율적으로 계산하는 알고리즘은 알려져 있지 않다. 이를 '''디피-헬먼 문제'''라고 부른다. 이산 로그 문제를 효율적으로 풀 수 있다면 디피-헬먼 문제도 풀 수 있지만, 그 역은 증명되지 않았다.

1976년에 휘트필드 디피와 마틴 헬만공개 키 암호 방식의 개념을 제안하면서 디피-헬먼 키 교환 프로토콜을 제시했다. 이 방식은 대칭 키 암호 방식에서 키 전달을 안전하게 수행하기 위해 고안되었다. 두 사용자가 공개 키와 비밀 키를 준비하고, 공개 키만 교환하여 공통 키를 생성하는 방식이다. 제3자가 통신을 도청해도 비밀 키나 공통 키를 알아내는 것은 계산적으로 어렵다. 이 알고리즘은 미국캐나다에서 특허를 받았으나, 1997년 4월 29일에 특허 기간이 만료되어 현재는 누구나 자유롭게 사용할 수 있다.

디피-헬만 키 교환은 안전한 키 교환을 제공하지만, 다음과 같은 보안 취약점이 존재한다.


  • 안전한 매개변수 선택: 안전한 키 교환을 위해 pg를 신중하게 선택해야 한다.
  • 중간자 공격: 중간자 공격에 취약하다.
  • Logjam 공격: 구현상의 취약점을 이용해 디피-헬먼 키 교환을 해독하는 Logjam 공격이 가능하다.

4. 1. 안전한 매개변수 선택

디피-헬먼 키 교환이 도청에 대해 안전하려면 소수 pg를 신중하게 선택해야 한다. g순환군 G의 차수가 소수이거나, 인수분해하기 어려운 큰 소수를 약수로 갖도록 해야 한다. 이러한 이유로 p\frac{p-1}{2}이 모두 소수인 안전 소수를 선택하기도 한다.[24] p가 안전 소수이면 G의 차수는 2 또는 \frac{p-1}{2}만을 약수로 갖게 된다.

생성기 ''g''는 종종 2와 같은 작은 정수를 사용한다. 이산 로그 문제의 무작위 자기 축약성으로 인해, 작은 ''g''는 동일한 그룹의 다른 모든 생성기만큼 안전하다.

또한 앨리스와 밥이 충분히 안전하지 못한 난수 생성기를 사용할 경우, 공격자는 이를 이용해 ab의 특성을 어느 정도 예측할 수 있어 엿듣기가 쉬워진다.[18]

디피-헬만 키 교환은 통신하는 대상과 비밀 정보를 공유할 수는 있지만, 상대방에 대한 인증은 보장되지 않으며 중간자 공격이 가능하다.

4. 2. 중간자 공격 (Man-in-the-Middle Attack)

디피-헬만 키 교환 자체는 통신하는 상대방을 인증하는 수단을 제공하지 않기 때문에, 중간자 공격에 취약하다.[24]

공격자 이브(Eve)는 DNS 스푸핑, ARP 스푸핑 등의 방법을 사용하여 앨리스(Alice)와 밥(Bob) 사이의 통신을 중계하고, *A*와 *B* 값을 가로챌 수 있다. 이브는 앨리스와 밥에게 각각 다른 키를 사용하여 두 개의 키 교환을 수행한다.

1. 이브는 비밀 값 *c*와 *d*를 선택한다.

2. 이브는 *c*를 사용하여 *AE* = *gc* mod *p* 를 계산하고, 밥에게 앨리스인 척하며 전송한다.

3. 이브는 *d*를 사용하여 *BE* = *gd* mod *p* 를 계산하고, 앨리스에게 밥인 척하며 전송한다.

4. 밥은 자신의 비밀 값 *b*와 앨리스에게서 받은 것으로 착각한 *AE*를 사용하여 *KBE* = *AEb* mod *p* 를 계산한다.

5. 앨리스는 자신의 비밀 값 *a*와 밥에게서 받은 것으로 착각한 *BE*를 사용하여 *KAE* = *BEa* mod *p* 를 계산한다.

6. 이브는 *A*와 *B*, 그리고 자신의 비밀 값 *c*와 *d*를 사용하여 *KEAE* = *Ad* mod *p* 와 *KEBE* = *Bc* mod *p* 를 계산한다.

결과적으로 앨리스와 이브는 *KAE* = *KEAE* = *gad* mod *p* 라는 동일한 키를 공유하고, 밥과 이브는 *KBE* = *KEBE* = *gbc* mod *p* 라는 동일한 키를 공유하게 된다. 이브는 이 두 키를 사용하여 앨리스와 밥의 통신을 도청하고 내용을 변조할 수 있다.[24]

이러한 공격을 막기 위해 STS 프로토콜과 같이 통신 당사자를 서로 인증하는 방법이 필요하다.[24]

4. 3. Logjam 공격

Logjam 공격은 구현상의 취약점을 이용하여 디피-헬먼 키 교환을 해독하는 공격 방식이다.[30] 이 공격은 서버 측이 약한 DHE를 허용하지 않더라도 가짜 서버에 접속하게 하는 중간자 공격을 통해 통신을 다운그레이드 시킬 수 있다.[30]

알렉사의 톱 100만 HTTPS 도메인 중 상당수가 512비트 또는 1024비트 DHE에서 단일 소수를 재사용하고 있으며, 이러한 소수에 대해 미리 계산을 수행하면 많은 서버의 통신을 해독할 수 있다는 점이 지적되었다.[30] 특히 512비트 소수에 대한 해독은 수천 개의 코어와 약 8일의 사전 계산으로 약 70초 만에 가능함을 보였다.[30]

1024비트 비수출 버전 DHE에 대해서도, 수억 1억달러의 비용을 들여 전용 하드웨어를 구축하면 1년 안에 해독이 가능할 수 있다는 가능성이 제기되었다.[30]

5. 실용적인 공격

디피-헬먼 키 교환 프로토콜은 그룹 ''G''와 생성원 ''g''가 적절하게 선택되면 도청에 대해 안전하다고 알려져 있다. 하지만, 이산 로그 문제를 해결하는 효율적인 알고리즘이 발견되면 이 프로토콜과 다른 많은 공개 키 암호 시스템이 취약해진다.[17]

일반 수체 체 알고리즘은 이산 대수 문제를 해결하는 데 가장 효과적인 알고리즘으로 알려져 있다. 이 알고리즘은 네 단계로 구성되는데, 처음 세 단계는 그룹 ''G''의 크기에만 의존한다.[22] 2010년대에 인터넷 트래픽의 상당 부분이 1024비트 이하 크기의 몇 안 되는 그룹 중 하나를 사용한다는 사실이 밝혀졌다.[23]

로그잼 공격은 이러한 취약점을 이용했다. 공격자들은 널리 사용되는 몇몇 그룹에 대해 일반 수체 체 알고리즘의 처음 세 단계를 미리 계산해 두었다. 이를 통해 특정 로그 값을 얻기 위해 마지막 단계만 수행하면 되었는데, 이는 훨씬 적은 계산량을 요구했다. 로그잼 공격은 순서가 512비트 소수인 그룹(소위 수출 등급)을 사용하는 다양한 인터넷 서비스를 공격하는 데 성공했다. 연구자들은 단일 512비트 소수에 대한 데이터를 미리 계산하는 데 일주일 동안 수천 개의 CPU 코어가 필요했으며, 개별 로그는 18코어 인텔 제온 CPU 2개를 사용하여 약 1분 만에 해결할 수 있었다고 밝혔다.[23]

로그잼 공격을 수행한 연구자들은 1024비트 소수에 대한 이산 로그 문제를 해결하는 데 필요한 사전 계산은 약 1억 달러의 비용이 들 것으로 추정했다. 이는 미국 국가 안보국(NSA)과 같은 대규모 정보 기관의 예산 범위 내에 있는 금액이다. 이들은 널리 재사용되는 1024비트 DH 소수에 대한 사전 계산이 유출된 NSA 문서에서 NSA가 현재 암호화의 상당 부분을 해독할 수 있다는 주장의 배경에 있다고 추측한다.[23]

로그잼 공격과 같은 취약점을 피하려면 타원 곡선 암호를 사용하는 것이 좋다. 이것이 불가능하다면 디피-헬만 그룹의 크기 ''p''는 최소 2048비트 이상이어야 한다. 연구자들은 2048비트 소수에 필요한 사전 계산이 1024비트 소수에 비해 109배 더 어렵다고 추정한다.[23]

6. 다양한 활용

디피-헬먼 키 교환은 엘가말 암호화[24], 통합 암호화 방식 등 공개 키 암호화 방식의 기반 기술로 활용된다. 또한, 전방 보안을 달성하는 프로토콜이나 비밀번호 인증 키 교환 (PK) 방식, 공개 키 기반 구조의 일부로도 사용될 수 있다.


  • 전방 보안 (Forward Secrecy):세션마다 새로운 키 쌍을 생성하고 세션 종료 시 이를 폐기하는 방식으로, 빠른 키 생성 속도 덕분에 디피-헬먼 키 교환이 자주 사용된다.[24]
  • 비밀번호 인증 키 교환 (Password-Authenticated Key Agreement): 앨리스와 밥이 비밀번호를 공유하는 경우, 중간자 공격을 방지하기 위해 사용된다. 공격자가 각 반복마다 상대방에 대해 하나의 특정 비밀번호만 테스트할 수 있다는 특징이 있으며, 보안 원격 비밀번호 프로토콜과 같은 프로토콜이 있다.
  • 공개 키 (Public Key): 앨리스의 공개 키 (g^a \bmod{p}, g, p)를 이용하여 밥이 앨리스에게 암호화된 메시지를 보낼 수 있다. 앨리스만이 개인 키 ''a''를 가지고 있으므로 메시지를 해독할 수 있다. RSA가 지배적인 공개 키 알고리즘이지만, 엘가말 및 DSA 서명 알고리즘도 디피-헬먼 키 교환과 관련이 있다.


하지만, 디피-헬먼 키 교환은 자체로는 인증을 제공하지 않아 중간자 공격에 취약할 수 있다. 또한, 공유한 비밀을 그대로 키로 사용하기보다는 해시하는 것이 보안상 권장된다.[26]

6. 1. 암호화

디피-헬먼 키 교환은 엘가말 암호화[24], 통합 암호화 방식 등 공개 키 암호화 방식의 기반 기술로 활용된다.

이 방식은 다음과 같이 수행된다. 먼저 큰 소수 pp-1을 나누는 큰 소수 q를 준비한다. 또한, g({\mathbb Z}/p{\mathbb Z})^{\ast}의 원소이며, 위수q인 값으로 한다. 이 p, q, g의 값은 공개되어 있다.

앨리스와 밥이 통신할 때, 앨리스와 밥은 각자 비밀 값 ''a'', ''b''를 선택한다. 이 값은 0 이상 ''q''−1 이하 중에서 랜덤으로 선택한다. 앨리스는 ''A''를 계산하여 밥에게 전송한다.

: A = g^a \bmod p

밥도 마찬가지로 ''B''를 계산하여 앨리스에게 전송한다.

: B = g^b \bmod p

앨리스는 비밀 값 ''a''와 밥에게서 받은 ''B''로 다음 값을 계산한다.

: K_A = B^a \bmod p

밥도 비밀 값 ''b''와 앨리스에게서 받은 ''A''로 다음 값을 계산한다.

: K_B = A^b \bmod p

이때 앨리스와 밥이 계산한 K_AK_B

: K_A = K_B = g^{ab} \bmod p

가 되어 일치하므로, 이후 이 값을 공통 키 암호 방식의 키 K로 사용한다.

제3자 이브가 두 사람의 통신을 엿보고 ''A''와 ''B''의 값을 알아냈다고 해도, A = g^a \bmod p B = g^b \bmod p 로부터 K = g^{ab} \bmod p다항 시간에 계산할 수 있는 방법은 현재까지 알려져 있지 않다. 따라서 제3자가 비밀 공통 키 K를 생성하는 것은 어렵다.

하지만 이브가 밥으로 위장하여 앨리스와 통신하여 공통 키 K를 만들었다면, 앨리스가 밥에게 보낸 암호화된 통신 내용 전부가 이브에게 해독될 수 있다.

디피-헬만의 첫 번째 논문에서는 g({\mathbb Z}/p{\mathbb Z})^{\ast}의 생성원을 사용하는 것이 제안되었지만, 이 경우 앨리스가 보낸 A르장드르 기호를 계산함으로써 앨리스의 비밀 정보 a의 최하위 비트가 누설된다.[25]

6. 2. 전방 보안 (Forward Secrecy)

전방 보안을 달성하는 프로토콜은 각 세션마다 새로운 키 쌍을 생성하고 세션 종료 시 이를 폐기한다. 디피-헬만 키 교환은 빠른 키 생성 속도 때문에 이러한 프로토콜에 자주 사용된다.[24]

디피-헬만 키 교환 방식에서는 먼저 큰 소수 pp-1을 나누는 큰 소수 q를 준비한다. 또한, g({\mathbb Z}/p{\mathbb Z})^{\ast}의 원소이며, 위수q인 값으로 한다. 이 p, q, g 값은 공개되어 있다.

앨리스와 밥이 통신할 때, 서로 자신만이 아는 비밀 값 ''a'', ''b''를 0 이상 ''q''−1 이하에서 랜덤으로 선택한다. 앨리스는 A = g^a \bmod p 를 계산하여 밥에게 전송하고, 밥은 B = g^b \bmod p 를 계산하여 앨리스에게 전송한다.

앨리스는 비밀 값 ''a''와 밥에게서 받은 ''B''로 K_A = B^a \bmod p를 계산하고, 밥은 비밀 값 ''b''와 앨리스에게서 받은 ''A''로 K_B = A^b \bmod p를 계산한다. 이때 K_AK_B K_A = K_B = g^{ab} \bmod p로 일치하므로, 이 값을 공통 키 암호 방식의 키 K로 사용한다.

제3자가 통신을 엿보아 ''A''와 ''B''를 알아내도, K = g^{ab} \bmod p다항 시간에 계산하는 방법은 알려져 있지 않아 비밀 공통 키 K를 생성하기 어렵다.

하지만, 제3자가 밥으로 위장하여 앨리스와 통신하면 앨리스가 밥에게 보낸 암호화된 통신 내용이 해독될 수 있다.

디피-헬만의 첫 번째 논문에서는 g({\mathbb Z}/p{\mathbb Z})^{\ast}의 생성원을 사용하는 것을 제안했지만, 이 경우 앨리스가 보낸 A르장드르 기호를 계산하여 앨리스의 비밀 정보 a의 최하위 비트가 누설될 수 있다.[25]

6. 3. 비밀번호 인증 키 교환 (Password-Authenticated Key Agreement)

앨리스와 밥이 비밀번호를 공유하는 경우, 중간자 공격을 방지하기 위해 디피-헬먼의 비밀번호 인증 키 교환 (PK) 형태를 사용할 수 있다. 한 가지 간단한 방식은 채널 양쪽에서 독립적으로 계산된 비밀번호와 연결된 '''s'''의 해시를 비교하는 것이다. 이러한 방식의 특징은 공격자가 각 반복마다 상대방에 대해 하나의 특정 비밀번호만 테스트할 수 있다는 것이며, 따라서 시스템은 비교적 약한 비밀번호로도 좋은 보안을 제공한다. 이 접근 방식은 ITU-T 권고안 X.1035에 설명되어 있으며, 이는 G.hn 홈 네트워킹 표준에서 사용된다.[24]

이러한 프로토콜의 예로는 보안 원격 비밀번호 프로토콜이 있다.

6. 4. 공개 키 (Public Key)

디피-헬먼 키 교환은 공개 키 기반 구조의 일부로 사용될 수 있다. 밥이 앨리스의 공개 키에 대한 신뢰할 만한 정보를 가지고 있다면, 앨리스만 해독할 수 있는 암호화된 메시지를 보낼 수 있다. 앨리스의 공개 키는 (g^a \bmod{p}, g, p)이다. 앨리스에게 메시지를 보내기 위해 밥은 임의의 ''b''를 선택한 다음, g^b \bmod p (암호화되지 않음)와 대칭 키 (g^a)^b \bmod{p}로 암호화된 메시지를 앨리스에게 보낸다. 앨리스만이 대칭 키를 결정할 수 있고, 따라서 메시지를 해독할 수 있는데, 그 이유는 앨리스만이 ''a'' (개인 키)를 가지고 있기 때문이다. 사전 공유된 공개 키는 또한 중간자 공격을 방지한다.[24]

실제로 디피-헬먼은 이러한 방식으로 사용되지 않으며, RSA가 지배적인 공개 키 알고리즘이다. 이는 주로 RSA 시큐리티가 키 서명을 위한 인증 기관을 만들었고, 이 기관이 Verisign이 되었다는 역사적, 상업적 이유 때문이다. 디피-헬먼은 인증서 서명에 직접 사용할 수 없다. 그러나 엘가말 및 DSA 서명 알고리즘은 수학적으로 이것과 관련이 있으며, MQV, STS 및 IPsec 프로토콜 모음의 IKE 구성 요소는 인터넷 프로토콜 통신을 보호하는 데 사용된다.

이 방식은 다음과 같이 수행된다.

단계설명
1소수 pp-1을 나누는 큰 소수 q를 준비한다. 또한, g({\mathbb Z}/p{\mathbb Z})^{\ast}의 원소이며, 위수q인 값으로 한다. 이 p, q, g의 값은 공개된다.
2앨리스와 밥은 서로 자신만이 아는 비밀 값 a, b를 선택한다. 이 값은 0 이상 q−1 이하 중에서 랜덤으로 선택한다. (0이나 작은 값을 선택하면 안전성이 손상되지만, 그 확률은 매우 작다.)
3앨리스는 다음 값 A를 계산하여 밥에게 전송한다.
4밥도 마찬가지로 다음 값 B를 계산하여 앨리스에게 전송한다.
5앨리스는 비밀 값 a와 밥에게서 받은 값 B로부터 다음 값을 계산한다.
6밥도 비밀 값 b와 앨리스에게서 받은 값 A로부터 다음 값을 계산한다.
7앨리스와 밥이 계산한 K_AK_B



제3자 이브가 통신을 엿보고 ''A''와 ''B''의 값을 입수했더라도, K = g^{ab} \bmod p다항 시간에 계산할 수 있는 방법은 현재까지 알려져 있지 않다. 따라서 이브가 비밀 공통 키 K를 생성하는 것은 어렵고, 앨리스와 밥은 안전하게 통신할 수 있다.

하지만 이브가 밥으로 위장하여 앨리스와 통신하면, 앨리스가 보낸 암호화된 통신 내용이 이브에게 해독될 수 있다.

디피-헬먼의 첫 번째 논문에서는 g({\mathbb Z}/p{\mathbb Z})^{\ast}의 생성원을 사용하는 것이 제안되었지만, 이 경우 앨리스가 보낸 A르장드르 기호를 계산하여 앨리스의 비밀 정보 a의 최하위 비트가 누설될 수 있다.[25]

공개 키는 정적이거나 임시적(ephemeral, '''DHE'''로 약기)일 수 있다. 임시 키는 인증이 없으므로 다른 방법으로 인증해야 한다. 인증이 없으면 중간자 공격에 취약해진다. 한쪽 키가 정적이면 중간자 공격 위험은 없지만, forward secrecy와 같은 보안을 누릴 수 없다. 정적 키를 가진 측은 비밀 키 유출을 막기 위해 상대방의 공개 키를 확인하고, 안전한 공통 키 생성 함수를 이용해야 한다.

공유한 비밀을 그대로 키로 사용할 수도 있지만, 디피-헬만 키 교환으로 생성된 약한 비트의 영향을 제거하기 위해 비밀을 해시하는 것이 권장된다.[26]

7. 추가적인 변형

디피-헬먼 키 교환은 사용되는 키의 종류에 따라 다양한 변형이 존재하며, 각각 다른 보안 속성과 사용 사례를 가진다. NIST SP 800-56A에서 이러한 변형에 대한 개요를 확인할 수 있다.[12]

기본적인 키 유형은 다음과 같다:


  • 임시, 임시: 키 합의에 주로 사용되며, 전방 보안을 제공하지만 인증은 제공하지 않는다.
  • 정적, 정적: 장기 공유 비밀을 생성하며, 전방 보안은 제공하지 않지만 암묵적인 인증을 제공한다. 키가 정적이므로 재생 공격과 같은 공격에는 취약하다.
  • 임시, 정적: ElGamal 암호화 또는 통합 암호화 방식(IES) 등에 사용된다. 키 합의에 사용될 경우, 암묵적인 일방향 인증(임시 측에서 정적 측의 인증을 확인)을 제공할 수 있지만, 전방 보안은 제공하지 않는다.


더 높은 보안을 위해 임시 키와 정적 키를 함께 사용하는 방법도 있으며, 이를 트리플 DH(3-DH)라고 부르기도 한다.
3중 디피-헬만 (3-DH) 프로토콜1997년 사이먼 블레이크-윌슨(Simon Blake-Wilson), 돈 존슨(Don Johnson), 알프레드 메네제스(Alfred Menezes)가 제안하고,[13] 2005년 C. 쿠들라(C. Kudla)와 K. G. 패터슨(K. G. Paterson)에 의해 개선된 3중 DH 방식이 존재한다.[14]

앨리스와 밥의 장기 비밀 키는 각각 ''a''와 ''b'', 공개 키는 ''A''와 ''B''로 표시하고, 임시 키 쌍은 ''x, X''와 ''y, Y''로 표시한다. 프로토콜은 다음과 같이 진행된다.

3중 디피-헬만(3-DH) 프로토콜
앨리스 (A = g^a)밥 (B = g^b)
X = g^xX \rightarrow {}
{} \leftarrow YY = g^y
K = \operatorname{KDF}\left( Y^x, B^x, Y^a, X, Y, A, B \right)K = \operatorname{KDF}\left( X^y, X^b, A^y, X, Y, A, B \right)



장기 공개 키는 별도의 신뢰할 수 있는 채널을 통해 사전에 전송되거나, 익명성 유지를 위해 공개 키를 암호화하여 전송할 수 있다. 사이드 채널 보호, 키 확인, 초기 메시지 및 추가적인 암호 인증 등에 대한 자세한 내용은 미국 특허 "키 합의 및 선택적 인증을 위한 고급 모듈식 핸드셰이크"를 참조할 수 있다.[15]
확장 3중 디피-헬만 (X3DH)X3DH는 Signal 프로토콜에서 사용되는 이중 래칫 알고리즘의 일부로 제안된 프로토콜이다. 순방향 비밀성(forward secrecy)과 암호학적 부인 방지(cryptographic deniability)를 제공하며, 타원 곡선(elliptic curve)에서 작동한다.[16]

이 프로토콜은 다섯 개의 공개 키를 사용한다. 앨리스는 ID 키 IKA와 임시 키 EKA를, 밥은 ID 키 IKB, 서명된 사전 키 SPKB, 그리고 일회용 사전 키 OPKB를 가진다.[16] 밥은 자신의 세 키를 서버에 게시하고, 앨리스는 이를 다운로드하여 서명을 검증한 후 교환을 시작한다.[16] OPK는 선택 사항이다.[16]

8. 문제점

디피-헬만 키 교환 방식은 제3자가 도청을 하더라도 비밀 키를 알아내기 어렵다는 장점이 있지만, 몇 가지 문제점도 존재한다.

대표적인 문제점은 중간자 공격에 취약하다는 것이다. 예를 들어 이브가 밥으로 위장하여 앨리스와 통신을 시도할 수 있다. 앨리스가 이 사실을 모르고 이브와 공통 키 ''K''를 생성하면, 앨리스가 밥에게 보내는 암호화된 메시지를 이브가 해독할 수 있게 된다.[24]

또한, 디피-헬만의 첫 번째 논문에서는 g({\mathbb Z}/p{\mathbb Z})^{\ast}의 생성원을 사용할 것을 제안했지만, 이 경우 앨리스가 보낸 A르장드르 기호를 계산하면 앨리스의 비밀 정보 a의 최하위 비트가 누설될 수 있다는 문제점이 발견되었다.[25]

8. 1. 처리 부하

디피-헬만 키 교환은 부하가 큰 처리이며, SSL/TLS에 적용했을 경우, 일반적인 RSA 암호에 의한 키 교환과 비교하여 서버의 처리량이 6분의 1 정도로 감소한다는 실험 결과도 존재한다.[27]

8. 2. 매개변수 설정 오류

2013년 조사에 따르면, SSL/TLS에서 디피-헬만 키 교환을 활성화한 서버 중 전자 서명의 비트 수보다 DH의 비트 수가 작아 총력 공격에 취약한 서버가 80% 이상 존재했다.[28]

8. 3. 서비스 거부 공격 (Denial-of-service attack)

2021년에 공개된 CVE (''[https://nvd.nist.gov/vuln/detail/CVE-2002-20001 CVE-2002-20001]'')는 임시 키를 사용하는 프로토콜 변형에 대한 서비스 거부 공격(DoS)을 공개했는데, 이를 D(HE)at 공격이라고 한다.[19] 이 공격은 디피-헬먼 키 교환에서 공격자가 실제로는 공개 키가 아닌 임의의 숫자를 보낼 수 있게 하여 피해자 측에서 비용이 많이 드는 모듈러 지수 계산을 유발한다는 점을 악용한다. 또 다른 CVE (''[https://nvd.nist.gov/vuln/detail/CVE-2022-40735 CVE-2022-40735]'')는 디피-헬만 키 교환 구현이 긴 개인 지수를 사용하여 불필요하게 모듈러 지수 계산을 비싸게 만들 수 있다는 점을 공개했고,[20] 다른 CVE (''[https://nvd.nist.gov/vuln/detail/CVE-2024-41996 CVE-2024-41996]'')는 불필요하게 상대방의 공개 키를 검사하여 긴 지수를 사용한 키 계산과 유사한 자원 요구 사항을 가질 수 있다는 점을 공개했다.[21] 공격자는 두 취약점을 모두 악용할 수 있다.

9. 명칭

2006년, 헬만은 공개 키 암호 방식의 발명에 대한 랠프 머클의 기여를 인정하여 알고리즘을 '''디피-헬만-머클 키 교환'''으로 부를 것을 제안하며 다음과 같이 적었다.[8]

"그 시스템은...이후 디피-헬만 키 교환으로 알려지게 되었다. 이 시스템은 디피와 저의 논문에 처음 기술되었지만, 머클이 개발한 공개 키 분배 시스템이므로, 이름이 관련되어야 한다면 '디피-헬만-머클 키 교환'이라고 불러야 한다. 저는 이 작은 연단이 머클의 공개 키 암호 방식 발명에 대한 동등한 기여를 인정하는 데 도움이 되기를 바랍니다."

참조

[1] 문서 Synonyms of Diffie–Hellman key exchange include: * Diffie–Hellman–Merkle key exchange * Diffie–Hellman key agreement * Diffie–Hellman key establishment * Diffie–Hellman key negotiation * Exponential key exchange * Diffie–Hellman protocol * Diffie–Hellman handshake
[2] 논문 Secure Communications Over Insecure Channels 1978-04
[3] 논문 New Directions in Cryptography http://ee.stanford.e[...] 1976-11
[4] 웹사이트 The possibility of Non-Secret digital encryption http://cryptocellar.[...] 1970-01
[5] 웹사이트 The Possibility of Secure Secret Digital Encryption https://www.gchq.gov[...] 2017-07-08
[6] 뉴스 GCHQ trio recognised for key to secure shopping online https://www.bbc.co.u[...] 2010-10-05
[7] 특허
[8] 간행물 An overview of public key cryptography http://www-ee.stanfo[...] 2002-05
[9] 서적 Real World Cryptography https://books.google[...] Manning
[10] 서적 Introduction to Cryptography https://books.google[...] Springer Science+Business Media
[11] 논문 An efficient key recovery attack on SIDH https://eprint.iacr.[...] 2023-04
[12] 보고서 Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography https://csrc.nist.go[...] National Institute of Standards and Technology 2018-04-16
[13] 간행물 Crytography and Coding
[14] 서적 Advances in Cryptology - ASIACRYPT 2005 https://iacr.org/arc[...] Springer
[15] 특허 Advanced modular handshake for key agreement and optional authentication https://patents.goog[...]
[16] 웹사이트 Specifications >> The X3DH Key Agreement Protocol https://www.signal.o[...]
[17] 학술회의 A Heuristic Quasi-Polynomial Algorithm for Discrete Logarithm in Finite Fields of Small Characteristic http://hal.inria.fr/[...]
[18] 뉴스 RFC 4306 Internet Key Exchange (IKEv2) Protocol Internet Engineeringrg
[19] 논문 D(HE)at: A Practical Denial-of-Service Attack on the Finite Field Diffie-Hellman Key Exchange 2023-12-25
[20] 서적 Advances in Cryptology — EUROCRYPT '96 Springer, Berlin, Heidelberg 1996
[21] 웹사이트 Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography https://csrc.nist.go[...] National Institute of Standards and Technology
[22] 특허 Authentication and Authenticated Key Exchanges
[23] 웹사이트 Imperfect Forward Secrecy: How Diffie–Hellman Fails in Practice https://weakdh.org/i[...] 2015-10
[24] 문서 (p,q,g)
[25] 간행물 The Decision Diflie-Hellman Problem https://doi.org/10.1[...] 1998
[26] 논문 An Efficient Protocol for Authenticated Key Agreement http://download.cert[...] Certicom 1998-08-28
[27] 문서 Syamntec (2013)
[28] 문서 Symantec (2013)
[29] 간행물 Authentication and Authenticated Key Exchanges http://people.scs.ca[...] 1992-03-06
[30] 간행물 Imperfect Forward Secrecy:How Diffie-Hellman Fails in Practice https://weakdh.org/i[...] 2015-10



본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com