ECDSA 곡선의 25년 미스터리, 타임스탬프로 풀다

핵심 요약

• NIST가 2000년 채택한 ECDSA 타원곡선 암호화 표준의 seed 값 출처가 수십 년간 미스터리였다. NSA가 설명 없이 제시한 이 값들은 보안 커뮤니티에서 의도된 백도어 가능성에 대한 의심을 받아왔다.
• Anthropic의 Claude가 2026년 10월 30분 내에 NIST P-192, P-224, P-256, P-384, P-521의 seed 출처를 규명했다. 해시 알고리즘이 아니라 C 라이브러리의 lrand48 난수생성기를 Unix 타임스탬프로 초기화해 생성한 것이었다.
• prime 곡선의 seed들은 1997년 5월~1998년 4월 사이의 타임스탐프에서 생성됐으며, 각각 특정 iteration 횟수 후 선택됐다. 예를 들어 P-256은 같은 실행에서 1842번째 후보였다.
• Claude는 lrand48의 출력 패턴 인식으로 사용된 생성기를 특정하고, 선형 합동 생성기 상태 복원을 위해 격자 기반 LLL 알고리즘을 적용했다. 10개 prime 곡선 seed와 5개 ANSI X9.62 곡선이 모두 lrand48() >> 23 패턴을 보였다.
• 백포인트 6개(P-192, ANSI X9.62 예제 곡선 5개)의 경우 1997년 5월에 FreeLIP 라이브러리의 난수생성기로 생성됐고, 구체적 seed 값(20000, 20420 등)으로 복원했다.
• P-224, P-256, P-384, P-521, 그리고 모든 NIST 이진곡선의 백포인트 생성 방식은 아직 규명되지 않았다. B-163 seed 하나도 설명되지 않았다.
• 규명되지 않은 선택의 기준이 있다. P-256의 경우 1842번째 후보 외에도 같은 실행에서 876번째가 유효한 곡선이었는데, P-224는 3개, ANSI 곡선들은 7개의 유효 후보를 건너뛰었다.
• 이는 암호학적 취약점이 아니며 오히려 백도어 가능성을 낮춘다. 타임스탬프 초기화로 생성된 매우 단순한 방식이므로 의도된 약화는 비신뢰적이다.
• Anthropic 팀이 발견한 내용을 검증하기 위한 재현 코드를 공개했다. 상금 36,864달러는 Internet Security Research Group에 기부된다.