암호화된 보안 유사성 번호 생성기

암호학적으로 안전한 유사수신기(CSPRNG) 또는 암호 유사수신기(CPRNG)^[1]는 암호학에서 사용하기에 적합한 속성을 가진 유사수신기(PRNG)이다. 또한 암호 난수 생성기(CRNG)라고도 한다(난수 생성 § "True" 대 의사 난수 참조).^[2][3]

대부분의 암호 애플리케이션은 다음과 같은 임의의 번호를 필요로 한다.

• 키 생성
• 논스
• ECDSA, RSASASA-PSS를 포함한 특정 서명 체계의 소금

이러한 애플리케이션에 필요한 무작위성의 "품질"은 다양하다. 예를 들어, 일부 프로토콜에서 noce를 만드는 것은 고유성만 필요로 한다. 반면에 마스터 키의 생성은 엔트로피와 같은 높은 품질을 필요로 한다. 그리고 일회용 패드의 경우, 완벽한 비밀 유지의 정보-이론적 보증은 핵심 자료가 엔트로피가 높은 진정한 무작위 출처에서 나온 것이기 때문에, 따라서 어떤 종류의 가성수 생성기가 불충분할 경우에만 유지된다.

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

요구 사항들

일반 PRNG의 요건도 암호화된 보안 PRNG에 의해 충족되지만, 그 반대는 사실이 아니다. CSPRNG 요건은 두 그룹으로 나뉜다. 첫째, 통계적 무작위성 시험을 통과한다는 것과 둘째, 공격자가 초기 상태나 실행 상태의 일부를 사용할 수 있는 경우에도 심각한 공격 하에서 잘 버틸 수 있다는 것이다.^{[citation needed]}

• 모든 CSPRNG는 다음 비트 시험을 만족해야 한다. 즉, 첫 번째가 주어진다면 k 랜덤 시퀀스의 비트, 예측 가능한 다항식 시간 알고리즘은 없다.k +^[4]1) 성공 확률이 50% 이상인 1/2비트 비트앤드류 야오는 1982년에 다음 비트 시험을 통과한 발전기가 임의성에 대한 다른 모든 다항 시간 통계 시험을 통과할 것이라는 것을 증명했다.^[5]
• 모든 CSPRNG는 "국가 타협 확장"을 견뎌야 한다. 그 상태의 일부나 전부가 밝혀진 경우(또는 정확하게 추측된 경우), 그 폭로에 앞서 무작위 숫자의 흐름을 재구성하는 것은 불가능해야 한다. 또한 실행 중에 엔트로피 입력이 있는 경우 CSPRNG 상태의 미래 조건을 예측하기 위해 입력 상태 지식을 사용하는 것이 불가능해야 한다.

예: 고려 중인 CSPRNG가 2진 확장 시 일부 미지의 지점에서 시작하여 순차적으로 π의 비트를 계산하여 출력을 생성하는 경우, 다음 비트 시험을 충분히 만족시킬 수 있으며 따라서 π은 무작위 시퀀스로 나타나기 때문에 통계적으로 무작위일 수 있다. (예를 들어 π이 정규수일 경우 이는 보장된다.) 그러나 이 알고리즘은 암호학적으로 안전하지 않다. 현재 어떤 pi 비트(즉, 알고리즘의 상태)가 사용 중인지 결정하는 공격자는 이전의 모든 비트도 계산할 수 있을 것이다.

대부분의 PRNG는 CSPRNG로 사용하기에 적합하지 않으며 두 계수에서 모두 실패한다. 첫째, 대부분의 PRNG 출력은 다양한 통계적 시험에 무작위로 나타나지만, 결정된 역 엔지니어링에 저항하지 않는다. 전문화된 통계 시험은 실제로 무작위 번호가 아닌 무작위 번호를 보여주는 그러한 PRNG에 특별히 맞춰져 있는 것을 발견할 수 있다. 둘째, 대부분의 PRNG의 경우, 상태가 공개되면 과거의 임의의 숫자를 모두 소급하여 공격자가 미래의 메시지뿐만 아니라 과거의 모든 메시지를 읽을 수 있게 된다.

CSPRNG는 이러한 유형의 암호 분석에 저항하도록 명시적으로 설계된다.

정의들

In the asymptotic setting, a family of deterministic polynomial time computable functions ${\displaystyle G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}}$ for some polynomial p, is a pseudorandom number generator (PRNG, or PRG in some references), if it stretches the length of its input (> > k $([\$displaystyle $p(k)>k})$ 및 그 출력이 계산상 참 무작위성과 구별할 수 없는 경우, 즉 1 또는 0을 구분자로 출력하는 확률론적 다항 시간 알고리즘 A의 경우,

${\displaystyle \왼쪽 \Pr_{0,1\}^{k}[A(G(x)]=1]-\Pr_{r\gets \{0,1\}^{p(k)}}}}}[A(r)=1]\오른쪽 <\mu(k)}$

일부 무시해도 될 함수 $[\displaystyle \mu }$^[6]. (표기법 $x{\displaystyle }$ ${\displaystyle \leftarrow }$ X$${\$displaystyle$ x$\gets X}$는 x가 설정된 X에서 무작위로 균일하게 선택됨을 의미한다$$.)

등가 특성화가 있다. ${\displaystyle {모든}_{}}$ 함수 패밀리 G $k{\displaystyle {}_{}}$:${\displaystyle }${ 0${\displaystyle ,}$ ${\displaystyle 1}$ ${\displaystyle {}^{}}$ ${\displaystyle k^{}}$→${\displaystyle }${ ${\displaystyle 0,}$ ${\displaystyle 1}$ ${\displaystyle {}^{}}$ ${\displaystyle p^{}}$ (${\displaystyle {}^{}}$)${\$k}\$colon \{0,$1\}^{$k}\to \{0,1\}^{p($k)}}}에 대해$,$ G의 다음 출력 비트를 다항 시간 알고리즘으로 예측할 수 없는 경우에만 G가 PRNG이다.^[7]

A forward-secure PRNG with block length ${\displaystyle t(k)}$ is a PRNG ${\displaystyle G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{k}\times \{0,1\}^{t(k)}}$, where the input string ${\displaystyle s_{i}}$ with length k is the current state at period i, and 출력(${\displaystyle {}_{}}$ ${\displaystyle i_{}}$+ ${\displaystyle 1_{}}$ ${\$ y ${\displaystyle i_{}}$ ${\$${i}})$은 다음 뜻으로 상태 절충 연장을 견디는 기간 i의$$ 다음 ${\displaystyle {상태}_{}}$i + ${\displaystyle 1_{}}$${\$와 periiiiiiiii의 가산덤 출력 블록 y ${\displaystyle i_{}}$로 구성된다. If the initial state ${\displaystyle s_{1}}$ is chosen uniformly at random from ${\displaystyle \{0,1\}^{k}}$, then for any i, the sequence ${\displaystyle (y_{1},y_{2},\dots ,y_{i},s_{i+1})}$ must be computationally indistinguishable from ${\displaystyle (r_1,{}_{}}$${\displaystyle r_{}}$$$ ${\displaystyle {2\mathrm{}}_{}}$…${\displaystyle }$, ${\displaystyle {}_{}}$ ${\displaystyle i_{}}$, s ${\displaystyle {\mathrm{i}}_{}}$+ 1${\displaystyle {}_{}}$) ${\displaystyle (r_{1},r_{2},\displaystyle$ r_{$i},$$s_{i+1$ 여기서 $r{\displaystyle {}_{}}$ i {${\displaystyle 0},{\displaystyle 1}$ ${\displaystyle {}^{}}$ ${\displaystyle {t(k}^{}}$) ${\$^[8]

Any PRNG ${\displaystyle G\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}}$ can be turned into a forward secure PRNG with block length ${\displaystyle p(k)-k}$ by splitting its output into the next state and the actual output. $이것$은 G${\displaystyle }$(${\displaystyle s}$ )${\displaystyle }$= ${\displaystyle {G\mathrm{}}_{}}$ 0${\displaystyle {}_{}}$( ${\displaystyle s}$) ${\displaystyle \Vert }$ ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$( ${\displaystyle s}$ )${\displaystyle$G ($s)=$를 설정함으로써 이루어진다.$G_{0}(s)\Vert G_{1}(s)}$, in which ${\displaystyle G_{0}(s) = s =k}$ and ${\displaystyle G_{1}(s) =p(k)-k}$; then G is a forward secure PRNG with ${\displaystyle G_{0}}$ as the next state and ${\displaystyle G_{1}}$ as the pseudorandOm 출력 블록.

엔트로피 추출

산타와 바지라니는 랜덤성이 약한 여러 비트 스트림이 결합되어 더 높은 품질의 준랜덤 비트 스트림을 생산할 수 있다는 것을 증명했다.^[9] 이보다 앞서 존 폰 노이만은 단순한 알고리즘이 어떤 비트 스트림에서 상당한 양의 편향을 제거할 수 있다는 것을 증명했는데,^[10] 산타-바지라니 설계의 어떤 변형을 사용하기 전에 각 비트 스트림에 적용해야 한다.

디자인

아래 논의에서 CSPRNG 설계는 세 가지 등급으로 나뉜다.

1. 암호 및 암호 해시와 같은 암호 원시성에 기반한 것,
2. 수학적인 문제에 기초하는 사람들은 어렵다고 생각되고,
3. 특수 목적의 설계

마지막 엔트로피는 가용할 때 추가 엔트로피를 도입하는 경우가 많으며, 엄격히 말하면, 이들의 출력이 초기 상태에 의해 완전히 결정되지 않기 때문에 "순수" 유사수 생성기가 아니다. 이 추가는 초기 상태가 손상되더라도 공격을 방지할 수 있다.

암호화 기본 요소 기반 설계

• 보안 블록 암호는 카운터 모드로^{[dubious – discuss]} 실행하면 CSPRNG로 변환할 수 있다. 임의의 키를 선택하고 0을 암호화한 다음 1을 암호화한 다음 2를 암호화하면 된다. 카운터는 0이 아닌 임의의 번호로 시작할 수도 있다. 생일 문제 이후 충돌 블록이 발생할^n/2 가능성이 높은 반면 CTR 모드의 블록 암호는 동일한 블록을 출력하지 않는다. 64비트 블록 암호의 경우, 이것은 안전한 출력 크기를 몇 기가바이트로 제한하고 128비트 블록은 일반적인 애플리케이션에 영향을 미치지 않을 정도로 제한적이다. 그러나 단독으로 사용할 경우 CSPRNG의 모든 기준을 충족하지 못한다. CSPRNG는 "국가 타협 확장"에 대해 강하지 않기 때문이다(이 경우 카운터와 키) 국가에 대한 지식으로 과거의 모든 출력을 예측할 수 있다.
• 암호화된 보안 카운터의 해시는 어떤 경우에는 좋은 CSPRNG로 작용할 수도 있다. 이 경우, 이 카운터의 초기 값은 무작위적이고 비밀스러운 것도 필요하다. 그러나 이러한 방식으로 사용하기 위한 이러한 알고리즘에 대한 연구는 거의 없었고, 적어도 일부 저자들은 이러한 사용에 대해 경고한다.^[vague][11]

• 대부분의 스트림 암호는 일반 텍스트와 결합(대부분 항상 XORed)된 유사 비트 스트림을 생성하여 작동한다. 카운터에서 암호를 실행하면 새로운 유사 데이터 스트림이 반환되며, 아마도 더 긴 기간이 있을 것이다. 암호는 반드시 이런 경우는 아니지만, 원래의 스트림이 좋은 CSPRNG일 경우에만 안전할 수 있다(RC4 암호 참조). 다시 말하지만 초기 상태는 비밀에 부쳐져야 한다.

숫자-이론적

• 블럼 블럼 슈브 알고리즘은 2차 잔류성 문제의 난이도에 근거한 보안 증거를 가지고 있다. 그 문제를 해결하는 유일한 방법은 계수를 인자화하는 것이기 때문에 일반적으로 정수 인자화의 난이도는 블럼 블럼 슈브 알고리즘에 대한 조건부 보안 증거를 제공하는 것으로 간주된다. 그러나 알고리즘은 매우 비효율적이며 따라서 극단적인 보안이 필요하지 않는 한 비현실적이다.
• 블럼-미칼리 알고리즘은 이산 로그 문제의 난이도에 근거한 보안 증거를 가지고 있지만 또한 매우 비효율적이다.
• Certicom의 Daniel Brown은 Dual_에 대한 2006년 보안 증명을 작성했다.EC_DRBG, Decisional Diffie–의 가정된 경도에 기초함헬맨 가정, x-logarithm 문제, 잘린 점 문제. 2006년 증명서는 명시적으로 Dual_보다 낮은 초과 기간을^{[clarification needed]} 가정한다.EC_DRBG 표준 및 Dual_의 P와 Q 표준EC_DRBG 표준(NSA에 의해 백도어될 가능성이 있는 것으로 2013년에 공개됨)은 백도어드되지 않은 값으로 대체된다.

특수 디자인

암호화된 보안성을 갖도록 설계된 실용 PRNG는 다음과 같다.

• 입력의 이방성 품질을 평가하려는 야로 알고리즘. 야로우는 2019년 12월경까지 맥OS와 다른 애플 OS에서 사용된다. 이후 애플은 포투나로 전환했다. ( /dev/random 참조).
• ChaCha20 알고리즘은 OpenBSD(버전 5.4),^[12] NetBSD(버전 7.0),^[13] FreeBSD(버전 12.0)에서 RC4를 대체했다.^[14]
• 차차20은 버전 4.8에서도 Linux에서 SHA-1을 대체했다.^[15]
• 야로우의 후속인 Fortuna 알고리즘으로, 입력물의 이방성 품질을 평가하려고 시도하지 않는다. Fortuna는 FreeBSD에서 사용된다. 애플은 2019년 12월경부터 대부분의 애플 OS를 포투나로 바꿨다.
• 마이크로소프트의 암호 응용 프로그램 프로그래밍 인터페이스에서 제공하는 CryptGenRandom 함수
• RC4 암호의 변종 기반 IACH
• NIST Statistical Test Suite에 기반한 진화 알고리즘으로 조정된 선형 피드백 시프트 레지스터.^[16][17]
• arc4random
• AES-CTR DRBG는 AES 암호화를 사용하는 시스템에서 랜덤 숫자 생성기로 자주 사용된다.^[18][19]
• FIPS 표준으로도 채택된 ANSI X9.17 표준(금융기관 키 관리(도매)). TDEA(키잉 옵션 2) 키 번들 k와 (초기 값) 64비트 랜덤 시드를 입력하는 것으로 한다.^[20] 무작위 번호가 필요할 때마다 다음과 같이 처리한다.
  • 현재 날짜/시간 D를 가능한 최대 해상도로 확보한다.
  • 임시 값 t = TDEA_k(D) 계산
  • 랜덤 값 x = TDEA_k(s s t)를 계산한다. 여기서 ⊕은 비트 배타적임을 나타낸다.
  • 시드 s 업데이트 = TDEA_k(x ⊕ t)

분명히, 이 기술은 어떤 블록 암호에도 쉽게 일반화된다; AES가 제안되었다.^[21]

표준

몇몇 CSPRNG가 표준화되었다. 예를 들어,

• FIPS 186-4
• NIST SP 800-90A:

이 철회된 표준은 4개의 PRNG를 가지고 있다. 그 중 두 가지는 논란의 여지가 없고 입증되었다: CSPRNGs 이름이 Hash_DRBG이고^[22] HMAC_DRBG이다.^[23]

이 표준의 세 번째 PRNG인 CTR DRBG는 카운터 모드에서 실행되는 블록 암호에 기초한다. 논란의 여지가 없는 설계를 가지고 있지만, 이 PRNG에서 출력되는 비트 수가 2보다 클 때, 비트 단위의 기본 블록 암호의 전력에 비해, 기본 블록 암호의 보안 수준보다, 공격을 구분하는 면에서 약하다는 것이 증명되었다.^[24]

이 PRNG에서 출력되는 최대 비트 수가 2와^blocksize 같을 때, 결과 출력은 키 크기가 생성할 것으로 예상되는 수학적으로 기대되는 보안 수준을 전달하지만, 출력은 실제 무작위 숫자 생성기와 구별할 수 없는 것으로 나타났다.^[24] 이 PRNG로부터의 최대 비트 출력 수가 그것보다 적을 때, 예상된 보안 레벨이 전달되고 출력은 실제 무작위 숫자 생성기와 구별할 수 없는 것으로 보인다.^[24]

CTR_DRBG에 대한 보안강도를 주장하는 것은 생성 요청당 제공된 비트와 총 생성 요청 수를 제한하는 것에 달려 있다.

이 표준의 네 번째 및 최종 PRNG는 Dual_로 명명된다.EC_DRBG. 암호화된 안전성이 없는 것으로 나타났으며, NSA 백도어가 있는 것으로 추정된다.^[25]

• NIST SP 800-90A 개정판 1: 이것은 본질적으로 NIST SP 800-90A with Dual_이다.EC_DRBG는 철회된 표준의 대체품이다.
• ANSI X9.17-1985 부록 C
• ANSI X9.31-1998 부록 A.2.4
• ANSI X9.62-1998 부록 A.4, ANSI X9.62-2005, 부록 D(HMAC_DRBG)에 의해 폐기됨

NIST는 좋은 참조를 유지한다.

또한 새로운 CSPRNG 설계의 통계적 시험에 대한 표준도 있다.

• 무작위 및 유사성 번호 생성기를 위한 통계 테스트 제품군, NIST 특별 간행물 800-22.

듀얼의 NSA 도벽 백도어EC_DRBG PRNG

가디언과 뉴욕 타임즈는 2013년에 국가안보국(NSA)이 NIST SP 800-90A의 유사 암호 번호 생성기(PRNG)에 백도어를 삽입하여 NSA가 Dual_의 도움으로 암호화된 물질을 쉽게 해독할 수 있도록 했다고 보도했다.EC_DRBG. 두 논문 모두 독립된 보안 전문가들이 오랫동안 의심했던 대로 ^[28]NSA가 CSPRNG 표준 800-90에 취약점을 도입하고 있다고 보도했는데^[26][27], 이는 에드워드 스노든이 가디언에 유출한 최고 기밀 문서 중 하나에서 처음으로 확인되었다. NSA는 2006년 NIST 초안 보안 표준의 자체 버전을 전세계적으로 사용하도록 승인받기 위해 은밀하게 작업했다. 유출된 문건에는 "결국 NSA가 단독 편집자가 됐다"고 적혀 있다. 도벽 백도어 및 Dual_의 기타 중요한 결함에 대한 알려진 잠재력에도 불구하고EC_DRBG, RSA Security와 같은 여러 회사에서 Dual_을 계속 사용함2013년 백도어가 확정되기 전까지 EC_DRBG.^[29] RSA Security는 NSA로부터 1000만 달러의 대금을 받았다.^[30]

보안 결함

DUHK 공격

On October 23, 2017, Shaanan Cohney, Matthew Green, and Nadia Heninger, cryptographers at The University of Pennsylvania and Johns Hopkins University released details of the DUHK (Don't Use Hard-coded Keys) attack on WPA2 where hardware vendors use a hardcoded seed key for the ANSI X9.31 RNG algorithm, stating "an attacker can brute-force encrypted 데이터: 나머지 암호화 매개 변수를 검색하고 웹 세션이나 VPN(가상 사설망) 연결을 암호화하는 데 사용되는 마스터 암호화 키를 추론하는 것."^[31][32]

일본 퍼플 암호기

제2차 세계 대전 동안, 일본은 외교 통신을 위해 암호기를 사용했다; 미국은 그것을 해독하고 그것의 메시지를 읽을 수 있었는데, 주로 사용된 "핵심 가치"가 불충분하게 무작위였기 때문이다.

참조

외부 링크

Wikibook 암호화에는 다음과 같은 주제의 페이지가 있다: 난수 생성

• RFC 4086, 보안을 위한 무작위 요구사항
• 암호화된 보안으로 예측할 수 없는 무작위 번호를 제공하는 Java "entropy 풀".
• 암호화된 강력한 의사 난수 생성기(PRNG)를 제공하는 Java 표준 클래스.
• CryptoA를 사용하지 않고 Windows에서 암호화된 보안 임의 번호PI
• ANSI-NIST 타원 곡선 RNG, Daniel R. L. Brown, IACR ePrint 2006/117의 추측 보안.
• NIST SP 800-90 타원 곡선 무작위 번호 생성기, Daniel R. L. Brown 및 Kristian Gjosten, IACR ePrint 2007/048의 보안 분석. CRIPTO 2007에 출연하기.
• Dual Elliptic Curve Philosorandom Generator, Berry Schenmakers 및 Andrey Sidorenko, IACR ePrint 2006/190의 암호화 분석.
• 효율적인 유사성 생성기 DDH 가정, Reza Rezaiian Farashahi 및 Berry Schenmakers와 Andrey Sidorenko, IACR ePrint 2006/321을 기반으로 한다.
• 리눅스 난수 생성기, Zvi Gatherman 및 Benny Pinkas 및 Tzachy Rinman 분석.
• NIST Statistical Test Suite 설명서 및 소프트웨어 다운로드.