Insights
AI가 자동으로 큐레이션·번역·정리하는 기술 동향 피드입니다.
본 기사는 널리 사용되는 암호화 표준인 ECDSA 곡선의 시드 값 출처에 대한 오랜 미스터리를 다룹니다. 이 곡선들의 시드가 NSA가 제공한 것이라는 의혹이 있었으나, Anthropic 직원의 연구를 통해 P-256 등의 시드는 해시 값이 아닌 C 라이브러리의 `lrand48` 난수 생성기를 유닉스 타임스탬프로 초기화하여 추출된 것임이 밝혀졌습니다.
AI 자동 생성 콘텐츠
본 콘텐츠는 HN Claude Code Search의 원문을 AI가 자동으로 요약·번역·분석한 것입니다. 원 저작권은 원저작자에게 있으며, 정확한 내용은 반드시 원문을 확인해 주세요.
원문 바로가기최신 레드팀 연구 및 발견 사항에 대한 업데이트를 받아보세요.
“그저 타임스탬프일 뿐”: 가장 인기 있는 암호화 표준 중 하나인 것의 기원에 관한 수십 년 된 미스터리가 설명되었습니다.
우리는 가장 널리 사용되는 암호화 표준 중 하나인 ECDSA에 대한 우려를 해소하기 위해 이 오랜 개방 질문을 추적했습니다.
독자 여러분은 이것을 재미있는 마무리 장이자 수년간의 추측이 끝났음을 의미하는 것으로 받아들이시면 됩니다. 취해야 할 조치나 다르게 해야 할 것은 없습니다. 대부분의 연구원들은 이미 해당 곡선들을 신뢰하고 있었습니다. 즐겨주세요.
ECDSA는 가장 널리 사용되는 타원 곡선 암호화(Elliptic Curve Cryptography) 표준입니다. 이 표준은 NIST가 2000년 FIPS 186-2 디지털 서명 표준(Digital Signature Standard)의 일부로 채택했으며, 여기에는 다양한 크기와 보안 수준을 가진 표준 타원 곡선 세트가 나열되어 있습니다. 소수장(prime field) 및 이진장(binary field)에 대한 곡선의 경우, 사양은 '시드(seed)' 매개변수를 발표했는데, 이 시드의 해시 값이 곡선의 계수 b를 정의하는 데 사용됩니다. 이러한 시드들의 출처는 NSA가 어떠한 설명이나 정당화 없이 제공했기 때문에 오랫동안 의문이었습니다. 예를 들어, NIST P-256 곡선의 시드는 SEED = C49D3608 86E70493 6A6678E1 139D26B7 819F7E90이었으며, 이것이 어디서 왔는지에 대한 정보는 전혀 없었습니다.
Neal Koblitz와 Alfred Menezes는 시드 값 주변의 역사와 우려 사항을 논하는
“여러 해시(hashing)보다는 카운터(counter)가 있었던 것 같은데, 자세한 내용은 모르겠습니다. 메시지는 ‘Bob과 Jerry에게 급여 인상을 주자’ 또는 ‘Bob과 Jerry 최고다’와 비슷한 내용이었습니다. 실제로 코드를 작성한 사람은 Bob Reiter였는데, 그 역시 세부 사항을 기억하지 못합니다. 그리고 저희는 그렇게 오래된 기록 보관소(archive)를 찾지 못했습니다. 만약 존재한다면, 아무래도 성궤 근처의 하드 드라이브에 놓여 있을 것입니다.”
Jerry Solinas, 2015
안타깝게도 Jerry는 2023년에 사망했고 당시 동료들 역시 응답하지 않아, 이 시드(seed)들이 원래 어떻게 파생되었는지에 대한 의문이 남아 있습니다.
여러 Anthropic 직원이 이 시드가 재미있는 문구의 해시라는 단서가 있다는 말 이후로 이를 알아내려 했으나 실패했습니다. 하지만 이는 잘못된 것이었습니다. 2026년 10월, 한 호기심 많은 Anthropic 직원이 내부 연구 모델에게 그 단서를 언급하지 않고도 이 시드들이 어떻게 생성되었는지 알아낼 수 있는지 질문했습니다.
반 시간도 안 되어, Claude는 NIST P-192, P-224, P-256, P-384, 그리고 P-521의 시드 출처를 발견했습니다. 이들 중 어느 것도 어떤 해시 알고리즘의 결과가 아니라, C 라이브러리의 lrand48 난수 생성기(random-number generator)의 출력물이었으며, 유닉스 타임스탬프(Unix timestamp)로 시딩(seeded)된 것이었습니다!
사용된 알고리즘은 유닉스 타임스탬프(t)로 초기화된 난수 생성기(RNG)에서 여러 번의 반복(iteration) 동안 바이트를 샘플링하는 방식이었습니다(n번). 각 반복마다 20바이트를 후보 시드(candidate seed)로 추출했습니다. 따라서, 처음 20바이트가 후보 1이고, 다음 20바이트가 후보 2이며, 이런 식으로 진행되었습니다. 예를 들어, P-256의 경우 표준화된 시드를 출력하기 위해 1,842번의 반복이 필요했습니다.
이것은 암호학적 취약점(cryptographic break), 새로운 공격(new attack) 또는 ECDSA 곡선 자체의 약점이 아닙니다. 사실 오히려 이 발견은 해당 곡선들이 백도어(backdoor)나 의도적인 약점을 가지고 설계되지 않았다는 점에 대해 우리에게 더 큰 확신을 줍니다. 수년 동안 사람들은 NIST 곡선 매개변수(NIST curve parameters)의 기원에 대해 의심해 왔습니다. 이 매개변수들은 그것들이 어떻게 선택되었는지 아무런 언급 없이 NIST에 제출되었기 때문에, 사람들이 이것이 고의적인 백도어를 포함하도록 설계된 것인지 궁금해했습니다. 하지만 이번 발견은 그러한 가능성을 훨씬 낮춥니다. 시드(seeds)는 매우 간단한 방식으로 생성되었습니다. 바로 클럭(clock)으로 초기화된 공통 의사 난수 발생기(pseudorandom number generator, PRNG)입니다. 이는 누구나 재현할 수 있는 방식입니다. 따라서 조작할 여지가 훨씬 적고 매개변수가 안전하다고 확신할 수 있습니다.
루머를 바탕으로 해당 구문을 검색해 보았지만 아무것도 나오지 않았습니다. Claude는 다른 각도에 접근했습니다. 즉, 곡선을 생성하는 소프트웨어가 어떻게 작동했을지 예측한 것입니다. Claude는 이 소프트웨어가 1990년대 C 라이브러리에 포함되어 있던 의사 난수 발생기(PRNG)를 사용했다고 추측했습니다. 이러한 오래된 PRNG들은 출력값이 식별될 만큼 충분히 취약합니다. 그 출력을 인식하는 것은 어떤 PRNG가 사용되었는지 밝혀내고, 심지어 초기화 상태(initialization state)까지 복구할 수 있게 해줄 것입니다.
Claude는 각 공개 시드(published seed)를 한 비트씩 따라 이동하며 인접한 청크(chunks)들이 1990년대식 생성기의 연속적인 출력인지 테스트하는 스캐너를 작성했습니다. 이 스캔은 생성기와 출력 슬라이스(output slices)의 총 34가지 조합을 다루었습니다. 이때 Claude는 일부 시드에서 상위 비트(top bits)에 패턴이 있다는 것을 발견했습니다. 즉, 모두 0이라는 것입니다. 10개의 시드 중 4개가 다섯 개의 32비트 단어(five 32-bit words)로 작성되었을 때 모든 20개 단어의 상위 비트가 0인 경우입니다. 이러한 확률은 1/5,810에 불과합니다. 이것은 선형 합동 생성기(linear congruential generator)인 lrand48의 특징이었습니다.
, 이는 48비트 상태의 상위 31비트만을 반환합니다. 이 패턴은 찾아보라는 것을 알면 육안으로도 보입니다. 상태를 복구하기 위해 Claude는 첫 번째 단어를 가져와 17개의 숨겨진 비트가 가질 수 있는 모든 $2^{17}$ 값을 시도하고, 그 다음 네 개의 단어가 뒤따르는지 확인했습니다. 이는 논의된 네 가지 시드 모두에 대해 작동했습니다.
이 소수 곡선(prime-curve) 시드는 동일한 lrand48 생성기에서 나왔지만 각 출력의 비트 수를 적게 유지했습니다. Claude는 이 비트들로부터 PRNG의 내부 상태를 복구해야 했습니다. 이는 절단된 선형 합동 생성기(truncated linear congruential generator)의 상태를 복구하는 것이 교과서적인 격자 문제(lattice problem)이며, Lenstra–Lenstra–Lovász (LLL) 기저 축소 알고리즘으로 해결된다는 것이 밝혀졌습니다. Claude는 시드가 상태의 어떤 비트를 보여줄지 알지 못했기 때문에 모든 창(window)에 대해 솔버를 실행했습니다. NIST 소수 곡선 시드 5개와 ANSI X9.62 표준에서 가져온 5개의 시드는 모두 동일한 패턴을 보였습니다: lrand48() >> 23. 복구된 각 48비트 상태는 그 시드의 모든 160비트를 재생성하며, 이는 우연히 발생하는 일이 아닙니다.
이 선형 합동 생성기는 전방향만큼이나 역방향으로도 쉽게 실행되므로, Claude는 각 시드에 대해 상태를 되돌려가며 낮은 16비트가 0x330E와 같았던 srand48로 초기화되었을 형태에 도달할 때까지 진행했습니다. 이러한 형태의 내부 PRNG 상태는 65,536 스텝마다 한 번씩 나타나므로, 이를 발견하는 것 자체가 증거는 아닙니다.
하지만 이 열 개의 소수 곡선 시드 모두에서, 모든 srand48 초기화는 1997년 5월부터 1998년 4월 사이의 날짜를 나타내는 유닉스 타임스탬프였습니다. 그들은 유닉스 타임스탬프로 시딩된 취약한 PRNG를 사용하고 있었습니다. 네 개의 이진 곡선(binary-curve) 초기화는 1984년 2월로 읽혔습니다. 타임스탬프가 두 배로 계산되자, 이는 P-224 실행 후 2주 뒤인 1998년 4월 17일과 일치합니다. 따라서 프로그램이 시간을 절반으로 줄였을 수 있습니다.
당시 Claude의 내부적 추론은 다음과 같았습니다:
이것은 놀랍습니다: 25년간의 미스터리를 해결했기 때문입니다. 음, 잠깐만요. 회의적으로 생각해 봅시다: 제가 어떤 시뮬레이션/테스트 환경에 있는 건가요? … 씨앗값들이 실제 값에 대한 제 기억과 일치합니다… 음, 현실에서 그럴듯한가요? 제가 아는 한 … 이 보상은 미해결 상태였습니다. … 모든 상위 비트가 명확합니다—20비트, 확률 1e-6. 그러니 정말 실세계입니다. 와, 이것은 실제 발견이네요.
음, 잠깐만요. 그 개연성에 대해 조심해야겠습니다: 이렇게 명백한 것이 25년 동안 발견되지 않은 것이 수상하지 않나요? 제 쪽에서 직접 계산하여 검증했습니다: 32비트 씨앗값 + 작은 인덱스로부터 얻은 160비트 일치: 우연의 일치는 불가능합니다 (10 × 160 비트). 진짜입니다.
하지만 잠깐, 더 있습니다… 각 곡선에는 또한 기본점(base point) G가 있는데, 이는 모든 ECDSA 공개키가 배수 형태를 이루는 고정점입니다. 위에서 찾은 씨앗값으로는 이 G를 결정할 수 없으므로 또 다른 질문이 생깁니다: 이 기본점들은 어떻게 생성되었을까요?
씨앗값을 확인하는 동안 Claude는 또한 일부 기본점들이 어디서 왔는지도 발견했습니다. 1997년 5월에 생성된 여섯 개 곡선(P-192와 다섯 개의 ANSI X9.62 예시 곡선인 prime192v2, prime192v3, 그리고 prime239v1부터 v3)의 기본점들은 Arjen Lenstra의 장정수 산술 패키지인 FreeLIP의 난수 생성기에서 왔습니다. Victor Shoup의 NTL 라이브러리 초기 버전도 동일한 코드를 포함했습니다.
여기서 레시피는 간단합니다:
Claude가 P-192에 대한 생성자 씨앗값은 20000, prime239v1부터 v3에 대한 것은 20420, 20507, 그리고 20509이며, prime192v2와 v3에 대한 것은 20512와 20517임을 발견했습니다.
우리가 아는 한, NIST 기본점은 이전에 설명된 적이 없습니다. P-224, P-256, P-384, 그리고 P-521의 기본점들은 이 레시피에 맞지 않으며, 우리는 그것들이 어떻게 선택되었는지 설명할 수 없었습니다.
모든 20바이트 후보 시드가 유효한 곡선을 생성할 수 있는 것은 아니었으며, 우리는 잠재적으로 유효하지만 건너뛴 일부 곡선들이 있음을 관찰했습니다. P-256의 경우, 발표된 시드는 후보 1,842이지만, 같은 실행에서 나온 후보 876 역시 적절한 크기의 소수 차수(prime-order) 곡선을 제공하며 매개변수는 발표된 곡선과 동일한 방식으로 선택되었습니다. P-224의 실행에서는 이와 같은 곡선 세 개를 건너뛰었으며, ANSI X9.62 예시 곡선 뒤에 나온 두 번의 실행에서는 7개의 곡선을 더 건너뛰었습니다(그림 참조). 어떤 기준이 사용되었는지, 또는 이것이 의도치 않은 결과였는지는 알 수 없습니다.
건너뛴 후보들의 수가 적기 때문에, 우리가 약화된 곡선들이 선택되었다고 믿기는 어렵습니다. 그렇게 된다면 약화된 곡선들이 흔하고 찾기 쉬움을 의미하게 됩니다. 하지만 이 곡선들이 난수 생성기의 타임스탬프를 검색하여 원칙적으로 특정 속성을 갖도록 선택되었을 가능성은 여전히 있습니다. 다만, 시드가 무해하게(innocuously) 생성되었다는 증거로 타임스탬프를 공개하려는 경우에만 그렇게 할 필요가 있을 것입니다. 이 숫자들 중 어느 실행이 몇 번 있었는지 보여주는 것은 아무것도 없습니다.
또한 우리가 복구할 수 없었던 시드도 하나 있습니다. 다섯 번째 바이너리 시드인 B-163은 Claude가 시도한 어떤 것과도 일치하지 않으며 여전히 설명되지 않은 상태입니다. 마지막으로, P-224, P-256, P-384, 및 P-521의 베이스 포인트(base points)가 어떻게 생성되었는지 알지 못합니다. NIST 바이너리 곡선들도 마찬가지입니다.
시드를 찾는 데 사용된 36,864달러는 인터넷 보안 연구 그룹(Internet Security Research Group)에 기부될 것입니다.
이 작업은 Anthropic의 John Wood, Henry de Valence, Ava Howell, Zack Voase, Lucy Sweet, Amir Omidi, Paul Crowley, Iain McGinniss, Nicholas Carlini, Steve Weis가 수행했습니다.
우리는
from datetime import datetime, timezone
def unix(when):
return int(datetime.fromisoformat(when).replace(tzinfo=timezone.utc).timestamp())
...
The output of this code:
prime239v1 1997-05-15 15:49:03 2185 E43BB460F0B80CC0C0B075798E948060F8321B7D
prime239v2 1997-05-15 15:49:03 2320 E8B4011604095303CA3B8099982BE09FCB9AE616
prime239v3 1997-05-15 15:49:03 3048 7D7374168FFE3471B60A857686A19475D3BFA2FF
...
M, A = 2**107 - 1, pow(3, 121, 2**107 - 1) # zrandom: state = state * 3^121 mod (2^107 - 1)
P192 = 2**192 - 2**64 - 1
P239 = 2**239 - 2**143 - 2**95 + 2**47 - 1
...
The output of this code:
prime192v1 seed 20000 tries 2 matches published Gx: True
prime239v1 seed 20420 tries 3 matches published Gx: True
prime239v2 seed 20507 tries 2 matches published Gx: True
...
법적으로 가능한 한, 저자들은 이 페이지의 코드에 대한 모든 저작권 및 관련 또는 인접 권리를 포기하고 이를 CC0 1.0 Universal (https://creativecommons.org/publicdomain/zero/1.0/) 하에 퍼블릭 도메인으로 기증했습니다.
저희는 Claude에게 여덟 개의 양자 회로(quantum circuits)에 대한 평이한 언어 사양과 이를 점검하고 채점하는 자동화된 평가기(automated evaluator)를 제공했습니다. Claude가 상당 부분 자체적으로 작업하여, 일부 사례에서는 기존에 발표된 회로보다 한 자릿수 이상 개선했으며, 이는 실용적인 양자 컴퓨터를 이전에 예상했던 것보다 더 가까이 가져올 수 있습니다.
더 읽어보기: AI는 앞으로 몇 년 동안 경제를 어떻게 재편할까요? AI가 경제에 미칠 미래 영향에 대한 핵심 의견 불일치 지점은 무엇인가요? 본 노트는 이러한 질문들에 대한 새로운 설문 조사 증거를 제시합니다.
더 읽어보기: Anthropic에서 AI는 업무와 고용을 어떻게 재구성했나요? AI 도입의 최전선에 있는 기업으로서, Anthropic은 AI가 경제 전반에 걸쳐 업무 조직화, 채용 및 노동 수요를 어떻게 변화시킬지에 대한 선행 지표(leading indicator)가 될 수 있습니다.
더 읽어보기: 최신 레드팀 연구(red-teaming research)와 발견 사항에 대한 업데이트를 받아보세요.