RNG 구현 테스트와 검증

난수 생성기 검사에는 근본적인 어려움이 있습니다. 진정한 무작위 수열과 성능이 좋은 PRNG에서 나온 의사난수 수열은 통계 검사에서 똑같아 보이기 때문입니다. 유한한 길이의 검사로 수열이 무작위임을 증명할 수는 없습니다. 통계는 일정한 신뢰도로 비무작위성만 감지할 수 있습니다. 검사는 RNG에 명백한 편향이나 패턴이 없는지 확인하지만 암호학적 보안을 증명하지는 못합니다. 암호학적 RNG 검사에는 서로 다른 두 가지 목표가 있습니다. (1) 통계적 품질 — 출력 분포가 균등하고 독립적으로 보이는지 확인합니다. (2) 암호학적 강도 — DRBG 알고리즘이 올바르게 구현되었고 보안 주장이 성립하는지 확인합니다. 이 두 목표에는 서로 다른 검사 방법이 필요합니다.

NIST SP 800-22는 비트 수열을 평가하기 위한 15가지 통계 검사를 제공합니다. 검사에는 다음이 포함됩니다. 빈도(단일 비트) 검사 — 1의 비율이 0.5에 가까워야 합니다. 블록 빈도 검사 — 각 m비트 블록에서 1의 빈도를 검사합니다. 연속 구간 검사 — 동일한 비트가 끊기지 않고 이어지는 구간의 개수를 검사합니다. 최장 구간 검사 — 1이 이어지는 가장 긴 구간의 길이를 검사합니다. 이진 행렬 계수 검사 — 수열로 구성한 이진 행렬의 계수를 검사합니다. 스펙트럼 검사(DFT) — 주기적인 패턴을 감지합니다. 겹치는 패턴 일치 검사 — 특정 패턴이 나타나는 횟수를 셉니다. Maurer의 보편 통계 검사 — 수열을 압축하고 얼마나 짧아지는지 측정합니다. 각 검사는 p값을 생성하며, p < 0.01이면 비무작위성을 시사합니다. 검사는 100만~10억 비트에 대해 수행됩니다.

TestU01(L'Ecuyer와 Simard, 2007)은 RNG 공동체에서 널리 사용하는 종합 통계 검사 모음입니다. SmallCrush: 10개 검사, 약 35초로 빠른 확인에 적합합니다. Crush: 144개 검사, 약 2시간이 걸립니다. BigCrush: 160개 검사, 약 24시간이 걸립니다. BigCrush 검사는 NIST SP 800-22가 놓치는 미묘한 상관관계를 찾아냅니다. 잘 설계된 암호학적 DRBG(HMAC_DRBG, CTR_DRBG)는 다항 시간 알고리즘으로는 출력과 무작위 수열을 계산적으로 구별할 수 없으므로 BigCrush를 쉽게 통과합니다. 비암호학적 PRNG(Mersenne Twister, 선형 합동 생성기)는 BigCrush의 일부 검사를 통과하지 못합니다. BigCrush 실패는 해당 RNG를 암호학적 용도로 사용해서는 안 된다는 강력한 신호입니다.

SP 800-90B와 90A는 DRBG가 작동 중에 지속적으로 수행해야 하는 상태 검사를 규정합니다. 연속 RNG 검사(CRNGT): 생성된 각 블록을 이전 블록과 비교하며, 두 블록이 같으면(RNG가 멈춘 경우) DRBG는 오류 상태로 전환하고 생성을 중지해야 합니다. 반복 횟수 검사: 엔트로피 추정치를 기준으로 보았을 때 연속된 표본에서 같은 값이 통계적으로 예상되는 횟수보다 많이 반복되면 실패로 판정합니다. 적응형 비율 검사: 어떤 창에서 가장 자주 나타나는 값이 임계 횟수보다 많이 나타나면 실패로 판정합니다. 이러한 상태 검사는 센서 고착이나 HWRNG 하드웨어 결함과 같은 엔트로피 원천의 장애를 감지하여 암호 키 생성을 조용히 손상시키기 전에 대응할 수 있게 합니다.

PractRand는 미리 정해진 길이를 요구하지 않고 수열이 생성되는 동안 분석하는 온라인(연속 처리) 평가를 위해 설계된 현대적인 RNG 검사 도구입니다. 이 도구는 간격 검사, 비트 분포 검사, 적응형 정밀도를 사용하는 스펙트럼 검사 등을 적용합니다. PractRand는 짧은 수열에서는 양호하지만 수십억 비트에 걸쳐 패턴을 드러내는 RNG를 특히 효과적으로 감지합니다. 암호학적 DRBG의 출력은 길이와 관계없이 PractRand가 무작위 수열과 구별할 수 없는데, 이것이 계산적 구별 불가능성의 운영상 정의입니다. PractRand는 엔트로피 원천을 평가하는 데에도 사용되어 /dev/urandom 출력과 RDRAND 출력을 검사하고 하드웨어 장애나 체계적인 편향을 감지합니다.

암호 알고리즘 검증 프로그램(CAVP)은 SP 800-90A DRBG를 위한 공식 검사 벡터를 제공합니다. CAVP 검사는 알려진 답 검사(KAT) 벡터를 사용하여 NIST의 자동 검사 시스템에 구현을 제출하는 방식으로 진행됩니다. 특정 엔트로피 입력, 논스, 개인 설정 문자열, 추가 입력이 주어지면 구현은 예상되는 출력 비트를 정확히 생성해야 합니다. CAVP는 통계적 특성을 검사하지 않고 알고리즘의 정확성을 검사합니다. FIPS 140-3 인증을 받으려면 모듈 경계 안에서 사용하는 모든 암호 알고리즘에 대해 CAVP 검증이 필요합니다. CAVP 검사 벡터는 NIST의 ACVP(자동 암호 검증 프로토콜) 서버에서 공개적으로 제공되며 OpenSSL, mbedTLS, BoringSSL의 검사 모음에 통합되어 있습니다.

DRBG를 안전하게 초기화하기 전에 엔트로피 원천을 검증해야 합니다. SP 800-90B는 다음을 규정합니다. (1) 엔트로피 추정 — 통계 검사(최소 엔트로피 추정)를 사용하여 비트당 실제 엔트로피를 측정합니다. (2) 시작 검사 — 처음 사용하기 전에 엔트로피 원천이 유효한 출력을 생성하는지 확인합니다. (3) 요청 시 검사 — 애플리케이션이 요청할 때 선택적으로 수행하는 검사입니다. (4) 잡음원 상태 검사 — 하드웨어 성능 저하를 감지합니다. 일반적인 엔트로피 원천과 추정된 비트당 엔트로피는 다음과 같습니다. CPU RDRAND/RDSEED(약 1비트/비트, 하드웨어 인증됨), /dev/urandom(여러 원천을 혼합하며 엔트로피 추정치는 보수적임), 링 발진기 TRNG(설계에 따라 0.5~0.9비트/비트), ADC 잡음(0.1~0.5비트/비트). SP 800-90B 검증에는 전문 장비를 사용하는 실험실 검사가 필요합니다.

가상 환경에서는 RNG 검사에 특유의 어려움이 생깁니다. VM은 시작할 때(하드웨어 이벤트가 없음) 또는 스냅샷을 복원한 후(상태 재설정)에 엔트로피가 낮은 상태가 될 수 있습니다. 도커 컨테이너는 호스트 커널의 RNG를 공유하므로 컨테이너에서 기반 엔트로피의 품질을 직접 검사할 수 없습니다. VM 배포에서의 검사: (1) /dev/random 읽기가 완료될 때까지 걸리는 시간을 측정합니다. 오래 기다리면 엔트로피가 부족하다는 뜻입니다. (2) 병렬 VM 인스턴스에서 생성된 중복 UUID 또는 키를 검사합니다(클라우드 배포에서 실제 장애 사례로 문서화된 문제입니다). (3) VM에 VIRTIO-RNG (virtio_rng.ko)가 적재되어 있는지 확인합니다. 이는 호스트에서 게스트로 엔트로피를 주입합니다. (4) 애플리케이션 시작 순서를 감사하십시오. 충분한 엔트로피를 사용할 수 있게 되기 전에 키 생성이 이루어집니까?

RNG의 포크 안전성을 검사하면 미묘한 취약점을 예방할 수 있습니다. 프로세스가 분기될 때 부모와 자식이 동일한 DRBG 상태를 공유하여 동일한 수열을 생성할 수 있기 때문입니다. 탐지 방법: 자식 프로세스 N개를 생성하고 각각에서 UUID를 하나씩 생성한 다음 모든 UUID가 고유한지 확인합니다. 둘이라도 일치하면 RNG는 포크에 안전하지 않습니다. OpenSSL은 2020년에 포크 안전성 결함을 수정했습니다(CVE-2020-1971은 DRBG를 직접 다룬 것은 아니지만 양상은 유사합니다). 현재 OpenSSL은 PID 기반 시드 갱신을 사용합니다. 마지막 호출 이후 PID가 변경되었으면(포크가 발생했음을 의미함) DRBG가 자동으로 다시 시드됩니다. 이를 검사하려면 포크 전후에 검사를 실행하고, 서로 다른 출력이 나오는지 확인하여 다시 시드되었음을 확인합니다.

RNG 구현을 위한 실용적인 감사 점검 목록입니다. (1) RNG가 시간 기반 시드가 아니라 OS(getrandom, BCryptGenRandom)에서 초기화됩니까? (2) DRBG 유형이 NIST SP 800-90A에서 승인한 방식(해시, HMAC, CTR)입니까? (3) 주장하는 보안 강도에 비해 시드 길이가 충분합니까? (4) 주기적으로 또는 생성 호출을 일정 횟수 수행한 후 다시 시드하도록 되어 있습니까? (5) 포크 안전성을 처리합니까(포크 후 다시 시드)? (6) 상태 검사가 활성화되어 있으며 실패 시 시스템을 중지합니까? (7) 종료 시 상태를 0으로 지웁니까? (8) CI/CD에서 CAVP 검사 벡터를 실행합니까? (9) 엔트로피 추정값을 문서화하고 검증합니까? (10) FIPS 요구 사항의 경우 모듈이 FIPS 140-3 인증을 받았습니까?

과거의 RNG 실패 사례는 그 위험성을 보여 줍니다. 데비안 OpenSSL(2006~2008년): 한 패치가 엔트로피 수집 코드 두 줄을 실수로 삭제하여 시드 공간을 15비트 PID 공간으로 줄였고, 데비안 전체 사용자 기반에서 생성될 수 있는 SSH 키가 32,767개에 불과했습니다. 데비안에서 생성된 모든 SSH 호스트 키와 사용자 키를 교체해야 했습니다. 안드로이드 비트코인 지갑(2013년): Android의 SecureRandom이 일부 장치에서 실패하는 Java 수준의 시드 설정을 사용하여 ECDSA 서명에서 k 값이 중복되었고, 이로 인해 개인 키가 직접 드러났습니다. 소니 PS3(2010년): ECDSA 펌웨어 서명에 상수 논스를 사용하여, 두 개의 서명에서 개인 키를 추출할 수 있었습니다(서로 다른 메시지에서 같은 k를 사용하면 간단한 대수 계산으로 키가 드러납니다).

다음 중 DRBG가 출력이 고정되어 같은 값을 반복해서 생성하고 있을 가능성을 탐지하는 검사는 무엇입니까?

통계 검사는 NIST SP 800-22, TestU01 BigCrush, PractRand를 사용하여 출력 품질을 검증하지만 암호학적 보안을 증명할 수는 없습니다. CAVP 알려진 답 검사는 SP 800-90A 구현의 알고리즘 정확성을 검증합니다. SP 800-90B 엔트로피 소스 검사(최소 엔트로피 추정, 상태 검사)는 시드 입력을 검증합니다. 연속 RNG 검사(CRNGT)는 실시간으로 출력이 특정 값에 고정되는 현상을 탐지합니다. VM 및 컨테이너 배포에는 엔트로피 주입(VIRTIO-RNG)과 시작 시 엔트로피 확인이 필요합니다. 포크 안전성 검사는 자식 프로세스가 부모의 DRBG 상태를 상속하지 않는지 확인합니다. 실제 실패 사례(데비안, 안드로이드)는 RNG 결함이 암호 키 손상으로 직접 이어질 수 있음을 보여 줍니다. 감사 점검 목록은 운영 환경 배포에서 이러한 검사를 체계화합니다.