Dual EC DRBG 백도어 사건

Dual EC 결정적 난수 비트 생성기(Dual EC DRBG)는 NIST가 2006년 SP 800-90A에서 표준화한 네 가지 DRBG 중 하나였습니다. 이 생성기는 두 타원 곡선 점 P와 Q를 사용하여 의사 난수 비트를 생성합니다. 각 단계에서 r_i = x(s_i * P)(점 곱셈 결과의 x좌표)를 계산한 다음, s_{i+1} = x(r_i * P)로 상태를 업데이트하고 output = x(r_i * Q)로 비트를 생성합니다. 이 생성기는 학술적 표기상 정당해 보였습니다. NIST SP 800-90A에 포함된 뒤 RSA Security가 자사의 BSAFE 암호 라이브러리에서 기본값으로 채택하면서 기업 및 정부 소프트웨어에 확산되었습니다.

Dual EC DRBG의 백도어는 P와 Q 사이의 관계를 악용합니다. 공격자가 Q = e * P를 만족하는 비밀 스칼라 e를 알고 있다면, 임의의 출력 블록이 주어졌을 때 다음을 계산할 수 있습니다. output = x(r * Q)에서 r*Q의 y좌표를 무차별 대입으로 찾은 다음, r*P = (1/e) * (r*Q) mod n을 계산합니다. r*P를 이용하면 모든 이후 출력을 예측하고 내부 상태를 복구할 수 있습니다. e를 아는 것이 백도어이며, 이는 P를 기준으로 한 Q의 이산 로그를 아는 것과 같습니다. NIST 표준은 P와 Q 값이 어떻게 선택되었는지 설명하지 않은 채 제공했으므로, 트랩도어 없이 무작위로 생성되었는지 검증할 수 없었습니다.

2007년 8월, 댄 쇼모와 닐스 퍼거슨은 CRYPTO의 Rump Session에서 "NIST SP800-90의 Dual EC Prng에 백도어가 존재할 가능성에 대하여"라는 제목의 획기적인 논문을 발표했습니다. 두 사람은 누군가 e(P에 대한 Q의 ECDLP)를 알고 있다면 약 32바이트의 출력만으로 모든 Dual EC DRBG 출력을 예측할 수 있음을 수학적으로 증명했습니다. 또한 간단한 예를 통해 이를 보여 주었습니다. 이 발표는 암호학계에서 큰 주목을 받았습니다. 브루스 슈나이어는 다음과 같이 썼습니다. "NSA가 Dual_EC_DRBG 출력을 읽을 수 있는지 없는지 우리는 알 방법이 없습니다." 이러한 경고에도 불구하고 Dual EC DRBG는 그 후 6년 동안 표준에 남아 있었습니다.

2013년 9월, 뉴욕 타임스, 가디언, ProPublica는 에드워드 스노든이 유출한 문서를 바탕으로, NSA가 암호 표준에 비밀리에 취약점을 도입했다는 사실을 밝히는 보도를 발표했습니다. "신호정보 활용 프로젝트"라는 제목의 한 문서는 암호화 표준과 제품에 "은밀하게 영향력을 행사"하기 위한 연간 2억 5천만 달러 규모의 프로그램을 설명했습니다. 이 문서에는 Dual EC DRBG가 명시적으로 언급되지 않았지만, 쇼모와 퍼거슨의 수학적 증명과 함께 고려한 암호학계는 NSA가 P와 Q를 알려진 관계 e를 갖도록 선택하고 e는 비밀로 유지한 채 그 상수를 NIST에 제출함으로써 백도어를 삽입했다고 널리 결론 내렸습니다.

로이터는 2013년 12월, NSA가 RSA Security에 1천만 달러를 지급하여 RSA의 BSAFE 암호 도구 모음에서 Dual EC DRBG를 기본값으로 설정하게 했다고 보도했습니다. 당시 EMC의 한 사업부였던 RSA Security는 금융 기관, 의료 기업, 정부 계약업체가 사용하는 기업용 소프트웨어에 BSAFE를 배포했습니다. RSA의 성명은 백도어를 알고도 구현했다는 점을 부인했지만, 해당 계약을 수락한 사실은 인정했습니다. 이 폭로는 특히 큰 타격이었습니다. BSAFE는 보안 제품으로 판매되었고, 고객들은 암호학적 보장을 기대하여 이를 특별히 선택했기 때문입니다. 이 사건으로 RSA Security의 평판은 크게 훼손되었고 2014년 RSA Conference 불매 운동으로 이어졌습니다.

스노든 폭로 이후 NIST는 여러 조치를 취했습니다. 2013년 9월, NIST는 SP 800-90A를 공개 의견 수렴 대상으로 다시 열고 검토가 진행되는 동안 Dual EC DRBG를 사용하지 말 것을 권고했습니다. 2014년 4월, NIST는 Dual EC DRBG를 완전히 제거한 SP 800-90A Revision 1을 발표했으며, Hash_DRBG, HMAC_DRBG, CTR_DRBG만 남았습니다. 또한 NIST는 모든 암호 표준과 지침을 검토하기 시작했으며, NSA의 영향으로 다른 표준이 손상되었는지도 구체적으로 조사했습니다. 향후 표준화 활동의 투명성과 대중의 참여를 높이기 위해 NIST 암호 표준 및 지침 절차 실무 그룹도 만들어졌습니다.

Dual EC DRBG 백도어는 암호학계가 표준 제정 기관을 신뢰하는 방식에 심대한 영향을 미쳤습니다. 이 사건은 국가 정보 기관이 전 세계적으로 사용되는 암호 표준을 의도적으로 약화할 수 있음을 보여 주었으며, 그 영향은 적국뿐 아니라 동맹국, 기업, 일반 시민에게까지 미쳤습니다. 또한 이 사건은 공개되어 검증할 수 있고 아무것도 숨기지 않은 수를 사용하는 알고리즘의 도입을 앞당겼습니다. SHA-3의 Keccak은 상수를 정하는 데 문서화된 알고리즘을 사용했고, BLAKE2와 BLAKE3는 수학 상수의 소수 부분에서 상수를 도출하며, Curve25519는 검증할 수 있도록 특별히 선택한 소수(2^255 - 19)를 사용합니다. 타원곡선 매개변수를 "검증 가능하게 무작위로" 생성하는 방식이 표준 관행이 되었습니다.

Dual EC DRBG 스캔들은 "아무것도 숨기지 않은"(NUMS) 상수라는 개념을 널리 알렸습니다. 이는 숨겨진 트랩도어를 포함할 수 없도록 공개적으로 검증 가능한 출처에서 생성한 암호 매개변수입니다. 예를 들어 SHA-2는 처음 8개 소수의 제곱근에서 도출한 초기 해시 값을 사용하고, 라운드 상수는 처음 64개 소수의 세제곱근에서 도출합니다. BLAKE2는 원주율과 그 밖의 수학 상수의 소수 전개에서 상수를 도출합니다. Ed25519는 2^255 - 19라는 소수와, 다른 어떤 점에 대해서도 이산 로그를 알고 있지 않다는 것을 증명할 수 있는 기저점을 사용합니다(이 점은 문자열의 해시로 선택됩니다). 이러한 관행을 사용하면 누구나 상수가 비밀 지식을 바탕으로 선택되지 않았는지 확인할 수 있습니다.

2015년 12월, Juniper Networks는 2012년부터 ScreenOS(자사의 방화벽 OS)에 허가되지 않은 코드가 존재했다고 공개했습니다. 조사 결과 두 개의 백도어가 드러났습니다. 하나는 Dual EC DRBG의 Q 상수를 공격자가 제어하는 값으로 바꾸어, 해당 e를 알고 있는 공격자가 VPN 통신을 복호화할 수 있게 했고, 다른 하나는 SSH 관리용 암호에 삽입되어 있었습니다. Dual EC의 Q를 바꾼 방식은 특히 정교했습니다. Juniper는 이미 표준과 다른 Q 값을 사용하고 있었는데, 공격자는 이를 자신의 값으로 바꾸어 Dual EC의 트랩도어 구조를 두 번 악용했습니다. 이는 NIST의 P/Q 값에서 벗어난 구현이라도 자신의 Q를 삽입한 누구나 공격할 수 있음을 보여 주었습니다.

Dual EC DRBG 사건은 몇 가지 교훈을 줍니다. (1) 투명성: 암호 매개변수에는 검증 가능한 출처가 있어야 하며, 도출 과정에 대한 문서가 없는 상수는 의심해야 합니다. (2) 알고리즘 설계: 알고리즘에는 트랩도어를 숨길 수 있는 구조가 없어야 합니다(Dual EC의 Q/P 관계는 더 단순한 DRBG 설계에 비해 보안상 이점이 없습니다). (3) 이해 충돌: 표준화 기관은 정보 기관과의 이해 충돌을 엄격하게 관리해야 합니다. (4) 공동체 검토: 학계 암호학자들이 표준이 발표된 후가 아니라 발표되기 전에 우려를 제기할 수 있도록 권한을 부여해야 합니다. (5) 배포 단계의 경계: 조직은 암호 라이브러리가 어떤 DRBG를 사용하는지 감사하고, 권장되지 않는 선택지를 사전에 제거해야 합니다.

Dual EC가 제거된 후 권장되는 DRBG는 Hash_DRBG, HMAC_DRBG, CTR_DRBG를 중심으로 정리되었습니다. 오픈 소스 공동체는 NIST 표준을 신뢰하지 않는 상황을 위해 NIST 외 DRBG도 채택했습니다. ChaCha20 기반 RNG(Linux 커널에서 5.17부터 사용되며 OpenBSD와 libsodium에서도 사용됨)는 트랩도어 구조가 없는 단순한 스트림 암호인 ChaCha20을 사용하므로 백도어에 강한 것으로 널리 여겨집니다. Fortuna는 SP 800-90A보다 먼저 만들어졌으며 FreeBSD와 이전 버전의 macOS에서 사용되어 여전히 신뢰받고 있습니다. Dual EC 사건은 하드웨어 RNG(RDRAND)를 엔트로피 원천으로 사용하는 데에도 다시 관심을 불러일으켰습니다. 다만 RDRAND 역시 백도어가 삽입되었을 가능성이 있다는 의혹을 받았으므로, RDRAND만 사용하는 대신 소프트웨어 엔트로피와 혼합하라는 권고가 나왔습니다.

Dual EC DRBG 백도어를 가능하게 하는 수학적 관계는 무엇입니까?

Dual EC DRBG는 2006년 NIST SP 800-90A에서 표준화되었습니다. 쇼모와 퍼거슨은 2007년에 e(Q=e*P)를 알고 있으면 32바이트의 출력만으로 모든 출력을 예측할 수 있음을 증명했습니다. 2013년 스노든의 유출 문서는 암호 표준에 대한 NSA의 영향력을 확인해 주었습니다. RSA Security는 BSAFE에서 Dual EC를 기본값으로 설정하는 대가로 1천만 달러를 받았다고 알려졌습니다. NIST는 2014년 SP 800-90A Revision 1에서 Dual EC를 제거했습니다. 2015년 Juniper 사건은 실제 제품에서 트랩도어가 악용될 수 있음을 보여 주었습니다. 교훈은 NUMS 상수, 투명한 도출 과정, 이해 충돌 관리, 표준화 이후의 감사 절차입니다. ChaCha20 기반 RNG는 신뢰할 수 있는 대안으로 등장했습니다.