SIKE: 노트북 한 대에 무너진 포스트퀀텀 암호

2022년 여름, 아이소제니 기반 암호는 좋은 한 해를 보내고 있었다. 10년 넘게 연구되어 온 SIDH — Supersingular Isogeny Diffie–Hellman — 와 그 위에 세워진 키 캡슐화 방식 SIKE는 NIST 포스트퀀텀 공모전에서 끝까지 살아남은 몇 안 되는 후보 중 하나였다. 그것도 가장 우아한 후보였다: 아주 작은 키, 그리고 고전 컴퓨터로도 양자 컴퓨터로도 효율적인 풀이가 알려지지 않은 문제에 기대는 안전성.

그러다 7월 30일, Wouter Castryck와 Thomas Decru가 몇백 줄짜리 Magma 코드를 첨부한 논문 An efficient key recovery attack on SIDH를 공개했다. 평범한 노트북의 코어 하나로, SIKE 최상위 파라미터 세트의 비밀키를 한 시간 만에 복원했다. 재구현들은 그 시간을 몇 분으로, 다시 몇 초로 줄였다. 그 어디에도 양자 컴퓨터는 없었다. 한 달도 안 되어 이 방식은 사망했다.

나는 이것이 현대 암호학에서 가장 배울 것이 많은 실패 사례 중 하나라고 생각해서, 아예 챌린지로 만들었다. 이 글은 그 배경 설명이다 — 그리고 이번에는 수식을 직접 쓸 생각인데, 이 공격은 정말로 아름다워서 산문만으로는 그 감각이 전해지지 않기 때문이다. 챌린지는 글 맨 아래에 있고, 스포일러는 하지 않겠다.

먼저, 등장인물

모든 것은 체 $\mathbb{F}_{p^2}$ 위에서 벌어진다. 소수는 다음 모양이다:

$p = 2^{e_A}\,3^{e_B} - 1 .$

초특이(supersingular) 타원곡선 $E_0/\mathbb{F}_{p^2}$ 하나를 고정하자. 초특이성은 점들의 군에 대해 아주 깔끔한 사실 하나를 보장한다:

$\#E_0(\mathbb{F}_{p^2}) = (p+1)^2 = \big(2^{e_A}3^{e_B}\big)^2 .$

따라서 $n \mid p+1$인 임의의 $n$에 대해 $n$-torsion은 전부 유리점이고 랭크 2의 자유군이다:

$E_0[n] = \{\,P \in E_0 : [n]P = \mathcal{O}\,\} \;\cong\; (\mathbb{Z}/n\mathbb{Z})^2 .$

특히 $E_0[2^{e_A}]$와 $E_0[3^{e_B}]$는 각각 원소 두 개짜리 기저를 가진다. 이 랭크 2 구조가 게임의 전부다.

아이소제니(isogeny) $\varphi : E \to E'$는 $\varphi(\mathcal{O}) = \mathcal{O}$를 만족하는, 곡선 사이의 상수가 아닌 사상(morphism)이며 자동으로 군 준동형이 된다. 분리 가능한(separable) 아이소제니는 커널로 완전히 결정된다: 임의의 유한 부분군 $G \subset E$에 대해 곡선 $E/G$와 사상

$\varphi : E \to E/G, \qquad \ker \varphi = G, \qquad \deg \varphi = |G|,$

이 존재하고, 목표 곡선의 동형을 무시하면 유일하며 Vélu 공식으로 $G$로부터 계산할 수 있다. "그래프를 걷는다"는 것은 작은 순환 부분군으로 반복해서 몫을 취한다는 뜻이다: 정점은 동형을 무시한 초특이 곡선들($j$-불변량으로 표시), 간선은 차수 $\ell$의 아이소제니이고, 이 그래프는 $(\ell+1)$-정규 라마누잔 확장 그래프(Ramanujan expander)다 — 걸음은 빠르게 섞이고 무작위처럼 보인다.

SIDH, 수식으로

공개 파라미터는 $E_0$, $E_0[2^{e_A}]$의 기저 $\{P_A, Q_A\}$, 그리고 $E_0[3^{e_B}]$의 기저 $\{P_B, Q_B\}$다.

앨리스는 비밀값 $\alpha \in \mathbb{Z}/2^{e_A}\mathbb{Z}$를 골라, $E_0[2^{e_A}]$의 한 순환 부분군을 커널로 갖는 2-아이소제니를 걷는다:

$A = \langle P_A + [\alpha]Q_A \rangle, \qquad \varphi_A : E_0 \to E_A = E_0/A .$

밥은 $\beta \in \mathbb{Z}/3^{e_B}\mathbb{Z}$를 골라 3-아이소제니를 걷는다:

$B = \langle P_B + [\beta]Q_B \rangle, \qquad \varphi_B : E_0 \to E_B = E_0/B .$

이제 만화 버전 설명이 건너뛰는 미묘한 지점이다. 교환을 끝내려면 앨리스는 자신의 커널을 밥의 아이소제니에 통과시켜야 한다 — 즉 $\varphi_B(P_A + [\alpha]Q_A)$가 필요하다. 앨리스는 $\varphi_B$를 볼 수 없고, 곡선 $E_B$만 볼 수 있다. 하지만 아이소제니는 준동형이므로 군 연산과 교환된다:

$\varphi_B\big(P_A + [\alpha]Q_A\big) = \varphi_B(P_A) + [\alpha]\,\varphi_B(Q_A) .$

바로 이 항등식 하나가 SIDH가 **torsion 점의 상(torsion-point image)**을 공개하는 이유다. 밥이 $\varphi_B(P_A)$와 $\varphi_B(Q_A)$를 건네주면, 앨리스는 $\varphi_B$를 전혀 모른 채 자신의 비밀 $\alpha$만으로 우변을 계산할 수 있다. 그래서 공개키는 다음과 같다:

각자는 상대의 곡선 위에서 다시 걷고,

두 몫이 모두 동형을 무시하면 $E_0/\langle A, B\rangle$와 같으므로 두 사람은 같은 곡선에 도착한다. 공유 비밀은 그 곡선의 지문이다:

$j(E_{AB}) = j(E_{BA}) =: \text{shared key}.$

$\varphi_B(P_A + [\alpha]Q_A) = \varphi_B(P_A) + [\alpha]\varphi_B(Q_A)$ — 이 항등식을 꼭 붙잡고 있어라. torsion 상은 SIDH를 돌아가게 만드는 톱니바퀴이자, 전체가 쪼개지는 균열선이다.

왜 어려워 보였는가

밥을 깨는 것은 torsion이 주어진 초특이 아이소제니 문제를 푸는 것이다: $E_0$, $E_B$, 그리고 상 $\varphi_B(P_A), \varphi_B(Q_A)$가 주어졌을 때 $\varphi_B$(동치로 $\beta$)를 복원하라. 비밀은 크기 $3^{e_B} \approx \sqrt{p}$의 공간에 살고, 가장 좋은 일반 공격은 양 끝점에서 동시에 걷는 중간 만남(meet-in-the-middle) / claw-finding으로, 비용은 다음과 같다:

$\approx 3^{e_B/2} \approx p^{1/4}.$

SIKE의 크기($p \approx 2^{434}$)에서 이는 $\approx 2^{108}$ — 닿을 수 없는 수치다. 메모리를 감안하면 양자 알고리즘도 의미 있게 낫지 않았다. 10년 동안 $p^{1/4}$가 곧 보안 수준이었고, 그 내내 훤히 공개되어 있던 torsion 상은 무해하다고 여겨졌다.

공격, 2차원에서

Castryck와 Decru의 수는 $\varphi_B$를 찾는 일을 멈추고, 대신 그에 대한 추측을 검증하는 것이다 — 추측이 맞을 때만 조립되는 고차원 대상을 만들어서.

엔진은 Kani의 보조정리(Ernst Kani, 1997)다. 아벨 곡면(abelian surface) 사이의 2차원 아이소제니가 언제 "분해 가능(reducible)"한지에 대한 명제다. $d = \deg\varphi_B = 3^{e_B}$로 두고 보조 거듭제곱을 고른다:

$N = 2^{e_A} \quad\text{with}\quad N > d .$

Kani는 $\varphi_B$를 차수 $N - d$의 보완 아이소제니와 함께, 아벨 곡면 사이의 단일 $N$-아이소제니

$\Phi : E_0 \times E_B \longrightarrow \mathcal{A},$

로 포장하는데, 그 커널은 본질적으로 $N$-torsion 위 $\varphi_B$의 그래프다:

$\ker \Phi \;=\; \big\lbrace\, \big(\theta(P),\ \varphi_B(P)\big) : P \in E_0[2^{e_A}] \,\big\rbrace,$

여기서 $\theta \in \mathrm{End}(E_0)$는 보완 차수를 실현하는 자기사상으로, $\theta\hat{\theta} = [\,N - d\,] = [\,2^{e_A} - 3^{e_B}\,]$를 만족한다. 이것이 계산 가능한 이유는 두 가지다:

• $\ker\Phi$를 적을 수 있는 것은 오직 $\varphi_B(P_A), \varphi_B(Q_A)$가 공개되어 있기 때문이다. 공격의 입력이 바로 그 도우미 데이터다.
• $\theta$를 만들려면 $N - d$를 $\mathrm{End}(E_0)$의 norm으로 표현해야 한다 — 예컨대 $N - d = u^2 + v^2$이고 $\iota = \sqrt{-1}$이 명시적 자기사상일 때 $\theta = u + v\,\iota$. CD의 공격이 자기사상환(endomorphism ring)이 알려진 시작 곡선(SIKE의 기준 곡선, 또는 $\sqrt{-1}$을 점에 직접 적용할 수 있는 $j = 1728$)을 필요로 하는 이유가 이것이다. 무작위 초특이 곡선에서는 $\theta$를 얻을 수 없다.

$N = 2^{e_A}$가 2의 거듭제곱이므로 $\Phi$는 주 편극(principally polarized) 아벨 곡면들 사이의 $(2,2)$-아이소제니 $e_A$개의 사슬로 분해된다 — 각 단계는 종수 2 곡선 위의 명시적 Richelot 아이소제니다. 그리고 여기가 결정타다. 주 편극 아벨 곡면은 정확히 둘 중 하나다:

$\mathcal{A} \;\cong\; \mathrm{Jac}(\mathcal{C}) \quad(\text{genus-2 curve}) \qquad\text{or}\qquad \mathcal{A} \;\cong\; E \times E' \quad(\text{product of elliptic curves}).$

Kani의 판별 기준에 따르면, 이 사슬이 타원곡선들의 곱으로 쪼개지는(split) 것은 다이아몬드가 닫힐 때 — 즉 집어넣은 $\varphi_B$ 조각이 진짜일 때 — 뿐이다. 그 불리언

$\texttt{Does22ChainSplit}(\cdot) \in \{\text{true},\ \text{false}\},$

이 정답 여부를 알려주는 오라클이다. 이제 이것을 키 복원으로 바꾸자. 밥의 비밀을 3진법으로 쓰고,

$\beta = \sum_{i} d_i\, 3^{i}, \qquad d_i \in \{0,1,2\},$

최상위 몇 자리를 추측한 뒤, torsion 상으로부터 해당하는 $(2,2)$-사슬을 조립하고, 쪼개지는지 묻는다. 맞는 추측은 쪼개지고, 틀린 추측은 쪼개지지 않는다. 이렇게 몇 자리씩 벗겨낸다(Oudompheng의 개선은 첫 분해에서 나머지를 곧바로 복원한다). 각 테스트는 고정 길이의 Richelot 단계 사슬 — $\log p$에 대한 다항 시간 — 이고, 그런 테스트가 $O(e_B)$번이다:

$\text{cost} \;=\; O\!\big(\mathrm{poly}(\log p)\big) \quad\text{vs.}\quad p^{1/4}.$

벽이 사라졌다. 아이러니는 정확하다: 키 교환을 가능하게 만든 데이터가 공격을 가능하게 만든 데이터다. 유일하게 미묘한 지점은 부등식 $N = 2^{e_A} > 3^{e_B}$인데, SIKE의 가장 균형 잡힌 파라미터($2^{216}$ 대 $3^{137} \approx 2^{217}$)는 아슬아슬하게 반대편에 있어서 짧은 보조 아이소제니로 수리된다. 몇 주 안에 Maino–Martindale과 Robert가 전체를 모든 경우에 대해 증명 가능한 다항 시간으로 일반화했다. SIKE는 철회되었다.

"양자 내성"은 애초에 약속의 전부가 아니었다

내가 계속 곱씹게 되는 부분: SIKE의 양자 내성은 진짜였다. 기반 문제에 대한 좋은 양자 알고리즘은 없었고, 지금도 없다. SIKE는 10년 동안 아무도 찾지 못했던 고전 공격에 무너졌다 — 키 크기가 아니라, 방식의 대수적 구조를 타고 올라온 공격에.

• 보안은 탐색 공간의 크기가 아니다. 그 공간에 공격자가 이용할 수 있는 구조가 있는지다. SIDH에는 그런 구조가 많았다.
• 프로토콜을 돌아가게 하려고 공개하는 도우미 데이터는, 위협 모델에 넣었든 안 넣었든 전부 공격 표면이다. SIDH의 torsion 상은 둘 다였다.
• "공격 $X$에 내성이 있다"는 슬그머니 "안전하다"로 읽힌다. 두 문장은 같은 문장이 아니다.

이 중 어느 것도 미리 자명하지 않았다. torsion 상은 10년간 공개되어 있었고 전문가들이 연구했다. 공격에는 평균적인 암호학자의 도구 상자에 없던 도구 — Kani의 보조정리, 종수 2 아이소제니 — 가 필요했다. 버그가 아니었다. 아직 아무도 건너지 않았던, 두 분야 사이의 다리였다.

챌린지: SIKE!

정확히 이 내용으로 챌린지를 만들었고, Dreamhack에 올라와 있다: SIKE!.

키 교환의 완전한 실행 한 번이 주어진다 — 양쪽 공개키, torsion 상 $\varphi(\cdot)$, 그리고 $j(E_{AB})$로 봉인된 플래그. 파라미터는 실제 SIKE 크기다: 무차별 대입 본능($\beta$ 추측, $p^{1/4}$ 중간 만남)이 절망적일 만큼 크고, 제대로 된 공격이라면 몇 초 만에 끝날 만큼 작다. (예전 버전은 중간 만남이 통할 만큼 작았는데 — 그건 핵심을 통째로 놓친 것이었다. 정작 유일하게 중요한 부분인 torsion 상은 건드리지도 않았으니까. 그래서 남은 문이 구조 하나뿐일 때까지 키웠다.)

어떤 공격인지는 말하지 않겠다. 여기까지 읽었다면 이미 그 이름을 알고 있고, 그 공격이 세워진 오라클의 모양도 봤다. 진짜 작업은 이 글이 건너뛴 부분이다: "이런 공격이 존재한다는 걸 안다"에서 "이 숫자들 위에서 돌아가게 만들었다"로 가는 것. 그 간극이 응용 암호해독의 대부분이고, 건너는 보람이 확실한 간극이다.

가서 깨 보자. 오후 반나절도 안 걸릴 것이다.