CVE-2008-0166-debian-openssl-predictable-prng.md

Debian OpenSSL 예측 가능한 PRNG (CVE-2008-0166)

메타데이터

항목	내용
CVE ID	CVE-2008-0166
영향 배포판/버전	Debian 계열 openssl 패키지 0.9.8c-1 ~ 0.9.8g-9 미만 (2006-09-17 ~ 2008-05-07 업로드분). Ubuntu 6.06/7.04/7.10/8.04 등 Debian 계열 파생 배포판 전반. 업스트림 OpenSSL 자체나 비-Debian 계열 배포판(Red Hat 등)은 영향받지 않음
공개일	2008-05-13 (DSA-1571-1)
CVSS	v2.0 7.8 HIGH (AV:N/AC:L/Au:N/C:C/I:N/A:N), v3.1 7.5 HIGH (AV:N/AC:L/PR:N/UI:N/S:U/C:H/I:N/A:N) — NVD 기준
CWE	CWE-338 (Use of Cryptographically Weak PRNG)
관련 CVE/Advisory	DSA-1571-1(openssl), DSA-1576-1(openssh, 약한 키 블랙리스트), USN-612-1~6, CERT/CC TA08-137A

개요

2006년 9월부터 2008년 5월까지, Debian 이 배포한 openssl 패키지는 Valgrind/Purify 같은 메모리 검사 도구가 내는 "초기화되지 않은 값 사용" 경고를 없애기 위해 Debian 자체 패치로 crypto/rand/md_rand.c 의 코드 한 줄을 주석 처리했다. 문제는 그 "초기화되지 않은 메모리"가 실제로는 OpenSSL 의 레거시 PRNG(ssleay_rand)가 의도적으로 엔트로피원으로 사용하던 스택/힙 버퍼 내용이었다는 점이다. 이 한 줄이 사라지면서 엔트로피 풀에 실질적으로 섞이는 가변 입력은 프로세스 ID(PID) 정도만 남았고, Linux 에서 PID 범위는 일반적으로 2 ~ 32768 (기본 pid_max 기준) 수준으로 매우 좁다. 그 결과 해당 기간 영향받는 Debian 계열 시스템에서 생성된 모든 RSA/DSA 키, SSH 호스트/사용자 키, SSL/TLS 인증서 키, X.509 CSR, OpenVPN 키 등이 "PID 값 하나당 키 하나"로 사실상 전수 열거(enumerate)가 가능한 수준까지 예측 가능해졌다. 근본 원인은 암호학적 결함이 아니라, 정적 분석 도구 경고를 그 코드가 왜 그렇게 작성됐는지 이해하지 못한 채 없앤 패키지 유지보수 프로세스의 실패였다.

사전 지식

CSPRNG 과 키 생성에 예측 불가능성이 필요한 이유

RSA/DSA 키 쌍, SSL/TLS 세션 키, SSH 호스트 키 같은 암호학적 키는 공격자가 그 값을 추측하거나 재현할 수 없어야 안전성이 성립한다. 이를 위해 키 생성 코드는 일반 PRNG(예: rand())가 아니라 CSPRNG(Cryptographically Secure PRNG)를 사용한다. CSPRNG 는 내부 상태(state)를 충분히 크고 예측 불가능한 엔트로피로 시딩(seeding)한 뒤, 그 상태를 해시나 블록암호 기반 함수로 반복 교반(mixing)해 출력을 뽑아낸다. 핵심 전제는 "공격자가 CSPRNG의 알고리즘 전체를 알고 있어도, 초기 시드값을 모르면 출력을 예측할 수 없다"는 것이다. 따라서 시드에 섞이는 엔트로피의 실질적인 양(비트 수)이 곧 그 시스템에서 생성 가능한 키 공간의 크기를 사실상 결정한다. 엔트로피원이 좁아지면 이론적인 키 공간(예: RSA-2048의 2^2048)과 무관하게, 실제로 그 시스템이 만들어낼 수 있는 키의 가짓수는 시드 후보의 가짓수로 붕괴한다.

md_rand.c 의 엔트로피 풀 모델

OpenSSL 0.9.8 계열이 쓰던 레거시 RNG 구현(crypto/rand/md_rand.c, 관용적으로 "ssleay_rand"라 부른다)은 커널의 /dev/random 같은 별도 하드웨어 엔트로피원에만 의존하지 않고, 애플리케이션이 여러 잡다한 소스를 RAND_add() / RAND_seed() 를 통해 계속 풀에 흘려 넣는 모델이었다. 대표적으로 다음과 같은 값들이 섞였다.

• 현재 시각(time(), gettimeofday()) — 초/마이크로초 단위
• 프로세스 ID(getpid()) 및 부모 PID
• /dev/urandom 이나 /dev/random 에서 읽은 바이트 (있는 경우)
• 애플리케이션이 RAND_add() 로 직접 넘기는 임의의 버퍼 — 여기에는 스택에 할당된 지역 변수나 힙 버퍼처럼, 호출 시점에 모든 바이트가 명시적으로 채워져 있지 않은 메모리도 포함되는 경우가 있었다

이 버퍼들은 내부적으로 MD5(또는 SHA-1) 같은 해시 함수의 MD_Update() 호출을 통해 내부 상태 버퍼(md_rand.c의 state[] 배열)에 누적 반영(mixing)된다. RAND_add() 의 설계 의도는, 호출자가 넘긴 값이 "완전히 검증된 고품질 엔트로피"라는 보장이 없어도, 그 바이트들을 해시 상태에 섞어 넣는 것 자체는 안전 쪽으로만 작용한다는 것이었다 — 진짜 무작위가 아니더라도 공격자가 정확히 예측하기 어려운 값이라면 섞어서 손해 볼 것이 없다는 논리다. 여기에는 프로세스 스택/힙의 그 순간 잔여값(다른 함수 호출들이 남긴 찌꺼기, 할당은 됐지만 아직 write 되지 않은 바이트 등)도 포함되었는데, 이는 당시 여러 오픈소스 RNG 구현에서 실제로 쓰이던 "공짜 엔트로피"기법이었다 — 값 자체의 무작위성을 증명할 수는 없지만, 공격자 입장에서 예측하기 어려운 부가 잡음으로 취급한 것이다. 다만 이 기법은 근본적으로 취약한 전제 위에 있다: 정적/동적 분석 도구 관점에서는 "초기화되지 않은 메모리 읽기"이고, 그 코드의 암호학적 의도를 모르는 사람이 보면 명백한 버그처럼 보인다는 점이다.

[ssleay_rand_add() 호출 시점 — 패치 이전, 의도된 형태]

  입력 소스들                       내부 해시 상태(state buffer)
 ┌────────────────┐
 │ time()          │──┐
 └────────────────┘  │
 ┌────────────────┐  │
 │ getpid()        │──┼──▶ MD_Update(&m, buf, j) ──▶ ┌───────────────┐
 └────────────────┘  │      (buf = 호출자가 넘긴      │  state[]      │
 ┌────────────────┐  │       버퍼 전체, 그 중 일부는  │  (MD5/SHA-1   │
 │ /dev/urandom    │──┤       "초기화 안 된" 스택/힙  │   내부 상태)  │
 └────────────────┘  │       잔여 바이트도 포함)       └───────────────┘
 ┌────────────────┐  │              │                        │
 │ 스택/힙 잔여값   │──┘              ▼                        ▼
 │ (의도된 엔트로피 │        해시로 섞여 들어가며         RAND_bytes() 로
 │  부가 소스)      │        "예측하기 어려운 잡음"을     꺼낼 때 매번 상태를
 └────────────────┘        엔트로피 추정치에 반영          다시 해시/갱신

Debian 패치 프로세스와 이번 사고의 구조적 원인

Debian/Ubuntu 는 업스트림 소프트웨어를 그대로 배포하지 않고, 배포판 고유의 빌드/보안/ 통합 요구를 반영한 패치 시리즈(quilt 패치 등)를 업스트림 소스 위에 얹어 패키징한다. 정상적인 프로세스라면, 이런 패치가 특히 암호 라이브러리처럼 민감한 컴포넌트의 핵심 로직을 건드릴 때는 (1) 왜 이 코드가 그렇게 작성됐는지 업스트림 개발자와 논의하고, (2) 변경이 안전하다는 확인을 받은 뒤에만 반영하며, (3) 가능하면 업스트림에도 같은 패치를 제안해 교차 검증받는 것이 바람직하다. 이번 사고에서 실제로 있었던 일은, Debian 유지보수자 Kurt Roeckx 가 Valgrind 경고를 없애기 위해 openssl-dev 메일링리스트에 문의했고, 업스트림 개발자 중 한 명(Ulf Möller)이 "그 특정 줄은 지워도 된다"는 취지로 답했지만, 실제로 패치가 건드린 곳은 그 특정 줄이 아니라 비슷하게 생겼지만 실제로는 진짜 엔트로피를 풀에 투입하는, 별개의 임계적인 줄이었다는 것이다. 즉 "정적 분석 도구가 경고하는 코드는 다 지워도 된다"는 피상적인 판단이, 그 코드의 암호학적 의도를 정확히 구분하지 못한 채 그대로 실행에 옮겨진 것이 근본 원인이다. 이는 하나의 코드 조각이 보안 관점에서 왜 그렇게 쓰였는지 충분히 이해하지 못한 상태로, 도구 경고를 없애는 것 자체를 목적으로 삼을 때 생기는 전형적인 실패 패턴이다.

취약점 분석

문제의 두 지점과 실제 타임라인

Debian 버그 #363516("valgrind-clean the RNG")은 2006-04-19 Richard Kettlewell 이 "OpenSSL 의 RNG 관련 Valgrind 경고가 이 라이브러리를 링크하는 모든 프로그램에 오탐성 경고를 흩뿌려서 진짜 버그를 찾기 어렵게 만든다"고 보고하며 시작됐다. 최초 제안은 crypto/rand/rand_unix.c 에서 임시 버퍼를 memset() 으로 0 초기화해 Valgrind 를 만족시키자는 것이었다. 유지보수자 Kurt Roeckx 는 이 제안 대신, 진짜 문제 지점이 crypto/rand/md_rand.c 안에 있다고 지적했다 — 해당 파일에는 다음 두 곳에 유사한 MD_Update(&m,buf,j); 호출이 있었다.

• ssleay_rand_add() 함수 안 (당시 기준 약 247번째 줄 부근) — 호출자가 RAND_add() 로 넘긴 입력 버퍼를 해시 상태에 섞어 넣는 호출
• ssleay_rand_bytes() 함수 안, #ifndef PURIFY ... #endif 로 감싸인 블록 (당시 기준 약 467번째 줄 부근, 주석에 /* purify complains */ 라고 적혀 있었음) — 출력을 뽑기 직전 스택 버퍼 잔여값을 한 번 더 섞어 넣는, PURIFY 빌드에서는 원래도 건너뛰도록 되어 있던 보조적인 호출

Debian 은 2006-05-14 에 openssl 0.9.8b-1 changelog 에 "Don't add uninitialised data to the random number generator. This stop valgrind from giving error messages in unrelated code. (Closes: #363516)" 라는 항목으로 이 변경을 반영했다. 이 시점의 실제 코드 변경분은 버그 스레드 상 별도 파일 경로에 놓여 빌드에 완전히 반영되지 않은 상태였고, Debian 자신의 사후 changelog 표현을 빌리면 이 문제는 이후 0.9.8c-1(2006-09-17, Kurt Roeckx)에서 "Move the modified rand/md_rand.c file to the right place, really fixing #363516." 라는 항목으로 실제 빌드에 적용되며 비로소 취약점이 살아 있는 패키지가 배포되기 시작했다.

ssleay_rand_add() 에서 사라진 한 줄의 의미

ssleay_rand_add() 는 RAND_add() 를 통해 호출자가 넘긴 버퍼(buf, 길이 j)를 받아 내부 해시 상태에 섞는, 대략 100줄 남짓의 함수다. 문제가 된 변경은 이 함수 본체 안에서 buf 를 실제로 해시 상태에 반영하는 MD_Update(&m,buf,j); 호출을 주석 처리(또는 #if 0 블록으로 비활성화)한 것이다. 이 한 줄이 사라지면, 함수는 buf, j 라는 파라미터를 받아놓고도 그 내용을 실질적으로 해시 상태에 반영하지 않는다 — 즉 RAND_add() 를 통해 애플리케이션이나 다른 OpenSSL 내부 코드가 아무리 많은 값(스택 잔여값, 파일에서 읽은 값 등)을 흘려보내도, 그 값들이 엔트로피 풀에 실제로 도달하지 못하고 버려지는 상태가 된 것이다. 2008-05-15 Bodo Moeller 가 openssl-dev 메일링리스트에서 지적한 바로는, 이 사고가 특히 뼈아팠던 이유는 Valgrind 가 실제로 경고했던 지점(randfile.c 에서 파일로부터 읽어들인, 일부만 채워진 버퍼를 RAND_add() 에 넘기는 코드)과, Debian 이 실제로 지운 지점(ssleay_rand_add() 안에서 그 버퍼를 풀에 섞는 핵심 로직)이 서로 다른 곳이었다는 점이다 — 겉보기엔 똑같이 생긴 MD_Update(&m,buf,j); 호출이 문맥에 따라 "제거해도 되는 부수적 호출"과 "제거하면 함수 자체를 무력화하는 핵심 호출"로 나뉘어 있었는데, 그 구분 없이 지워버린 것이다.

그 결과 시딩 이후 실질적으로 엔트로피 풀 상태에 가변성을 부여하는 입력은 사실상 getpid() 로 얻는 프로세스 ID 하나로 축소됐다. Linux 에서 PID 는 기본적으로 /proc/sys/kernel/pid_max (전형적으로 32768)보다 작은 정수이므로, 어떤 아키텍처·키 종류·키 길이 조합에 대해 실제로 만들어질 수 있는 키의 가짓수는 많아야 PID 범위 수준(약 3만여 개)으로 붕괴한다. 이는 이론적인 키 공간(RSA-2048 이라면 2^2048)과 비교할 수 없을 만큼 작을 뿐 아니라, 공격자가 모든 PID 값에 대해 미리 키를 생성해두는 "사전 계산 테이블(정확 매칭용 오프라인 데이터베이스)"을 실용적인 시간·저장공간 안에 만들 수 있는 규모다.

[패치 전(버그가 들어간 버전) — ssleay_rand_add() 내부, 실제 동작]

  RAND_add(buf, j, entropy_estimate)  호출
        │
        ▼
  ssleay_rand_add(buf, j, entropy_estimate)
        │
        │   MD_Update(&m, buf, j);   ← 이 줄이 주석 처리됨
        │   (buf 의 내용이 해시 상태에 전혀 반영되지 않음)
        │
        ▼
  state[] 내부 해시 상태: buf 로부터는 사실상 아무 것도 섞이지 않음
        │
        └── 실질적으로 남는 유일한 가변 입력: getpid() (PID)

  최종 결과:
  ┌───────────────────────────────────────────────────────┐
  │ 의도된 엔트로피 풀 상태 공간:  2^(수백~수천 비트)        │
  │ 실제로 도달 가능한 상태 공간:  PID 값의 가짓수 (~32768) │
  └───────────────────────────────────────────────────────┘
        │
        ▼
  같은 아키텍처/키 종류/키 길이라면, PID 가 같으면 키(쌍)도 동일하게 재현됨
  → RSA/DSA 키, SSH 호스트/사용자 키, X.509 CSR, OpenVPN 키 등이
    전수 열거(offline pre-computation) 가능한 수준으로 예측됨

DSA 키는 특히 더 취약했다. DSA 서명은 서명할 때마다 새로 뽑는 비밀 난수 k 에 의존하는데, 이 값이 예측 가능하거나 다른 서명에서 재사용되면 개인키 자체를 서명값에서 역산해낼 수 있다. 이 때문에 DSA-1571-1 은 "해당 기간 영향받는 Debian 계열 시스템에서 서명·인증 목적으로 사용된 모든 DSA 키는 손상된 것으로 간주해야 한다"고 명시했다 — 키 생성 시점뿐 아니라, 취약한 OpenSSL 로 서명 연산 자체를 수행한 이력이 있다면 그 자체로 위험하다는 뜻이다.

수정 방법

실제 Debian 수정

Debian 은 2008-05-07 openssl 0.9.8g-9 changelog 에 다음 항목으로 수정을 반영했다 (작성자 Kurt Roeckx).

openssl (0.9.8g-9) unstable; urgency=high

  [ Kurt Roeckx ]
  * ssleay_rand_add() really needs to call MD_Update() for buf.

 -- Kurt Roeckx <kurt@roeckx.be>  Wed, 07 May 2008 20:32:12 +0200

이 수정은 앞서 지워졌던 MD_Update(&m,buf,j); 호출을 ssleay_rand_add() 안에 다시 살려, 호출자가 RAND_add() 로 넘기는 버퍼 내용이 다시 실제로 해시 상태에 반영되도록 되돌리는 것이다. 즉 패치 자체는 "원래 있던 한 줄을 원래대로 복원"하는 최소 변경이며, 알고리즘을 새로 설계하거나 엔트로피 소스를 추가한 것이 아니다 — 2년 전에 실수로 제거된 한 줄을 되돌리는 것만으로 근본 원인이 해소된다는 점이 이 버그의 특징이다. DSA-1571-1 은 이 수정을 담은 openssl 0.9.8c-4etch3(stable/etch), 0.9.8g-9(unstable) 이상으로 업그레이드할 것을 권고했다.

[패치 후 — ssleay_rand_add() 내부, 복원된 동작]

  RAND_add(buf, j, entropy_estimate)  호출
        │
        ▼
  ssleay_rand_add(buf, j, entropy_estimate)
        │
        │   MD_Update(&m, buf, j);   ← 복원됨: buf 내용이 다시 해시 상태에 반영
        │
        ▼
  state[] 내부 해시 상태: time(), getpid(), /dev/urandom, 기타 RAND_add() 입력이
                          모두 다시 섞여 들어감
        │
        ▼
  ┌───────────────────────────────────────────────────────┐
  │ 실제로 도달 가능한 상태 공간이 PID 하나로 붕괴하지 않고 │
  │ 다시 여러 엔트로피 소스가 결합된 넓은 공간으로 회복됨   │
  └───────────────────────────────────────────────────────┘

"패치만으로는 끝나지 않는" 이유와 사후 대응

이 취약점의 특수성은, 패키지를 업그레이드해서 PRNG 를 고치는 것만으로는 과거에 이미 생성된 키까지 안전해지지 않는다는 데 있다. 취약한 기간 동안 생성된 키는 이미 파일로 저장되어 서버·클라이언트에 배포되었고, 그 값 자체가 예측 가능한 좁은 집합에서 나왔다는 사실은 패키지를 업그레이드해도 바뀌지 않는다. 그래서 Debian/Ubuntu 대응은 두 축으로 진행됐다.

1. 탐지 도구 배포: openssl-vulnkey(추후 ssh-vulnkey 로 OpenSSH 쪽에도 유사한 도구가 나왔다)는 알려진 취약 키(또는 취약 키에서 파생된 모듈러스/공개키 해시)의 블랙리스트를 아키텍처·키 길이·키 종류별로 미리 계산해 배포하고, 로컬에 있는 인증서· 요청·키 파일을 이 블랙리스트와 대조해 취약 여부를 판정하는 도구다. 이는 "PID 범위가 좁다"는 사실을 역이용해, 방어자 쪽에서도 가능한 모든 키를 미리 계산해두고 조회만 하면 되는 구조다.
2. 키 재발급 권고: DSA-1571-1 은 영향받는 기간에 생성된 모든 키 자료(SSH 키, SSL/TLS 인증서와 그 개인키, OpenVPN 키, DNSSEC 키 등)를 처음부터 다시 생성할 것을 강력히 권고했다. 특히 DSA 서명·인증에 쓰인 키는 키 생성 시점이 취약 기간 밖이더라도 취약한 OpenSSL 로 서명 연산을 수행한 이력이 있다면 손상된 것으로 간주해야 한다고 명시했다 (DSA 서명의 난수 k 재사용/예측 문제).

DSA-1576-1(openssh)은 OpenSSH 쪽에도 알려진 취약 키를 거부하도록 하는 관련 패치를 포함해 별도로 공개됐다.

공격 측 도구로는 H D Moore 가 아키텍처·키 종류·키 길이 조합별로 가능한 모든 키를 미리 계산해 공개한 자료가 잘 알려져 있으며(메타스ploit 진영에서 배포), 이는 이후 ssh-vulnkey/openssl-vulnkey 같은 방어 도구의 블랙리스트 생성에도 참고됐다. 이런 사전 계산 키 세트와 익스플로잇 스크립트를 재구성해 정리한 저장소가 공개돼 있다 (예: https://github.com/g0tmi1k/debian-ssh — 미검증, 참고용으로만 언급하며 본 보고서 작성 과정에서 실행하지 않았다).

참고 자료

• CVE-2008-0166 — NVD
• CVE-2008-0166 — CVE.org
• DSA-1571-1 openssl — Debian Security Advisory
• DSA-1571-1 원문 메일 — debian-security-announce
• DSA-1576-1 openssh — Debian Security Advisory (블랙리스트 연동)
• Debian Bug #363516 — valgrind-clean the RNG (원본 버그 스레드, 최초 패치 논의)
• CVE-2008-0166 — Debian Security Tracker
• openssl unstable changelog — ftp-master.debian.org (0.9.8c-1, 0.9.8g-9 항목 원문)
• Debian vulnerability has widespread effects — LWN.net
• research!rsc: Lessons from the Debian/OpenSSL Fiasco (Russ Cox)
• Bodo Moeller, openssl-dev 메일링리스트 — Valgrind/PURIFY 관련 정정 설명
• Gergely Riskó — Debian's OpenSSL maintainer should be changed (사후 비평, 타임라인 정리)
• US-CERT TA08-137A — Debian/Ubuntu OpenSSL Random Number Generator Vulnerability
• SSLkeys — Debian Wiki (사용자 대응 가이드, openssl-vulnkey 안내)
• openssl-vulnkey(1) — Ubuntu manpage
• g0tmi1k/debian-ssh — 취약 키 사전 계산/PoC 재구성 저장소 (GitHub, 미검증 3자 자료, 참고용 언급만)

미해결/불확실 지점

• md_rand.c 안에서 문제가 된 두 MD_Update(&m,buf,j); 호출의 정확한 줄 번호(약 247번째, 467번째 줄)는 2차 자료(LWN, 여러 사후 분석 글)에서 일관되게 언급되지만, 이는 당시 특정 소스 트리 버전 기준의 줄 번호이며 본 보고서 작성 과정에서 원본 패치 diff 파일(.dpatch/debian/patches 형태)의 실제 hunk 내용을 직접 원문으로 대조하지는 못했다. 확인 필요.
• 2006-05-14 반영된 0.9.8b-1 changelog 항목("Don't add uninitialised data...")과 2006-09-17 0.9.8c-1 changelog 항목("Move the modified rand/md_rand.c file to the right place, really fixing #363516.") 사이의 정확한 관계 — 즉 0.9.8b-1 시점에 이미 패치 파일 자체는 작성됐으나 빌드에 완전히 적용되지 않았고, 0.9.8c-1 에서 파일 경로 문제가 해결되며 비로소 실제 배포 바이너리에 반영됐다는 설명은 버그 스레드 후속 코멘트(Thijs Kinkhorst 등)를 근거로 하지만, 그 경로 불일치가 정확히 어떤 디렉터리/ 파일명 문제였는지는 원본 패치 파일을 직접 보지 못해 세부까지 확인하지 못했다.
• openssl-dev 메일링리스트에서 Debian 측 문의에 응답한 업스트림 개발자가 정확히 누구였고 (Ulf Möller로 다수 2차 자료에서 언급됨), 그 응답의 정확한 원문 인용은 여러 사후 분석글을 통해 재구성한 것이며 해당 메일 원문 아카이브를 직접 열람해 1차 확인하지는 못했다. 확인 필요.