요약
NIST 타원곡선의 시드는 해시가 아니라 타임스탬프로 초기화한 lrand48 난수였습니다.
앤트로픽 연구진이 내부 연구용 Claude 모델로 ECDSA 표준 곡선 시드의 출처를 밝혀냈다고 발표했습니다. 이 시드는 2000년 FIPS 186-2에 실렸지만 만든 방법이 공개되지 않아 25년 동안 백도어 의혹이 따라다녔습니다.
왜 중요한가
- 단순하고 재현할 수 있는 절차가 확인되면서, 연구진은 곡선에 백도어가 없다는 확신이 오히려 커졌다고 밝혔습니다.
- NSA의 제리 솔리나스가 농담 문구를 해시해 시드를 만들었다는 오랜 통설은 틀린 것으로 드러났습니다.
- 사람들이 그 소문을 좇다 풀지 못한 문제를 Claude는 소문에 기대지 않고 30분도 안 되어 풀었습니다.
핵심 내용
- P-192, P-224, P-256, P-384, P-521 시드는 C 라이브러리 lrand48(의사난수 생성기)이 뽑은 값이었습니다.
- 생성기는 1997년 5월에서 1998년 4월 사이의 Unix 타임스탬프로 초기화됐습니다.
- Claude는 일부 시드의 최상위 비트가 모두 0인 점에서 lrand48을 알아챘고, 나머지는 격자 기저 축소(LLL)로 풀었습니다.
- 유효한 후보 일부를 건너뛴 이유와 B-163 시드, P-256 등 네 곡선의 기준점은 아직 설명되지 않았습니다.
- 필리포 발소르다가 내건 현상금 3만 6,864달러는 Let's Encrypt를 운영하는 ISRG에 기부됩니다.
HN 반응
- 몇 달에 걸쳐 버린 후보는 알 수 없다는 의심에, 고를 여지가 30비트 남짓이라 약한 곡선을 노릴 수 없다는 반박이 이어졌습니다.
- 공동 저자 스티브 와이스는 문구 해시설을 4명에게서 확인했지만 모두 틀렸다고 했고, 일부 이용자는 일부러 흘린 말이 아니냐고 의심했습니다.
이 글은 곡선이 어떻게 만들어졌는지는 확인해 주지만, 어떤 곡선을 골랐는지에 대해서는 아무 말도 해주지 않습니다. 몇 달에 걸쳐 생성된 것으로 보이는 만큼 더 그렇습니다. 특히 생성됐다가 버려진 후보들은 볼 수 없습니다.
"이 곡선들이 난수 생성기에 넣는 타임스탬프를 이리저리 탐색해서 특정한 성질을 갖도록 골라졌을 가능성은 원리상 여전히 있다."
맞습니다.
"하지만 그렇게 하는 건 시드가 문제없이 생성됐다는 증거로 타임스탬프를 공개할 때에나 필요한 일이다."
"아무것도 하지 않고 아무 말도 안 하는 것"으로 충분한 상황에서는 논리적으로 성립하지 않는 얘기입니다.
1997년에 이 계산이 얼마나 비쌌을지 생각하면 몇 달이 걸린 건 당연합니다. 하지만 1997년의 모든 타임스탬프를 다 시도하고 그중 어느 타임스탬프에서든 처음 나오는 유효한 후보 16개 가운데 임의로 골랐다고 가정해도, 자유도는 고작 30비트 정도입니다.
무작위로 2^30번만 시도해도 걸릴 만큼 큰 약한 256비트 타원곡선 집단이 존재한다는 게 밝혀진다면, 그건 모든 타원곡선 암호가 깨졌다는 걸 발견하는 것에 맞먹는 암호 분석상의 돌파구일 겁니다.
Koblitz와 Menezes 논문의 3.1절을 읽어 보세요. 자유도가 160비트였어도 이미 말이 안 되는 얘기였습니다. https://eprint.iacr.org/2015/1018
NSA가 ECC가 깨져 있다는 걸 알면서도 위험을 무릅쓰고 미국 정부를 ECC로 옮겼는데, 30년 동안 아무도 같은 약점을 찾아내지 못했다고 믿고 싶다면 그러셔도 됩니다. 다만 그 가설에서 시드 선택이 어떤 역할을 한다고 우기는 건 이제 끝났습니다.
완전한 비전문가로서 궁금한데, n이 비트 수가 아니라 곡선이 뒤로 갈수록 커지는 건 왜인가요? 그러면 '더 열심히 찾았다'는 뜻 아닌가요?
n의 작은 값 대부분은 유효한 곡선 값이 아니라서, 말씀대로 "더 열심히" 찾긴 했지만 그건 유효한 시드를 찾기 위해서였습니다. 1의 생성기 출력을 보면 이렇습니다.
n 값의 개수에 비하면 버려진 유효한 시드는 아주 적습니다. 유효한 시드의 절반쯤이 왜 버려졌는지는 아직 모르지만, 곡선 유효성 검사기에 버그가 있었다는 설명이 저한테는 그럴듯해 보입니다.
질문하신 바로 그 점에 대해, prime192와 prime239 곡선은 대부분 유효한 시드를 찾으려면 더 큰 n 값이 필요했습니다. 이 둘은 크기가 더 작고 더 이른 타임스탬프를 썼습니다.
더 정확히 말하면, 그다지 무작위가 아닌 시도라는 겁니다.
가설 속의 ECC 약점이 어떻게든 LCG 구조와 상관관계가 있다고 보는 게 아니라면, LCG에서 뽑은 값은 무작위나 다름없습니다.
그런 상관관계가 생기는 것도 가능하긴 합니다. 하지만 그건 이게 무작위 탐색의 결과인 경우보다 훨씬 이상한 일이고, 무작위 탐색의 결과인 것만 해도 이미 아주 이상한 일입니다.
저는 조금은 덜 이상하다고 봅니다. 실제 구현에서 ECC 자체가 아닌 부분을 노리는 간접 공격의 가능성이 보이거든요. 네트워크 클라이언트가 서로 다르지만 어딘가 완전히 무관하지는 않은 곡선들을 각각 여러 번 요청할 수 있는 곳이라면, 지금까지 치명적이라고 여기지 않던 부채널을 드러낼 수도 있습니다. IV와 패딩의 결정성/무작위성이 "진짜 암호" 자체만큼 중요하다고 여겨지게 만든 발견들과 같은 방향입니다. 그 경우 어떻게든 상호작용해야 하는 구조는 ECC와 LCG가 아니라, 그저 LCG와 키 유도일 겁니다.
"..위험을 무릅쓰고 미국 정부를 ECC로 옮겼는데.."
으악, 그 얘기라면 할 말이 좀 있는데요...
계속 말해 보세요...
3DES요...
그래도 이제 그 분석을 해볼 방법이 생겼잖아요! 시드 생성 함수의 입력 매개변수를 (어떤 자유도든) 바꿔 가며 곡선을 잔뜩 만들어서, 생성된 곡선들 사이에 차이가 있는지 보면 됩니다.
이 곡선들에 NOBUS 취약점이 있을 가능성은 이걸로 배제되는 것 아닌가요? 제 생각이 좀 엉성할 수 있는데, 곡선이 만든 쪽만 N비트 보안으로 악용할 수 있는 NOBUS가 되려면, 곡선 2^N개 중 1개만 가진 성질이 있어야 할 것 같습니다. 그런 성질을 가진 타임스탬프를 찾을 때까지 해시를 돌리려면, 평균적으로 2^(N-1)개의 타임스탬프를 해시해야 하는데, N이 어지간히 크기만 해도 그건 현실적으로 불가능합니다.
맞아요, 현실적인 NOBUS 취약점을 만들기엔 여기 반복 횟수가 턱없이 부족합니다.
“Claude는 30분도 안 돼서 NIST P-192, P-224, P-256, P-384, P-521 시드의 출처를 밝혀냈다. 그 어느 것도 해시 알고리즘의 결과가 아니었고, 유닉스 타임스탬프를 시드로 쓴 C 라이브러리의 lrand48 난수 생성기가 낸 출력이었다!”
정말 멋지네요. 이걸 만든 NSA 직원이 머리를 다쳤던 건지, 아니면 지난 사반세기 동안 혼자 몰래 킬킬대고 있었던 건지 궁금하네요.
그 두 사람은 Bob Reiter와 Jerry Solinas였습니다. Jerry는 2015년에 Daniel Bernstein에게 보낸 이메일에서 암호문(passphrase)의 해시라고 생각한다고 썼습니다. 저는 비공식으로 전직 NSA 직원 두 명을 포함해 4명에게서 같은 이야기를 확인했습니다.
그런데 다들 틀렸던 겁니다!
Bob과는 연락이 닿지 않았습니다. 2018년 기준으로 민간 업계에서 일하고 있었지만 답이 없었습니다.
그게 문구라는 소문을 퍼뜨렸다는 게 좀 수상하네요. 이런 건 잊어버리거나 타임스탬프와 헷갈릴 만한 일이 아니잖아요.
그 "문구 해시" 방식은 다른 경우, 예를 들면 이와 무관하고 공개되지 않았을 수도 있는 다른 알고리즘에 쓰였을 수 있습니다. 그리고 나중에 그게 이 곡선들에 쓰인 방식과 혼동됐을 수도 있고요.
어쩌면 그 설명이 아직 밝혀지지 않은 나머지 부분을 설명해 주는 걸까요?
아니면 거짓말을 한 거거나요...
방금 누가 이걸 올렸네요.
https://www.youtube.com/watch?v=eOQfNT6Jdkg
기사 본문: 이 작업은 Anthropic에서 [...]와 Steve Weis가 진행했다.
다른 작업에 비해 영상에는 시간을 얼마나 들였을지 궁금하네요.
친구가 Claude로 만들어 줬으니 시간은 0입니다.
아, 이 스레드에서 다른 글도 봤는데 이름을 못 알아봤어요. 제 조사 실력이 이 정도입니다.
그래도 지난 20년을 연구하면서 2^51개 문장을 해시하며 보내지는 않았잖아요.
진지하게 묻는 건데, 이 음모론 모임에 인생의 며칠이나 쓰셨나요?
이 글들에서 시작된 예전 논의가 몇 개 있습니다. https://blog.cryptographyengineering.com/2015/10/22/a-riddle-wrapped-in-curve/ https://eprint.iacr.org/2015/1018
그 영상은 농담으로 만든 거예요. 이 영상 자막을 다른 자막으로 바꿔 다는 게 흔한 유행이거든요.
Tptacek은 이 분야 전문가예요. ECDSA가 아마 약화돼 있지 않다는 걸 설명하느라 상당한 시간을 쓰셨을 거라고 상상이 가네요.
스페인어를 알아들으면 오히려 흐름이 깨지긴 하는데, 어느 쪽이든 정말 웃기네요. ㅋㅋ
저는 라틴 아메리카 출신이라 스페인어를 알아듣는데도, 스페인 억양과 정신 나간 듯한 웃음 때문에 한참 동안 그 사람 말을 한마디도 못 알아들었고, 그래도 밈은 잘 즐겼습니다. 그런데 몇 년 전에 진짜 자막으로 보니까 머릿속에서 뭔가 딱 맞아떨어졌고, 지금은 보면 대체로 그 사람 말이 잘 들립니다. 대신 이제 밈은 망했어요. 두 가지 말을 동시에 듣고 읽기가 어렵거든요. 우리 뇌가 참 신기하다는 일화입니다.