양자 컴퓨팅은 인터넷 보안에 점점 더 현실적인 위협이 되고 있다. 일부에서는 대규모 양자 컴퓨터가 이르면 2030년 등장할 수 있다고 예상하며, 이 경우 전 세계 은행 시스템과 메시징, 사이버 보안을 뒷받침하는 암호 기술이 위험에 처하게 된다. 디지털 서명은 수학적 알고리즘을 사용해 결제, 메시지 또는 소프트웨어 업데이트의 출처를 확인한다.

이러한 보장이 없다면 글로벌 연결성과 금융을 구동하는 시스템은 작동을 멈추게 된다. 이 위협이 대중의 의식 속에 본격적으로 자리 잡은 것은 최근이지만, 기술 업계는 훨씬 전부터 이에 대비해 왔다.

미국 국립표준기술연구소(NIST)는 현재 암호 표준을 대체할 포스트퀀텀 기술을 개발하기 위해 거의 10년 동안 공개 경쟁을 진행해 왔다. 이 가운데 하나가 현재 진행 중이다. 올해 5월에는 9개의 디지털 서명 알고리즘이 3차 검토에 진출했으며, 8월 14일 최종 설계 변경안을 제출했다.

Claude Mythos가 주요 포스트퀀텀 후보 HAWK를 해독하다

이 작업의 중요성은 7월 28일 Anthropic이 논문 2편을 발표하면서 더욱 부각됐다. Anthropic은 보안 연구자들이 Project Glasswing을 통해 이용할 수 있는 비공개 모델 Claude Mythos Preview가 공모전에 제출된 암호 알고리즘 가운데 하나에서 새로운 공격 경로를 발견했다고 주장했다.

이 회사는 이를 자사 대표 모델의 사이버 보안 역량이 한 단계 향상된 사례로 설명했다. 지금까지 이 모델은 프로그래머가 알고리즘을 코드에 구현할 때 발생한 오류만 식별할 수 있었다. 이는 Anthropic의 최근 발표와는 다른 내용이다. Anthropic은 Claude가 "알고리즘 자체의 수학적 결함을 찾아낼 수 있다"고 주장했다.

영향을 받은 모델 가운데 하나는 HAWK였다. 이 실험적 서명 방식은 남은 NIST 후보 중 격자를 기반으로 구축된 유일한 방식이다. 격자는 수백 차원에 걸친 점들의 격자를 다루는 기하학의 한 분야다. 이 때문에 HAWK는 메모리 효율성이 가장 높은 사례 중 하나이며, 가장 낮은 보안 설정에서는 서명 크기가 555 bytes에 불과하다.

그러나 지난해 발표된 학술 연구에 따르면 이러한 방식은 격자에 숨겨진 대칭성에 기반한 취약점에 노출되기 쉽다. 이 대칭성은 키 복구 문제를 대략 절반으로 줄일 수 있다. 이는 순전히 가설에 불과한 우려였지만, Claude Mythos Preview가 HAWK-256에서 실제로 이러한 대칭성을 찾아냈다.

이 HAWK 암호 표준 구성은 개발자들이 공개적인 스트레스 테스트를 목적으로 공개한 것이다. Anthropic은 자사 모델이 이 취약점을 식별하게 함으로써 비밀 키를 탈취하는 데 필요한 연산 횟수를 18 quintillion에서 275 billion으로 줄였다.

처음 HAWK-256 비밀 키를 해독하는 데 드는 비용은 상당했다. Anthropic의 실험에는 약 $100,000의 컴퓨팅 비용이 들었고 약 60 hours가 소요됐다. 그러나 이 방법의 실현 가능성이 확인된 현재는 96-core 서버에서 후속 복구 작업을 4시간 이내에 수행할 수 있다.

HAWK는 폐기됐지만 AES는 영향을 받지 않았다

HAWK-256은 NIST에 제출된 구성보다 의도적으로 약화된 구성이라는 점을 거듭 강조할 필요가 있다. HAWK-512와 HAWK-1024 역시 추정 공격 비용이 낮아지지만, 남은 보안 여유는 여전히 현재 어떤 공격자의 역량을 크게 웃돈다. 그럼에도 원래의 보안 여유를 회복하려면 키 크기를 두 배로 늘려야 하며, 이에 따라 HAWK의 소형화라는 장점을 포기해야 한다.

그 결과 HAWK 개발자들은 이후 HAWK를 심사 대상에서 철회했다. Google의 포스트퀀텀 컴퓨팅 연구원 Sophie Schmieg는 이후 “기본적으로 이 논문으로 HAWK는 끝났다”고 선언했다.

Anthropic은 HAWK 발표와 동시에 두 번째 암호 표준인 AES에서도 취약점을 발견했다고 밝혔다. AES는 현재 대부분의 암호화된 트래픽을 보호하는 실제 사용 중인 암호다. Anthropic은 기존 최선의 공격보다 200 to 800배 빠른 공격을 구현했다고 주장했지만, 여기에는 여러 가지 완화 요소가 있다.

첫째, 이 공격은 완전한 10라운드 암호가 아니라 축소된 7라운드 연구용 버전을 대상으로 했다. 또한 공격자가 동일한 키로 암호화된, 특별히 선택된 메시지를 약 400 octillion개 확보할 수 있다고 가정했다. 이러한 명백한 실행 불가능성 때문에 Anthropic은 전체 공격을 수행하지 않고, 일부만 계산을 통해 검증한 뒤 최종 결과를 추정했다.

그 결과 두 번째 발견은 첫 번째 발견보다 실질적으로 중요도가 낮다. 첫 번째 발견은 유망했던 포스트퀀텀 서명 후보를 퇴출시켰다.