루위(鹭羽)凹非寺 보도
양자웨이(量子位) | 위챗 공식계정 QbitAI
오늘 아침, AI 업계가 또 다시 발끈했다。。。
다른 이유가 아니라, AI의 이번 문제 풀이 붐이 암호학계의 20년 묵은 옛날 장부까지 넘어가 뒤집은 것이다.
전원 대탈출, 이번 차례는Claude——
방금 Anthropic의 공개에 따르면, Claude는30분도 채 걸리지 않고5개의 NIST 표준 타원곡선의 시드 생성 방식을 규명했다.
이 업계에서 20년 넘게 쓰여 온 숫자들은 한때 암호학 표준에 기재되었지만, 처음에 어떻게 선택되었는지는 아무도 설명하지 못했다.
사람들은 심지어 당사자까지 찾아냈고, 단서는“Bob과 Jerry에게 승진급여를 주라”는 패스프레이즈 해시 연산을 가리켰다.
그런데 극적인 결과가 나왔다. Claude의 말: 완전히 틀렸다고!
진짜 답은시간에서 나왔다. 90년대 컴퓨터 시계였다.
그리고 이 미스터리는 현상금 발기인의 독립 검증까지 마쳤다.
30분 만에 풀어낸 암호학 미스터리
일은 '신분 확인'에 쓰이는 기술에서 시작됐다.
ECDSA는 전칭 타원곡선 디지털 서명 알고리즘이다.
이 알고리즘은 수신 측이 한 데이터가 주장하는 서명자가 서명한 것인지, 그리고 서명 후 수정되지 않았는지 확인할 수 있게 해준다. 2000년, 미국 국립표준기술연구소(NIST)는 이를 FIPS 186-2 디지털 서명 표준에 채택했다.
이 알고리즘을 사용하기 전에 먼저 곡선 P-192, P-224, P-256, P-384, P-521을 포함한 몇 가지 공용 수학 파라미터를 선택해야 한다.
논란은 바로 이 곡선들의시드에서 나왔다.
시드는 곡선 파라미터를 생성하는 시작 재료로 이해할 수 있다: 시드를 받아 표준에 규정된 절차대로 연산하면 뒤의 파라미터가 맞아떨어지는지 검증할 수 있다.
그런데왜 하필이면 이 시드였는지는아무도 모른다.
당시 시드를 제공했던 Jerry Solinas조차 기억이 흐릿해서, 그들이 아마도 임금 인상을 놀리는 농담 문구를 숫자로 변환한 뒤 카운터를 더했다는 것만 대략 기억하고 있을 뿐이다.
그래서 이 20여 년 동안 모두가 이 방향으로 추측해 왔고, 암호학 엔지니어 Filippo Valsorda는 아예현상 공고를 내고 이 다섯 개 시드의 원형을 찾아보라고 대놓고 사람들을 초청하기도 했다.
결과는 모두 무소득으로 끝났고, 그러다Claude가 등장했다.
Anthropic의 설명에 따르면, 직원이 이 문제를 내부 연구 모델에 넘길 때 임금 인상 농담 문구라는 단서는 알려주지 않았다.
그러자 Claude는 스스로 이 숫자들이90년대 C 언어 라이브러리의 의사난수 생성기에서 왔을 것이라고 추측했다.
이런 프로그램이 생성하는 숫자들은 겉보기엔 뒤죽박죽이지만 그 이면에는 고정된 규칙이 숨어 있기 때문이다. 규칙만 알아내면 생성 과정을 역으로 추적할 기회가 생긴다.
이어 Claude는스캔 프로그램을 작성해 공개된 시드의 이진수를 한 자리씩 옮겨가며 검사했고, 34가지 생성기와 출력 잘라내기 방식의 조합을 테스트했다.
그 결과, 네 개의 시드를 각각 다섯 개의 32비트 정수로 나눈 뒤 이 20개 정수의 최상위 비트를 확인하니전부 0이었다。
사건은 해결됐다. 범인은 아마도lrand48 난수 생성기。
lrand48은 내부에 48비트 정수를 저장하고 있으며, 호출될 때마다 이 정수에 고정 상수를 곱하고 다른 상수를 더한 뒤, 결과의 하위 48비트만 남겨 다음 상태로 사용한다.
그러나 출력 결과는 그중 상위 31비트만 나오며, 32비트에 넣으면 나머지는 0으로 채울 수밖에 없다.
기계를 찾은 후 Claude는 다시LLL 격자 기약 알고리즘을 사용해 종자가 잘린 상태를 복원했다.
다음으로 남은 문제는 하나뿐이다. 처음에는 어떻게 시작되었을까?
초기화를 담당하는 함수는 srand48이며, 이 함수는 입력값을 48비트 상태의 상위 32비트에 넣고 하위 16비트를 0x330E로 고정한 뒤, 점화 관계를 따라 거슬러 올라가 계산한다. 목표는Unix 타임스탬프。
이다. 이러한 초기화 입력들이 집중적으로 분포한 구간은1997년 5월부터 1998년 4월。
이었다. 즉,어느 순간의 시간을 정수로 바꾸어생성기에 넘기고, 정해진 방식으로 숫자를 추출하면 표준의 종자를 다시 얻을 수 있다.
P-256을 예로 들면, 대응하는 초기화 시각은 1997년 8월 16일 UTC 01:52:34이다.
이 시각부터 생성기를 실행하여 1842번째 후보 그룹을 취하면, 얻어지는 것이 바로 C49D로 시작하는 그 종자이다. 나머지 네 그룹도 하나하나 일치했다.
물론 A사는 이번 결과가 아직 모든 역사적 공백을 메운 것은 아니라고 밝혔다.
연구자들은 당시 프로그램이 조건에 부합해 보이는 일부 후보 곡선을 건너뛰었음을 발견했는데, 그 이유는 여전히 불명확하다. B-163의 종자, 그리고 일부 곡선의 기저점 생성 방식도 아직 설명되지 않았다.
그러나 새로운 결과는 이러한 곡선에 잠재적 보안 취약점이 전혀 존재하지 않는다는 것을 의미하며, 안심하고 사용할 수 있다.
참고 링크:
[1]
https://www.anthropic.com/research/ecdsa-curve-origins
[2]
https://x.com/sweis/status/2111165738836717980
[3]
https://words.filippo.io/seeds-bounty/