AMD의 난수 생성기는 0을 만들지 못하나요?

AI 요약

flat assembler 포럼의 Jessé는 데이터 분포를 그리는 어셈블리 프로그램을 작성하다 AMD 프로세서의 하드웨어 난수 명령어에서 이상한 결과를 발견했습니다. 같은 프로그램을 Intel 프로세서에서 실행하면 0이 정상적으로 나타나지만, AMD 시스템에서는 요청한 폭 전체가 0인 값이 나오지 않았습니다. 작성자는 Zen 2에서 특히 나타나는 문제일 수 있다고 추정했지만, 당시 접근할 수 있었던 AMD 시스템이 두 대뿐이어서 모든 AMD 제품군의 동작으로 일반화하지는 않았습니다.

테스트 프로그램과 관찰 결과

첨부된 gtk4-bargraph.tar.gz는 콘솔 화면의 임의 위치에 그래프를 렌더링하는 flat assembler 프로그램입니다. fastcall_v1 매크로 키트가 있어야 그대로 빌드할 수 있습니다. 그래프의 첫 번째 막대는 0이 나온 횟수를 표시합니다. RDRAND 결과는 빨간색, RDSEED 결과는 파란색, 작성자가 만든 TSC 기반 방식은 초록색으로 표시합니다. 나머지 막대는 16비트 공간의 다른 65,535개 값을 나타냅니다.

작성자의 AMD 시스템에서는 초록색 막대가 계속 변하지만 RDRAND와 RDSEED의 0 카운터는 변하지 않았고, 그래프의 최솟값 기준도 0보다 커지지 않았습니다. Intel 시스템에서는 세 방식 모두 0이 나타났습니다. 포럼에서 제시한 우회 방법은 16비트 레지스터로 직접 결과를 받지 않고, RDRAND와 RDSEED를 32비트 또는 64비트 레지스터로 실행한 뒤 하위 16비트만 그래프에 사용하는 방식입니다. 이렇게 하면 AMD에서도 하위 16비트가 모두 0인 값이 관찰됐습니다. 따라서 단순히 내부 난수원이 0을 만들지 못하는지, 16비트 결과를 기록하는 명령어 경로에서 값이 빠지는지는 분리해서 봐야 합니다.

다른 폭과 프로세서별 차이

작성자는 16비트 결과에서만 문제가 보이는지 확인하기 위해 32비트와 64비트 결과도 비교했습니다. 32비트나 64비트 결과의 하위 부분에서는 0이 나왔지만, 요청한 전체 폭이 0인 값은 AMD에서 계속 나오지 않았다고 설명했습니다. 이후 테스트 프로그램에 벤치마크 기능과 RDSEED를 지원하지 않는 프로세서용 경로도 추가했습니다.

측정값은 프로세서마다 크게 달랐습니다. 2012년형 Core i5는 초당 1,260만 개, 2017년형 Core i7-7700은 초당 75만 개, Ryzen 7은 약 260만 개의 난수를 생성했습니다. 작성자는 AMD 쪽 생성 속도가 클록 변화에 거의 영향을 받지 않았고, 2012년형 Core i5는 테스트에서 클록 속도에 100% 의존하는 것처럼 보였다고 적었습니다. 이 차이를 근거로 제조사와 세대에 따라 RNG 회로 또는 구현 버전이 상당히 다를 수 있다고 추측했지만, 내부 동작을 설명하는 충분한 공개 자료는 찾지 못했다고 밝혔습니다.

포럼의 revolution은 과거 알려진 구조를 기준으로, 내부의 불안정 잡음 발생기가 단일 비트를 만들고 클록 샘플러, 편향 제거 회로, 직렬 시프트 레지스터를 거쳐 128비트 시드를 만든다고 설명했습니다. 이후 RDRAND는 AES 기반 CSPRNG를 카운터 모드로 사용해 고속 결과를 내고, 내부 엔트로피가 충분히 쌓이면 다시 시드한다고 했습니다. RDSEED는 내부 시드에서 원시 비트를 직접 가져오는 경로라고 설명했습니다. 다만 현재 회로가 과거와 같다는 보장은 없다고 덧붙였습니다.

재현과 원인에 관한 논쟁

Hacker News에서는 이 현상이 Zen 2에 한정되는지, 16비트 명령어 경로에만 있는지, 실제로 0이 절대 나오지 않는다고 증명할 수 있는지를 두고 의견이 갈렸습니다. Zen 3에서 16비트 0을 정상적으로 얻었다는 보고가 있었고, Ryzen 5 3600에서는 RDRAND32가 정상적으로 0을 반환하지만 RDRAND16은 0을 만들지 못한다는 재현 결과도 나왔습니다. 해당 사용자는 Zen 2에서 과거 RDRAND가 항상 -1, 즉 모든 비트가 1인 값을 반환하던 버그가 마이크로코드 업데이트로 수정됐던 일을 함께 언급했습니다.

다만 반복 테스트에서 0을 보지 못했다는 사실만으로 0을 생성할 수 없다고 증명할 수는 없습니다. 16비트 균등 분포라면 특정 값이 나올 확률은 1/65,536이므로 충분한 샘플이 필요하지만, 11시간 동안 실행한 테스트에서 다른 값과 비슷한 빈도로 0이 나와야 한다는 반론도 제기됐습니다. 32비트와 64비트 전체가 0인 값은 관측에 훨씬 긴 시간이 필요하므로, 16비트 결과에서 나타난 이상과 같은 방식으로 검증하기 어렵다는 지적도 있었습니다.

암호학적 사용을 둘러싼 논의도 이어졌습니다. 하드웨어 난수는 보통 직접 키로 쓰지 않고 CSPRNG의 시드나 운영체제 난수 풀에 넣으므로 실용적 영향이 작다는 의견이 있었습니다. 반대로 감사할 수 없는 칩 내부 RNG에 전적으로 의존하면 안 되며, 여러 엔트로피원을 섞어야 한다는 주장도 나왔습니다. 한 댓글은 8비트 RNG가 0 하나만 만들지 못해도 출력 공간이 줄고 일부 비트가 항상 고정되므로 예측 가능성이 생긴다고 설명했습니다. 작성자는 AMD에 문의했고 내부적으로 담당 부서에 전달됐다는 답을 받았지만, 포럼에 공유할 만한 구체적인 기술 설명은 아직 받지 못했다고 업데이트했습니다.

Hacker News 반응

• @CodesInChaos — 당황스러운 문제이지만, 이런 하드웨어 난수는 보통 직접 사용하지 않고 CSPRNG의 시드로 사용하므로 실질적인 영향은 작을 것입니다.
  • @leonidasrup — Theodore Ts’o에 따르면 Intel 엔지니어들이 /dev/random이 RDRAND에만 의존하도록 압박했다고 합니다. 칩 내부에 봉인되어 감사할 수 없는 하드웨어 난수 생성기에 전적으로 의존하는 것은 나쁜 생각입니다. CSPRNG에 백도어를 넣는 방식은 암호를 무너뜨리는 흔한 방법입니다. Dual_EC_DRBG가 그 사례입니다.
• @matja — 제 Zen 3 칩에서는 16비트 0이 나옵니다. +1은 3,821회, 0은 3,893회, -1은 3,895회였습니다. 32비트 결과도 통계적으로 의미 있는 표본을 모은 뒤 포럼 스레드를 업데이트하겠습니다. Zen 2 이후에 수정된 문제일까요?
  • @rbanffy — 수천 개의 Zen 2 칩이 있는 HPC 클러스터에 접근할 수 있는 사람이 있나요? 64비트 값도 확인해 보고 싶습니다. 장비 규모에 따라 몇 년쯤 걸릴 것 같습니다. 슈투트가르트 고성능 컴퓨팅 센터의 720,320개 Zen 2 코어로 해볼 사람은 없나요?
• @jstanley — Zen 2의 RNG 버그는 이번이 처음이 아닙니다. 예전에 RDRAND가 항상 -1, 즉 모든 비트가 1인 값을 반환해서 프로그램이 시작하자마자 종료되는 일이 있었고, 마이크로코드 업데이트로 수정됐습니다. 이번에는 항상 1을 반환하는 문제를 고치면서 절대 0을 반환하지 않게 된 것인지도 모르겠습니다. Ryzen 5 3600에서 처음에는 재현하지 못했지만, 다시 확인해 보니 RDRAND32는 정상이고 RDRAND16은 0을 만들지 못했습니다.
  • @RandomOnyx — RDRAND32를 실행한 뒤 결과의 하위 16비트를 사용하면 0이 나오나요? 16비트 레지스터에 쓰는 명령어 버전의 문제인지, 내부 RNG 자체의 문제인지 궁금합니다.
  • @jstanley — 그렇습니다. 처음에는 rdrand32() % 65535를 사용했고, 0이 예상 빈도로 나왔기 때문에 문제가 없다고 잘못 생각했습니다.
  • @goalieca — 하위 16비트를 마스킹하려면 & 0xFFFF를 사용해야 합니다. 나머지 연산의 값이 1만큼 틀렸습니다.
• @ZiiS — 해당 값을 사용하는 암호 코드가 0을 건너뛰는 편이 더 안전하다고 판단했을 가능성이 있습니다. 수학적으로 0이 특별히 덜 나올 이유는 없지만, 누군가 실제로 그 키를 시도할 가능성은 훨씬 높습니다. 반대로 코드가 0을 너무 많이 만들어서 가장 쉬운 수정으로 전부 버렸을 가능성도 있습니다.
  • @dark-star — 암호는 보통 그런 식으로 작동하지 않습니다.
• @throwawayffffas — 목적은 범위 안의 모든 값을 정확히 같은 확률로 고르는 것이 아니라 예측 불가능하게 만드는 것입니다. 16,542가 절대 나오지 않는다고 해서 문제가 될까요?
  • @antiloper — 목적은 실제로 범위 안의 모든 값을 정확히 같은 확률로 고르는 것입니다. Intel SDM 7.3.17과 해당 문서가 참조하는 NIST SP 800-90A의 난수 정의를 보세요.
  • @gnfargbl — 8비트 RNG를 생각해 보세요. 0이 나오지 않아도 문제가 없다고 하면 {1, 2, 3, ..., 253}이 나오지 않아도 문제가 없어야 합니다. 결국 254와 255만 출력하는 RNG가 됩니다. 호출마다 어느 값이 나올지는 예측할 수 없더라도 8비트 중 7비트가 항상 고정되어 완전히 예측 가능합니다. 공격자가 이를 어떻게 악용할지 상상할 수 있지 않나요?
• @hnacobsxph — 예전에 KDF에서 비슷한 버그를 추적한 적이 있습니다. 16비트 추출값을 히스토그램으로 그려서야 발견했고, 통계 테스트 도구들은 문제를 표시하지 않았습니다.
• @20k — 하드웨어 검증에 이렇게 많은 자원이 들어가는데도 이런 버그가 생기는 과정이 늘 궁금합니다. 어떻게 검증망을 빠져나갔는지 알 수 있다면 흥미로울 것 같습니다.
• @strenholme — 보안이 중요한 소프트웨어에서는 여러 엔트로피원을 XOF에 넣는 방식을 사용합니다. 예를 들어 rdrand16을 100번 실행한 값과 시스템 시간, 네트워크 패킷 간격을 함께 XOF에 넣으면 rdrand16이 0x0000을 한 번도 반환하지 않아도 출력 스트림에는 그런 흔적이 남지 않습니다.
  • @stingraycharles — 여러 난수원을 섞어 이런 문제를 완화하는 방식은 /dev/random이나 /dev/urandom 같은 시스템이 하는 일 아닌가요? 단일 난수원에 의존하거나 직접 구현할 이유가 잘 보이지 않습니다.
• @rbanffy — 16비트 값에서만 이상한 동작이 나타나는지, 32비트와 64비트에서도 같은지 궁금합니다. 0이 다른 고정값으로 바뀌어 출력 빈도를 늘리는지도 확인해야 합니다. RDRAND가 내부 상태를 여러 번 읽어 더 큰 값을 조합하는 구조라서 폭이 커질수록 느려지는지도 궁금합니다.

원문: flat assembler forum, 커뮤니티: Hacker News / 번역·요약: Trawling