유머 문구 해시설 틀려…상금 3만6864달러 ISRG 기부
앤트로픽 클로드가 NIST 곡선 시드가 시각값으로 초기화해 난수를 만들어내는 생성기의 출력임을 규명했다고 회사가 16일(현지시간) 밝혔다.
시드 출처를 설명하지 않은 채 곡선이 표준에 실려 의도적 약점 의혹이 남았다고 회사 발표문은 적었다. 암호학자 필리포 발소르다(Filippo Valsorda)는 대니얼 번스타인·타냐 랑게가 가정한 약 70비트 선택 여유는 이번 결과로 배제된다고 썼다.
클로드, 30분 안에 생성법 추적
회사 발표문에 따르면 직원 여러 명이 유머 문구의 해시라는 단서를 따라가다 실패했다. 올해 10월 한 직원이 그 단서를 주지 않은 채 내부 연구 모델에 시드 생성법을 물었다. 클로드는 30분도 안 돼 P-192·P-224·P-256·P-384·P-521 시드의 출처를 찾아냈다.
클로드는 1990년대 C 라이브러리 의사난수 생성기의 출력 패턴을 가정하고, 생성기·출력 슬라이스 조합 34가지를 도는 스캐너를 짰다. 시드 일부에서 상위 비트가 모두 0인 패턴을 보고 lrand48로 좁혔다. 우연히 그럴 확률은 5810분의 1이다.
소수체 시드는 출력을 잘라 썼기 때문에 내부 상태 복원에 격자 축소(LLL) 알고리듬이 필요했다. NIST 시드 다섯 개에 더해 ANSI X9.62 예시 곡선 시드 다섯 개도 같은 패턴이었다. lrand48 출력을 23비트 오른쪽으로 이동한 형태였고, 복원한 48비트 상태는 시드 160비트를 그대로 다시 만들었다.
시드, 1997–98년 시각과 일치
회사 발표문에 따르면 시드는 해시 결과가 아니었다. 유닉스 타임스탬프로 srand48을 건 뒤 lrand48로 20바이트씩 후보를 뽑는 방식이었다. P-256 표준 시드는 1997년 8월 16일 01시 52분 34초(UTC) 실행의 1842번째 후보와 일치한다.
P-192는 같은 해 5월 18일 실행의 139번째 후보였다. P-384는 8월 30일 실행의 2688번째, P-224는 1998년 4월 3일 실행의 7026번째 후보였다. 소수체 곡선 시드 열 개의 초기값은 모두 1997년 5월부터 1998년 4월 사이 시각이었다.
이진 곡선 네 개는 시계를 반으로 나눈 값으로 보면 1998년 4월 17일로 모인다. 회사는 재현 코드를 공개 도메인으로 올렸다. 클로드는 1997년 5월에 만든 곡선 여섯 개의 기저점도 함께 추적했다.
회사 발표문에 따르면 아르연 렌스트라(Arjen Lenstra)의 FreeLIP 난수 생성기가 출처였다. 작은 정수를 넣고 앞 출력을 버리는 방식이었고, P-192 기저점 시드는 20000이었다. P-224·P-256·P-384·P-521 기저점은 이 방식에 맞지 않았다.
회사, 암호 붕괴 아니라고 밝혀
이는 암호학적 붕괴도, 새로운 공격도, ECDSA 곡선의 취약점도 아니다. 오히려 곡선이 백도어나 의도적 취약점 없이 선택됐다는 확신을 더 갖게 한다.
— 앤트로픽, 연구 발표 10월 16일 · “This is not a cryptographic break, new attack, or weakness in the ECDSA curves. In fact, this makes us more confident the curves were chosen without any backdoors or intentional weaknesses.”
발소르다는 자신의 글에서 알고리듬을 Go로 다시 구현해 청구를 검증했다고 밝혔다. 1997–98년 시각과 앞쪽 후보 16개만 허용해도 선택 여유는 약 30비트에 그친다. 곡선 위수 n의 비트 길이가 기반 체 p보다 긴 후보를 버리는 조건도 있었다.
곡선 자체는 2000년 FIPS 186-2에 실렸다. NSA가 설명 없이 시드를 넘긴 뒤부터 출처 논쟁이 이어졌다. 제리 솔리나스(Jerry Solinas) 전 NSA 직원이 유머 문구를 해시했다고 회상했으나 2023년 초 사망했고, 이번 재현은 그 기억과 맞지 않았다.
상금은 ISRG에…미해결도 남아
발소르다는 15일 01시 07분 51초(UTC)에 청구가 들어왔다고 적었다. 3년 전 내건 현상금은 기부금과 합쳐 3만6864달러가 됐고, 인터넷보안연구그룹(ISRG)으로 보낸다. 연구 크레딧에는 존 우드, 헨리 드 발랑스, 니컬러스 칼리니(Nicholas Carlini), 스티브 와이스(Steve Weis) 등 열 명이 올랐다.
B-163 시드는 아직 어떤 생성기와도 맞지 않았다. P-256 실행에서는 공개된 1842번 후보 앞에 유효한 876번 후보도 있었고, P-224 실행은 유효 후보 셋을 지나쳤다. 어떤 기준으로 후보를 걸렀는지는 아직 정해지지 않았다.