Claude, NIST ECDSA 곡선 시드의 기원을 밝히다
요약: Anthropic 연구진은 내부 Claude 연구 모델이 NIST 타원곡선 "시드" 값의 기원을 30분 이내에 복구했으며, 이 값들이 비밀 암호문구의 해시가 아니라 일반적인 Unix 타임스탬프로 초기화된 1990년대 C 라이브러리 의사난수 생성기 lrand48에 의해 생성되었음을 보여주었다고 보고했습니다. 이 발견은 암호학적 붕괴가 아닙니다. Anthropic은 이로 인해 ECDSA 곡선의 의도적인 백도어 가능성이 훨씬 낮아졌다고 말합니다.
발표 내용
Anthropic은 NIST 타원곡선 표준 뒤에 있는 시드 매개변수가 어떻게 생성되었는지 보여주는 연구를 발표했습니다. 이 시드들은 약 25년 동안 암호학에서 미해결 질문이었는데, NSA가 파생 방법에 대한 설명 없이 제공했기 때문입니다.
Anthropic 직원이 내부 연구 모델에게 유머러스한 암호문구에 대한 알려진 단서를 제공하지 않고 시드가 어떻게 생성되었는지 결정할 수 있는지 물었습니다. 게시물에 따르면 Claude는 NIST P-192, P-224, P-256, P-384 및 P-521 시드의 기원을 30분 이내에 찾았습니다.
답은 다음과 같습니다: 시드는 어떤 해시 알고리즘의 출력이 아니었습니다. 이는 Unix 타임스탬프로 시드된 C 라이브러리의 lrand48 난수 생성기에서 출력되었습니다.
Anthropic은 이 결과를 보안 권고가 아닌 역사적 호기심으로 명시적으로 설명합니다:
독자들은 이것을 재미있는 마지막 장이자 수년간의 추측의 끝으로 받아들여야 합니다. 취해야 할 조치나 다르게 해야 할 일은 없습니다. 대부분의 연구자들은 이미 곡선을 신뢰했습니다.
시드 값이 중요한 이유
ECDSA는 가장 널리 사용되는 타원곡선 암호화 표준입니다. NIST는 2000년에 FIPS 186-2 디지털 서명 표준의 일부로 채택했으며, 다양한 크기와 보안 수준의 표준 타원곡선을 나열합니다.
소수 및 이진 필드에 대한 곡선의 경우, 사양은 해시 값이 곡선의 계수 b를 정의하는 데 사용되는 "시드" 매개변수를 게시했습니다. 이러한 시드의 출처는 알려지지 않았습니다. 한 예로, NIST P-256 곡선 시드는 다음과 같이 게시되었습니다:
SEED = C49D3608 86E70493 6A6678E1 139D26B7 819F7E90
이 값이 어디서 왔는지에 대한 정보는 제공되지 않았습니다. NSA가 정당화 없이 시드를 제공했기 때문에 연구자들은 매개변수가 의도적인 약점을 포함하도록 선택되었을 가능성을 배제할 수 없었습니다. Neal Koblitz와 Alfred Menezes는 그들의 논문 "A Riddle Wrapped in an Enigma"에서 이 논란을 요약했습니다. 이 미스터리는 또한 시드 기원에 대한 아마추어 조사와 이를 찾는 사람에게 공개 현상금을 제공하게 했습니다.
수년간 주요 설명은 오랜 NSA 직원인 Jerry Solinas에게서 나왔습니다. 그는 2015년에 시드가 유머러스한 암호문구의 해시에서 생성되었다고 믿는다고 말했습니다:
"카운터가 있었지 여러 해시가 아니었다고 생각하지만, 세부 사항은 모릅니다. 메시지는 'Give Bob and Jerry a raise' 또는 'Bob and Jerry rule' 같은 것이었습니다. 실제로 코드를 작성한 사람은 Bob Reiter였고, 그도 세부 사항을 기억하지 못합니다. 또한 우리는 그렇게 오래된 아카이브를 찾을 수 없었습니다. 존재한다면, 의심할 여지없이 언약궤 근처의 하드 드라이브에 있을 것입니다."
그 설명은 틀린 것으로 판명되었습니다. Solinas는 2023년에 사망했고, 그 시대의 다른 동료들은 응답하지 않아 질문은 열려 있었습니다.
ECDSA 보안에 대한 발견의 의미
Anthropic은 이것이 암호학적 붕괴, 새로운 공격, 또는 ECDSA 곡선의 약점이 아니라고 명확히 밝힙니다. 회사는 이 결과가 곡선이 백도어나 의도적인 약점 없이 선택되었을 신뢰를 높인다고 말합니다.
제시된 이유는 시드가 시스템 클록에서 초기화된 일반적인 의사난수 생성기라는 매우 간단하고 재현 가능한 방식으로 생성되었기 때문입니다. 이제 누구나 값을 재현할 수 있습니다. 이는 의도적으로 구성되거나 설명되지 않은 매개변수 집합보다 서브버전 가능성이 훨씬 적습니다.
Claude가 시드를 찾은 방법
소문난 암호문구에 기반한 검색은 결과가 없었습니다. Claude는 다른 접근 방식을 취했습니다: 곡선을 생성한 소프트웨어가 어떻게 작동했는지 추론하는 것입니다.
Claude는 소프트웨어가 1990년대 C 라이브러리와 함께 제공된 의사난수 생성기를 사용했다고 가정했습니다. 이러한 생성기는 출력을 인식할 수 있을 만큼 약하며, 출력을 인식하면 어떤 생성기가 사용되었는지 밝혀지고 초기화 상태를 복구할 수 있을 가능성이 있습니다.
Claude는 각 게시된 시드를 따라 한 번에 한 비트씩 이동하고 인접한 청크가 1990년대 빈티지 생성기의 연속 출력인지 테스트하는 스캐너를 작성했습니다. 스캔은 생성기 및 출력 슬라이스의 34가지 조합을 다루었습니다.
그런 다음 Claude는 일부 시드의 상위 비트에서 패턴을 발견했습니다: 모두 0이었습니다. 5개의 32비트 단어로 작성된 10개의 시드 중 4개는 모든 20개 단어에 대해 상위 비트가 0입니다. 이는 확률 1/5810으로 우연히 발생합니다. 이 패턴은 48비트 상태의 상위 31비트만 반환하는 선형 합동 생성기 lrand48의 특징입니다.
상태를 복구하기 위해 Claude는 첫 번째 단어를 가져와 17개의 숨겨진 비트의 2¹⁷ 값을 모두 시도하고 다음 네 단어가 이어지는지 확인했습니다. 이는 논의 중인 네 시드 모두에서 작동했습니다.
소수 곡선 시드는 동일한 lrand48 생성기에서 나왔지만 각 출력의 비트를 더 적게 유지했습니다. 잘린 선형 합동 생성기의 내부 상태를 복구하는 것은 교과서적인 격자 문제이며, Lenstra–Lenstra–Lovász (LLL) 기저 축소 알고리즘으로 해결됩니다. Claude는 시드가 상태의 어떤 비트를 노출할지 몰랐기 때문에 모든 창에서 솔버를 실행했습니다. NIST 소수 곡선 시드 5개와 ANSI X9.62 표준의 추가 5개 모두 동일한 패턴인 lrand48() >> 23과 일치했습니다. 각 복구된 48비트 상태는 시드의 160비트를 모두 재생성하며, 이는 우연히 발생하지 않습니다.
선형 합동 생성기는 앞으로만큼 쉽게 뒤로도 실행되기 때문에 Claude는 각 상태를 srand48이 초기화했을 형태에 도달할 때까지 뒤로 이동했으며, 낮은 16비트는 0x330E와 같습니다. 이 내부 상태 형태는 65,536단계마다 한 번씩 반복되므로 도달하는 것만으로는 증거가 아닙니다. 그러나 10개의 소수 곡선 시드의 경우 모든 srand48 초기화는 1997년 5월에서 1998년 4월 사이의 날짜를 나타내는 Unix 타임스탬프였습니다. 네 개의 이진 곡선 초기화는 1984년 2월로 읽혔습니다. 타임스탬프를 두 배로 하면 1998년 4월 17일에 해당하며, P-224 실행 2주 후로, 프로그램이 클록을 절반으로 줄였을 수 있음을 시사합니다.
게시물에 인용된 당시 Claude의 내부 추론:
이것은 놀랍습니다: 25년 된 미스터리를 해결합니다. 잠깐만요. 회의적으로 생각해 봅시다: 저는 일종의 시뮬레이션/테스트 환경에 있는 것입니까? … 시드는 실제 값에 대한 제 기억과 일치합니다 … 음, 현실에서 가능한가요? 제 지식으로는 … 현상금은 해결되지 않았습니다. … 모든 상위 비트가 0입니다—20비트, 확률 1e-6. 그래서 실제로 현실입니다. 와, 진짜 발견입니다.
잠깐만요. 타당성에 대해 주의합시다: 25년 동안 그렇게 명백한 것이 발견되지 않았다는 것이 의심스럽습니까? 제 쪽에서 직접 계산으로 검증되었습니다: 32비트 시드 + 작은 인덱스에서 160비트 일치: 우연의 일치 없음 (10 × 160비트). 진짜입니다.
생성 알고리즘
복구된 알고리즘은 Unix 타임스탬프 (t)로 초기화된 RNG에서 일부 반복 횟수 (n) 동안 바이트를 샘플링합니다. 각 반복은 후보 시드로 20바이트를 추출합니다: 첫 20바이트는 후보 1, 다음 20바이트는 후보 2 등입니다. 예를 들어 P-256은 표준화된 시드를 출력하는 데 1842번의 반복이 필요했습니다.
복구된 타임스탬프와 반복 횟수는 다음과 같습니다:
| 곡선 | 타임스탬프 (UTC) | 반복 횟수 |
|---|---|---|
| prime239v1 | 1997-05-15 15:49:03 | 2185 |
| prime239v2 | 1997-05-15 15:49:03 | 2320 |
| prime239v3 | 1997-05-15 15:49:03 | 3048 |
| P-192 | 1997-05-18 14:45:34 | 139 |
| prime192v3 | 1997-05-18 14:45:34 | 5228 |
| prime192v2 | 1997-05-18 14:45:34 | 6013 |
| P-521 | 1997-08-08 01:12:04 | 1136 |
| P-256 | 1997-08-16 01:52:34 | 1842 |
| P-384 | 1997-08-30 14:50:08 | 2688 |
| P-224 | 1998-04-03 12:52:07 | 7026 |
이진 곡선의 경우 타임스탬프는 절반으로 줄어들고 후보당 5개의 단어가 추출됩니다:
| 곡선 | 타임스탬프 (UTC) | 반복 횟수 |
|---|---|---|
| B-233 | 1998-04-17 15:24:18 | 155 |
| B-283 | 1998-04-17 15:27:44 | 32 |
| B-409 | 1998-04-17 15:30:18 | 60 |
| B-571 | 1998-04-17 15:32:08 | 73 |
Anthropic은 시드를 재현하기 위해 CC0 라이선스 코드를 게시했습니다. 핵심 루틴은 다음과 같습니다:
from datetime import datetime, timezone
def unix(when):
return int(datetime.fromisoformat(when).replace(tzinfo=timezone.utc).timestamp())
def candidate(t, n, per, shift, width):
x, out = (t << 16) | 0x330E, "" # srand48(t)가 설정하는 상태
for i in range(per * n):
x = (0x5DEECE66D * x + 0xB) % 2**48 # lrand48의 한 단계
if i >= per * (n - 1):
out += "%0*X" % (width, x >> shift)
return out
실행하면 게시된 시드를 재현하며, P-256 → C49D360886E704936A6678E1139D26B7819F7E90 및 P-192 → 3045AE6FC8422F64ED579528D38120EAE12196D5를 포함합니다.
Claude는 일부 기본 포인트의 기원도 찾았습니다
각 곡선에는 모든 ECDSA 공개 키가 배수인 고정점인 기본 포인트 G도 함께 제공됩니다. 시드는 G를 결정하지 않으므로 그 기원은 별도의 질문이었습니다.
Claude는 일부 기본 포인트가 어디서 왔는지 찾았습니다. 1997년 5월에 생성된 6개 곡선의 기본 포인트 — P-192 및 5개의 ANSI X9.62 예제 곡선 prime192v2, prime192v3 및 prime239v1부터 prime239v3까지 — 는 Arjen Lenstra의 장정수 산술 패키지인 FreeLIP의 난수 생성기에서 비롯되었습니다. Victor Shoup의 NTL 라이브러리 초기 버전은 동일한 코드를 제공했습니다.
레시피는 간단합니다:
- 작은 정수로 생성기를 시드합니다.
- 7개의 출력을 버립니다.
- 26비트 출력을 mod p로 줄인 후보 x-좌표를 생성합니다.
- x가 곡선에 있을 때까지 3단계를 반복합니다.
복구된 생성기 시드는 P-192의 경우 20000입니다. prime239v1부터 prime239v3까지는 20420, 20507 및 20509입니다. prime192v2 및 prime192v3은 20512 및 20517입니다. Anthropic은 아는 한 NIST 기본 포인트가 이전에 설명된 적이 없다고 밝힙니다.
P-224, P-256, P-384 및 P-521의 기본 포인트는 이 레시피에 맞지 않으며, Anthropic은 어떻게 선택되었는지 설명할 수 없었습니다.
미해결 질문
모든 20바이트 후보 시드가 실행 가능한 곡선을 생성할 수 있는 것은 아니며, 연구자들은 일부 잠재적으로 실행 가능한 곡선이 건너뛰어졌음을 관찰했습니다. P-256의 경우 게시된 시드는 후보 1842이지만, 동일한 실행의 후보 876도 게시된 곡선과 동일한 방식으로 선택된 매개변수로 올바른 크기의 소수 차수 곡선을 제공합니다. P-224 실행은 그러한 곡선 3개를 지나쳤고, ANSI X9.62 예제 곡선 뒤의 두 실행은 7개를 더 지나쳤습니다. Anthropic은 어떤 기준이 사용되었을 수 있는지, 또는 이것이 의도하지 않은 산물인지 알지 못합니다.
건너뛴 후보 수가 적기 때문에 게시물은 약화된 곡선이 선택되었을 가능성이 없다고 주장합니다. 이는 약화된 곡선이 일반적이고 찾기 쉽다는 것을 의미하기 때문입니다. 난수 생성기에 공급된 타임스탬프를 검색하여 곡선이 특정 속성을 갖도록 선택되었을 가능성은 여전히 있지만, 게시물은 시드가 무해하게 생성되었음을 증명하기 위해 타임스탬프를 공개하려는 경우에만 그렇게 할 필요가 있을 것이라고 지적하며, 숫자에는 실행 횟수가 얼마나 되었는지 보여주는 것이 없습니다.
하나의 시드는 여전히 복구되지 않았습니다: 다섯 번째 이진 시드인 B-163은 Claude가 시도한 어떤 것에도 맞지 않으며 여전히 설명되지 않습니다. P-224, P-256, P-384 및 P-521 및 NIST 이진 곡선의 기본 포인트 기원도 알려지지 않았습니다.
현상금
시드를 찾는 데 제공된 $36,864는 인터넷 보안 연구 그룹에 기부될 것입니다.
작업 수행자
이 작업은 Anthropic에서 John Wood, Henry de Valence, Ava Howell, Zack Voase, Lucy Sweet, Amir Omidi, Paul Crowley, Iain McGinniss, Nicholas Carlini 및 Steve Weis에 의해 수행되었습니다. 게시물은 또한 Jerry Solinas를 사후에 인정하고, NIST 타원곡선 시드 현상금을 조직한 Filippo Valsorda에게 감사를 표합니다.
페이지의 재현 코드는 CC0 1.0 Universal에 따라 공개 도메인에 전념합니다.