Claude가 추적한 ECDSA 공개 매개변수의 기원

배경과 문제

ECDSA는 타원곡선 위의 계산을 이용하는 전자서명 방식이다. NIST는 2000년 표준에 여러 곡선을 포함했고, 공개된 seed를 해시해 곡선의 계수 b를 정했다. 문제는 NSA가 제공한 seed 자체를 어떻게 골랐는지 설명하지 않았다는 것이다. P-256의 seed처럼 긴 16진수는 누구나 볼 수 있었지만, 그 숫자를 선택한 과정은 알 수 없었다.

연구자들이 걱정한 것은 공개된 숫자에 비밀스러운 선택 기준이 있었을 가능성이다. 이전 조사와 현상금도 이를 추적했다. 오래된 증언은 직원 이름을 넣은 유머 문구를 해시했을 것이라는 단서를 남겼지만, 당시 기록과 기억이 부족했다. 이 글의 발견은 곡선을 새로 만드는 것이 아니라 이미 사용하던 곡선의 생성 이력을 되찾는 일이다.

기존 접근의 한계

Anthropic 직원들도 처음에는 소문의 문구를 바꾸어 해시하는 접근을 시도했지만 실패했다. Claude에 문제를 맡길 때는 그 단서를 알려주지 않았다. 모델은 문구 대신 당시 소프트웨어가 사용했을 난수 생성기를 의심했다. 가설을 바꾸자 같은 공개 숫자에서 살펴볼 특징도 달라졌다.

여기서 곡선 seed와 난수 생성기의 초기값은 서로 다른 값이다. 곡선 seed는 160비트 공개 출력이고, 생성기의 초기값은 그 출력을 만들기 위해 넣은 시간값이었다. 출력은 임의의 숫자처럼 보여도 오래된 생성기의 구조적 흔적을 남길 수 있다. 따라서 메타데이터가 없다는 사실이 생성 경위를 영원히 복원할 수 없다는 뜻은 아니다.

연구방법을 단계별로

Claude는 소문에 기반한 문구 검색 대신, 1990년대 C 라이브러리에 포함된 의사난수 생성기(PRNG)를 사용했을 것이라고 가정했다. 당시의 PRNG는 출력이 충분히 약해서 그 패턴을 인식할 수 있고, 인식에 성공하면 어떤 생성기가 사용되었는지와 초기화 상태까지 복구할 수 있다. Claude는 각 공개 seed를 한 비트씩 이동하며 인접한 청크가 1990년대 생성기의 연속 출력인지 검사하는 스캐너를 작성했고, 34가지 생성기와 출력 슬라이스 조합을 탐색했다.

스캐너는 생성기와 출력 구간의 조합 34가지를 검사했다. 그중 일부 seed를 32비트 단위로 나누면 맨 위 비트가 계속 0이라는 패턴이 보였다. 이는 48비트 내부 상태에서 상위 31비트만 돌려주는 lrand48의 특징과 맞았다. 연구팀의 설명에 따르면 모델은 출력에서 보이지 않는 17비트의 가능한 값을 대조하고 후속 출력이 맞는지 검사해 네 seed의 상태를 복원했다.

소수체 곡선의 seed는 같은 lrand48 생성기에서 나왔지만 각 출력의 더 적은 비트만 유지했다. Claude는 이 비트들로부터 PRNG의 내부 상태를 복구해야 했는데, 잘린 선형합동생성기의 상태 복구는 Lenstra–Lenstra–Lovász(LLL) 격자 축소 알고리즘으로 푸는 전형적인 격자 문제다. Claude는 seed가 상태의 어떤 비트를 보여주는지 몰랐기 때문에 모든 윈도우에 대해 솔버를 실행했다. 그 결과 NIST 소수체 곡선 5개와 ANSI X9.62 표준의 5개 seed 모두 'lrand48() >> 23'이라는 동일한 패턴을 보였고, 복구된 48비트 상태가 각 seed의 160비트 전체를 재생성했다. 저자들은 긴 출력 전체의 일치를 생성 경위를 뒷받침하는 강한 근거로 본다.

결과와 숫자의 의미

선형합동생성기는 역방향으로도 쉽게 실행되므로, Claude는 각 seed에 대해 상태를 거슬러 올라가 srand48로 초기화되었을 형태, 즉 하위 16비트가 0x330E인 상태에 도달할 때까지 되감았다. 이 형태의 내부 상태는 65,536걸음마다 한 번씩 나오므로 그 자체로는 증거가 되지 않는다. 그러나 10개의 소수체 곡선 seed 모두에서 srand48 초기화 값이 1997년 5월부터 1998년 4월 사이의 Unix 타임스탬프로 해석되었다. 이는 약한 PRNG를 Unix 타임스탬프로 시드했음을 강력히 시사한다.

이진체 곡선 네 개의 초기값은 그대로 읽으면 1984년 2월이지만, 두 배로 하면 1998년 4월 17일이 된다. 그래서 당시 코드가 시간값을 반으로 나누었을 가능성을 제시한다. 이는 저자의 해석이다. 소수체 예인 P-256은 1997년 8월 16일 01:52:34 UTC를 초기값으로 삼았을 때 1842번째 후보에서 공개 seed와 일치한다.

seed와 별개로, 공개키 계산의 출발점인 기준점도 추적했다. P-192와 ANSI 예제 다섯 곡선에서는 FreeLIP의 난수 생성기를 작은 정수로 초기화하고 앞의 출력 일곱 개를 버린 뒤 후보 좌표를 만들면 공개된 기준점의 x좌표가 재현됐다. P-192의 초기 정수는 20000이었다. 모든 곡선의 기준점을 설명한 것은 아니며, 이는 seed 복원과 구분되는 추가 발견이다.

구체적인 예시

P-256을 예로 들면, 시간값 t로 lrand48의 내부 상태를 초기화하고 출력을 차례로 만든다. 소수체 곡선에서는 lrand48() >> 23을 적용한다. 즉 31비트 출력의 하위 23비트를 버리고 상위 8비트를 취한다. 이렇게 얻은 20바이트를 후보 하나로 묶고 다음 20바이트를 다음 후보로 묶는다. 1842번째 묶음이 표준에 적힌 160비트 seed와 일치한다. 재현 가능한 것은 이 공개 숫자의 생성 과정이며, 사용자의 비밀키가 아니다.

기준점 복원에서도 처음 나온 숫자가 곧 답은 아니다. 생성기의 출력 조각을 모아 x좌표 후보를 만들고, 실제 곡선 위의 점이 될 수 있는지 검사하며 반복한다. P-192는 두 번째 시도에서 공개된 x좌표와 맞았다. 원문은 코드와 출력을 함께 제공해 이런 주장을 확인할 수 있게 한다. 이번 해설은 그 자료를 대조했으며 코드를 독립 실행해 재현했다고 주장하지 않는다.

한계와 오해하기 쉬운 점

약한 난수 생성기를 썼다는 사실을 곧바로 ECDSA 취약점으로 해석하면 안 된다. 여기서 복원한 값은 원래 공개된 곡선 매개변수다. 저자들은 단순한 생성법이 드러나 의도적으로 약한 곡선을 숨겨 골랐다는 의혹이 줄었다고 해석한다. 그러나 생성 경위에 대한 신뢰 증가와 암호 전체의 안전성 증명은 다른 주장이다.

남은 의문도 구체적이다. P-256의 1842번째 후보보다 앞선 876번째 후보도 적합한 곡선을 만들 수 있는데 건너뛴 이유를 모른다. 다른 실행에서도 적합한 후보를 몇 개 건너뛰었다. 시도한 시간값의 총수나 선택 기준은 숫자만으로 알 수 없다. 저자들은 건너뛴 후보가 적다는 점에서 약한 곡선을 의도적으로 골랐을 가능성을 낮게 보지만, 그 가능성을 수학적으로 배제한 것은 아니다.

또한 다섯 번째 이진체 seed인 B-163은 Claude가 시도한 어떤 것과도 맞지 않아 여전히 설명되지 않았다. P-224, P-256, P-384, P-521의 기준점과 NIST 이진 곡선들의 기준점이 어떻게 생성되었는지도 밝혀지지 않았다. 따라서 이 연구는 완전한 해답이 아니라, 오랜 미스터리의 상당 부분을 해소한 중간 단계로 보아야 한다. 일반 사용자가 키를 변경하거나 다른 조치를 취할 필요는 없다고 저자들은 명시한다.

실제로 어떻게 활용할까

이 사례는 공개 매개변수의 생성 과정도 재현할 수 있게 남기는 것이 신뢰에 도움이 된다는 점을 보여준다. 수십 년 뒤라도 코드와 출력이 연결되면 막연한 의심을 검증 가능한 질문으로 바꿀 수 있다. 일반 사용자에게 키 변경 등 조치가 필요하다는 발견은 아니며, 원문도 별도 조치를 요구하지 않는다.

또한 이 연구는 오래된 암호학적 미스터리를 해결하는 데 AI 모델이 어떻게 기여할 수 있는지 보여주는 사례다. Claude는 기존의 실패한 접근법을 반복하지 않고, 생성 소프트웨어의 동작을 예측하고 약한 PRNG의 통계적 특징을 식별하는 새로운 각도를 취했다. 이는 암호학적 분석에서 가설 전환과 패턴 탐색의 중요성을 보여주며, 유사한 미해결 문제에 대한 방법론적 참고가 될 수 있다. 다만 이는 특정 발견 사례이며 일반적인 추론 속도나 성공률의 벤치마크로 해석해서는 안 된다.