암호학적으로 안전한 유사난수 생성기

암호학적으로 안전한 유사난수 생성기(Cryptographically secure pseudorandom number generator, CSPRNG) 또는 암호 유사난수 생성기(cryptographic pseudorandom number generator, CPRNG)는 암호학에 사용하기에 적합한 속성을 가진 유사난수 (PRNG)이다. 이는 암호 난수 생성기 (CRNG)라고도 불린다.

배경

대부분의 암호 애플리케이션은 예를 들어 다음과 같은 난수를 요구한다.

• 키 생성
• 초기화 벡터
• 논스
• ECDSA 및 RSASSA-PSS를 포함한 특정 서명 체계의 솔트
• 토큰 생성

이러한 애플리케이션에 필요한 난수의 "품질"은 다양하다. 예를 들어, 일부 암호 프로토콜에서 논스를 생성하는 데는 고유성만 필요하다. 반면에 마스터 키를 생성하려면 더 높은 품질, 예를 들어 더 많은 엔트로피가 필요하다. 그리고 원 타임 패드의 경우, 완벽한 비밀 유지의 정보 이론적 보장은 키 자료가 높은 엔트로피를 가진 진정한 무작위 소스에서 나오는 경우에만 유효하므로, 어떤 종류의 유사난수 생성기로는 충분하지 않다.

이상적으로 CSPRNG에서 난수 생성은 일반적으로 운영 체제의 무작위성 API와 같은 고품질 소스에서 얻은 엔트로피를 사용한다. 그러나 겉으로 보기에 독립적인 여러 프로세스에서 예상치 못한 상관 관계가 발견되었다. 정보 이론적 관점에서 생성될 수 있는 무작위성의 양인 엔트로피는 시스템에서 제공하는 엔트로피와 같다. 그러나 때로는 실제 상황에서 사용 가능한 엔트로피가 제공할 수 있는 것보다 더 많은 무작위성을 가진 숫자가 필요하다. 또한 실행 중인 시스템에서 무작위성을 추출하는 프로세스는 실제로는 느리다. 이러한 경우 CSPRNG를 사용할 수 있다. CSPRNG는 사용 가능한 엔트로피를 더 많은 비트에 걸쳐 "늘릴" 수 있다.

요구 사항

일반 PRNG의 요구 사항은 암호학적으로 안전한 PRNG에 의해서도 충족되지만, 그 반대는 사실이 아니다. CSPRNG 요구 사항은 두 가지 그룹으로 나뉜다.

1. 난수성 검정을 통과한다.
   • 모든 CSPRNG는 다음 비트 테스트를 충족해야 한다. 즉, 무작위 시퀀스의 처음 k비트가 주어졌을 때, (k+1)번째 비트를 50%보다 무시할 수 없을 정도로 더 나은 성공 확률로 예측할 수 있는 다항 시간 알고리즘은 없다.^[1]
   • 야오치즈는 1982년에 다음 비트 테스트를 통과하는 생성기는 난수성에 대한 다른 모든 다항 시간 통계 테스트를 통과할 것이라고 증명했다. 즉, 어떤 다항 시간 알고리즘도 RNG의 출력을 진정한 난수성과 구별할 수 없을 것이다.^[2]
   • 다항 시간 복잡도 대신, 실제에서 고려되는 또 다른 측정 기준은 구분기가 출력을 진정한 난수성과 구별하는 데 필요한 절대 연산 횟수이다. 연산 횟수로부터 특정 CSPRNG에 대한 구별 공격에 대한 보안 수준 (보안 비트)을 정의할 수도 있다.^[3][4]
2. 초기 또는 실행 상태의 일부가 공격자에게 노출되더라도 심각한 공격에 잘 견딘다.^[5]
   • 모든 CSPRNG는 "상태 손상 확장 공격"에 저항해야 한다.^[5]:4 상태의 일부 또는 전부가 공개되었거나 (또는 올바르게 추측되었을 경우) 공개 이전에 난수 스트림을 재구성하는 것은 불가능해야 한다. 또한 실행 중에 엔트로피 입력이 있는 경우, 입력 상태에 대한 지식을 사용하여 CSPRNG 상태의 미래 조건을 예측하는 것은 불가능해야 한다.
   • 예를 들어, 고려 중인 PRNG가 이진 확장 내의 알려지지 않은 지점부터 순서대로 원주율 비트를 계산하여 출력을 생성하는 경우, 정규수로 추정되므로 다음 비트 테스트를 잘 만족하고 통계적으로 무작위일 수 있다. 그러나 이 알고리즘은 암호학적으로 안전하지 않다. 원주율의 어떤 비트가 현재 사용 중인지 (즉, 알고리즘의 상태)를 알아낸 공격자는 이전의 모든 비트도 계산할 수 있을 것이다.

대부분의 PRNG는 CSPRNG로 사용하기에 적합하지 않으며 두 가지 모두에서 실패한다.

1. 대부분의 PRNG 출력은 다양한 통계 테스트에서 무작위로 보이지만, 결정론적인 역공학에 저항하지 못한다. 이러한 PRNG에 특별히 맞춰진 특수 통계 테스트는 난수가 진정으로 무작위가 아님을 보여줄 수 있다. 동시에 CSPRNG는 모든 통계 테스트에 저항하도록 설계되었으며 (그러한 테스트가 발견될 때까지 안전하다고 믿어짐), CSPRNG는 어떤 비암호화 애플리케이션에서도 어떤 진정한 난수 생성기도 대체할 수 있다.
2. 대부분의 PRNG의 경우, 상태가 노출되면 과거의 모든 난수를 역추적할 수 있어 공격자가 과거 메시지와 미래 메시지를 모두 읽을 수 있게 된다. CSPRNG는 이러한 유형의 암호 해독에 명시적으로 저항하도록 설계되었다.

정의

점근적 설정에서, 어떤 다항식 p에 대해 결정론적 다항 시간 계산 가능 함수 ${\displaystyle G_{k}\colon \{{\texttt {0}},{\texttt {1}}\}^{k}\to \{{\texttt {0}},{\texttt {1}}\}^{p(k)}}$의 패밀리는 입력의 길이를 늘리고 (${\displaystyle p(k)>k}$ for any k), 출력이 진정한 난수와 계산적으로 구별 불가능하다면 유사난수 (PRNG 또는 일부 참조에서는 PRG)이다. 즉, 구별자로서 1 또는 0을 출력하는 어떤 확률적 다항 시간 알고리즘 A에 대해

${\displaystyle \left|\Pr _{x\gets \{{\texttt {0}},{\texttt {1}}\}^{k}}[A(G(x))=1]-\Pr _{r\gets \{{\texttt {0}},{\texttt {1}}\}^{p(k)}}[A(r)=1]\right|<\mu (k)}$

어떤 무시할 수 있는 함수 ${\displaystyle \mu }$에 대해.^[6] (표기법 ${\displaystyle x\gets X}$는 x가 집합 X에서 균일하게 무작위로 선택됨을 의미한다.)

등가적인 특성화가 있다: 어떤 함수 패밀리 ${\displaystyle G_{k}\colon \{{\texttt {0}},{\texttt {1}}\}^{k}\to \{{\texttt {0}},{\texttt {1}}\}^{p(k)}}$에 대해, G는 G의 다음 출력 비트가 다항 시간 알고리즘에 의해 예측될 수 없는 경우에만 PRNG이다.^[7]

블록 길이 ${\displaystyle t(k)}$를 가진 전방 보안 PRNG는 ${\displaystyle G_{k}\colon \{{\texttt {0}},{\texttt {1}}\}^{k}\to \{{\texttt {0}},{\texttt {1}}\}^{k}\times \{{\texttt {0}},{\texttt {1}}\}^{t(k)}}$ 형태의 PRNG이다. 여기서 길이 k를 가진 입력 문자열 ${\displaystyle s_{i}}$는 주기 i에서의 현재 상태이고, 출력 (${\displaystyle s_{i+1}}$, ${\displaystyle y_{i}}$)는 다음 상태 ${\displaystyle s_{i+1}}$와 주기 i의 유사난수 출력 블록 ${\displaystyle y_{i}}$로 구성되며, 다음과 같은 의미에서 상태 손상 확장에 저항한다. 초기 상태 ${\displaystyle s_{1}}$이 ${\displaystyle \{{\texttt {0}},{\texttt {1}}\}^{k}}$에서 균일하게 무작위로 선택되는 경우, 어떤 i에 대해서도 시퀀스 ${\displaystyle (y_{1},y_{2},\dots ,y_{i},s_{i+1})}$는 ${\displaystyle (r_{1},r_{2},\dots ,r_{i},s_{i+1})}$와 계산적으로 구별 불가능해야 하며, 여기서 ${\displaystyle r_{i}}$는 ${\displaystyle \{{\texttt {0}},{\texttt {1}}\}^{t(k)}}$에서 균일하게 무작위로 선택된다.^[8]

어떤 PRNG ${\displaystyle G\colon \{{\texttt {0}},{\texttt {1}}\}^{k}\to \{{\texttt {0}},{\texttt {1}}\}^{p(k)}}$도 출력을 다음 상태와 실제 출력으로 분할함으로써 블록 길이 ${\displaystyle p(k)-k}$를 가진 전방 보안 PRNG로 전환될 수 있다. 이는 ${\displaystyle G(s)=G_{\texttt {0}}(s)\Vert G_{\texttt {1}}(s)}$로 설정함으로써 이루어지며, 여기서 ${\displaystyle |G_{\texttt {0}}(s)|=|s|=k}$이고 ${\displaystyle |G_{\texttt {1}}(s)|=p(k)-k}$이다. 그러면 G는 ${\displaystyle G_{\texttt {0}}}$를 다음 상태로, ${\displaystyle G_{\texttt {1}}}$를 현재 주기의 유사난수 출력 블록으로 하는 전방 보안 PRNG이다.

엔트로피 추출

 이 부분의 본문은 무작위성 추출기입니다.

산타와 바지라니는 약한 무작위성을 가진 여러 비트 스트림을 결합하여 더 높은 품질의 유사 무작위 비트 스트림을 생성할 수 있음을 증명했다.^[9] 그보다 더 일찍 존 폰 노이만은 간단한 알고리즘으로 모든 비트 스트림에서 상당한 양의 편향을 제거할 수 있음을 증명했으며,^[10] 이는 산타-바지라니 설계의 어떤 변형을 사용하기 전에 각 비트 스트림에 적용되어야 한다.

설계

CSPRNG 설계는 두 가지 클래스로 나뉜다.

1. 암호 및 암호화 해시와 같은 암호학적 프리미티브에 기반한 설계
2. 어렵다고 생각되는 수학적 문제에 기반한 설계

암호학적 프리미티브에 기반한 설계

• 안전한 블록 암호는 예를 들어 NIST SP 800-90A에서 CTR DRBG라고 부르는 특별한 구성체를 사용하여 카운터 모드로 실행함으로써 CSPRNG로 변환될 수 있다. CTR_DRBG는 일반적으로 고급 암호화 표준 (AES)을 사용한다.
  • AES-CTR_DRBG는 AES 암호화를 사용하는 시스템에서 난수 생성기로 자주 사용된다.^[11][12]
  • NIST CTR_DRBG 체계는 요청된 무작위성이 추가 주기를 실행하여 출력된 후 키를 삭제한다. 이는 성능 관점에서 낭비적이지만, 전방 보안에 즉각적인 문제를 일으키지는 않는다. 그러나 성능 영향을 인지하고, NIST는 양자 후 암호화 프로젝트 제출을 위해 "확장 AES-CTR-DRBG 인터페이스"를 권장한다. 이 인터페이스는 중간 삭제 없이 여러 세트의 무작위성을 생성할 수 있으며, 사용자가 요청 종료를 명시적으로 신호할 때만 삭제한다. 결과적으로 "확장 인터페이스"가 오용되면 키가 장기간 메모리에 남아 있을 수 있다. 최신 "빠른 키 삭제" RNG는 무작위성이 요청되는 즉시 키를 무작위성과 함께 삭제한다.^[13]
• 스트림 암호는 CSPRNG로 변환될 수 있다. 이는 RC4, ISAAC, ChaCha20 등에서 이루어졌다.
• 암호학적으로 안전한 해시는 예를 들어 NIST가 Hash DRBG라고 부르는 구성체를 사용하여 좋은 CSPRNG의 기반이 될 수도 있다.
• HMAC 프리미티브는 CSPRNG의 기반으로 사용될 수 있으며, 예를 들어 NIST가 HMAC DRBG라고 부르는 구성체의 일부로 사용될 수 있다.

수론적 설계

• 블룸 블룸 슈브 알고리즘은 2차 잉여 문제의 어려움에 기반한 보안 증명을 가지고 있다. 그 문제를 해결하는 유일한 알려진 방법이 모듈러스를 인수분해하는 것이기 때문에, 일반적으로 소인수분해의 어려움이 블룸 블룸 슈브 알고리즘에 대한 조건부 보안 증명을 제공한다고 간주된다. 그러나 이 알고리즘은 매우 비효율적이므로 극도의 보안이 필요하지 않다면 비실용적이다.
• 블룸-미칼리 알고리즘은 이산 로그 문제의 어려움에 기반한 보안 증명을 가지고 있지만 역시 매우 비효율적이다.
• 서티콤의 대니얼 브라운은 결정성 디피-헬만 가정, x-로그 문제, 그리고 잘린 점 문제의 가정된 난이도에 기반하여 Dual EC DRBG에 대한 2006년 보안 증명을 작성했다. 2006년 증명은 Dual_EC_DRBG 표준보다 낮은 outlen (반복당 제공되는 비트량)과 Dual_EC_DRBG 표준의 P와 Q (2013년에 NSA에 의해 백도어되었을 가능성이 높은 것으로 드러남)가 백도어되지 않은 값으로 대체된다는 것을 명시적으로 가정한다.

실용적인 체계

"실용적인" CSPRNG 체계는 CSPRNG 알고리즘뿐만 아니라 시드를 비밀로 유지하면서 초기화("시드")하는 방법을 포함한다. 다음과 같은 여러 체계가 정의되었다.

• 유닉스 계열 시스템의 /dev/random 구현.
  • 야로는 시드 입력의 엔트로피 품질을 평가하려고 시도하며, 내부적으로 SHA-1 및 3DES를 사용한다. 야로는 2019년 12월까지 macOS 및 다른 애플 OS에서 사용되었으며, 그 이후 포르투나로 전환했다.
  • 포르투나는 야로의 후속작으로, 입력의 엔트로피 품질을 평가하려고 시도하지 않는다. SHA-256과 "모든 좋은 블록 암호"를 사용한다. 포르투나는 FreeBSD에서 사용된다. 애플은 2019년 12월경부터 대부분 또는 모든 애플 OS에 포르투나를 적용했다.
  • 리눅스 커널 CSPRNG는 ChaCha20을 사용하여 데이터를 생성하고,^[14] BLAKE2s를 사용하여 엔트로피를 흡수한다.^[15]
• arc4random, /dev/random에서 시드되는 유닉스 계열 시스템의 CSPRNG이다. 원래는 RC4에 기반했지만, 현재 모든 주요 구현은 ChaCha20을 사용한다.^[16][17][18]
• 마이크로소프트의 CryptoAPI의 일부인 CryptGenRandom은 윈도우에서 제공된다. 윈도우의 여러 버전은 다른 구현을 사용한다.
• ANSI X9.17 표준 (금융 기관 키 관리 (도매))은 FIPS 표준으로도 채택되었다. 이는 TDEA (키 옵션 2) 키 번들 k와 64비트 난수 시드 s의 초기값을 입력으로 받는다.^[19] 난수가 필요할 때마다 다음 단계를 실행한다.
  1. 가능한 최대 해상도로 현재 날짜/시간 D를 얻는다.
  2. 임시 값 t = TDEA_k(D)를 계산한다.
  3. 난수 값 x = TDEA_k(s ⊕ t)를 계산한다. 여기서 ⊕는 비트 단위 배타적 논리합을 나타낸다.
  4. 시드 s = TDEA_k(x ⊕ t)를 업데이트한다.

분명히 이 기술은 어떤 블록 암호에도 쉽게 일반화될 수 있다. AES가 제안되었다.^[20] 키 k가 유출되면 전체 X9.17 스트림을 예측할 수 있다. 이 약점은 야로를 생성한 이유로 언급된다.^[21]

위에서 언급된 모든 체계는 X9.17을 제외하고 CSPRNG의 상태를 추가적인 엔트로피 소스와 혼합한다. 따라서 이들은 출력이 초기 상태에 의해 완전히 결정되지 않는다는 의미에서 "순수한" 유사난수 생성기가 아니다. 이 추가는 초기 상태가 손상되더라도 공격을 방지하는 것을 목표로 한다.^[a]

표준

여러 CSPRNG가 표준화되었다. 예를 들어:

• FIPS 186-4^[23]
• NIST SP 800-90A

이 철회된 표준에는 네 가지 PRNG가 있다. 그 중 두 가지는 논란의 여지가 없고 입증된 것이다: Hash_DRBG^[24] 및 HMAC_DRBG^[25]로 명명된 CSPRNG.

이 표준의 세 번째 PRNG인 CTR DRBG는 카운터 모드로 실행되는 블록 암호를 기반으로 한다. 논란의 여지가 없는 설계를 가지고 있지만, 이 PRNG에서 출력되는 비트 수가 기본 블록 암호의 블록 크기 비트의 2제곱보다 클 경우, 구별 공격 측면에서 기본 블록 암호의 보안 수준보다 약하다는 것이 입증되었다.^[26]

이 PRNG에서 출력되는 최대 비트 수가 2^blocksize와 같을 때, 결과 출력은 키 크기가 생성할 것으로 예상되는 수학적으로 예상되는 보안 수준을 제공하지만, 출력은 진정한 난수 생성기와 구별할 수 없다는 것이 나타났다.^[26] 이 PRNG에서 출력되는 최대 비트 수가 그것보다 적을 때, 예상되는 보안 수준이 제공되고 출력은 진정한 난수 생성기와 구별할 수 없는 것으로 나타난다.^[26]

다음 개정판에서는 CTR_DRBG에 대한 주장된 보안 강도가 총 생성 요청 수와 생성 요청당 제공되는 비트 수를 제한하는 것에 달려 있다고 명시되어 있다.

이 표준의 네 번째이자 마지막 PRNG는 Dual EC DRBG로 명명되었다. 이것은 암호학적으로 안전하지 않은 것으로 밝혀졌으며, 클렙토그래피 NSA 백도어가 있는 것으로 믿어진다.^[27]

• NIST SP 800-90A Rev.1

이는 본질적으로 Dual_EC_DRBG가 제거된 NIST SP 800-90A이며, 철회된 표준의 대체품이다.

• ANSI X9.17-1985 Appendix C
• ANSI X9.31-1998 Appendix A.2.4
• ANSI X9.62-1998 Annex A.4, ANSI X9.62-2005, Annex D (HMAC_DRBG)에 의해 폐기됨

좋은 참고 자료는 NIST에서 관리한다.^[28]

새로운 CSPRNG 설계의 통계적 테스트를 위한 표준도 있다.

• 암호화 애플리케이션을 위한 난수 및 유사난수 생성기 통계 테스트 스위트, NIST 특별 출판물 800-22.^[29]

보안 결함

Dual_EC_DRBG PRNG의 NSA 클렙토그래피 백도어

 이 부분의 본문은 Dual_EC_DRBG입니다.

가디언과 뉴욕 타임스는 2013년에 NSA가 NIST SP 800-90A의 유사난수 (PRNG)에 백도어를 삽입하여, NSA가 Dual EC DRBG의 도움을 받아 암호화된 자료를 쉽게 해독할 수 있게 했다고 보도했다. 두 신문은 독립 보안 전문가들이 오랫동안 의심했던 것처럼,^[30][31] NSA가 CSPRNG 표준 800-90에 취약점을 심고 있었다고 보도했으며,^[32] 이는 에드워드 스노든이 가디언에 유출한 일급 기밀 문서 중 하나에 의해 처음으로 확인되었다. NSA는 2006년에 자체 버전의 NIST 보안 표준 초안을 전 세계적으로 승인받기 위해 은밀히 작업했다. 유출된 문서에는 "결국 NSA가 유일한 편집자가 되었다"고 명시되어 있다. 클렙토그래피 백도어 및 Dual_EC_DRBG의 다른 알려진 중요한 결함의 잠재력에도 불구하고, RSA 시큐리티와 같은 여러 회사는 2013년에 백도어가 확인될 때까지 Dual_EC_DRBG를 계속 사용했다.^[33] RSA 시큐리티는 이를 위해 NSA로부터 1,000만 달러를 받았다.^[34]

DUHK 공격

2017년 10월 23일, 펜실베이니아 대학교와 존스 홉킨스 대학교의 암호학자인 샤난 코니, 매튜 D. 그린, 나디아 헤닝거는 WPA2에 대한 DUHK(Don't Use Hard-coded Keys) 공격의 세부 정보를 발표했다. 이 공격은 하드웨어 공급업체가 ANSI X9.31 RNG 알고리즘에 하드코딩된 시드 키를 사용하여 "공격자가 암호화된 데이터를 무차별 대입하여 나머지 암호화 매개변수를 발견하고 웹 세션 또는 가상사설망 (VPN) 연결을 암호화하는 데 사용된 마스터 암호화 키를 추론할 수 있다"고 밝혔다.^[35][36]

일본 PURPLE 암호기

제2차 세계 대전 중, 일본은 외교 통신을 위해 암호기를 사용했다. 미국은 주로 사용된 "키 값"이 불충분하게 무작위였기 때문에 이를 해독하고 메시지를 읽을 수 있었다.^[37]

내용주

1. CSPRNG 초기화 후 엔트로피 혼합 사용은 대니얼 J. 번스타인에 의해 의문이 제기되었다.^[22]