디피-헬만 키 교환

디피-헬만 프로토콜은 두 당사자가 사전에 공유된 키 없이도 안전하지 않은 채널을 통해 공유 비밀을 설정할 수 있도록 하며, 이는 개인 지수에서 파생된 공개 값을 교환함으로써 이루어집니다.

Definition

디피-헬만 키 교환은 각 당사자가 공통 생성자를 개인 지수로 거듭제곱하고, 그 결과를 교환하며, 수신된 값을 자신의 지수로 다시 거듭제곱하여, 도청자가 계산하기 어려운 동일한 공유 비밀에 도달하는 프로토콜입니다.

Scope

이 주제는 디피-헬만 키 교환 프로토콜과 그 보안의 기반이 되는 이산 로그 문제, 계산 및 결정 디피-헬만 가정, 동일한 구조를 기반으로 하는 엘가말 암호화, 순방향 비밀성을 위한 임시 키 교환, 그리고 인증을 필요로 하는 중간자 공격 위협을 다룹니다. RSA(인수분해 기반)와 디피-헬만의 타원 곡선 구현은 제외되며, 이는 타원 곡선 암호화에서 다루어집니다.

Core questions

• 도청자가 모든 메시지를 보는 상황에서 두 당사자가 어떻게 공유 비밀에 합의할 수 있습니까?
• 이산 로그 문제가 교환된 비밀을 복구하기 어렵게 만드는 이유는 무엇입니까?
• 계산 디피-헬만(Computational Diffie-Hellman) 가정과 결정 디피-헬만(Decisional Diffie-Hellman) 가정의 차이점은 무엇입니까?
• 임시 디피-헬만은 어떻게 순방향 비밀성을 제공합니까?
• 인증되지 않은 디피-헬만이 중간자 공격에 취약한 이유는 무엇입니까?

Key concepts

• 공유 비밀 합의
• 생성자 및 순환군
• 개인 및 공개 지수
• 이산 로그 문제
• 계산 디피-헬만 (CDH)
• 결정 디피-헬만 (DDH)
• 임시 키 교환 및 순방향 비밀성
• 중간자 공격
• 엘가말 암호화

Key theories

이산 로그의 어려움

디피-헬만은 모듈러 거듭제곱은 쉽지만, 공개 값으로부터 개인 지수(이산 로그)를 복구하는 것은 적절한 그룹에서 다루기 어렵다고 여겨지기 때문에 안전합니다.

계산 및 결정 디피-헬만 가정

보안은 CDH 가정(공유 비밀을 계산하기 어려움)과 더 강력한 DDH 가정(공유 비밀이 무작위와 구별할 수 없음)을 통해 공식화되며, 후자는 증명 가능한 보안 엘가말 스타일 암호화의 기반이 됩니다.

Mechanisms

공개 생성자 g를 가진 순환군(cyclic group)에서 앨리스는 비밀 a를 선택하고 g^a를 전송하며, 밥은 b를 선택하고 g^b를 전송합니다. 각자는 수신된 값을 자신의 지수로 거듭제곱하여 공유 비밀 g^(ab)를 계산합니다. 도청자는 g, g^a, g^b를 보지만, g^(ab)를 찾기 위해서는 이산 로그 문제 또는 디피-헬만 문제를 해결해야 합니다. 세션당 새로운(임시) 지수를 사용하면 순방향 비밀성(forward secrecy)이 제공됩니다. 즉, 나중에 장기 키가 손상되더라도 과거 세션 키는 노출되지 않습니다.

Clinical relevance

디피-헬만은 TLS, IPsec/IKE, SSH, Signal, WireGuard에서 키 설정의 기반이 됩니다. 임시 변형(DHE 및 타원 곡선 ECDHE)은 미래의 키 손상으로부터 기록된 트래픽을 보호하는 순방향 비밀성을 제공합니다. (인증서 또는 서명을 통한) 교환 인증은 일반 디피-헬만이 노출될 수 있는 중간자 공격을 방어하는 방법입니다.

Evidence & guidelines

유한체 디피-헬만 매개변수는 RFC 7919(안전한 명명된 그룹)에 명시되어 있으며, NIST SP 800-56A는 키 설정을 표준화합니다. 모범 사례는 순방향 비밀성을 위해 임시 키와 잘 검증된 그룹을 사용합니다. Logjam 공격(2015)은 취약한 512비트 수출 등급 및 재사용된 1024비트 그룹이 악용될 수 있음을 보여주었으며, 이는 2048비트 그룹 또는 타원 곡선으로의 전환을 촉발했습니다.

History

디피와 헬만은 1976년 논문에서 키 교환 프로토콜을 발표하여 공개 키 암호화를 시작했으며, 이는 머클의 초기 퍼즐 아이디어에 기반을 두었습니다. (말콤 윌리엄슨은 1974년 GCHQ에서 동등한 방법을 발견했습니다.) 엘가말은 1985년에 이 구성을 공개 키 암호화 및 서명 방식으로 일반화했습니다. 이 프로토콜은 유한체 그룹에서 타원 곡선으로 이동하여 인터넷에서 세션 키 설정의 표준 수단이 되었습니다.

Key figures

• Whitfield Diffie
• Martin Hellman
• Ralph Merkle
• Taher ElGamal
• Malcolm Williamson

Seminal works

• diffie1976
• katz2020
• menezes1996

Frequently asked questions

디피-헬만 자체로 당사자를 인증합니까?

아니요. 일반 디피-헬만은 공유 비밀을 설정하지만 상대방이 누구인지 확인하지 않으므로, 능동적인 공격자는 두 번의 교환을 실행하여 중간에 개입할 수 있습니다. 실제 프로토콜은 인증서, 서명 또는 사전 공유 키를 사용하여 교환을 인증합니다.

순방향 비밀성(forward secrecy)이란 무엇이며 디피-헬만은 어떻게 이를 제공합니까?

순방향 비밀성은 나중에 장기 키가 손상되더라도 과거 세션이 노출되지 않음을 의미합니다. 각 세션에 대해 새로운 임시 디피-헬만 지수를 사용하고 사용 후 폐기함으로써, 저장된 어떤 키도 이전에 기록된 트래픽을 재구성할 수 없도록 보장합니다.