Claude, NIST 타원곡선 시드 출처 30분 만에 규명

Anthropic은 10월 16일 자사 모델 Claude가 NIST 타원곡선 P-192, P-224, P-256, P-384, P-521의 시드가 어떻게 만들어졌는지 찾아냈다고 발표했다. 한 직원이 내부 연구 모델에게 단서를 주지 않고 시드 생성 방식을 알아낼 수 있는지 물었고, Claude는 30분이 채 걸리지 않아 답을 냈다. 시드는 해시 알고리즘의 결과가 아니라 C 라이브러리의 lrand48 난수 생성기를 유닉스 타임스탬프로 초기화해 얻은 출력이었다.

Anthropic은 이번 결과가 암호 해독이나 새 공격, ECDSA 곡선의 약점이 아니라고 밝혔다. 오히려 곡선이 백도어 없이 고른 것이라는 확신이 커졌다는 입장이다. 독자가 해야 할 조치도 없으며, 대부분의 연구자는 이미 이 곡선을 신뢰하고 있었다고 Anthropic은 적었다.

수십 년 묵은 의문

ECDSA는 가장 널리 쓰이는 타원곡선 암호 표준으로, 2000년 NIST가 FIPS 186-2 디지털 서명 표준에 포함해 채택했다. 소수체와 이진체 위의 곡선에는 "시드" 매개변수가 공개되어 있고, 이 시드의 해시값이 곡선의 계수 b를 정의하는 데 쓰인다. 시드는 NSA가 설명이나 근거 없이 제공한 것이다. 예컨대 P-256의 시드는 C49D3608 86E70493 6A6678E1 139D26B7 819F7E90이다.

Neal Koblitz와 Alfred Menezes가 이 논란을 정리한 글 "A Riddle Wrapped in an Enigma"를 썼고, 아마추어 조사와 현상금도 이어졌다. 가장 유력한 이야기는 NSA의 오랜 직원 Jerry Solinas가 우스꽝스러운 문구의 해시로 시드를 만들었다는 것이었다. Solinas는 2015년 해시를 여러 번 돌린 것이 아니라 카운터를 쓴 것 같다고 했다. 문구는 "Give Bob and Jerry a raise"나 "Bob and Jerry rule" 정도였고, 코드를 실제로 쓴 사람은 Bob Reiter인데 그도 세부를 기억하지 못한다고 했다. 오래전 기록은 찾지 못했다. Solinas는 2023년에 숨졌고 당시 동료들도 응답하지 않아 의문이 남아 있었다.

Claude가 찾은 방법

Anthropic 직원 여럿이 해시 문구 단서를 따라 시드를 쫓았으나 실패했고, 그 단서는 틀린 것으로 드러났다. Claude는 문구를 찾는 대신 곡선을 만든 소프트웨어가 어떻게 동작했을지 추정했다. 1990년대 C 라이브러리의 의사난수 생성기(PRNG)는 출력을 알아볼 수 있을 만큼 약하다는 점에 착안했다.

Claude는 공개된 시드를 한 비트씩 밀며 인접한 조각이 1990년대식 생성기의 연속 출력인지 검사하는 스캐너를 짰다. 생성기와 출력 조각의 34가지 조합을 훑던 중 일부 시드의 최상위 비트가 모두 0인 패턴을 발견했다. 32비트 단어 다섯 개로 쓰면 시드 열 개 중 이진체 시드 네 개의 단어 20개 모두에서 최상위 비트가 0이었고, 우연히 일어날 확률은 1/5810이다. 48비트 상태 중 상위 31비트만 내놓는 선형 합동 생성기 lrand48의 특징이었다. Claude는 첫 단어에서 숨은 17비트의 2¹⁷가지 값을 모두 시도해 다음 네 단어가 이어지는지 확인했고, 해당 시드 네 개에서 모두 통했다.

소수체 곡선 시드는 같은 lrand48을 쓰되 출력마다 남기는 비트가 더 적었다. 잘린 선형 합동 생성기의 상태를 복원하는 일은 교과서적인 격자 문제여서 Lenstra–Lenstra–Lovász(LLL) 기저 축소 알고리즘으로 풀었다. 어떤 상태 비트가 드러나는지 몰랐던 Claude는 모든 구간에 풀이기를 돌렸다. NIST 소수체 곡선 시드 다섯 개와 ANSI X9.62 표준의 시드 다섯 개가 모두 lrand48() >> 23 패턴이었다. 복원한 48비트 상태 하나가 시드의 160비트를 전부 재생성했는데, 우연으로는 일어나지 않는 일이라고 Anthropic은 설명했다.

이 생성기는 앞뒤 어느 방향으로도 쉽게 돌릴 수 있다. Claude는 시드마다 상태를 거꾸로 되돌려 srand48이 초기화했을 형태, 즉 하위 16비트가 0x330E인 상태에 닿을 때까지 갔다. 이런 형태는 65,536 걸음마다 한 번 나오므로 그 자체는 증거가 아니다. 그러나 소수체 시드 열 개의 초기화 값은 모두 1997년 5월부터 1998년 4월 사이 날짜의 유닉스 타임스탬프였다. 이진체 시드 네 개(B-233, B-283, B-409, B-571)의 초기화 값은 1984년 2월로 읽히는데, 값을 두 배 하면 P-224 실행 2주 뒤인 1998년 4월 17일이 된다. 프로그램이 시계 값을 절반으로 나눴을 수 있다고 Anthropic은 적었다.

알고리즘은 유닉스 타임스탬프 t로 초기화한 난수 생성기에서 매 반복마다 20바이트를 뽑아 후보 시드로 삼는다. 첫 20바이트가 후보 1, 다음 20바이트가 후보 2다. P-256은 1842번째 반복에서 표준 시드가 나왔다. 이진체 곡선 B-233, B-283, B-409, B-571의 시드는 타임스탬프를 절반으로 나눴다는 해석이 맞을 경우 1998년 4월 17일 15시 24분부터 32분 사이(UTC)의 시각으로 재현됐다.

Anthropic이 공개한 Claude의 당시 내부 추론에는 스스로 시험 환경이 아닌지 의심하는 대목이 있다. 최상위 비트 20개가 모두 0일 확률이 약 1e-6이라는 점, 32비트 시드와 작은 인덱스로 160비트가 일치한다는 점을 들어 실제 발견이라고 판단했다.

기준점 일부도 규명

각 곡선에는 모든 ECDSA 공개키가 배수로 삼는 기준점 G가 있고, 시드로는 G가 정해지지 않는다. Claude는 시드를 검증하다 일부 기준점의 출처도 찾았다. 1997년 5월에 만든 여섯 곡선(P-192와 ANSI X9.62 예시 곡선 prime192v2, prime192v3, prime239v1~v3)의 기준점은 Arjen Lenstra의 큰 정수 연산 패키지 FreeLIP의 난수 생성기에서 나왔다. Victor Shoup의 NTL 라이브러리 초기 버전도 같은 코드를 담고 있었다.

• 작은 정수로 생성기를 초기화한다.
• 출력 일곱 개를 버린다.
• 26비트 출력을 p로 나눈 나머지로 x좌표 후보를 만든다.
• x가 곡선 위의 점이 될 때까지 3단계를 반복한다.

생성기 시드는 P-192가 20000, prime239v1~v3가 20420, 20507, 20509, prime192v2와 v3가 20512, 20517이다. Anthropic이 아는 한 NIST 기준점의 출처가 설명된 것은 이번이 처음이며, 그 대상은 P-192 등 일부 기준점뿐이다.

남은 의문과 현상금

모든 20바이트 후보가 쓸 만한 곡선을 만드는 것은 아닌데, 일부 쓸 만한 곡선이 건너뛰어진 흔적이 있다. P-256은 공개 시드가 후보 1842번이지만 같은 실행의 876번도 소수 위수에 같은 방식으로 정한 매개변수를 갖춘 곡선을 준다. P-224 실행은 이런 곡선 세 개를, ANSI X9.62 예시 곡선을 만든 두 실행은 일곱 개를 더 지나쳤다. 어떤 기준이 쓰였는지, 의도하지 않은 결과인지는 알 수 없다고 Anthropic은 밝혔다.

Anthropic은 건너뛴 후보 수가 적다는 점을 근거로, 약화된 곡선을 골랐다고 보기는 어렵다고 판단했다. 그랬다면 약한 곡선이 흔하고 찾기 쉽다는 뜻이 되기 때문이다. 다만 타임스탬프를 바꿔 가며 특정 성질을 가진 곡선을 찾았을 가능성은 이론상 남는다. 그렇더라도 시드가 무해하게 생성됐다는 증거로 타임스탬프를 공개하려는 경우에나 그럴 이유가 있으며, 숫자만으로는 실행이 몇 번이었는지 알 수 없다고 했다.

이진체 시드 다섯 번째인 B-163은 Claude가 시도한 어떤 방법으로도 설명되지 않았다. P-224, P-256, P-384, P-521과 NIST 이진체 곡선의 기준점 생성 방식도 알려지지 않았다. 시드를 찾는 이에게 걸린 현상금 36,864달러는 Internet Security Research Group에 기부한다.

연구는 John Wood, Henry de Valence, Ava Howell, Zack Voase, Lucy Sweet, Amir Omidi, Paul Crowley, Iain McGinniss, Nicholas Carlini, Steve Weis가 수행했다. Anthropic은 고인이 된 Solinas에게 감사를 표했고, 현상금을 조직한 Filippo Valsorda에게도 사의를 밝혔다. 시드와 일부 기준점을 재현하는 코드는 CC0 1.0으로 공개됐다.