NIST 곡선 시드의 비밀: ECDSA 기원에 관한 5가지 오해

25년 동안 NIST ECDSA 곡선 시드는 응용 암호학에서 가장 풀리지 않은 미제 사건과 같았습니다. NSA가 아무런 설명 없이 NIST에 넘긴 다섯 개의 160비트 값은 TLS 연결부터 비트코인 트랜잭션까지 모든 서명의 기반이 되어 왔죠. 이번 주에 사건이 종결됐는데, 답은 거의 민망할 정도입니다. 시드는 1997년과 1998년의 Unix 타임스탬프로 시드를 설정한 C 라이브러리의 lrand48() 생성기 출력이었습니다. 그게 전부입니다. 비밀 패스프레이즈의 해시도, 이국적인 장치도 없어요. 보안 강의에서 절대 쓰지 말라고 하는 바로 그 패턴, srand48(time(NULL))이었습니다.

발견은 Anthropic의 연구 모델에서 나왔습니다. 호기심 많은 직원이 문제를 던졌고, 모델은 공개된 상수에서 1990년대 선형 합동 생성기의 통계적 특징을 알아보고 상태를 거꾸로 돌려 달력 날짜에 도달했죠. 암호 시스템을 감사하며 몇 년을 보낸 입장에서 이건 중요하다고 봅니다. 곡선이 깨졌다는 뜻은 아니에요(깨지지 않았습니다). 업계가 자신 있게 믿어 온 여러 가지를 무너뜨리기 때문입니다. 하나씩 오해를 짚어 보죠.

오해 1: 설명되지 않은 상수는 숨겨진 백도어를 뜻한다

이런 의심이 전혀 터무니없었던 건 아닙니다. NIST가 2000년 FIPS 186-2 곡선을 발표했을 때, 각 곡선에는 해시값이 곡선 계수 b를 결정하는 시드가 함께 붙어 있었습니다. NIST는 시드가 곡선이 '검증 가능하게 무작위'임을 보장한다고 했지만, 시드 자체를 어떻게 생성했는지는 설명하지 못하거나 하지 않았죠. Koblitz와 Menezes는 '수수께끼에 싸인 수수께끼(A Riddle Wrapped in an Enigma)'라는 제목의 논문을 써서 이 논쟁을 다뤘습니다. 커뮤니티가 가진 가장 유력한 단서는 NSA의 Jerry Solinas였습니다. 그는 2015년에 입력이 '밥과 제리에게 월급 인상을 주자' 같은 유머 문구의 해시였다고 회상했어요. 그는 2023년에 세상을 떠났고, 세부 사항은 끝내 복구되지 않았습니다.

음모론을 좋아하는 사람들에게 불편한 진실이 있습니다(저도 가끔 그랬어요). 설명되지 않음은 대개 문서화되지 않았다는 뜻이지, 악의가 있었다는 뜻이 아닙니다. 실제 생성 과정은 개발자가 작은 C 프로그램을 돌려 기본 PRNG가 벽시계로 스스로 시드를 설정하게 하고, 사용 가능한 곡선을 만들어 낸 첫 후보를 골라 쓴 것이었습니다. P-256의 공개된 시드는 1997년 8월 16일 새벽 1시 52분에 시작된 실행의 1,842번째 후보였죠. 이건 숫자 이론적 트랩도어를 심으려는 기관의 작업 방식이 아닙니다. 새벽 한 시에 뭔가 유효한 값이 나올 때까지 루프를 돌리는 엔지니어의 모습이죠.

이런 패턴은 사고 회고에서 셀 수 없이 봤습니다. 정체불명의 설정값, 문서화되지 않은 매직 상수, 아무도 설명하지 못하는 배포 단계. 그런데 사후 분석을 해 보면 지친 엔지니어가 당시에는 합리적이라고 생각한 지름길이었고, 그걸 문서로 남기지 않았을 뿐입니다. NSA의 진짜 잘못은 곡선에 백도어를 심은 것이 아닙니다. 암호 상수를 README 없이 전 세계에 배포한 것이죠.

오해 2: 생성 방식을 보면 선택이 정직했음을 증명한다

이번 주 많은 논평이 '그냥 타임스탬프였다'는 말을 완전한 무죄 입증으로 취급합니다. 그렇지 않고, 연구자들도 이를 조심스럽게 말하고 있어요. 후보가 어떻게 생성됐는지 안다고 해서 최종 곡선이 어떻게 선택됐는지는 알 수 없습니다. 그리고 선택은 1997년 5월부터 1998년 4월까지 몇 달에 걸쳐 이루어졌습니다.

증거는 양쪽으로 작용합니다. P-256 실행에서 후보 876번도 같은 파라미터 규칙으로 만든 올바른 크기의 소수 위수 곡선을 만들었지만 건너뛰었습니다. 공개된 곡선은 1,842번 후보입니다. P-224 실행은 유효한 곡선 세 개를 넘겼고, ANSI X9.62 실행은 일곱 개를 더 건너뛰었습니다. 기록된 실행에서 도달 가능한 후보의 이력만 볼 수 있고, 버려진 후보의 전체 이력은 볼 수 없죠. 누군가 특정한 희귀 속성을 가진 곡선을 원했다면, 원리적으로는 타임스탬프를 뒤져서 찾아낸 뒤 그 타임스탬프에 대해서는 입을 다물 수 있었습니다. '하고도 말하지 않기'는 언제나 선택지였습니다.

약한 곡선 연구를 몇 년간 지켜본 제 판단은 이렇습니다. 백도어 가설은 심하게 상처 입었지만 공식적으로 죽은 건 아닙니다. 건너뛴 후보 수가 적어서, 체리피킹이 가능하다면 약한 곡선이 흔하고 쉽게 찾을 수 있다는 뜻이 되는데, 20년간의 공개 암호 분석은 그렇지 않다고 말합니다. 이 곡선들을 무작위 곡선과 구별하는 판별기는 지금까지 공개된 적이 없습니다. 하지만 '알려진 약점이 없다'와 '약점이 없음이 증명됐다'는 전혀 다른 말이고, 정직한 입장은 전자입니다. 이건 표준 수준에서 벌어진 명세와 구현의 간극의 전형입니다. 명세는 '검증 가능하게 무작위'라고 했지만, 구현은 '시계가 가리킨 값'이었으니까요.

시드는 대학원생이 할 법한 방식으로 생성됐습니다. 기본 PRNG와 시스템 시계요. 스캔들의 핵심은 수학이 아니었습니다. 문서가 없었다는 점이죠.

오해 3: 오래된 약한 PRNG도 한 번만 쓰면 무해하다

srand(time(NULL))를 한 번이라도 타이핑해 본 엔지니어라면 이 오해에 정신이 번쩍 들어야 합니다. 25년 동안 신비의 장막이 드리워져 있던 이유는 lrand48()의 한 가지 설계 특성 때문이었습니다. 이 생성기는 48비트 상태의 상위 31비트만 반환하기 때문에 출력 워드의 최상위 비트가 항상 0입니다. 32비트 워드로 보면, 이진 곡선 시드 열 개 중 네 개에서 연속 스물 개 워드의 최상위 비트가 모두 0으로 나타납니다. 균등 분포라는 가정하에 이런 일이 생길 확률은 약 58,000분의 1입니다. 누군가 조금이라도 들여다봤다면 맨눈으로도 보이는 신호였죠.

그다음 공격은 민망할 만큼 싸게 먹힙니다. 이진 곡선 상태를 복구하려면 첫 번째 출력 워드에서 숨겨진 하위 2^17 비트를 무차별 대입하고, 다음 네 워드가 맞는지 확인하면 됩니다. 계산 시간은 몇 밀리초입니다. 소수 곡선의 경우 시드가 출력마다 적은 비트만 남겼기 때문에, 상태 복구에는 고전적인 잘린 LCG 공격이 필요했습니다. 격자 문제로 모델링하고 LLL 기저 축소를 적용하는 방식이죠. 말 그대로 교과서적인 내용입니다. 상태를 얻으면 LCG는 앞으로 돌리는 것만큼 쉽게 거꾸로 돌릴 수 있어서, srand48 초기화 형태, 즉 하위 비트가 0x330E와 같아질 때까지 되돌리고 시드된 타임스탬프를 읽어내면 됩니다.

# The whole mystery, reproduced
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, ""   # state set by srand48(t)
for i in range(per * n):
x = (0x5DEECE66D * x + 0xB) % 2**48   # one lrand48 step
if i >= per * (n - 1):
out += "%0*X" % (width, x >> shift)
return out
# P-256: run started 1997-08-16 01:52:34 UTC, candidate 1842
print(candidate(unix("1997-08-16 01:52:34"), 1842, 20, 40, 2))
# -> C49D360886E704936A6678E1139D26B7819F7E90  (the published NIST seed)

이 교훈은 표준 기구에만 해당하지 않습니다. 세션 토큰, 요청 ID, 솔트, 파일명 등 '무작위처럼 보이는' 값은 모두 그것을 만든 생성기의 지문을 지니고 있습니다. 그 생성기가 선형 합동 엔진이나 메르센 트위스터라면, 몇 개의 출력만으로 내부 상태를 재구성할 수 있고, 그 전후에 생성한 모든 값이 예측 가능해집니다. 25년 전 노이즈처럼 보이도록 만든 파일의 단 한 번의 사용이 완전히 뒤집힌 셈이죠. 공격자가 관찰할 수 있는 무엇이든 비암호학적 난수 생성기로 만들어진 코드를 리뷰할 때, 앞으로 저는 이 이야기를 근거로 들겠습니다.

오해 4: 아무것도 숨기지 않은 상수(nothing-up-my-sleeve)가 진짜 보호막이었던 적은 없다

'nothing-up-my-sleeve' 개념은 파이의 자릿수처럼 명백히 무해한 것에서 상수를 도출해 설계자의 자유도를 제한하려는 것입니다. 제 상수가 공개된 엄격한 절차에서 나왔다는 것을 보여줄 수 있다면, 트랩도어를 몰래 넣을 여지가 없었다는 뜻이죠. NIST 시드는 절차상 이 테스트에 실패했습니다. 절차가 비밀이었으니 자유도의 한계를 알 수 없었던 거죠. 하지만 이번 일이 진짜로 드러내는 것은, 이 테스트가 제대로 작동할 때조차 우리가 믿었던 것보다 약하다는 점입니다.

'타임스탬프에서 나온 검증 가능한 무작위'가 실제로 무엇을 보장하는지 생각해 보세요. 그럴듯한 시간 범위의 타임스탬프는 약 31비트의 엔트로피를 가집니다. 원래 저자를 포함한 누구나 수백만 개의 타임스탬프를 훑어 수백만 개의 후보 곡선을 만들고, 원하는 것 하나와 그 무해해 보이는 시드만 공개할 수 있습니다. 비밀 약점을 가진 곡선이 백만 분의 1 비율로 존재한다면, 타임스탬프 그라인딩으로 하루 오후면 하나를 찾아낼 수 있습니다. 시드는 숫자가 어디서 왔는지는 증명하지만, 왜 그 숫자가 선택됐는지는 거의 말해주지 않습니다. 패스프레이즈 해시 방식도 마찬가지이며, 솔린스의 유머 문구에 대한 소문이 완전히 안심을 주지 못했던 이유도 여기에 있습니다.

현대적으로 더 강한 방법은 엄격한 곡선 구성입니다. 공개된 보안 기준 목록을 만족하는 가장 작은 계수를 고르고, 탐색을 시작하기 전에 선택 규칙을 고정하는 방식이죠. Curve25519의 철학이 바로 이것이며, Dan Bernstein의 엄격성 논증은 커뮤니티가 곡선을 평가하는 방식을 바꿔 놓았습니다. 악의적인 상수에 대한 실제 보호는 멋진 유도 이야기가 아니었습니다. 탐색 공간을 최소화하고, 기준을 미리 공개하고, 숨겨진 속성이 숨겨진 채로 남을 수 없도록 충분히 많은 독립적인 눈이 수학을 검토하게 하는 것입니다. 상수를 감사한다는 것은 그 상수를 걸러낸 과정을 감사한다는 뜻이고, 그래서 여기 남은 의문들, 즉 건너뛴 후보, P-256 등의 설명되지 않은 기준점, 아직 밝혀지지 않은 B-163 시드는 축하 분위기에 묻히지 말고 기록에 열린 채로 남아 있어야 합니다.

오해 5: LLM은 그저 되뇌기만 할 뿐, 독창적인 암호 분석은 못 한다

제가 일부 믿었던 오해라서 가장 뜨끔합니다. 이 미해결 문제는 36,864달러의 공개 현상금과 숙련된 아마추어들의 관심에도 25년 동안 풀리지 않았습니다. Anthropic의 여러 연구자도 직접 이 문제를 쫓으며 '재미있는 문구의 해시'라는 단서를 따라갔지만 성과가 없었습니다. 그런데 소문을 전혀 듣지 않은 내부 연구 모델이 30분도 안 되는 시간에 다른 각도로 접근했습니다. 해시 입력을 추측하는 대신, 어떤 소프트웨어가 시드를 만들었을지를 물었고, 1990년대 C 라이브러리 PRNG를 가설로 세운 뒤, 각 시드를 훑으며 34가지 생성기와 출력 조합을 검사하는 스캐너를 작성했습니다. 최상위 비트가 0인 패턴을 찾아냈고, 잘린 출력에 격자 공격을 실행한 뒤 상태를 거꾸로 돌려 달력 날짜에 도달했죠.

이 작업 흐름이 무엇인지 보세요. 이것은 기억해 내기가 아닙니다. 훈련 문서에 정답이 있었을 리 없습니다. 답이 어디에도 존재하지 않았으니까요. 이것은 가설 생성, 도구 사용, 검증이 결합된 것으로, 실제 암호 분석 작업의 모습 그대로입니다. 모델은 실행 도중 스스로 상식 점검도 했습니다. 이게 시뮬레이션 테스트 환경은 아닌가? 이렇게 명백한 것이 25년 동안 발견되지 않았을 리가 있나? 32비트 시드에서 나온 160비트 일치가 우연을 배제하는가? 이런 자기 회의는 사람 분석가에게서 기대하는 바이고, 솔직히 일부 사람 분석가는 이걸 건너뜁니다. 이 사이트에서도 오랫동안 이 모델들이 실제로 무엇을 하는지에 대한 오해를 검증해 왔는데, 이번 사례는 깔끔한 데이터 포인트입니다. LLM은 이제 벤치마크뿐 아니라 실제 세계의 산출물을 대상으로 다단계 포렌식 추론을 수행할 수 있습니다.

실무자들의 타당한 반론은 출처에 관한 것입니다. 모델이 LCG 상태 복구나 LLL을 발명한 것은 아닙니다. 이름이 알려진 연구자와 익명의 연구자들이 수십 년간 발표한 암호 분석 위에 서 있고, 자신의 접근법을 누구의 논문이 형성했는지는 말해 줄 수 없습니다. 저는 이 점이 일부 사람들만큼 신경 쓰이지는 않습니다. 스캐너, 검증 코드, 재현 스크립트는 모두 공개되어 있고, 팀의 사람들이 질문을 지시하고 결과를 검증했습니다. 역할 분담을 정직하게 인정하자면, 기계는 지치지 않는 가설 탐색을 제공했고, 사람은 판단과 책임을 제공했습니다. 36,864달러의 현상금이 Internet Security Research Group에 돌아간 것은 이 문제를 매듭짓는 품격 있는 방식이었습니다.

이것이 보안 감사에 바꾸는 것

그렇다면 실무 엔지니어에게 이건 무엇을 의미할까요? 앞으로 감사에 접근하는 방식에서 몇 가지 구체적인 변화가 있을 것 같습니다. 첫째, 프로토콜이나 코드베이스의 모든 매직 상수를 자연의 사실이 아니라 포렌식 산출물로 취급하세요. 어떤 생성기가 만들었을지 묻고, '무작위다'라는 답을 받아들이기 전에 최상위 비트 편향, LCG 상관 관계가 있는 연속 워드, 타임스탬프로 그럴듯한 상태 복구 같은 구조적 지문을 확인하세요. 이를 위한 도구는 이제 아주 쉽게 구할 수 있습니다.

둘째, 상수를 공개한다면 생성기도 함께 공개하세요. 소스 코드, 정확한 입력, 정확한 환경까지요. 재현 가능한 레시피 없는 '검증 가능한 무작위'는 25년간의 의심과 유산에 걸린 현상금을 사는 것과 같습니다. 셋째, P-256은 계속 사용하세요. 이번 발견은 곡선에 대한 신뢰를 낮추기보다 오히려 높입니다. 그리고 타원 곡선의 실제 위협 모델은 1997년 워크스테이션의 시계가 아니라 양자 하드웨어입니다. 다만 남은 질문들은 정직하게 읽으세요. 설명되지 않은 기준점과 건너뛴 후보는 풀리지 않은 실마리이고, 성숙한 보안 작업이란 그것들을 장부에 계속 남겨 두는 일입니다.

가장 깊은 교훈은 제도적 기억에 관한 것입니다. Jerry Solinas는 결국 틀린 것으로 드러난 월급 인상 농담을 기억했습니다. 그의 말로는 기록 보관소는 아마 언약궤 근처 하드 드라이브에 있었을 거라고 합니다. 오늘날 우리가 진실을 아는 유일한 이유는 출력 자체가 자백할 만큼 충분한 구조를 간직하고 있었기 때문입니다. 여러분의 시스템도 지금 이 순간 모든 ID, 토큰, 상수 속에 스스로의 자백을 쓰고 있습니다. 그 자백이 여러분이 자랑스러워할 내용이 되도록 신경 쓰세요.