기술 요약: MCSI – 마스킹된 가환 초특이 등가류 키 교환 (A Masked Commutative Supersingular Isogeny Key Exchange)

1. 문제 정의

본 논문은 CSIDH(Commutative Supersingular Isogeny Diffie-Hellman) 작용에 기반한 포스트 양자 인증 키 교환(AKE) 프로토콜의 설계를 다룹니다. CSIDH는 포스트 양자 제품군 중 가장 작은 공개 키를 제공하지만, 이 군 작용(group action) 상에서의 표준 미인증 교환은 다음과 같은 두 가지 주요 문제를 겪습니다:

1. 서비스 거부(DoS) 취약성: 표준 교환 방식에서 응답자(responder)는 개시자(initiator)가 제공한 곡선에 대해 값비싼 군 작용(수십 밀리초 소요)을 수행해야 하며, 메시지의 진위 여부를 확인하기 전까지는 이를 수행할 수밖에 없습니다. 인증되지 않은 공격자는 응답자가 이 비용이 많이 드는 계산을 반복적으로 수행하도록 강제할 수 있습니다.
2. 에페머럴(Ephemeral) 기밀성 결여: 표준 CSIDH 교환은 에페머럴 공개 요소(곡선)를 평문으로 전송하므로, 수동적 도청자가 키 교환의 중간 상태를 관찰할 수 있게 합니다.

또한, 본 논문은 흔히 오해되는 사실을 명확히 합니다. SIDH 계열의 이소제니 암호와 달리, 가환 CSIDH 계열은 토션 포인트 이미지를 공개하지 않습니다. 따라서 여기서의 "마스킹(masking)"은 토션 포인트 공격(SIDH를 무너뜨린 공격)에 대한 대응책이 아니라, 에페머럴 공개 요소를 숨기고 DoS를 방지하기 위한 메커니즘입니다.

2. 방법론 및 프로토콜 설계

저자들은 CSIDH 군 작용과 인증 암호화(Authenticated Encryption)를 통합한 2-메시지 키 교환 프로토콜인 MCSI(Masked Commutative Supersingular Isogeny)를 제안합니다.

핵심 메커니즘

• 정적 키(Static Keys): 양 당사자는 CSIDH 클래스 군 작용으로부터 유도된 장기 정적 키 쌍 $(a, pk_A)$ 및 $(b, pk_B)$를 보유합니다.
• 정적-정적 공유 값 ($Z_{ss}$): 세션 시작 전, 당사자들은 각자의 정적 비밀값과 상대방의 정적 공개 키를 사용하여 공유 값 $Z_{ss} = (ab) \star x_0$를 계산합니다. 클래스 군의 가환성 덕분에 양 당사자는 동일한 $Z_{ss}$를 도출합니다.
• 블라인딩 레이어(Blinding Layer): 정적-정적 공유 값 $Z_{ss}$는 **인증된 연관 데이터 기반 암호화(AEAD)**를 위한 대칭 키를 유도하는 데 사용됩니다.
• 프로토콜 흐름:
  1. 개시자(Initiator): 에페머럴 비밀 $u$를 생성하고, 에페머럴 공개 요소 $T_A = u \star x_0$를 계산한 뒤, $Z_{ss}$로 키잉된 AEAD 스킴을 사용하여 이를 암호화하여 전송합니다.
  2. 응답자(Responder): 캐싱된 $Z_{ss}$로부터 유도된 키를 사용하여 메시지를 복호화합니다. 만약 인증 태그(authentication tag) 검증에 실패하면, 응답자는 값비싼 군 작용 계산을 수행하지 않고 즉시 해시/태그 확인 단계에서 중단합니다. 유효하다면, $T_A$를 복구하고 자신의 에페머럴 비밀 $w$를 생성하여 $T_B = w \star x_0$를 계산한 후, 이를 암호화하여 보냅니다.
  3. 키 유도: 양 당사자는 트랜스크립트(transcript)와 다음 세 가지 공유 값을 해싱하여 세션 키를 계산합니다:
     • $Z_{ee} = (uw) \star x_0$ (에페머럴-에페머럴, 순방향 비밀성 제공).
     • $Z_{es} = (ub) \star x_0$ (에페머럴-정적, 인증 제공).
     • $Z_{se} = (aw) \star x_0$ (정적-에페머럴, 인증 제공).
     • $Z_{ss}$ (정적-정적, 마스킹에 사용).

설계 근거

저자들은 블라인딩 키를 세션 비밀 자체로부터 유도하는 것이 순환 의존성을 만들기 때문에 이를 명시적으로 거부하며, 대신 사전에 공유된 정적-정식 값을 신뢰합니다. 또한, 공개 바이트 치환 레이어(S-box)를 암호문에 추가하는 것이 보안상 추가적인 이득을 주지 않음을 증명하여, 표준 AEAD를 수정 없이 사용하는 것을 정당화합니다.

3. 주요 기여

본 논문은 다음과 같은 구체적인 기여를 합니다:

1. 프로토콜 명세: CSIDH로 구현 가능한 추상적 유효 군 작용 위에서의 MCSI 프로토콜 명세를 제공합니다. 여기에는 블라인딩 키가 세션 비밀이 아닌 정적 비밀로부터 유도되어야 한다는 설계 논거가 포함됩니다.
2. 정확성 증명: 클래스 군의 가환성, 군 작용 공리, 그리고 Montgomery 곡선 대표자의 유일성에 엄격히 의존하는 제로 에러 정확성(zero-error correctness) 정리를 증명합니다.
3. 보안 증명: **강한 병렬화 가정(Strong Parallelisation Assumption, GA-StCDH)**으로 환원되는 세 가지 Random Oracle Model(ROM) 보안 정리를 제시합니다:
   • 세션 키 식별 불가능성: 수동적 공격자에 대해 세션 키는 무작위 값과 구별할 수 없습니다.
   • 블라인딩 기밀성: 에페머럴 요소는 수동적 관찰자로부터 숨겨집니다.
   • 전송 무결성: 정적 비밀이 없는 공격자는 수신자가 수락할 수 있는 메시지를 위조할 수 없습니다.
   • 참고: 증명은 CSIDH에서 genus theory로 인해 거짓임이 알려진 결정적 군 작용 가정(GA-DDH)을 명시적으로 피합니다.
4. 파라미터 분석: 소수 선택에 대한 비판적 분석을 수행합니다. 저자들은 표준 타원 곡선 이산 로그 문제(예: $p = 2^{521}-1$인 NIST P-521)를 위해 선택된 소수들이 CSIDH에서는 사용 불가능함을 보여줍니다. 이는 $p+1$이 효율적인 계산 가능한 클래스 군 작용을 생성하는 데 필요한 매끄러움(smoothness, 작은 소인수들)을 갖추지 못하기 때문입니다.
5. 참조 구현: 알려진 정답 벡터(known answer vectors)를 통해 교차 검증된 휴대 가능한 C 및 Python 이중 구현을 제공합니다.
6. 부채널 분석: 참조 구현의 타이밍 동작을 상세히 측정하여, 최적화되지 않은 구현이 실행 시간을 통해 개인키의 1-노름(one-norm)을 유출함을 밝혀냈습니다.

4. 결과 및 측정

성능 및 오버헤드

• 비용: 프로토콜은 당사자당 세션당 4번의 군 작용 계산을 요구합니다($Z_{ss}$를 위한 1회의 캐싱된 계산 포함). 이는 인증되지 않은 CSIDH 교환보다 2배 높은 수치이지만, 대칭 레이어(AEAD)의 비용은 군 작용(130 ms)에 비해 무시할 만한 수준(4 $\mu$s)입니다.
• DoS 완화: 주요 성능 이점은 DoS 저항성에 있습니다. 인증되지 않은 메시지는 군 작용 계산(130 ms)이 아닌 태그 확인(2.4 $\mu$s) 단계에서 거부되므로, 약 50,000배의 속도 향상을 보입니다.
• 크기: MCSI는 격자 기반(ML-KEM) 또는 코드 기반(Classic McEliece) 대안보다 현저히 작은 공개 키를 제공합니다. 512비트 보안 레벨의 경우, 공개 키는 64바이트이며 총 세션 트래픽은 192바이트입니다.

구현 결과

• 타이밍 누설: 참조 구현은 상수 시간(constant-time)이 아닙니다. 저자들은 개인키의 1-노름과 실행 시간 사이에 강한 상관관계(Pearson 0.90)가 있음을 측정했습니다.
• 누설 심각도: 1-노름 차이가 단 5(최대 370 중)인 두 키를 약 200번의 타이밍 측정만으로 구별할 수 있습니다.
• 검증: 감사 결과, Validate 함수(곡선의 초특이성 여부 확인)는 비밀 의존적 제어 흐름이 없는 것으로 나타났으나, 군 작용 계산 자체는 구조적으로 정보를 유출합니다.

5. 의의 및 한계

본 논문은 MCSI를 배포 가능한 솔루션이 아닌, 작동하는 참조 구현을 갖춘 하나의 명세로 규정합니다.

의의:

• 암묵적 상호 인증 및 에페머럴 기밀성을 갖춘 CSIDH 기반의 인증된 키 교환이 가능하다는 것을 입증합니다.
• "마스킹"이 깨진 결정적 가정(GA-DDH)에 의존하지 않음을 엄격하게 증명합니다.
• CSIDH와 같은 가환 이소제니를 위해서는 소수가 매끄러움(smoothness)을 위해 특수하게 구성되어야 한다는, 흔히 간과되는 중요한 제약 조건을 강조합니다.

명시적 한계 (논문이 증명하지 않은 것):

• 블라인딩의 순방향 비밀성: 공격자가 나중에 정적 비밀을 획득하면, $Z_{ss}$를 재계산하여 기록된 트랜스크립트에서 블라인딩을 제거하고 에페머럴 요소를 드러낼 수 있습니다.
• 강한 보안 모델: 본 증명은 에페머럴 키 노출이나 키 탈취 임파슨(key compromise impersonation)에 대한 저항성을 다루는 CK(Canetti-Krawczyk) 또는 확장된 CK 모델을 다루지 않습니다.
• 능동적 공격자: 전송 무결성은 증명되었으나, 메시지 전달을 제어하는 능동적 공격자에 대한 완전한 세션 키 보안은 확립되지 않았습니다.
• 구현 보안: 참조 구현은 상수 시간이 아니며 타이밍 공격에 취로합니다. 저자들은 실제 배포를 위해 상수 시간 실행이 필수적인 전제 조건임을 명시합니다.
• 악의적인 피어: 프로토콜은 유효한 정적 키를 보유하고 있으나 악의적으로 행동하는 피어를 보호하기 위한 Fujisaki-Okamoto 변환을 포함하지 않습니다.

결론적으로, MCSI는 이론적으로 견고하고 효율적이며 작은 크기의 포스트 양자 키 교환 설계를 제공하지만, 저자들은 실제 환경에서 안전하게 사용하기 위해서는 상수 시간 실행과 같은 상당한 하드닝(hardening) 과정이 선행되어야 함을 강조합니다.