SIDH와 SIKE: 설계 및 암호 분석

초특이 등원 디피-헬먼(SIDH)은 2011년에 Jao와 De Feo가 제안한 공개 키 교환 프로토콜로, 디피-헬먼과 유사하지만 초특이 타원곡선 위의 등원사상을 사용합니다. 양측은 Fp2 위의 동일한 초특이 곡선 E에서 시작합니다. 앨리스는 비밀 등원사상 phi_A: E -> E_A(2^a-비틀림 부분군에서 무작위로 선택한 핵)를 계산하고, E_A와 phi_A에 따른 밥의 비틀림 생성원들의 상을 공개합니다. 밥은 phi_B: E -> E_B(3^b-비틀림 부분군에서 무작위로 선택한 핵)를 계산하고, E_B와 phi_B에 따른 앨리스의 비틀림 생성원들의 상을 공개합니다. 앨리스는 밥이 공개한 데이터를 사용하여 phi_A': E_B -> E_AB를 계산하고, 밥은 phi_B': E_A -> E_AB를 계산합니다. 양측은 모두 j(E_AB)를 공유 비밀로 얻습니다.

SIDH의 특수한 소수 형식 p = 2^a * 3^b * f - 1(f는 소수성을 위한 작은 보조 인자)은 Fp2 위의 곡선 E가 필요한 비틀림 구조를 갖도록 합니다. SIKEp434(NIST 보안 수준 1, 128비트 양자 내성 보안)의 경우 p = 2^216 * 3^137 - 1, a = 216, b = 137입니다. 즉, 앨리스는 2-등원사상을 216번 연속 적용하고, 밥은 3-등원상을 137번 연속 적용합니다. 키 크기는 다음과 같습니다. 앨리스의 공개 키는 E_A와 두 개의 Fp2 점(phi_A(P_B), phi_A(Q_B))으로 구성되며, 그 크기는 3 * 2 * 54 = 324바이트입니다. SIKEp751은 고전적 보안 192비트 및 양자 보안 128비트를 목표로 하며 564바이트의 공개 키를 사용합니다. 이 공개 키들은 NIST PQC 후보 중 가장 작지만, 그 대가로 계산 속도가 100~1000배 느립니다.

SIKE(초특이 등원 키 캡슐화)는 후지사키-오카모토 변환을 사용하여 SIDH로부터 구축된 IND-선택 암호문 공격 2 보안 KEM입니다. SIKE.Encaps에서는 무작위 메시지 m을 선택하고, (c0 = m을 시드로 사용한 SIDH 공개 키, c1 = H2(m) XOR pk)를 계산한 다음 (c0, c1)을 보냅니다. SIKE.Decaps에서는 비밀 키를 사용하여 c0에서 m을 복구하고, c1을 검증하며, 일관성을 확인하기 위해 (c0, c1)을 다시 계산한 뒤 K = H3(m, c0)을 출력합니다. FO 변환은 SIDH의 CPA 보안 교환을 선택 암호문 공격 2 보안 KEM으로 변환합니다. SIKE는 NIST PQC의 네 차례 경쟁(2017~2022년)에 모두 참가하여 광범위한 암호 분석을 견뎠지만, 2022년 7월에 치명적인 고전적 공격이 등장하면서 무너졌습니다.

2011년부터 2022년까지 SIDH는 상당한 암호 분석을 견뎠습니다. 당시 SIDH에 대한 가장 우수한 공격은 다음과 같았습니다. (1) 일반적인 SSIP 알고리즘: 고전적으로 O(p^{1/4}), Tani 알고리즘을 사용하는 양자 환경에서 O(p^{1/6})입니다. (2) 등원 경로에 대한 중간에서 만나는 공격: 고전적으로 O(p^{1/4})로 SSIP와 동일합니다. (3) 특정 구조적 공격을 위한 다항 시간 알고리즘(van Oorschot-Wiener): SIDH에는 적용되지 않습니다. 수십 편의 논문이 SIDH 보안을 분석했지만, 11년 동안 다항 시간 고전 공격이나 양자 공격은 발견되지 않았습니다. 이러한 연구 기록으로 SIKE는 신뢰할 수 있는 NIST 최종 후보가 되었습니다. 결국 SIDH를 무너뜨린 것은 SSIP에 대한 직접적인 공격이 아니라, SIDH가 제공하는 보조 비틀림점 정보를 악용한 공격이었습니다.

2022년 7월 30일, Wouter Castryck과 Thomas Decru는 SIDH에 대한 다항 시간 고전 공격을 보여 주는 프리프린트를 게시했습니다. 이 공격은 SIDH의 보조 비틀림점 phi_A(P_B), phi_A(Q_B)에 포함된 추가 정보를 사용합니다. 이 정보는 본질적으로 phi_A가 3^b-비틀림 부분군에 작용하는 방식을 드러냅니다. 이를 상 곡선 E_A와 결합하면, 복소 곱셈을 갖는 타원곡선 이론과 리셸로 등원사상의 기법을 사용하여 phi_A의 핵을 복원할 수 있으며, 따라서 phi_A 자체도 복원할 수 있습니다. 이 공격은 128비트 양자 내성 보안을 제공하도록 설계된 매개변수 집합인 SIKEp434를 노트북에서 62분 만에 실행했습니다. 며칠 안에 독립적인 연구자들이 이 공격을 확인하고 모든 SIDH 매개변수로 확장했습니다.

SIDH의 설계에서는 양측이 자신의 비밀 등원사상에 따른 상대방의 비틀림 기저점들의 상을 공개해야 했습니다. 이는 프로토콜이 작동하는 데 필요했습니다. phi_A(P_B)와 phi_A(Q_B)가 없으면 밥은 자신의 등원사상을 앨리스의 곡선으로 옮겨 공유 비밀을 계산할 수 없기 때문입니다. 그러나 phi_A가 3^b-비틀림 부분군에 제한되어 작용하는 방식을 드러내는 이 추가 정보는 예상보다 훨씬 많은 정보를 누출하는 것으로 밝혀졌습니다. 캐스트릭-드크루 공격은 종수 2 곡선과 리셸로 등원사상을 사용하여 문제를 더 높은 종수의 대상으로 끌어올리며, 이곳에서는 제한된 작용만으로도 phi_A가 완전히 결정됩니다. 이러한 누출은 SIDH에 구조적으로 내재되어 있으므로 프로토콜의 근본적인 설계를 바꾸지 않고는 해결할 수 없습니다.

2022년 7월 5일, 캐스트릭-드크루 공격이 발표되기 전에 NIST는 최초의 PQC 표준화 대상으로 ML-KEM(Kyber), ML-DSA(Dilithium), SLH-DSA(SPHINCS+), FN-DSA(Falcon)를 발표했습니다. SIKE는 2차 검토 단계에 있었기 때문에 이 목록에 포함되지 않았습니다. 2022년 7월에 등장한 캐스트릭-드크루 공격으로 인해 NIST는 SIKE를 검토 대상에서 완전히 제외했습니다. NIST는 다음과 같이 밝혔습니다. "SIKE는 더 이상 표준화 대상으로 고려되지 않습니다." 이는 NIST PQC 경쟁에서 가장 극적인 암호 분석 발전이었으며, 11년간의 분석을 견딘 체계도 근본적으로 새로운 수학적 통찰을 통해 무너질 수 있음을 보여 주었습니다.

캐스트릭-드크루 공격이 발표된 지 일주일 안에 Thomas Decru와 Luciano Maino가 독립적으로, 이어서 Damien Robert가 추가 개선 결과를 발표했습니다. Robert의 변형 공격은 같은 통찰을 사용하지만 등원사상의 핵을 직접 계산하는 대신 E_A의 자기준동형환을 계산하며, 수학적으로 설명하기도 더 간단하다고 볼 수 있습니다. 이러한 신속한 독립적 재발견은 캐스트릭-드크루 공격이 난해한 요령이 아니라 근본적인 구조적 약점을 찾아냈음을 확인해 주었습니다. 이후 논문들이 빠르게 발표된 것은 많은 연구자가 SIDH의 비틀림점 누출을 잠재적인 공격 경로로 연구하고 있었음을 보여 주기도 합니다. 연구자들은 이것이 이례적인 정보 공개라는 사실을 알고 있었지만, 캐스트릭과 드크루가 종수 2로 이어지는 연결 고리를 찾기 전까지는 이를 악용하지 못했습니다.

FESTA(초특이 비틀림 공격을 이용한 고속 암호화, 2023년)는 SIDH에서 영감을 얻었지만 비틀림점 보조 데이터를 사용하지 않는 KEM 설계입니다. FESTA는 다른 프로토콜 구조를 사용합니다. 공개 키에는 상대방의 비틀림 기저점들의 상이 포함되지 않고, 비밀 등원사상은 상 곡선만을 통해 커밋됩니다(보조점 없음). FESTA는 구조적 정보를 더 적게 드러내는 방식으로 등원사상을 사용하여 암호화합니다. 초기 보안 분석에 따르면 FESTA는 캐스트릭-드크루 공격의 구조를 피하는 것으로 보입니다. 그러나 FESTA는 더 새로운 체계이고 SIKE가 11년 동안 축적한 연구 기록만큼 면밀한 검토를 받지 않았습니다. 따라서 등원사상 연구 공동체는 광범위한 분석이 이루어지기 전에 새로운 체계를 배포하는 데 신중한 태도를 보이고 있습니다.

SIKE의 붕괴는 중요한 교훈을 제공합니다. (1) 보조 정보 공개는 위험합니다. SIDH의 추가 비틀림점 데이터는 프로토콜에 필요했지만 치명적인 정보 누출을 일으켰습니다. 프로토콜 설계자는 주요 값만이 아니라 공개되는 모든 데이터를 분석해야 합니다. (2) 연구 기록은 보안 증명이 아닙니다. 알려진 공격 없이 11년을 견뎠다는 사실은 안심할 수 있는 근거이지만 보장은 아닙니다. 잘 정의된 난제로의 환원에 기반한 암호학적 증명이 권위에 의존한 주장이나 검증을 견뎠다는 사실보다 더 신뢰할 만합니다. (3) 새로운 수학적 도구는 위험을 만듭니다. 캐스트릭-드크루 공격은 이전에는 등원사상 암호 분석에 적용되지 않았던 수학 도구인 종수 2 리셸로 등원사상을 사용했습니다. 새로운 암호 원시기법을 조사하는 암호 분석가는 새로운 수학 영역도 고려해야 합니다.

SIKE가 무너졌지만 등원사상 기반 암호학은 계속 연구 분야로 남아 있습니다. SQISign 서명은 1단계에서 177바이트로 알려진 PQC 서명 중 가장 작으며, SIDH 공격의 영향을 받지 않는 다른 난이도 가정인 자기준동형환 문제를 사용합니다. CSIDH 기반 프로토콜은 비틀림점 누출 없이 클래스군 작용 구조(가환 등원사상)를 사용하지만, CSIDH 자체에도 과제가 있습니다. SIDH보다 느리고 양자 보안 분석도 진행 중입니다. 등원사상 연구 공동체는 SIKE의 붕괴를 등원사상 프로토콜에서 어떤 정보를 숨겨야 하는지에 대한 이해를 높인 학습 경험으로 보고 있습니다. 이는 미래의 체계를 설계하는 데 유용한 지식입니다.

SIDH의 어떤 설계 측면이 캐스트릭-드크루 공격을 가능하게 했습니까?

SIDH는 두 당사자 사이에서 2^a 및 3^b 등원사슬을 번갈아 사용하고, 키 교환을 가능하게 하기 위해 보조 비틀림점의 상을 공유합니다. SIKE는 후지사키-오카모토 변환으로 SIDH를 감싸 선택 암호문 공격 2 보안을 제공합니다. SIKE는 모든 NIST PQC 후보 중 가장 작은 키(374바이트)를 사용했지만 100~1000배 느렸습니다. 11년간 보안을 유지한 뒤, 캐스트릭-드크루는 2022년 7월 종수 2 리셸로 등원사상을 사용하여 비틀림점 누출을 악용함으로써 SIKE를 무너뜨렸습니다. NIST는 SIKE를 제외했습니다. FESTA는 비틀림점 공개를 피합니다. SQISign은 자기준동형환의 난이도를 계속 사용합니다. SIKE의 붕괴는 보조 공개 데이터를 주요 프로토콜 값만큼 신중하게 분석해야 한다는 점을 보여 줍니다.