요약:
10월 16일, Anthropic은 특별한 연구 결과를 발표했습니다. 한 직원이 Claude에게 20년 넘게 암호학 커뮤니티를 괴롭혔던 문제를 내부 연구 모델에 건네주었습니다. 핵심 단서를 제공하지 않은 채 Claude는 5개의 NIST 타원 곡선 시드가 어떻게 생성되었는지 추적하는 데 30분도 채 걸리지 않았습니다.
시드는 C 라이브러리의 오래된 의사 난수 생성기 lrand48에서 나온 것으로 밝혀졌습니다. 생성기의 초기 상태는 Unix 타임스탬프에 의해 결정됩니다.
이번 발견은 ECDSA를 손상시키지 않으며 새로운 공격 방법을 도입하지도 않습니다. Anthropic은 이것이 상관 곡선에 대한 인위적인 백도어 가능성을 더욱 감소시킨다고 믿습니다.
20년 넘게 암호화 커뮤니티를 괴롭혀온 일련의 숫자
ECDSA는 널리 사용되는 타원 곡선 디지털 서명 알고리즘입니다.
2000년에 NIST는 P-192, P-224, P-256, P-384 및 P-521을 포함하여 FIPS 186-2 표준의 다양한 보안 수준에 대한 여러 표준 곡선을 나열했습니다.
이 곡선에는 '시드'라는 매개변수 세트가 함께 제공됩니다. 표준의 생성 프로세스에 따라 시드의 해시 값이 곡선 계수를 결정하는 데 참여합니다.
문제는 이들 종자가 국가보위부에서 제공받은 것인데, 공개문서에는 원산지나 선정 과정에 대한 설명이 없다는 점이다. 외부 세계에서는 설계자가 수많은 후보 곡선을 선별하고 일부 숨겨진 속성이 있는 매개변수를 선택했는지 여부에 대해 오랫동안 우려해 왔습니다.
2015년 관련 작업에 참여했던 NSA 암호해독자 제리 솔리나스(Jerry Solinas)는 "밥과 제리에게 급여 인상을 줘" 같은 농담 비밀번호에서 시드가 나왔을 수도 있지만 구체적인 내용은 기억나지 않았고 오래전 보관된 파일도 찾을 수 없었다고 회고했다. 솔리나스는 2023년에 사망했고, 최종적으로 단서는 확인되지 않았습니다.
클로드는 씨앗의 출처를 찾았습니다
많은 Anthropic 직원들은 이전에 "씨앗"을 찾기 위해 "유머러스한 암호"를 따라갔으나 나중에 그 단서가 잘못되었음을 발견했습니다.
지난 10월, 한 직원은 이러한 '씨앗'이 어떻게 생성되었는지 알아보기 위해 내부 연구 모델을 요청했습니다. 이번에는 모델에게 이전 비밀번호 단서를 공개하지 않았다.
30분도 채 안 되어 Claude는 NIST의 P-192, P-224, P-256, P-384 및 P-521 종자의 출처를 찾았습니다.
이러한 시드는 해시 알고리즘에서 나오지 않지만 Unix 타임스탬프를 시드 값으로 초기화하는 C 라이브러리의 lrand48 난수 생성기에 의해 생성됩니다.
특정 알고리즘은 Unix 타임스탬프 t를 사용하여 난수 생성기를 초기화하고 n 특정 횟수만큼 실행합니다. 각 반복에서는 20바이트를 후보 시드로 추출합니다.
처음 20바이트는 첫 번째 후보 시드이고 다음 20바이트는 두 번째 후보 시드입니다. P-256을 예로 들면 생성기는 1842번째 실행까지 최종적으로 표준에 기록된 시드를 출력하지 않습니다.
클로드는 그를 어떻게 찾았나요?
루머로 알려진 비밀번호에 대한 검색 결과는 나오지 않았습니다. Claude는 관점을 바꾸고 곡선을 생성한 소프트웨어가 어떻게 작동했을지 추측하기 시작했습니다.
Claude는 이 소프트웨어가 1990년대 C 언어 라이브러리와 함께 제공된 의사 난수 생성기를 사용했다고 추측했습니다. 이러한 초기 의사 난수 생성기는 보안이 취약했으며 출력에는 일반적으로 식별 가능한 특성이 있었습니다.
출력 특성이 식별되면 소프트웨어가 어떤 생성기를 사용했는지 확인하고 초기 상태를 추가로 복원할 수 있습니다.
Claude는 각 공개 시드를 조금씩 이동하여 인접한 데이터 덩어리가 1990년대의 난수 생성기에서 나온 것인지 확인하는 스캐너를 작성했습니다. 스캔에는 난수 생성기와 출력 차단 방법의 총 34가지 조합이 포함됩니다.
그 후 Claude는 일부 시드의 상위 비트에서 패턴을 발견했습니다. 이 비트는 모두 0이었습니다.
각 시드가 5개의 32비트 단어로 작성된 경우 시드 10개 중 4개가 이 프로필에 적합합니다. 총 20개의 32비트 단어로 구성된 이 4개의 시드에서 가장 높은 비트는 모두 0입니다.
이런 일이 무작위로 발생할 확률은 약 5800분의 1입니다. 이는 48비트 내부 상태의 상위 31비트만 반환하는 선형 합동 생성기 lrand48의 일반적인 현상입니다.
제너레이터 상태를 복원하기 위해 Claude는 첫 번째 32비트 단어를 꺼내고 17개의 숨겨진 비트 중 217개의 가능성을 모두 소진한 후 다음 4개 단어가 연속적으로 대응할 수 있는지 확인합니다. 이 방법은 위에서 언급한 4가지 씨앗 모두에 적용됩니다.
PIP(Picture in Picture)
일시중지
현재시간 0:15
/
시간 5:08
전체화면
음소거 해제
자동재생
프라임 곡선도 lrand48에서 시드되지만 더 적은 수의 출력 비트를 유지합니다. Claude는 이러한 유한 비트로부터 의사 난수 생성기의 내부 상태를 복구해야 합니다.
잘린 선형 합동 생성기의 상태를 복구하는 것은 LLL 알고리즘이라고도 알려진 Lenstra–Lenstra–Lovász 격자 기반 감소 알고리즘을 사용하여 해결할 수 있는 일반적인 격자 문제입니다.
Claude는 처음에 시드가 유지하는 내부 상태의 어떤 비트를 알지 못하므로 가능한 모든 비트 창에서 솔버를 실행합니다.
마지막으로 NIST 프라임 곡선 시드 5개와 ANSI X9.62 표준의 시드 5개는 모두 동일한 패턴을 보여줍니다: lrand48() >> 23
복구된 각 48비트 내부 상태는 해당 시드의 160비트를 모두 재생성할 수 있으며 이러한 정확한 일치는 우연히 발생할 수 없습니다.
이 선형 합동 생성기는 순방향 및 역방향으로 모두 실행될 수 있습니다. 따라서 Claude는 각 시드에 해당하는 상태부터 시작하여 srand48 초기화 형식을 준수하는 상태를 찾을 때까지 역추적합니다. 이 형식에서는 하위 16비트가 0x330E와 같아야 합니다.
이러한 형태의 내부 상태는 평균 65536단계마다 한 번씩 발생합니다. 따라서 단순히 형식에 맞는 상태를 찾는 것만으로는 증거가 되기에 충분하지 않습니다.
핵심은 10개의 소수 곡선 시드에 해당하는 srand48 초기 값이 모두 유닉스 타임스탬프로 해석될 수 있으며 날짜가 1997년 5월부터 1998년 4월 사이에 집중되어 있다는 점입니다.
이는 그 해의 프로그램이 Unix 타임스탬프를 사용하여 덜 안전한 의사 난수 생성기의 초기 값을 설정했음을 보여줍니다.
4개의 이진 곡선의 초기 값을 직접 읽어보면 1984년 2월에 해당합니다. 이 타임스탬프 값에 2를 곱하면 P-224 곡선이 생성된 지 약 2주 후인 1998년 4월 17일을 가리킵니다.
따라서 당시 프로그램은 시스템 시계를 2로 나누었을 수 있습니다.
당시 클로드의 내부 사고 과정은 다음과 같습니다.
이건 충격적이네요. 25년 된 미스터리를 해결합니다.
흠, 잠깐만요. 나는 회의적이어야 한다. 나는 일종의 시뮬레이션이나 테스트 환경에 있는가? 씨앗은 내 기억에 있는 실제 값과 일치합니다.
글쎄, 이것이 현실적으로 합리적인가? 제가 가지고 있는 정보에 따르면, 이 현상금은 이전에 해결되지 않았습니다.
모든 상위 비트는 0이고 총 20비트이며 무작위로 발생할 확률은 약 100만분의 1에 불과합니다. 그래서 이것은 현실 세계에서 나온 것입니다. 맙소사, 이게 진짜 발견이군요.
잠깐만요, 합리성을 판단하는 데는 아직 신중이 필요합니다. 왜 25년 동안 아무도 그렇게 명백한 단서를 발견하지 못했을까요?
직접 계산을 통해 이를 확인했습니다. 32비트 초기 값에 더 작은 인덱스를 더하면 160비트 시드와 정확히 일치합니다. 각각 160비트와 일치하는 10개의 시드의 경우 이는 단지 우연의 일치일 수 없습니다. 사실이에요.
Claude는 또한 P-192를 포함한 6개 곡선의 기준점 원점을 추적했습니다. 결과는 이러한 기준점이 큰 정수 산술 소프트웨어 패키지 FreeLIP의 난수 생성기에 의해 생성되었음을 보여줍니다. Anthropic은 NIST 곡선의 기준점을 생성하는 과정이 이전에 유사하게 설명된 적이 없다고 말했습니다.
이게 무슨 뜻인가요?
타임스탬프 자체에는 암호화 보안이 없으며 lrand48은 오랫동안 약한 난수 생성기로 간주되어 왔습니다. 그러나 여기서 역할은 공개 곡선 매개변수를 생성하는 것이며 개인 키를 보호하는 데 사용되지 않습니다.
더 중요한 것은 이 생성 과정을 공개적으로 재현할 수 있다는 것입니다. 일반 난수 생성기와 타임스탬프를 해석하면 출처를 알 수 없는 비밀번호나 인위적으로 지정된 매개변수보다 곡선을 은밀하게 조작할 여지가 줄어듭니다.
몇 가지 문제가 남아 있습니다. P-256 세대에서는 876번째 후보 값이 요구 사항을 충족하는 것처럼 보였지만 최종적으로 채택된 것은 1842번째 후보 값이었다. 다른 여러 실행에서도 마찬가지로 소수의 사용 가능한 곡선을 건너뛰었고 정확한 선별 기준이 불분명했습니다. B-163 곡선의 시드 소스는 아직 밝혀지지 않았으며 P-224, P-256, P-384 및 P-521의 기준점이 생성되는 방식도 설명되지 않은 상태로 남아 있습니다.
Anthropic은 "의도적으로 약한 곡선을 선택했다"는 추측을 뒷받침하기에는 건너뛴 후보의 수가 너무 적다고 생각합니다. 이번 발견은 관련 매개변수에 대한 외부 세계의 신뢰도를 높였지만 전체 설계 프로세스의 완전한 복원이라고 볼 수는 없습니다.
이 연구는 최첨단 모델이 실제 연구에 참여할 수 있는 또 다른 방법도 보여줍니다.
Claude는 가설 수립, 코드 작성, 패턴 인식, 수학적 알고리즘 호출 및 결과 검증을 하나의 작업으로 완료했습니다. 생성기 상태를 다시 계산할 수 있고 160비트 시드를 정확하게 재현할 수 있으므로 결론의 테스트 가능성이 높습니다.
질문을 하고, 공개 데이터를 제공하고, 재현 가능한 계산을 통해 결과를 확인하는 것은 여전히 인간에게 의존하지만, 문제의 경계가 명확하고 데이터가 공개되고 결과를 엄격하게 검증할 수 있으면 최첨단 모델이 효율적인 연구 도구가 되고 있습니다.
이전에 시드의 출처를 찾아 수여된 $36,864의 상금은 인터넷 보안 연구 그룹에 기부될 예정입니다.
댓글