Key exchanges

이번 장에서는

• key exchange가 무엇이고, 유용한
• Diffie-Hellman, Elliptic Curve-Hellman key exchange
• key exchange를 사용할 때의 보안 고려사항
  을 배울 것이다.

key exchanges란?

Key exchange는 안전한 통신을 위해 공통 비밀 키를 생성하거나 공유하는 방법이다

1. 문제: 안전한 키 공유

• 서비스를 운영하며 MAC으로 메시지의 무결성을 검증하려면, 키를 모든 사용자와 공유해야 합니다.
• 하지만 모든 사용자에게 같은 키를 배포하면, 악의적인 사용자가 MITM(중간자 공격)을 수행할 수 있고,
  각 사용자마다 다른 키를 설정하는 것은 비효율적이고 관리가 어렵습니다.

2. Key Exchange의 해결책

• 서버는 키 교환(Key Exchange) 키 쌍(공개 키/개인 키)을 생성하고, 클라이언트에게 공개 키를 제공합니다.
• 클라이언트는 서버의 공개 키를 사용하여 안전하게 키를 공유할 수 있습니다.
• Authenticated Key Exchange:
  서버의 공개 키를 클라이언트가 알고 있기 때문에, MITM 공격자가 서버를 가장할 수 없습니다.
• Mutually Authenticated Key Exchange:
  서버와 클라이언트 모두 인증된 키 교환을 수행하여 양측의 신뢰를 보장합니다.

3. 확장성 문제

• 사용자 수가 증가해도 Key Exchange는 확장성을 제공합니다.
• 그러나 서비스 수가 증가하면 문제 발생:
  • 각 브라우저가 모든 웹사이트의 공개 키를 저장해야 하는 비효율적인 상황이 발생합니다.
  • 인터넷 환경에서는 이를 해결하기 위해 PKI(Public Key Infrastructure) 같은 공개 키 관리 시스템이 필요합니다.

Key exchange는 효율적이고 안전한 키 공유를 가능하게 합니다. 특히 인증된 키 교환은 MITM 공격을 방지하며, 사용자와 서비스 간 신뢰를 확립합니다. 하지만 많은 서비스와 사용자가 연결되는 환경에서는 공개 키 관리 체계가 필요합니다.

4. Key exchange의 한계

• Key exchange는 효율적인 키 공유를 가능하게 하지만, 모든 시나리오에서 확장성 문제가 있을 수 있습니다.
• 특히 신뢰 확장이 필요한 경우, 디지털 서명이라는 보조 프리미티브가 필요합니다.
• 디지털 서명은 신뢰를 체계적으로 확장하는 데 도움을 줍니다. (7장에서 다룰 내용)

5. Key Exchange의 실제 사용:

• 실제로 Key exchange는 독립적으로 사용되기보다는 복잡한 프로토콜의 빌딩 블록으로 사용됩니다.
• 단, 특정 상황(예: 수동적인 공격자에 대한 방어)에서는 단독으로 유용할 수 있습니다.

6. libsodium을 사용한 Key Exchange 예제:

• libsodium 라이브러리는 안전한 Key exchange를 위한 인터페이스를 제공합니다.
• 내부적으로 X25519 키 교환 알고리즘을 사용

7. libsodium의 특징:

• 안전한 기본값을 제공하여 개발자가 복잡한 내부 세부사항을 직접 처리하지 않아도 됩니다.
• 안전하면서도 간단한 인터페이스로 Key exchange를 구현할 수 있습니다.

Diffie-Hellman(DH) key exchange

Group theory

DH key exchange는 group theory라는 수학 이론을 기반으로 생겼다.

group이란?

• elements의 set
• 이런 elements에 정의된 특수 이진 연산(+ 또는 ×)

set과 operation이 어떤 속성을 만족시키는 데 성공하면, 그룹이 된다.
(DH는 곱셈 그룹에서 작동한다)

집합과 그 연산이 그룹이 되려면 아래 속성이 필요하다.

• closure : 두 요소에 대해 operating하면 동일한 set의 또다른 element가 생긴다. 예로, 그룹 a와 b, ab는 또다른 그룹 요소이다.
• associativity : 한번에 여러개의 element를 순서에 상관없이 operating해도 결과는 같다. 예로, a(bc)와 (ab)c는 같은 그룹 element이다
• identity element : 이 element와 operating하여도 다른 operand의 결과는 바뀌지 않는다.
• inverse element : 모든 그룹 요소에 대한 역이 존재한다.

1. DH는 양의 정수 집합인 1,2,3,4,..., p-1로 구성된 그룹을 사용한다(p:prime number, 1: identity element)
2. modular multiplication를 특수하게 사용한다.

그룹은 두 가지고 나눈다.

• commutative(교환법칙)
• finite field(유한 필드)

cyclic subgroup은 단일 generator(or base)로 만들어질 수 있는 subgroup이다.

• group은 몇 속성을 가진 binary operation을 갖는 숫자 집합이다
• DH는 Galois group에서 동작한다. Galois group은 엄격히 양수에서 소수까지(포함되지 않음)의 집합과 모듈러 곱셈으로 구성된 그룹이다.
• DH group에서, 각 원소는 subgroup의 생성자이다.

Discrete Logarithm Problem(이산로그문제): DH의 기초

DH key exchange의 보안은 그룹 내의 이산 로그 문제에 의존하는데, 이 문제는 해결하기 어렵다.

예로, $3^x mod 5 = 2$에서 x는 3임을 쉽게 알 수 있지만, p(여기서 5)가 아주 큰 소수일 때는 계산이 매우 어렵다.

DH key exchange에서는 이 특성을 이용해 보안을 보장한다.

DH에서 key pair를 만드는 방법
1. 모든 참가자는 큰 소수 p와 generator g를 공유한다.
2. 각 참가자는 임의의 비공개 키 x를 생성한다
3. 각 참가자는 공개 키는 $g^x mod p$로 계산

DH key exchange algorithm에서 이 수학을 사용하는 방법

• alice는 비밀 키 a, 공개 키 $A=g^a mod p$를 가진다
• bob는 비밀 키 b, 공개 키 $B=g^b mod p$를 가진다

Bob의 공개 키를 알면, Alice는 shared secret을 $B^a mod p$로 계산할 수 있다.
Bob도 Alice의 공개 키와 자신의 개인 키로 $A^b mod p$ 계산을 할 수 있다.
당연히, 이 두 계산은 똑같은 값을 갖는다.
$B^a = (g^b)^a = g^ab = (g^a)^b = A^b mod p$

외부인이 공개키 A, B를 알아도 키 교환 $g^{ab}$의 결과를 알아낼 수 없다.

Diffie-Hellman 표준

Elliptic Curve Diffie-Hellman(ECDH) key exchange

elliptic curve란?

방정식을 푸는 모든 좌표 x와 y로 정의된다.
$y^2 + a_1xy + a_3y = x^3 + a_2x^2 + a_4x + a_6$

오늘날, 대부분의 곡선은 short Weierstrass equation으로 단순화될 수 있다.

$y^2 = x^3 + ax + b (where 4a^3 + 27b^2 ≠ 0)$

두 가지 유형의 곡선(binary curves, curves of characteristic 3)에 대한 단순화는 못하지만, 이러한 곡선은 거의 사용되지 않으므로, 이 장의 나머지 부분에서는 Weierstrass 형태를 사용할 것이다.

x, y는 좌표평면 상의 점을 나타내며, a, b는 곡선을 정의하는 상수이다.
$4a^3 + 27b^2 ≠ 0$ 조건은 곡선이 비특이(non-singular), 즉 뾰족하거나 교차하지 않도록 보장한다.

그래프의 모양: 타원모양이 아닌, 곡선 형태의 구조를 생성한다

addition operation

• 타원곡선 위의 두 점 $P(x_1, y_1), Q(x_2, y_2)$를 더해 새로운 점 $R(x_3, y_3)$를 정의한다.
• 이 연산은 곡선의 방정식과 기하학적 규칙에 따라 수행된다.
  • 점 P, Q를 잇는 직선이 곡선과 만나는 또다른 점 $R'$를 찾는다
  • 이 점 $R'$을 곡선에 대해 대칭 이동하여 최종 결과 $R$를 얻는다

이 규칙이 작동하지 않는 특이 케이스

• point를 그 자체에 추가하려면? 두 선간 선을 그리는 대신, 접선을 그린다
• 1단계(또는 2단계)에서 그린 선이 다른 어떤 지점에서 곡선과 닿지 않는다면 어떻게 될까? 결과를 만들어낸 점으로 정의해야 한다. 새로 만든 점을 point at infinity(O)라고 한다.

이제 우리는 암호화할 수 있는 그룹을 갖게 되었다.

이산로그 작동
point G를 취하고, 덧셈 연산을 통해 x번 더해서 또다른 점 P를 생성한다.
이를 $P = G+ ... +G$(x번)으로 쓸 수도 있고, mathematical syntactic sugar를 사용해 $P=[x]G$(x번의 G)로 쓸 수도 있다.
elliptic curve discrete logarithm problem(ECDLP)는 P와 G를 알면 숫자 x를 찾을 수 있다.

ECDH key exchange는 어떻게 동작하는가?

ECDH에서 key pair를 생성하려면

1. 모든 참가자는 타원 곡선 방정식, finite field(대부분 소수), generator G(base point, 기본점라고 함)에 대해 합의한다
2. 각 참가자는 랜덤 숫자 x를 생성한다 (비밀 키가 된다)
3. 각 참가자는 그들의 public key를 $[x]G$로 파생한다

보안

Elliptic Curve Discrete Logarithm Problem, ECDLP에 기반한다.

• 공개 키 $A=[a]G$에서 개인 키 a를 찾지 못한다.
• a, b를 알지 못하는 공격자는 $[a][b]G$를 계산할 수 없다

ECDH와 DH 비교

일반 DH에서는 $g^x mod p$와 같은 모듈러 거듭제곱을 사용하지만
ECDH는 타원곡선 위의 스칼라 곱 연산을 사용한다.
타원곡선은 더 작은 키 크기로 동일한 수준의 보안을 제공한다.

ECDH의 장점

1. 보안성: ECDLP는 계산이 매우 어려워, 공개키를 통해 개인 키를 찾는게 사실상 불가능하다.
2. key 크기 작음: DH에 비해 훨씬 작은 키 크기를 제공한다. RSA 2048 bit ≈ ECC 256 bit
3. 효율성: 연산량이 적어 모바일 및 IoT 환경에서 적합하다

수동적인 공격자는 공개 키를 보는 것만으로는 shared point를 도출해낼 수 없다.

ECDH 표준

타원곡선 암호학(ECC), ECDH key exchange에서 사용되는 표준
두 가지 주요 곡선 P-256, Curve25519

ECDH와 타원곡선 암호학의 채택
타원곡선 암호학은 1985년에 처음 발표된 이후로 강력한 보안을 제공하며 주요 정부와 기관(NATO, NSA 등)에 의해 채택되었습니다.
특히, 타원곡선은 기존 암호화 방식보다 더 작은 키 크기로 높은 보안을 제공하기 때문에 널리 사용됩니다.

ECDH 표준화의 역사
NIST 곡선 논란: 일부 연구는 NIST(미국 국립표준기술연구소)가 정의한 곡선들이 NSA에 의해 약화된 곡선일 가능성이 있다고 지적했습니다.

• Bruce Schneier는 NSA가 일부 곡선의 상수를 조작했을 가능성을 주장했습니다.

결과적으로, 현재 대부분의 애플리케이션은 두 가지 곡선에 집중합니다:

• P-256 (NIST FIPS 186-4)
• Curve25519 (RFC 7748)

P-256(secp256r1)

정의 : $y^2 = x^3 + ax + b mod p$

• $a = -3$
• b, p 는 고정된 큰 수
  • $b = 41058363725152142129326129780047268409114441015993725554835256314039467401291$
  • $p = 2^{256} – 2^{224} + 2^{192} + 2^{96} – 1$

속성

• 기본점(Base Point, $G$): 곡선 위의 고정된 점으로, 모든 계산의 시작점.
  - $G=(48439561293906451759052585252797914202762949526041747995844080717082404635286,$$36134250956749795798585127919587881956611106672985015071877198253568414405109)$
• Order : 곡선 위에 있는 점의 총 개수는 소수 $n$으로 정의됨.
  - $n=115792089210356248762697446949407573529996955224135760342422259061068512044369$
• 약 128 bit 의 보안 제공

논란

• P-256은 "Nothing-up-my-sleeve" 상수(임의 조작이 없음을 보장하는 상수)를 사용하지만, 상수 생성에 대한 명확한 설명이 부족합니다.
• 일부 전문가들은 이 상수가 NSA의 백도어 가능성을 배제하지 못한다고 주장합니다.

Curve25519

정의 : $y^2 = x^3 + 486662 x^2 + x$ mod $p$, where $p = 2^{255} – 19$
속성

• 기본점(base point): $G=(9, 14781619447589544791020593568409986887264606134616475288964881837755586237401)$
• order : $n=2^{252}+27742317777372353535851937790883648493$
• 약 128 bit 보안 제공
• Curve25519는 효율성과 간단함으로 인해 널리 사용된다
  X25519
• ECDH에서 Curve25519를 사용하는 경우, 이를 X25519라고 부른다
• 모바일 환경, TLS, VPN 등에서 널리 사용된다.

small subgroup attack과 다른 보안 고려사항

요약

인증되지 않은 key exchanges는 두 사용자가 서로 비밀을 공유할 수 있게 해주는 방법이다. 이 방식은 제3자가 몰래 엿보는 수동적 MITM(중간자 공격) 공격자가 이 비밀을 알아내는 것을 막는다.

인증된 key exchanges는 능동적 MITM 공격자가 통신 중 한쪽을 속이는 것을 방지한다. 상호 인증된 키 교환은 능동적 MITM 공격자가 양쪽 모두를 속이는 것을 막는다

인증된 key exchanges을 수행하려면 상대방의 공개 키를 알아야 한다. 하지만 이 방법은 확장성이 부족해서 더 복잡한 상황을 처리하려면 signature기술을 사용해야 한다.(7장에서 설명)

DH는 최초로 발명된 key exchanges 알고리즘이다.

DH를 사용할 때는 RFC 7919 표준을 따르자. 보통 2048 bit 소수 사용이 권장된다

타원곡선 디피 헬만(ECDH)는 DH보다 훨씬 작은 키 크기를 필요로 한다. 예로 128bit 수준의 보안을 원한다면, DH는 2048 bit 키를 써야하지만, ECDH는 256 bit 키만 있으면 된다.

ECDH에서 가장 널리 사용되는 곡선은 P-256과 Curve25519이다. 모두 128bit 수준의 보안을 제공. 256 bit 수준 보안이 필요하다면 P-521, Curve448을 사용하자.

키 교환을 구현할 때는 반드시 상대방으로부터 받은 공개 키가 유효한지 확인해야한다. 유효하지 않은 키는 많은 버그의 원인이 될 수 있기 때문이다.