원문 캡처 · words.filippo.io
원문 캡처 · words.filippo.io

앤스로픽 팀이 NIST 타원곡선의 시드 생성 방식을 밝혀 3년 전 발표된 현상금 전액을 받았다. 시드는 영문 문장을 해시한 값이 아니라 1997~98년의 시각을 입력해 drand48로 만든 난수열이었다.

존 우드(John Wood), 헨리 드 발랑스(Henry de Valence), 에이바 하월(Ava Howell), 잭 보스(Zack Voase), 루시 스위트(Lucy Sweet), 아미르 오미디(Amir Omidi), 폴 크롤리(Paul Crowley), 이언 맥기니스(Iain McGinniss), 니컬러스 칼리니(Nicholas Carlini), 스티브 와이스(Steve Weis)가 수수께끼를 풀었다. 이들은 2026년 10월 15일 01:07:51 UTC에 3년 전 발표된 현상금 전액을 받았고, 상금을 Let’s Encrypt를 운영하는 비영리단체 ISRG에 기부했다. 기부금은 현상금의 세 배인 36,864달러(36 Ki$)가 됐다. 현상금에는 아미르 오미디, 크리스 파머(Chris Palmer), 콜름 맥카르타이(Colm MacCárthaigh), 데이비드 에이드리언(David Adrian), 데이비드 앤더슨(David Anderson), 제프 호지스(Jeff Hodges), 맷 그린(Matt Green), 매슈 맥퍼린(Matthew McPherrin), 폴 키러(Paul Kehrer), 라이언 슬리비(Ryan Sleevi), 소아톡(Soatok)도 기여했다.

NIST 타원곡선 P-192, P-224, P-256, P-384, P-521은 NIST가 2000년 FIPS 186-2에서 발표했다. ANSI X9.62에 따라 임의의 시드를 정하고 이를 SHA-1로 해시한 뒤, 그 결과로 일부 매개변수를 도출하는 방식으로 생성됐다. 이번 주까지는 그 임의의 시드를 어떻게 골랐는지 알려지지 않았다.

기존에는 2023년 초 세상을 떠난 제리 솔리나스 박사가 1997년에 영문 문장을 해시해 시드를 만들었지만, 나중에 어떤 문장이었는지 잊었다는 이야기가 전해졌다. 더 자세한 배경은 스티브 와이스의 글과 현상금 발표문에서 볼 수 있다. 실제로는 POSIX 표준 난수 생성기인 drand48을 사용했다.

알고리즘은 당시 UNIX 타임스탬프를 srand48()에 넣고 drand48로 바이트를 하나씩 생성하는 방식이다. 20바이트씩 묶은 값을 ANSI X9.62에 따른 시드 후보로 시험하고, 결과 곡선이 유효하지 않으면 버린다. 첫 곡선을 찾은 뒤에도 후보를 계속 시험해 같은 타임스탬프에서 여러 곡선을 만들기도 했다. 이 주장을 확인하기 위해 Go로 알고리즘을 재구현했다. 자세한 내용은 앤스로픽의 설명에 나와 있다.

ANSI X9.62의 조건 외에도 문서화되지 않은 기준이 두 가지 더 있었다. 하나는 비교적 분명하지만, 다른 하나는 아직 밝혀지지 않았다. 생성된 곡선의 위수 n의 비트 길이가 바탕체 p의 비트 길이보다 크면 시드를 거부했다. 조건은 더 엄격한 n < p가 아니다. prime239v2의 경우 p < n < 2²³⁹이기 때문이다.

이 기준만으로는 발표된 것보다 유효한 시드가 대략 두 배 더 남는다. 이 차이를 설명할 여러 가능성을 살펴봤지만, 잘 들어맞는 설명은 찾지 못했다. 시드를 검증할 때 같은 난수 생성기를 사용해 출력을 소비하고 일부 후보를 건너뛰었을 수도 있다. 다만 건너뛴 후보 사이의 간격은 규칙적이지 않다. 1997년에는 오늘날 몇 분 만에 범용 소프트웨어로 할 수 있는 계산도 당시 최첨단이었으므로, 알고리즘 중 하나의 버그가 절반의 결과를 잘못 반환했을 가능성도 있다.

NIST 곡선을 이용한 타원곡선 암호의 보안에 대해서는 이번 발견 전에도 실무자 사이에 심각한 우려가 없었다. 닐 코블리츠와 알프레드 메네제스는 2015년 논문 「A riddle wrapped in an enigma」 3.1절에서, NSA가 15년 넘는 암호 분석을 피해 갈 약점을 노리고 시드를 골랐다는 가설은 개연성이 낮다고 논증했다. 이후 버전의 논문에 따르면 대니얼 번스타인과 탄자 랑게는 2017년 코블리츠와 메네제스에게 시드 선택의 70비트 자유도를 이용해 가상의 2⁶¹개 약한 소수 위수 곡선을 겨냥할 수 있는 기법을 설명했다. 경쟁 타원곡선 설계인 Curve25519의 저자인 번스타인의 설명은 음모론을 지속시키는 데 영향을 줬다.

이번 발견은 번스타인과 랑게가 설명한 기법으로는 NIST 곡선을 겨냥할 수 없음을 보여준다. NSA가 1997~98년의 모든 타임스탬프와, 설명되지 않은 거부까지 넉넉히 고려해 소수 위수 후보 중 앞선 16개를 고를 수 있었다고 가정해도 선택의 자유도는 약 30비트에 불과하다. 이는 가상의 소수 약곡선 중 일부를 의도적으로 겨냥하거나 NOBUS 백도어를 심기에 충분하지 않다.

글쓴이는 결정론적 ECDSA 서명 알고리즘과 무작위성을 더한 서명 방식, 형식 검증된 유한체 구현, 2015년 르네스·코스텔로·바티나의 완전한 덧셈 공식을 함께 고려하면 NIST 타원곡선 암호의 ‘재평가 과정’이 잘 마무리됐다고 본다. 글쓴이는 이제 NIST 곡선을 Curve25519·Ed25519·X25519보다 개인적으로 더 권한다고 덧붙였다. 다만 양자내성 서명이 이를 대체할 시점에 맞춰 나온 발견이라고도 했다.

앤스로픽 팀은 이진체 위의 NIST B-곡선 시드 생성 방식도 알아냈지만, 해당 곡선을 사용하는 곳은 없다고 전했다.