Claude가 밝혀낸 ECDSA 곡선 시드의 기원

AI 요약

NIST는 2000년 ECDSA 표준에 여러 타원곡선을 수록했지만, 곡선 계수를 정하는 데 쓰인 시드가 어떻게 만들어졌는지는 공개하지 않았습니다. NSA가 시드를 제공하고 설명을 덧붙이지 않아, 의도적으로 약한 곡선을 골랐을 가능성이 오랫동안 논쟁거리였습니다. Jerry Solinas는 2015년 유머러스한 문구를 해시해 시드를 만들었다는 이야기를 전했지만, Anthropic 연구팀이 Claude로 시드를 분석한 결과 그 설명은 맞지 않았습니다.

시드에서 찾은 난수 생성기

Claude는 1990년대 C 라이브러리의 의사난수 생성기(PRNG)가 시드 생성에 쓰였을 가능성을 살폈습니다. 공개된 시드에서 비트 구간을 조금씩 옮겨 가며 여러 생성기의 출력을 비교했고, 일부 시드에서 32비트 단어의 최상위 비트가 모두 0인 패턴을 발견했습니다. 네 개 시드에서 이런 패턴이 나타날 확률은 우연히 발생하기 어렵다고 보고, 48비트 상태를 쓰는 lrand48을 후보로 좁혔습니다. lrand48은 출력에서 최상위 31비트만 돌려줍니다.

곡선 시드 일부는 lrand48 출력의 상위 비트만 포함해 내부 상태를 바로 복원하기 어려웠습니다. Claude는 잘린 선형 합동 생성기 상태를 복구하는 문제를 격자 문제로 바꾸고, LLL(Lenstra-Lenstra-Lovasz) 알고리즘을 적용했습니다. 가능한 비트 구간을 모두 검사한 뒤 NIST의 소수체 곡선 5개와 ANSI X9.62 예제 곡선 5개의 시드가 모두 lrand48() >> 23 출력과 일치하는 것을 확인했습니다. 복원한 48비트 상태로 시드의 160비트를 재생성했습니다.

타임스탬프와 아직 남은 질문

생성기의 상태를 거꾸로 되돌려 srand48 초기 상태를 찾자, 소수체 곡선 10개의 초기값은 1997년 5월부터 1998년 4월 사이의 Unix 타임스탬프와 연결됐습니다. 이진체 곡선 4개는 1984년 시각으로 나타났으며, 타임스탬프를 두 배로 보면 1998년 4월 17일로 이어집니다. 연구팀은 당시 프로그램이 시계를 절반으로 처리했을 가능성을 제시하지만, 그 이유는 확인하지 못했습니다.

시드가 생성된 방식이 밝혀졌다고 해서 곡선에 대한 모든 의문이 해소된 것은 아닙니다. 이진체 곡선 B-163 시드는 분석한 생성 방식에 맞지 않았고, P-224, P-256, P-384, P-521의 기준점 생성법도 설명하지 못했습니다. 연구팀은 생성 과정에서 표준에 실리지 않은 유효한 곡선 후보가 일부 건너뛰어진 사실도 확인했습니다. 왜 후보를 제외했는지는 자료로 알 수 없습니다. 연구팀은 발견 결과가 공격이나 ECDSA 취약점은 아니며, 시드를 단순한 방식으로 재현할 수 있어 의도적인 백도어 가능성을 낮춘다고 설명합니다. 시드 발견 포상금 36,864달러는 Internet Security Research Group에 기부할 예정입니다.

Hacker News 반응

• @tptacek — NIST 암호화 음모론을 믿어 온 한 세대에게는 참담한 소식이군요.
  • @nickysielicki — NIST가 독립 암호학계의 신뢰와 호의를 이렇게 많이 잃을 이유가 있었는지 의문입니다. 시드에 숨겨 둔 것이 없다는 점을 실증적으로 설명하면 됐습니다.
  • @sweis — 실제 작업을 맡았던 Jerry Solinas도 기억하지 못했고, 여러 사람이 같은 잘못된 이야기를 전했습니다. 만약 알고 있었다면 15년 전에 타임스탬프를 공개해 의혹을 끝낼 수도 있었을 겁니다.
• @EGreg — 이제 Bitcoin과 Ethereum 생태계가 NSA 백도어 걱정 없이 P-256 ECDSA 서명 검증용 opcode와 사전 컴파일 계약을 배포할 수 있겠군요. 양자 컴퓨터 문제는 별개입니다.
  • @tptacek — 타원곡선 암호 연구를 아는 사람 중 이 시드로 백도어를 만들었다고 믿은 사람은 없었습니다. 다만 이제 그 논쟁을 직접 끝낼 수 있게 된 점은 좋습니다.
  • @FiloSottile — 1997년의 모든 타임스탬프를 시도하고 각 시각에서 처음 16개 후보 중 하나를 골랐다고 가정해도 선택 자유도는 약 30비트입니다. 그 정도 시도로 무작위로 찾을 수 있는 256비트 곡선 약점이 있다면 타원곡선 암호 전체를 흔드는 암호 분석 결과가 됩니다.
• @adastra22 — 약한 곡선이 무작위로 천 개나 백만 개 중 하나꼴로 있다면, 타임스탬프나 반복 횟수를 바꿔 그런 곡선을 찾은 뒤 나중에 그럴듯한 설명을 내놓을 수 있습니다. 이 방식은 오히려 약한 곡선의 모습과 같습니다.
  • @matthewdgreen — 그런 검색으로 찾을 수 있을 만큼 약한 타원곡선이 많다면 ECC 자체가 잘못된 선택이었다는 뜻입니다.
• @fidotron — 생성 방식을 알아냈다고 곡선의 선택 기준까지 밝혀진 것은 아닙니다. 생성 후 버린 후보는 확인할 수 없고, 공개된 타임스탬프가 무해한 생성의 증거로 쓰이리라는 가정도 논리적으로 따라오지 않습니다.
  • @FiloSottile — 타임스탬프를 모두 시도했다고 해도 선택 자유도는 제한적입니다. 그 범위에서 맞출 수 있는 약한 곡선 집합이 있다면 그 자체가 큰 암호 분석 성과입니다.
• @slowin — Anthropic과 선택받은 사람은 Claude로 이런 작업을 할 수 있지만, 일반 사용자는 차단될 수 있습니다. 이런 격차가 모델 제공자와 대중 사이에 커질 수 있습니다. 공개 모델의 발전이 그 격차를 잇는 유일한 방법입니다.
  • @Retr0id — 저도 Claude로 이 문제를 풀어 봤지만 차단되지는 않았습니다. 다만 해결에는 실패했습니다.
  • @comex — 이 과제가 차단됐을지는 의문이지만, 일반적인 격차 문제에는 동의합니다.
• @teddyh — 아직 설명되지 않은 B-163 시드는 단순한 오타 때문에 분석이 실패했을 가능성이 있습니다.
  • @lukeify — Zodiac 암호 중 하나가 오랫동안 풀리지 않은 이유도 전사 실수였던 것으로 압니다.

원문: Anthropic / 번역·요약: Trawling