NIST 타원곡선 시드 생성의 수수께끼가 풀려 현상금 지급

NIST 타원곡선의 시드는 영어 문장의 해시가 아니라, 1997~1998년의 UNIX 타임스탬프로 초기화한 drand48 난수 생성기의 출력에서 만들어졌음

Anthropic 연구팀이 생성 방식을 밝혀 현상금 전액을 수령했으며, 상금을 Let’s Encrypt 운영 비영리단체 ISRG에 기부하기로 해 기부액이 3배인 36,864달러로 늘어남

생성 과정은 난수로 만든 20바이트 시드를 ANSI X9.62 절차에 따라 시험하고 부적합한 곡선을 제외하는 방식임. 다만 유효한 후보 일부가 공개 곡선에서 빠진 이유는 아직 밝혀지지 않음

확인된 생성 방식에서는 시드 선택의 자유도가 넉넉히 잡아도 약 30비트에 그쳐, 70비트의 자유도를 이용하는 Bernstein과 Lange의 가상 취약 곡선 표적화 기법을 배제함

이번 결과는 NIST 타원곡선에 대한 신뢰를 강화함. 현상금 제안자 Filippo Valsorda는 기존 구현 및 서명 기법의 개선까지 고려해 개인적으로 Curve25519/Ed25519/X25519보다 NIST 타원곡선을 권장함

밝혀진 시드의 기원과 현상금

Anthropic의 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에 기부하기로 했으며, 이에 따라 금액이 3배인 36,864달러(36 Ki$) 로 늘어남

NIST는 P-192, P-224, P-256, P-384, P-521을 2000년 FIPS 186-2에 공개함

ANSI X9.62에 따라 임의의 시드를 SHA-1으로 해시하고, 그 출력으로 일부 곡선 매개변수를 도출함

이번 발견 전까지는 그 임의의 시드를 어떻게 골랐는지 알 수 없었음

기존에는 2023년 초 별세한 Jerry Solinas가 1997년에 영어 문장을 해시해 시드를 만들고 나중에 문장을 잊었다는 이야기가 전해졌음

이제 NIST 타원곡선 암호를 Curve25519/Ed25519/X25519보다 추천한다는데, NIST 곡선의 장점은 무엇인가? Curve25519의 코팩터(cofactor)가 문제를 일으킨 건 알지만, ristretto로 완화된 것으로 알고 있었음.

양쪽의 소소한 장점을 정리해 둔 목록을 언젠가 공개할 생각이지만, 가장 큰 요인은 P-256이 하드웨어를 포함해 어디에나 쓰인다는 점임. 장단점이 미미하고 엇갈리며 맥락에 따라 달라진다면, 두 곡선에 역량을 나누기보다 하나를 아주 잘 구현하는 편을 선호함.
어쨌든 이제 이 비교는 무의미함. ECDSA P-256과 Ed25519 중 무엇을 고를지 묻는다면, 올바른 답은 ML-DSA-44임.

잘 모르고 틀릴 가능성도 높은 직관이지만, 타원곡선에 N비트 보안 수준의 NOBUS 취약점이 있으려면 전체 곡선 중 1/(2^N)에만 해당하는 성질이 필요하지 않을까? 그렇다면 ECDSA에 백도어를 넣었다고 의심받는 NIST나 NSA 등은 해당 취약점을 가진 곡선을 생성하는 타임스탬프 하나를 찾기까지 평균 2^(N-1)개의 타임스탬프를 해시해야 할 듯함. 더 잘 아는 분들이 보기에도 맞는 추론인가?
Filippo의 글에서 해당 범위의 타임스탬프가 약 2^30개뿐이라고 한 건 알지만, 더 일반적인 경우가 궁금함.

이런 우려 때문에 ECDSA를 비활성화해서 상호운용성 문제가 생기는 것을 봤고, Ed25519만 지원하는 프로토콜과 ECDSA만 지원하는 내 하드웨어 토큰·TPM 사이의 호환성 문제도 자주 겪고 있음. 주류의 합의에 맞게 ECDSA를 허용해 달라고 여러 프로젝트를 설득했지만 성과가 없었음. 이번 일을 계기로 https://github.com/jtesta/ssh-audit 도 ECDSA를 경고 대상으로 표시하지 않기를 바람.
다만 비전문가 사이에 음모론이 퍼져 견고한 암호 시스템의 신뢰를 해쳤다는 대목은 조금 가혹하게 느껴짐. Bernstein과 Lange의 기법이 이번 주에야 완전히 배제됐다면, 그전까지 ECDSA를 의심한 것이 그렇게 비합리적이었을까?
저자 자신도 양자내성암호 전환 일정 단축에 관한 글에서 설득력 있게 강조함. 핵심은 2030년에 암호 해독이 가능한 양자컴퓨터가 존재한다고 100% 확신하는지가 아니라, 존재하지 않는다고 100% 확신하는지이며, 그 판단에는 사용자의 목숨이 걸려 있음.

곡선에 백도어가 없었다는 좋은 소식인지, 시드를 만드는 데 이렇게 단순한 선형 합동 생성기를 썼다는 나쁜 소식인지 모르겠음. 암호학자라면 시드 생성에 암호학적으로 안전한 의사난수 생성기(CSPRNG) 를 써야 한다는 걸 알았을 텐데? 시드에 이렇게 약한 방식을 썼다면 곡선에서는 또 무엇을 잘못했을지 의문임.