Diffie–헬만키 교환

Diffie–헬만 키 교환은^{[nb 1]} 공개 채널을 통해 안전하게 암호 키를 교환하는 수학적 방법이며 랄프 머클이 고안하고 휘트필드 디피와 마틴 헬만의 이름을 딴 최초의 공개 키 프로토콜 중 하나였습니다.^[1][2] DH는 암호학 분야에서 구현된 공개 키 교환의 가장 초기의 실용적인 예 중 하나입니다. 1976년 Diffie and Hellman에 의해 출판된 이 작품은 개인 키와 그에 상응하는 공개 키의 아이디어를 제안한 최초의 대중적으로 알려진 작품입니다.

전통적으로 두 당사자 간의 안전한 암호화 통신은 신뢰할 수 있는 택배원이 전송하는 종이 키 목록과 같은 일부 안전한 물리적 수단을 통해 먼저 키를 교환해야 했습니다. 디피-헬만키 교환 방식은 서로에 대한 사전 지식이 없는 두 당사자가 안전하지 않은 채널을 통해 공유 비밀키를 공동으로 설정할 수 있습니다. 그런 다음 이 키를 사용하여 대칭 키 암호를 사용하여 후속 통신을 암호화할 수 있습니다.

Diffie–헬만은 다양한 인터넷 서비스를 보안하는 데 사용됩니다. 그러나 2015년 10월에 발표된 연구에 따르면 당시 많은 DH 인터넷 애플리케이션에 사용되고 있는 매개 변수는 일부 국가의 보안 서비스와 같이 매우 자금이 좋은 공격자의 타협을 방지할 만큼 충분히 강하지 않습니다.^[3]

이 계획은 1976년 휘트필드 디피(Whitfield Diffie)와 마틴 헬먼(Martin Hellman)이 발표했지만,^[2] 1997년 영국 신호 정보 기관인 GCHQ의 제임스 H. 엘리스(^[4]James H. Ellis), 클리포드 콕스(Clifford Cocks), 말콤 J. 윌리엄슨(Malcolm J. Williamson)이 이전에^[5] 공개 키 암호화가 어떻게 달성될 수 있는지 보여주었음이 밝혀졌습니다.^[6]

비록 디피-Hellman 키 합의 자체는 인증되지 않은 키 합의 프로토콜이며, 다양한 인증 프로토콜의 기초를 제공하며, 트랜스포트 계층 보안의 임시 모드(암호 제품군에 따라 EDH 또는 DHE라고 함)에서 순방향 보안을 제공하는 데 사용됩니다.

이 방법은 곧이어 비대칭 알고리즘을 사용한 공개 키 암호화를 구현한 RSA가 도입되었습니다.

1977년부터 만료된 미국 특허^[7] 4,200,770호에는 현재 공개 영역 알고리즘이 기재되어 있습니다. 헬만, 디피, 머클을 발명가로 인정합니다.

이름.

2006년 헬만은 Diffie라고 불리는 알고리즘을 제안했습니다.Hellman – Merkle 키 교환은 Ralph Merkle이 공개 키 암호학의 발명에 기여한 것을 인정받아 다음과 같이 썼습니다(Hellman, 2006).

시스템이...그 후로 디피라고 알려지게 되었습니다.헬만 키 교환. 이 시스템은 Diffie와 저에 의해 논문에서 처음 기술되었지만, 공개 키 분배 시스템이며, Merkle에 의해 개발된 개념이므로 'Diffie–'라고 불러야 합니다.이름이 연관되는 경우 '헬맨-머클 키 교환'. 저는 이 작은 강단이 공개 키 암호학의 발명에 머클의 동등한 기여를 인정하는 데 도움이 되기를 바랍니다.^[8]

묘사

일반개요

Diffie–헬만 키 교환은 공용 네트워크를 통해 데이터를 교환하기 위한 비밀 통신에 사용될 수 있는 두 당사자 간의 공유 비밀을 설정합니다. 매우 큰 숫자 대신 색상을 사용하여 공개 키 교환의 개념을 보여주는 예가 있습니다.

이 과정은 앨리스와 밥 두 당사자가 비밀에 부칠 필요가 없는 임의의 시작 색상에 대해 공개적으로 합의하는 것으로 시작됩니다. 이 예에서 색상은 노란색입니다. 또한 각각의 사람들은 자신만의 색깔인 빨간색과 청록색을 선택합니다. 그 과정의 결정적인 부분은 앨리스와 밥이 각각 자신의 비밀색을 서로 공유하는 색과 혼합하여 각각 오렌지-탄과 연-청 혼합물을 만든 다음 공개적으로 두 가지 혼합색을 교환하는 것입니다. 마지막으로 각자 파트너에게 받은 색상과 자신만의 프라이빗한 색상을 혼합합니다. 결과물은 파트너의 최종 색상 혼합물과 동일한 최종 색상 혼합물(이 경우 황갈색)입니다.

제3자가 교환을 들었다면 공통색(노란색)과 첫 번째 혼합색(주황색-탄색-연청색)만 알 수 있을 뿐 최종 비밀색(노란색-갈색)을 알아내는 것은 매우 어려울 것입니다. 색이 아닌 큰 수를 사용하여 비유를 실제 교환으로 되돌리는 이 결정은 계산 비용이 많이 듭니다. 현대식 슈퍼컴퓨터도 실용적인 시간 안에 계산하는 것은 불가능합니다.

암호학적 설명

나중에 RFC 7919에서 유한 필드 디피 헬만(^[2][9]Finite Field Diffie-Hellman)으로 공식화된 프로토콜의 가장 단순하고 독창적인 구현은 정수 모듈롭의 곱셈 그룹을 사용합니다. 여기서 p는 소수이고 g는 원시 루트 모듈롭입니다. 이 두 값은 결과적으로 공유된 비밀이 1에서 p-1까지의 값을 가질 수 있도록 하기 위해 선택됩니다. 다음은 비비밀 값을 파란색으로 표시하고 비밀 값을 빨간색으로 표시하는 프로토콜의 예입니다.

1. Alice와 Bob은 공개적으로 모듈러스 p = 23과 기저 g = 5(원근 모듈로 23)를 사용하는 것에 동의합니다.
2. Alice는 비밀 정수 a = 4를 선택한 다음 Bob A = g mod p를 보냅니다.
   • A = 5 mod 23 = 4 (이 예에서 A와 a는 모두 동일한 값 4를 갖지만 일반적으로 그렇지 않습니다)
3. Bob은 비밀 정수 b = 3을 선택한 다음 Alice B = g mod p를 보냅니다.
   • B = 5³ mod 23 = 10
4. Alice 계산 = B modp
   • s = 10⁴ mod 23 = 18
5. Bob 계산 = A modp
   • s = 4³ mod 23 = 18
6. 앨리스와 밥은 이제 비밀(숫자 18)을 공유합니다.

Alice와 Bob 둘 다 같은 값에 도달했습니다. 왜냐하면 modp 하에서,

${\displaystyle {\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}}}$

좀 더 구체적으로 말하자면,

${\displaystyle({\color {Blue}g}^{\color {Red}a}{\bmod {\color {Blue}p}}^{\color {Blue}p}}= ({\color {Blue}g}^{\color {Red}b}}^{\color {Blue}p}}^{\color {Red}a}{\bmod {\color {Blue}p}}}$

a와 b만 비밀로 합니다. 다른 모든 값(p^a, g, g mod^b p 및 g mod p)은 클리어로 전송됩니다. 이 방식의 강점은 p, g, g, g mod p 및 g mod p에 대한 지식만으로 g mod p = g mod p가 알려진 알고리즘에 의해 계산되는 데 매우 오랜 시간이 걸린다는 사실에서 비롯됩니다. 계산은 쉽지만 반전이 어려운 그런 함수를 일방향 함수라고 합니다. Alice와 Bob이 공유된 비밀을 계산하면, 그들은 그것을 같은 열린 통신 채널을 통해 메시지를 보내기 위한 암호화 키로 사용할 수 있습니다.

물론 n mod 23의 가능한 결과가 23개에 불과하기 때문에 이 예제를 안전하게 만들려면 a, b, p 값이 훨씬 더 커야 합니다. 그러나 p가 최소 600자리의 소수라면, 가장 빨리 알려진 알고리즘을 사용하는 가장 빠른 현대 컴퓨터도 주어진 g, p 및 g mod^a p만 찾을 수 없습니다. 이러한 문제를 이산 로그 문제라고 합니다.^[3] g^a mod p의 계산은 모듈식 지수화로 알려져 있으며 큰 수에서도 효율적으로 수행할 수 있습니다. g는 전혀 클 필요가 없으며, 실제로는 대개 작은 정수(2, 3, ... 등)입니다.

비밀도

아래 차트는 비밀이 아닌 값을 파란색으로, 비밀 값을 빨간색으로 표시하여 누가 무엇을 알고 있는지 보여줍니다. 여기서 이브는 도청자입니다 – 그녀는 앨리스와 밥 사이에 전송되는 것을 보지만, 그들의 대화 내용을 바꾸지는 않습니다.

• g, Alice, Bob 및 Eve에게 알려진 공용(primitive 루트) 베이스. g = 5
• p, 앨리스, 밥, 이브에게 알려진 공공 (프라임) 모듈러스. p = 23
• a, 앨리스에게만 알려진 앨리스의 개인 키. a = 6
• b, Bob의 개인 키는 Bob에게만 알려져 있습니다. b = 15
• A, 앨리스, 밥, 이브에게 알려진 앨리스의 공개 키. A = g^a mod p = 8
• B, Alice, Bob, Eve에게 알려진 Bob의 공개 키. B = g^b mod p = 19

앨리스야. 알려진. 알 수 없는 p = 23 g = 5 a = 6 b A = 5a mod 23 A = 56 mod 23 = 8 B = 19 s = Ba mod 23 s = 196 mod 23 = 2

밥. 알려진. 알 수 없는 p = 23 g = 5 b = 15 a B = 5b mod 23 B = 515 mod 23 = 19 A = 8 s = Ab mod 23 s = 815 mod 23 = 2

이브 알려진. 알 수 없는 p = 23 g = 5 a, b A = 8, B = 19 s

Now s는 공유된 비밀키이고 앨리스와 밥 모두에게 알려져 있지만 이브에게는 알려져 있지 않습니다. 이브가 g^{a + b} mod p와 같은 AB를 계산하는 것은 도움이 되지 않습니다.

참고: Alice가 Bob의 개인 키를 위해 해결하거나 Bob이 Alice의 개인 키를 위해 해결하는 것은 어려울 것입니다. 앨리스가 밥의 개인 키를 해결하는 것이 어렵지 않다면(또는 그 반대의 경우), 도청자인 이브는 단순히 자신의 개인 키/공개 키 쌍을 대체하고, 밥의 공개 키를 개인 키에 꽂고, 가짜 공유 비밀 키를 만들어 밥의 개인 키를 해결할 수 있습니다(그리고 공유 비밀 키를 해결하는 데 사용합니다). 이브는 밥의 개인 키를 쉽게 해결할 수 있는 공개/개인 키 쌍을 선택하려고 시도할 수도 있습니다.

유한 순환군으로의 일반화

프로토콜에 대한 보다 일반적인 설명은 다음과 같습니다.^[10]

1. Alice와 Bob은 순서 n의 유한 순환군 G에서 자연수 n과 생성 원소 g에 대해 일치합니다. (이는 일반적으로 나머지 프로토콜보다 훨씬 이전에 수행되며, g와 n은 모든 공격자에 의해 알려진 것으로 가정됩니다.) 그룹 G는 곱셈적으로 작성됩니다.
2. Alice는 1 < a < n으로 임의의 자연수 a를 선택하고 G의 원소 g를^a Bob에게 보냅니다.
3. 밥은 1 < b < n 을 가진 임의의 자연수 b 를 선택하고, G 의 원소^b g 를 앨리스에게 보냅니다.
4. Alice는 G의 원소 (g) = g를 계산합니다.
5. Bob은 G의 원소 (g) = g를 계산합니다.

이제 앨리스와 밥 모두 공유 비밀 키 역할을 할 수 있는 그룹 요소 g = g를 소유하고 있습니다. 그룹 G는 g^ab, g^a, g를^b 결정하는 효율적인 알고리즘이 존재하지 않는 한 안전한 통신을 위한 요구 조건을 만족합니다.

예를 들어, 타원 곡선 Diffie-헬만 프로토콜은 G의 한 요소를 정수 모듈이 아닌 타원 곡선의 한 점으로 표현하는 변형입니다. 과립성 곡선을 사용한 변형도 제안되었습니다. 초단일 동위원소 키 교환은 디피(Diffie)입니다.양자 컴퓨터에 대해 안전하도록 설계된 헬만 변종이 2022년 7월에 고장났습니다.^[11]

임시 및/또는 정적 키

사용되는 키는 일시적이거나 정적(장기)인 키일 수 있지만, 반정적 DH라고 불리는 키를 혼합할 수도 있습니다. 이러한 변형은 특성이 다르므로 사용 사례가 다릅니다. 예를 들어, NIST SP 800-56A에서 많은 변형 및 일부 논의에 대한 개요를 확인할 수 있습니다.^[12] 기본 목록:

1. 일시적, 일시적: 일반적으로 키 합의에 사용됩니다. 순방향 비밀성을 제공하지만 진위 여부는 제공하지 않습니다.
2. 정적, 정적: 장기적인 공유 비밀을 생성할 수 있습니다. 순방향 비밀성을 제공하는 것이 아니라 암묵적인 진정성을 제공합니다. 예를 들어 키가 정적이기 때문에 다시 보기 공격으로부터 보호되지 않습니다.
3. 일시적, 정적: 예를 들어, ElGamal 암호화 또는 IES(Integrated Encryption Scheme)에서 사용됩니다. 키 합의에 사용될 경우 암묵적인 일방적인 진위 여부를 제공할 수 있습니다(일시적인 측에서는 정적인 측의 진위 여부를 확인할 수 있습니다). 순방향 비밀은 제공되지 않습니다.

NIST SP 800-56A에서와 같이 더 많은 보안을 제공하기 위해 하나의 키 합의에서 일시적 키와 정적 키를 사용할 수 있지만, 단일 DH 키 교환에 있는 키를 결합하여 3-DH(트리플 DH)라고 하는 것도 가능합니다.

트리플디피-헬맨(3-DH)

1997년 사이먼 블레이크-윌슨, 돈 존슨, 알프레드 메네제스가 C에 의해 개선된 "주요 협정 프로토콜과 그들의 보안 분석(1997)"^[13]에서 일종의 삼중 DH를 제안했습니다. Kudla와 K.G. Paterson은 "주요 계약 프로토콜에 대한 모듈식 보안 증명(2005)"^[14]에서 안전한 것으로 나타났습니다. 다른 변형에도 사용되거나 언급됩니다. 예:

• 확장 트리플 디피-헬맨
• sci. crypt 뉴스 그룹 (2002.08.08 ~ )
• 이중 래칫 알고리즘
• 신호 프로토콜

Alice와 Bob의 장기 비밀 키는 각각 a와 b로 표시되며, 공개 키 A와 B, 그리고 임시 키 쌍 x, X와 y, Y로 표시됩니다. 프로토콜은 다음과 같습니다.

Triple Diffie-Hellman 프로토콜

$$(A = ${\$displaystyle A = g^{a}})		밥 ($$ = ${\displaystyle {}^{}}$ ${\$display style B = g^{b}})
${\displaystyle X=g^{x}}$	${\displaystyle X\오른쪽 화살표 {}$
	${\displaystyle {}\leftarrow Y}$	${\displaystyle Y=g^{y}}$
${\displaystyle K=\operatorname {KDF} \left(Y^{x},\,B^{x},\,Y^{a},\,X,\,Y,\,A,\,B\right)}$		${\displaystyle K=\operatorname {KDF} \left(X^{y},\,X^{b},\,A^{y},\,X,\,Y,\,A,\,B\right)}$

장기 공개 키는 어떻게든 전송해야 합니다. 이는 신뢰할 수 있는 별도의 채널에서 사전에 수행할 수 있으며, 익명성을 유지하기 위해 일부 부분 키 합의를 사용하여 공개 키를 암호화할 수 있습니다. 이러한 세부 사항뿐만 아니라 사이드 채널 보호나 명시적 키 확인, 초기 메시지 및 추가 비밀번호 인증과 같은 기타 개선 사항에 대해서도 "키 합의 및 선택적 인증을 위한 고급 모듈식 핸드셰이크"^[16]를 살펴볼 수 있습니다.

2인 이상의 당사자가 있는 운영

Diffie–헬만 키 합의는 단 두 명의 참가자가 공유하는 키를 협상하는 것에 국한되지 않습니다. 계약 프로토콜의 반복을 수행하고 중간 데이터를 교환하여 모든 사용자가 계약에 참여할 수 있습니다(자체는 비밀로 할 필요가 없습니다). 예를 들어, 앨리스, 밥, 캐롤은 디피에 참여할 수 있었습니다.헬만 협정은 다음과 같으며, 모든 작업은 모듈화됩니다.

1. 당사자들은 알고리즘 매개변수 p와 g에 대해 동의합니다.
2. 당사자들은 a, b, c라는 이름의 개인 키를 생성합니다.
3. Alice는^a g mod p를 계산하여 Bob에게 보냅니다.
4. Bob은 () mod p = g mod p를 계산하여 Carol에게 보냅니다.
5. Carol은 () mod p = g mod p를 계산하여 자신의 비밀로 사용합니다.
6. 밥은^b g mod p를 계산해서 캐롤에게 보냅니다.
7. Carol은 () mod p = g mod p를 계산하여 Alice로 보냅니다.
8. Alice는 () mod p = g mod p = g mod p를 계산하여 자신의 비밀로 사용합니다.
9. 캐롤은^c g mod p를 계산해서 앨리스에게 보냅니다.
10. Alice는 () mod p = g mod p를 계산하여 Bob에게 보냅니다.
11. 밥은 () mod p = g mod p = g mod p를 계산하여 자신의 비밀로 사용합니다.

도청자는 g^a mod p, g^b mod p, g^c mod p, g^ab mod p, g^ac mod p, g^bc mod p를 볼 수 있었지만, g^abc mod p를 효율적으로 재생하기 위해 이들의 어떤 조합도 사용할 수 없습니다.

이 메커니즘을 더 큰 그룹으로 확장하려면 다음 두 가지 기본 원칙을 따라야 합니다.

• g로만 구성된 "빈" 키에서 시작하여 현재 값을 모든 참가자의 개인 지수로 순서에 상관없이 한 번 올리는 방식으로 비밀을 만듭니다(첫 번째 이러한 지수는 참가자 자신의 공개 키를 산출합니다).
• 중간값(최대 N-1 지수 적용, 여기서 N은 그룹 참여자 수)은 공개적으로 공개될 수 있지만 최종값(모든 N 지수 적용)은 공유 비밀을 구성하므로 공개적으로 공개되어서는 안 됩니다. 따라서 각 사용자는 마지막으로 자신의 개인 키를 적용하여 비밀의 복사본을 얻어야 합니다(그렇지 않으면 마지막 기여자가 그룹이 보호하고자 하는 바로 그 비밀로 키를 바꾸었기 때문에 마지막 기여자가 최종 키를 수신자에게 전달할 방법이 없을 것입니다).

이러한 원칙은 참가자가 키에 기여하는 순서를 선택할 수 있는 다양한 옵션을 열어 둡니다. 가장 간단하고 명확한 해결책은 N명의 참가자를 원 안에 배치하고 N개의 키를 원 안에서 회전시키는 것입니다. 결국 모든 키가 N명의 참가자(소유자와 함께 종료)에 의해 기여되고 각 참가자가 N개의 키(자신의 키와 함께 종료)에 기여할 때까지 말입니다. 그러나 이를 위해서는 모든 참가자가 N개의 모듈식 지수를 수행해야 합니다.

보다 바람직한 순서를 선택하고 키가 중복될 수 있다는 사실에 의존함으로써 각 참가자가 수행한 모듈식 지수를 8명의 참가자에 대해 주어진 분할 정복 방식을 사용하여 (N)+1로 기록하는₂ 횟수를 줄일 수 있습니다.

1. 참가자 A, B, C, D는 각각 하나의 지수를 수행하여 g를^abcd 산출합니다. 이 값은 E, F, G, H로 전송됩니다. 그 대가로 참가자 A, B, C, D는 g를^efgh 받습니다.
2. 참가자 A와 B는 각각 하나의 지수화를 수행하여 G를^efghab C와 D로 보내고, C와 D는 동일하게 수행하여 G를^efghcd 생성하여 A와 B로 보냅니다.
3. 참가자 A는 지수화를 수행하여 g를^efghcda B에게 보내고, 마찬가지로 B는 A에게 g를^efghcdb 보냅니다. C와 D는 비슷하게 합니다.
4. 참가자 A는 하나의 최종 지수를 수행하여 비밀 g = g를 산출하는 반면, B는 g = g를 얻기 위해 동일하게 수행합니다. 다시 C와 D는 유사하게 수행됩니다.
5. 참가자 E~H는 동시에 g를^abcd 시작점으로 하여 동일한 연산을 수행합니다.

이 작업이 완료되면 모든 참가자는 비밀 g를^abcdefgh 소유하게 되지만, 각 참가자는 단순한 순환 배열로 암시된 8개가 아닌 4개의 모듈식 지수를 수행하게 됩니다.

보안.

프로토콜은 G와 g가 적절하게 선택되면 도청자에 대해 안전하다고 간주됩니다. 특히 G 그룹의 순서가 커야 합니다. 특히 동일한 그룹이 대용량 트래픽에 사용되는 경우에는 더욱 그렇습니다. 도청자는 디피를 풀어야 합니다.g를^ab 구하는 헬만 문제. 이는 현재 주문량이 충분히 많은 그룹에서는 어려운 것으로 간주됩니다. 이산 로그 문제를 푸는 효율적인 알고리즘은 a나 b를 쉽게 계산하고 디피를 푸는 것을 가능하게 할 것입니다.헬만 문제, 이것과 다른 많은 공개 키 암호 시스템을 불안정하게 만듭니다. 특성이 작은 필드는 덜 안전할 수 있습니다.^[17]

G의 순서는 Pohlig의 사용을 방지하기 위한 큰 주요 인자를 가져야 합니다.a 또는 b를 구하는 헬만 알고리즘. 이러한 이유로 소피 제르맹 소수 q는 때때로 안전 소수라고 불리는 p = 2q + 1을 계산하는 데 사용되는데, 그 이유는 G의 순서가 2와 q로 나뉘기 때문입니다. 그런 다음 g는 G가 아닌 G의 순서 q 부분군을 생성하도록 선택되어 g의 레전드르 기호가 a의 낮은 순서 비트를 절대 드러내지 않습니다. 이러한 선택을 사용하는 프로토콜은 예를 들어 IKEv2입니다.^[18]

g는 종종 2와 같은 작은 정수입니다. 이산 로그 문제의 무작위 자기 축소성 때문에 작은 g는 같은 그룹의 다른 생성기와 마찬가지로 안전합니다.

앨리스와 밥이 출력이 완전히 무작위적이지 않고 어느 정도 예측할 수 있는 난수 생성기를 사용하면 도청하기가 훨씬 쉽습니다.

원래 설명에서, 디피-헬만 교환은 그 자체로 통신 당사자에 대한 인증을 제공하지 않으므로 중간자 공격에 취약합니다. 말로리(Man-in-the-middle 공격을 실행하는 능동 공격자)는 두 개의 별개의 키 교환을 설정할 수 있습니다. 하나는 앨리스로, 다른 하나는 밥으로 위장하여 사실상 앨리스에서 밥으로 위장하고, 반대로 그녀가 암호를 해독한 다음, 그들 사이에 전달된 메시지를 다시 암호화할 수 있습니다. Mallory는 Alice와 Bob이 통신할 때마다 메시지를 적극적으로 해독하고 다시 암호화하면서 계속 중간에 있어야 합니다. 만약 그녀가 부재한다면, 앨리스와 밥에게 그녀의 이전의 존재가 드러납니다. 그들은 그들의 모든 사적인 대화가 채널의 누군가에 의해 가로채고 해독되었다는 것을 알 것입니다. 대부분의 경우 말로리가 두 교환에 동일한 키를 사용했더라도 말로리의 개인 키를 얻는 데 도움이 되지 않습니다.

이러한 유형의 공격을 방지하기 위해서는 일반적으로 통신 당사자를 서로 인증하는 방법이 필요합니다. Diffie의 변형 –이러한 유형의 공격을 피하기 위해 STS 프로토콜과 같은 헬만을 대신 사용할 수 있습니다.

인터넷 트래픽에 대한 실질적인 공격

일반적으로 이산 로그 문제를 푸는 데 가장 효과적인 숫자 필드 체 알고리즘은 4개의 계산 단계로 구성됩니다. 처음 세 단계는 그룹 G의 순서에만 의존하고 유한 로그를 원하는 특정 숫자에는 의존하지 않습니다.^[19] 많은 인터넷 트래픽이 1024비트 이하의 소수 그룹 중 하나를 사용하는 것으로 나타났습니다.^[3] 가장 일반적인 그룹에 대해 숫자 필드 체의 첫 세 단계를 미리 계산함으로써, 공격자는 특정 로그를 얻기 위해 첫 세 단계보다 계산 비용이 훨씬 덜 드는 마지막 단계만 수행하면 됩니다. Logjam 공격은 이 취약성을 이용하여 순서가 512비트 소수인 그룹을 사용할 수 있는 다양한 인터넷 서비스를 손상시켰습니다. 저자들은 단일 512비트 프라임에 대한 데이터를 미리 계산하기 위해 일주일 동안 수천 개의 CPU 코어가 필요했습니다. 이렇게 하면 18코어 Intel Xeon CPU 2개를 사용하여 약 1분 만에 개별 로그를 해결할 수 있습니다.^[3]

로그잼 공격의 저자들이 추정한 바와 같이, 1024비트 프라임에 대한 이산 로그 문제를 해결하는 데 훨씬 더 어려운 사전 계산은 미국 국가 안보국(NSA)과 같은 대형 국가 정보 기관의 예산 범위 내에서 1억 달러의 비용이 들 것입니다. Logjam 저자들은 광범위하게 재사용되는 1024비트 DH 소수점에 대한 사전 계산이 NSA가 현재 암호화의 많은 부분을 깰 수 있다는 유출된 NSA 문서의 주장의 배경이라고 추측합니다.^[3]

이러한 취약성을 피하기 위해, Logjam 저자들은 유사한 공격이 알려지지 않은 타원 곡선 암호를 사용할 것을 권장합니다. 그들은 디피의 순서 p를 추천합니다.헬만 그룹은 최소 2048비트여야 합니다. 그들은 2048비트 프라임에 필요한 사전 계산이 1024비트 프라임보다 10배⁹ 더 어렵다고 추정합니다.^[3]

기타 용도

암호화

Diffie 기반 공개 키 암호화 방식-헬만 키 교환이 제안되었습니다. 그러한 체계의 첫 번째는 ElGamal 암호화입니다. 더 현대적인 변형은 통합 암호화 체계입니다.

순방향비밀

순방향 비밀성을 달성하는 프로토콜은 각 세션에 대해 새로운 키 쌍을 생성하고 세션이 끝날 때 폐기합니다. 디피-헬만 키 교환은 빠른 키 생성 때문에 이러한 프로토콜에 자주 선택됩니다.

비밀번호인증키약정

Alice와 Bob이 비밀번호를 공유할 때, 그들은 Diffie의 비밀번호 인증 키 합의(PK) 양식을 사용할 수 있습니다.중간자 공격을 막기 위한 헬맨. 한 가지 간단한 방법은 연결된 해시를 채널의 양쪽 끝에서 독립적으로 계산된 암호와 비교하는 것입니다. 이러한 체계의 특징은 공격자가 상대방과 반복할 때마다 하나의 특정 암호만 테스트할 수 있으므로 시스템은 상대적으로 취약한 암호로 우수한 보안을 제공한다는 것입니다. 이 접근 방식은 G.hn 홈 네트워킹 표준에서 사용하는 ITU-T 권장 사항 X.1035에 설명되어 있습니다.

이러한 프로토콜의 예로는 Secure Remote Password 프로토콜이 있습니다.

공개키

Diffie를 사용하는 것도 가능합니다.Hellman은 공개 키 인프라의 일부로서 Bob이 메시지를 암호화하여 Alice의 공개 키에 대한 신뢰할 수 있는 지식을 가지고 있는 것 외에 그들 사이의 사전 통신 없이 Alice만 메시지를 해독할 수 있도록 허용합니다. Alice의 공개 키는${\displaystyle }$(${\displaystyle ga}$ ${\displaystyle mod}$ p${\displaystyle ,}$ g${\displaystyle ,}$ ${\displaystyle p}$)$${\$displaystyle (g^{a}{\bmod {p}},$ g$,p)}$ 입니다$.$ 그녀에게 메시지를 보내려면, Bob은 랜덤 b를 선택한 다음 Alice ${\displaystyle g^{}}$ $b{\displaystyle {}^{}}$ ${\displaystyle mod}$ p ${\$암호화되지 않음)를 대칭키$({\displaystyle {ga}^{}{}^{}}$ b ${\displaystyle mod}$ p ${\$ ($g^{a})^{b}{\bmod {p}}$로 암호화된 메시지와 함께 보냅니다$.$ 앨리스만이 대칭 키를 결정할 수 있으므로 메시지를 해독할 수 있습니다. 왜냐하면 앨리스만이 (개인 키)를 가지고 있기 때문입니다. 사전 공유 공개 키를 사용하면 중간자 공격도 방지할 수 있습니다.

실제로, 디피-헬만은 이러한 방식으로 사용되지 않으며, RSA가 지배적인 공개 키 알고리즘입니다. 이는 주로 역사적, 상업적인 이유 때문입니다.^{[citation needed]} 즉, RSA Security가 Verisign이 된 키 서명을 위한 인증 기관을 만든 것입니다. Diffie–헬만은 위에서 설명한 바와 같이 인증서 서명에 직접 사용할 수 없습니다. 그러나 ElGamal 및 DSA 서명 알고리즘은 수학적으로 관련되어 있으며, 인터넷 프로토콜 통신의 보안을 위한 IPsec 프로토콜 모음의 MQV, STS 및 IKE 구성 요소도 관련되어 있습니다.

참고 항목

• 타원곡선 디피-헬만키 교환
• 초단일 동위원소 키 교환
• 순방향비밀

메모들

참고문헌

일반 참고문헌

• Gollman, Dieter (2011). Computer Security (2nd ed.). West Sussex, England: John Wiley & Sons, Ltd. ISBN 978-0470741153.
• Williamson, Malcolm J. (January 21, 1974). Non-secret encryption using a finite field (PDF) (Technical report). Communications Electronics Security Group. Archived (PDF) from the original on 2017-03-23. Retrieved 2017-03-22.
• Williamson, Malcolm J. (August 10, 1976). Thoughts on Cheaper Non-Secret Encryption (PDF) (Technical report). Communications Electronics Security Group. Archived (PDF) from the original on 2004-07-19. Retrieved 2015-08-25.
• 비밀 암호화의 역사 JH Ellis 1987 (28K PDF 파일) (HTML 버전)
• 공개키 암호의 첫 10년 Whitfield Diffie, IEEE Proceedings of the IEEE, vol. 76, No. 5, 1988년 5월, pp: 560–577 (1.9)MBPDF파일)
• 메네즈, 알프레드, 반 오어쇼트, 폴, 반스톤, 스콧 (1997). 응용 암호학 핸드북, 플로리다 보카 라톤: CRC 프레스. ISBN 0-8493-8523-7. (온라인 사용 가능)
• 싱, 사이먼 (1999) 코드북: 스코틀랜드의 메리 퀸에서 양자암호학으로의 비밀의 진화 뉴욕: 더블데이 ISBN 0-385-49531-5
• 공개키 암호의 개요 마틴 E. Hellman, IEEE Communications Magazine, 2002년 5월, pp. 42–49. (123kB PDF 파일)

외부 링크

이 기사의 외부 링크 사용은 위키백과의 정책이나 지침을 따르지 않을 수 있습니다. 과도하거나 부적절한 외부 링크를 제거하고, 해당되는 경우 유용한 링크를 각주 참조로 변환하여 이 글을 개선해 주시기 바랍니다. (2016년 3월) (본 템플릿 메시지를 제거하는 방법과 시기에 대해 알아보십시오.)

• 미네소타 대학교 찰스 배비지 연구소의 마틴 헬먼 구술 역사 인터뷰. 선도적인 암호학 학자인 마틴 헬만(Martin Hellman)은 1970년대 중반 스탠포드 대학의 공동 연구자인 휘트필드 디피(Whitfield Diffie) 및 랄프 머클(Ralph Merkle)과 함께 공개 키 암호학을 발명한 배경과 기본적인 통찰력에 대해 논의합니다.
• RFC 2631 – Diffie–헬만 키 합의 방법. E. 레스콜라. 1999년 6월.
• RFC 3526 – MODP(Modular Exponential) Diffie –인터넷 키 교환(IKE)을 위한 헬만 그룹. T. Kivinen, M. Kojo, SSH 통신 보안부입니다. 2003년 5월.
• ANSI X9.42 요약: 이산로그 암호를 이용한 대칭키 합의 (64K PDF 파일) (ANSI 9 표준 설명)
• 2007년 Talk by Martin Hellman, YouTube 동영상
• Crypto dream team Diffie & Hellman, $100M 2015 Turing Award 수상 (일명 "컴퓨팅 노벨상")
• 디피-Python3에서 작성된 Hellman 데모 – 이 데모는 매우 큰 키 데이터를 적절히 지원하고 필요한 경우 소수를 사용하도록 강제합니다.