농담 섞인 해시가 아니라 타임스탬프였다 — NIST P-256 시드의 출처와, 풀린 것과 안 풀린 것

25년 묵은 시드의 출처가 밝혀졌다. 이것은 P-256에 대한 의심을 끝낸 증명인가, 아니면 의심의 위치를 옮긴 설명인가?

도입

2026년 10월 16일, Anthropic의 Frontier Red Team은 「Claude reveals ECDSA curve origins」라는 글을 올렸다. 해커뉴스에서는 1,000점 넘게 받았다. 글의 요지는 한 줄이다. NIST P-192, P-224, P-256, P-384, P-521 곡선의 계수를 정하는 데 쓰인 20바이트 「시드」는 어떤 문장의 해시가 아니라, C 라이브러리의 lrand48 난수 생성기를 Unix 타임스탬프로 초기화해 뽑은 출력이었다는 것이다.

이 시드들은 NSA가 출처 설명 없이 제공한 값이었고, 그래서 오랫동안 의심의 대상이었다. 예컨대 P-256의 시드는 C49D3608 86E70493 6A6678E1 139D26B7 819F7E90 이다. 왜 하필 이 값인가. 이 질문에 대해 지금까지 가장 그럴듯한 답은 고 Jerry Solinas 본인의 회고, 즉 「Bob과 Jerry에게 월급을 올려 달라」 같은 농담 문장을 해시했다는 이야기였다. 그 이야기는 틀린 것으로 드러났다.

발표문은 스스로 「암호학적 돌파나 새 공격이 아니다」라고 못박고, 오히려 곡선에 백도어가 없다는 확신을 높인다고 말한다. 이 글에서는 세 가지를 나눠서 본다. 정확히 무엇이 발견됐는가, 그것은 어떻게 검증되는가, 그리고 그 결과가 P-256에 대한 신뢰를 어디까지 바꾸는가. 마지막 질문에 대해 발표문과 해커뉴스의 반론은 같은 문장을 다르게 읽는다.

현상 분석 — 무엇이 발견됐나

먼저 배경부터 정리한다. Steve Weis가 2023년 9월에 정리한 글에 따르면, ECDSA는 1999년 ANSI X9.62에서 출발해 2000년 FIPS 186-2로 NIST에 채택되었다. 소수체 위의 곡선마다 「시드」를 공개하고, 그 해시값으로 곡선 계수를 정하는 방식이다. 당시 X9.62의 주 저자였던 Alfred Menezes는 Weis에게 「Jerry Solinas가 1997년 가을에 시드를 건네주었다」고 답했다. Weis는 2018년 NIST와 NSA에 정보공개청구도 넣었지만, NIST는 문서가 없다고 했고 NSA는 응답을 멈췄다고 적는다.

이후 2023년 10월, Filippo Valsorda가 이 시드의 「원문」을 찾는 사람에게 현상금을 걸었다. 기본 12,288달러, 수령자가 자선단체 기부를 택하면 세 배인 36,864달러다. 현상금 공지 역시 「영어 문장을 SHA-1로 해시했다」는 소문을 전제로, 패스워드 크래커들에게 참전을 호소하는 내용이었다. 현상금 페이지에는 대상이 된 다섯 개 NIST 소수 곡선 시드와, 대상 외인 ANSI 예제 곡선 및 이진 곡선 시드 목록이 함께 실려 있다.

Anthropic 발표문에 따르면 Anthropic 직원 몇 명도 「농담 문장」 단서를 쫓았다가 실패했다. 2026년 10월, 한 직원이 내부 연구 모델에게 그 단서를 주지 않은 채 시드가 어떻게 생성되었는지 알아낼 수 있느냐고 물었고, Claude는 30분이 안 되어 다섯 NIST 소수 곡선 시드의 출처를 찾았다고 한다.

발표문이 설명하는 경로는 이렇다.

  • 접근 방향의 전환. 문장을 추측하는 대신, 곡선을 만든 소프트웨어가 어떻게 동작했을지를 추정했다. 1990년대 C 라이브러리에 딸린 의사난수 생성기(PRNG)는 약해서 출력만 보고도 어떤 생성기인지 식별할 수 있다는 가정이다.
  • 스캐너. 공개된 시드를 1비트씩 밀어 가며, 인접한 조각이 1990년대 생성기의 연속 출력인지 시험했다. 생성기와 출력 슬라이스 조합 34개를 훑었다.
  • 최상위 비트의 패턴. 32비트 워드 다섯 개로 쓰면, 시드 열 개 중 네 개는 20개 워드 전부의 최상위 비트가 0이었다. 우연일 확률은 5,810분의 1이다. 48비트 상태 중 상위 31비트만 돌려주는 lrand48의 지문이다. 첫 워드에서 숨은 17비트를 전수 대입해 다음 네 워드가 맞는지 확인했다(발표문의 재현 코드를 보면 이 네 개는 이진 곡선 B-233, B-283, B-409, B-571이다).
  • 소수 곡선은 격자 문제로. 소수 곡선 시드는 같은 lrand48에서 나왔지만 출력마다 더 적은 비트만 남겼다. 잘린 선형합동생성기의 상태 복원은 교과서적인 격자 문제이고, LLL 기저 축약으로 풀었다. 결과는 NIST 다섯 개와 ANSI X9.62 다섯 개 모두 lrand48() >> 23 패턴이었다.
  • 시계까지 되감기. 선형합동생성기는 거꾸로도 쉽게 돌릴 수 있다. 상태를 되감아 srand48이 만드는 형태(하위 16비트가 0x330E)에 도달하게 하면 초기값이 나온다. 그 값은 1997년 5월부터 1998년 4월 사이의 Unix 타임스탬프였다.

예를 들어 P-256은 1997년 8월 16일 01:52:34(UTC)로 초기화한 생성기에서 20바이트씩 뽑은 1,842번째 후보다. P-192는 1997년 5월 18일의 139번째, P-224는 1998년 4월 3일의 7,026번째다.

부산물도 있다. 발표문은 1997년 5월에 만들어진 여섯 곡선(P-192와 ANSI 예제 곡선 다섯 개)의 기준점 G가 Arjen Lenstra의 FreeLIP 패키지 난수 생성기에서 나왔다는 것도 밝혔다. 작은 정수(P-192는 20000)로 초기화하고, 출력 일곱 개를 버린 뒤, 곡선 위의 x가 나올 때까지 후보를 만드는 방식이다. 발표문은 지금까지 설명된 NIST 기준점은 없었던 것으로 안다고 적는다.

심층 분석 — 주장과 검증을 분리하기

이 사건의 흥미로운 점은 「AI가 해냈다」는 주장과 「결과가 맞다」는 주장이 서로 독립적이라는 데 있다. 앞의 것은 Anthropic의 서술에만 의존한다. 뒤의 것은 누구나 확인할 수 있다.

누구나 돌릴 수 있는 검증

발표문은 CC0으로 재현 코드를 공개했다. 핵심은 아래 몇 줄이다.

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

필자는 이 함수로 다섯 NIST 소수 곡선 시드를 재생성해, Anthropic 글이 아니라 Valsorda의 현상금 페이지에 실린 시드 목록과 비교했다. 다섯 개 모두 일치했다. 대조로 타임스탬프를 1초 늘리거나 후보 번호를 하나 늘리면 다섯 개 모두 불일치했다. 즉 「주어진 타임스탬프와 번호에서 공개 시드가 정확히 나온다」는 사실은 실행으로 확인된다.

우연의 일치일 수 있는가

해커뉴스에서 가장 날카로운 회의론은 이것이다. 사용자 ezoe는 선형합동생성기는 1990년대에도 품질이 나쁘기로 유명했는데 왜 그걸 썼겠느냐, 타임스탬프들의 날짜는 왜 이렇게 띄엄띄엄하냐, 후보 번호 139와 7,026은 무슨 의미냐고 물으며, Claude가 우연히 20바이트 일치를 맞췄을 뿐이라고 의심했다(직접 인용은 아니고, 코멘트의 요지를 요약). 사용자 greatgib도 해시 충돌처럼 우연일 수 있지 않느냐고 물었다(직접 인용은 아니고, 코멘트의 요지를 요약).

이 의문은 정보량으로 답할 수 있다. 이하는 필자의 계산이다. 탐색 공간은 대략 32비트 타임스탬프와 수천 단위의 후보 번호, 그리고 몇십 가지 생성기·슬라이스 조합이다. 넉넉히 잡아도 2의 50제곱 남짓의 후보다. 그 안에서 특정 160비트 값이 우연히 나올 확률은 2의 마이너스 110제곱 수준이고, 그것이 열 번 독립적으로 일어나야 한다. 발표문 속 Claude의 추론 기록도 같은 논리를 쓴다. 「32비트 시드와 작은 인덱스에서 160비트 일치, 우연은 없다(10 × 160비트)」.

다만 발표문은 스스로 약한 증거와 강한 증거를 구분한다. srand48 형태의 상태는 65,536 스텝마다 한 번씩 나오므로, 되감다가 그 형태에 닿았다는 것만으로는 증거가 아니라고 명시한다. 강한 증거는 그렇게 얻은 값이 전부 1997~1998년의 날짜로 읽힌다는 점이다. 그리고 이것은 독립적인 기록과 맞물린다. Menezes는 Solinas가 1997년 가을에 시드를 건넸다고 증언했다. 무작위 32비트 값 열 개가 모두 그 1년 안에 떨어질 리는 없다.

반면 덜 단단한 부분도 있다. 이진 곡선 네 개의 초기값은 그대로 읽으면 1984년 2월인데, 두 배 하면 1998년 4월 17일, P-224 실행 2주 뒤가 된다. 발표문은 「프로그램이 시계를 반으로 나눴을 수 있다」고 쓰고, 재현 코드 주석에서도 「그 해석이 맞다면」이라는 단서를 단다. 출력 일치는 사실이지만, 「왜 반으로 나눴나」는 추정이다.

「사람의 기억」이 틀린 자리

더 조용하지만 중요한 사실이 있다. Solinas는 2014~2015년 Daniel Bernstein에게 보낸 메일에서 「SHA-1이었던 것 같다」, 「반복 해시가 아니라 카운터였던 것 같다」, 「Give Bob and Jerry a raise 같은 문장이었다」고 회고했다. Weis는 비슷한 이야기를 들은 사람을 여럿 찾아 교차 확인까지 했다. 그런데 계산은 해시 자체가 없었다고 말한다. 여러 사람의 일치하는 증언이 하나의 틀린 기억을 반복하고 있었던 셈이다. 현상금 페이지도 「사람의 기억은 악명 높게 불완전하다」는 단서를 달아 두었지만, 공격자들이 쓴 전략 자체는 그 기억을 전제로 짜여 있었다.

「Claude가 해냈다」는 부분

이 부분은 검증이 어렵다. 해커뉴스의 andyjohnson0는 Claude가 성공 방향으로 얼마나 유도되었는지 물었다(직접 인용은 아니고, 코멘트의 요지를 요약). 발표문은 「단서를 가리키지 않고」 물었다고만 적고 프롬프트 원문은 공개하지 않았다. 사용자 nullc는 9월에 친구의 Anthropic 크레딧으로 같은 문제를 맡겼는데 에이전트가 몇 시간 동안 아무것도 찾지 못했다고 적었다(직접 인용은 아니고, 코멘트의 요지를 요약). 이는 공개 모델과 「내부 연구 모델」의 차이일 수도, 프롬프트와 운용의 차이일 수도 있다. 어느 쪽인지는 공개된 자료로 판단할 수 없다. 또 발표문의 저자 명단에는 현상금의 계기가 된 연구를 한 Steve Weis와 현상금 기여자 명단에 있던 Amir Omidi가 포함되어 있다. 이 문제를 오래 알던 사람들이 운용했다는 사실은, 결과의 진위에는 영향이 없지만 「단서 없이」라는 표현의 무게를 읽을 때 고려할 만하다.

전망과 시사점 — P-256 신뢰는 어디로 옮겨 가나

발표문의 결론은 「곡선이 백도어 없이 선택되었다는 확신이 커진다」이다. 해커뉴스에서 가장 많이 반박된 문장도 이것이었다.

사용자 adastra22는 이것이 오히려 약한 곡선이 정확히 어떤 모습일지를 보여 준다고 반박했다. 비밀 공격에 취약한 곡선이 천 개나 백만 개 중 하나라면, 타임스탬프나 반복 횟수를 바꿔 가며 찾은 뒤 그럴듯한 부인 가능성을 남길 수 있다는 것이다. 현대 설계가 제곱근 2 같은 자유도 없는 상수를 쓰는 이유가 그것이라고 덧붙였다(직접 인용은 아니고, 코멘트의 요지를 요약). 사용자 fidotron은 생성 방법은 확인되었지만 선택에 대해서는 아무것도 말해 주지 않으며, 버려진 후보는 볼 수 없다고 지적했다(직접 인용은 아니고, 코멘트의 요지를 요약).

흥미롭게도 이 반론의 재료는 발표문 자체에 있다. P-256의 공개 시드는 1,842번째 후보지만, 같은 실행의 876번째 후보도 같은 방식의 조건을 만족하는 소수 위수 곡선을 준다. P-224 실행은 그런 곡선 세 개를, ANSI 예제 곡선 실행 둘은 일곱 개를 더 건너뛰었다. 발표문은 그 기준을 모른다고 인정하고, 이론적으로는 타임스탬프를 바꿔 가며 특정 성질의 곡선을 고를 수 있었다고도 인정한다. 그러면서도 건너뛴 후보가 적으므로 약한 곡선이 흔하고 찾기 쉬워야만 성립하는 시나리오이며 그럴 법하지 않다고 본다.

이 논쟁을 정리하는 데는 SafeCurves의 「강직성(rigidity)」 분류가 쓸모 있다. SafeCurves는 곡선 생성 과정을 네 등급으로 나눈다. 모든 선택이 설명되는 「fully rigid」, 설명되지 않은 부분이 적은 「somewhat rigid」, 설명되지 않은 큰 입력이 있어 생성자가 넓은 공간에서 고를 수 있는 「manipulatable」, 그리고 역산까지 쉬운 「trivially manipulatable」이다. SafeCurves는 NIST P-256을 「설명되지 않은 시드를 해시해 계수를 생성」한다는 이유로 manipulatable로 분류한다. 반면 Curve25519는 소수 2의 255제곱 빼기 19를 고른 이유부터 계수 A=486662가 조건을 만족하는 가장 작은 양의 정수라는 점까지 각 선택에 근거가 적혀 있어 fully rigid로 분류된다.

이번 발견이 바꾼 것은 「설명되지 않은 큰 입력」의 성격이다. 이전에는 160비트 시드가 통째로 미지였다. 이제 그 시드는 32비트 남짓의 타임스탬프와 몇천 단위의 후보 번호로 환원된다. 이는 분명 자유도를 줄인다. 그러나 「누가 몇 번 돌렸는가」는 여전히 설명되지 않는다. 발표문의 말처럼 숫자만으로는 실행이 몇 번 있었는지 알 수 없다. SafeCurves의 기준으로 보면, P-256이 manipulatable에서 벗어났다고 말하기는 어렵다. 그러나 「NSA가 160비트 공간에서 마음대로 골랐을 수 있다」는 가장 강한 의심은 「1997년 몇 달 동안의 실행 중에서 골랐을 수 있다」로 줄어들었다.

여기서 반대 방향의 논거도 함께 읽어야 한다. Valsorda는 현상금 공지에서 Koblitz와 Menezes의 논증을 인용했다. 시드를 완전히 통제했더라도, NSA는 25년간 학계와 업계가 아무도 발견하지 못할 만큼 큰 약한 곡선 군을 알고 있어야 했다는 것이다. 그는 또 강직성 자체가 과대평가되어 있으며, 객관적으로 최선인 선택이란 없다고 각주에 적었다. 이 관점에서 이번 결과는 「원래 믿을 만했던 곡선에 남은 FUD를 걷어낸 것」이다. 발표문이 「대부분의 연구자는 이미 곡선을 신뢰했다」고 쓴 것도 같은 입장이다.

실무적 함의는 그래서 크지 않다. 발표문 스스로 「해야 할 조치는 없다」고 적었다. 남은 미해결 과제도 명시되어 있다. 이진 곡선 B-163의 시드는 어떤 방법에도 맞지 않는다. P-224, P-256, P-384, P-521의 기준점과 NIST 이진 곡선의 기준점이 어떻게 정해졌는지도 모른다. 해커뉴스의 teddyh는 B-163은 같은 방식으로 만들어졌지만 공개 과정에서 숫자 하나가 잘못 옮겨졌을 가능성을 제시했다(직접 인용은 아니고, 코멘트의 요지를 요약). 검증된 바는 없다.

결론

이번 발표에서 확실한 것은 하나다. 공개된 재현 코드는 실제로 돌고, 1997~1998년의 타임스탬프와 후보 번호에서 다섯 NIST 소수 곡선 시드가 비트 단위로 정확히 나온다. 필자도 현상금 페이지의 독립된 시드 목록과 대조해 확인했고, 1초만 어긋나도 일치하지 않음을 확인했다. 우연의 일치일 가능성은 실질적으로 없다. 「농담 문장의 해시」라는 25년간의 정설은 틀렸다.

확실하지 않은 것도 분명히 남는다. 이진 곡선의 「반으로 나눈 시계」는 해석이다. 건너뛴 후보들의 선택 기준은 모른다. 실행이 몇 번 있었는지도 모른다. 「단서 없이 30분」이라는 서술은 Anthropic 측 설명이며 외부에서 재현된 것은 아니다.

그러면 P-256은 믿을 만해졌는가. 정확히 말하면, 의심의 위치가 옮겨 갔다. 「출처를 알 수 없는 160비트」에서 「출처는 알지만 선택 기준을 알 수 없는 몇 개의 후보」로. 이 이동은 의미 있는 진전이지만, 처음부터 모든 선택의 근거를 적어 둔 Curve25519 같은 설계와 같은 자리에 서게 해 주지는 않는다. 그 차이는 수학이 아니라 기록의 차이다. 1997년에 누군가 「타임스탬프는 이렇고, 이 기준으로 골랐다」는 한 줄을 남겼다면 이 25년은 필요 없었다.

당신의 팀이 오늘 어떤 상수나 파라미터를 「적당히」 고른다면, 그 이유를 어디에 적어 두고 있는가.

출처: