두 수학자가 일반 PC 한 대로 한 시간 만에 SIKE 양자내성암호를 깨다

2022년 8월, NIST가 결국 RSA와 Diffie-Hellman을 대체할 네 가지 양자내성암호 알고리즘을 선정한 지 몇 주 후, KU Leuven의 컴퓨터 보안 및 산업 암호학 그룹 연구진은 'An Efficient Key Recovery Attack on SIDH'를 발표했다. 이는 복잡한 수학과 일반 PC 한 대를 사용해 약 한 시간 만에 SIKE로 보호되는 거래의 키를 복구하는 기법이다. 논문의 저자인 Wouter Castryck과 Thomas Decru는 Microsoft의 5만 달러 포상금을 받을 자격을 얻게 되었다.

SIKE(Supersingular Isogeny Key Encapsulation)는 NIST가 잠재적 백업으로 진출시킨 네 가지 추가 알고리즘 중 하나였으며, 초특이 아이소제니 그래프에 비밀을 인코딩하여 양자 컴퓨터에 저항한다고 여겨졌다. 이는 오랫동안 우아하게 어렵다고 간주되어 온 구성이다. 새로운 공격은 SIKE의 초석 프로토콜인 SIDH(Supersingular Isogeny Diffie-Hellman)가 1997년 수학자 Ernst Kani가 증명한 glue-and-split 정리와 2000년 Howe, Leprévost, Poonen의 도구, 그리고 알려진 GPST 적응형 공격을 기반으로 취약하다는 것을 보여준다.

그 중요성은 즉각적이었다. SIKE는 표준화 경쟁에서 사실상 탈락할 가능성이 있었고, NIST가 표준으로 선정한 네 가지 알고리즘은 완전히 다른 수학에 기반하고 있어 영향을 받지 않았다. 워털루 대학 교수이자 SIKE의 공동 발명자인 David Jao는 이 약점을 '분명히 큰 타격'이라고 불렀고, 이 공격을 '정말 예상치 못한' 것이라고 말했다.

SIDH는 항상 알려진 아이소제니 차수를 가진 보조점을 함께 전송했다. 1997년의 정리(glue-and-split)는 그 설계상의 편의를 키 복구 기계로 바꾸어 놓는다.

이 공격은 1997년 이래 눈앞에 숨어 있던 4반세기 전의 수학을 재활용했다.

양자 컴퓨터는 필요하지 않았다. SIKE가 대비하도록 설계된 위협인 양자 컴퓨터 없이, 단 하나의 코어와 한 시간만 있으면 되었다.

결함은 구조적이었다. 보조점과 알려진 아이소제니 차수가 프로토콜 설계에 내장되어 있었다.

이 결과는 발표 후 며칠 만에 정부 표준화 경쟁의 순위를 다시 매겼다.

프로토콜에 설계된 편의는 잠재적 취약점이다. 한 기법이 사용성을 위해 노출하는 보조 데이터는 공격자에게 정확히 필요한 단서가 될 수 있다.

NIST 대안 후보였던 SIKE는 사실상 고려 대상에서 제외되었다. 이미 선정된 네 가지 양자내성 표준은 다른 수학에 의존했기 때문에 영향을 받지 않았다. 연구진은 Microsoft의 5만 달러 포상금을 받을 수 있게 되었고, SIKE 공동 발명자 David Jao는 공개적으로 이 공격의 심각성을 확인했다.