암호화로 보호된 의사 난수 생성기

암호학적으로 안전한 Pseudorandom Number Generator(CSPRNG; 의사난수발생기) 또는 Cryptographic Pseudorandom Number Generator(CPRNG;^[1] 암호의 의사난수발생기)는 암호학에 적합한 속성을 가진 Peudorandom Number Generator(PRNG; 의사난수발생기)입니다.암호 난수 생성기(CRNG)라고도 합니다(랜덤 번호 생성 " "참"^[2]^[3] 대 의사 난수 참조).

대부분의 암호화 애플리케이션에는 난수가 필요합니다.다음은 예를 제시하겠습니다.

키 생성
하지 않다
ECDSA, RSASSA-PSS를 포함한 특정 시그니처 스킴의 소금

이러한 애플리케이션에 필요한 랜덤성의 「품질」은 다릅니다.예를 들어 일부 프로토콜에서 난스를 만들려면 고유성만 있으면 됩니다.한편, 마스터 키의 생성은 엔트로피의 증가 등, 보다 높은 품질을 필요로 합니다.또, 원타임 패드의 경우, 키 재료가 엔트로피가 높은 진정한 랜덤 소스로부터의 것이므로, 어떠한 의사난수 발생기도 불충분할 경우에만 완전 비밀의 정보이론적 보증이 유지된다.

이상적으로는 CSPRNG의 난수 생성은 고품질 소스(일반적으로 운영체제의 랜덤성 API)에서 얻은 엔트로피를 사용합니다.그러나 이러한 표면적으로 독립적인 여러 프로세스에서 예기치 않은 상관관계가 발견되었습니다.정보이론의 관점에서 랜덤성의 양, 즉 생성 가능한 엔트로피는 시스템에 의해 제공되는 엔트로피와 같다.하지만 실제 상황에서는 엔트로피가 없는 것보다 더 많은 난수가 필요할 수 있습니다.또, 실행중의 시스템으로부터 랜덤을 추출하는 프로세스는, 실제로는 느립니다.이러한 경우 CSPRNG를 사용할 수 있습니다.CSPRNG는 사용 가능한 엔트로피를 더 많은 비트에 걸쳐 "스트레치"할 수 있습니다.

요구 사항들

일반 PRNG의 요건도 암호학적으로 안전한 PRNG에 의해 충족되지만 그 반대는 사실이 아닙니다.CSPRNG 요건은 두 가지 그룹으로 나뉩니다.첫 번째는 통계적 랜덤성 테스트에 합격하는 것, 두 번째는 공격자가 ^{[citation needed]}초기 상태 또는 실행 상태의 일부를 이용할 수 있게 된 경우에도 심각한 공격에도 잘 버티는 것입니다.

모든 CSPRNG는 다음 비트테스트를 충족해야 합니다.즉, 첫 번째가k랜덤 시퀀스의 비트, (다항 시간 알고리즘은 없습니다)k +1) 성공 확률이 50%^[4]보다 높은 비트입니다.Andrew Yao는 1982년에 다음 비트 테스트를 통과한 발전기가 무작위성에 ^[5]대한 다른 모든 다항식 시간 통계 테스트를 통과한다는 것을 증명했습니다.
모든 CSPRNG는 '상태 타협 확장'에 견딜 수 있어야 합니다.그 상태의 일부 또는 전부가 밝혀진 경우(또는 정확하게 추측된 경우), 폭로가 발생하기 전에 난수의 흐름을 재구성하는 것은 불가능해야 한다.또한 실행 중에 엔트로피 입력이 있을 경우 입력 상태에 대한 지식을 사용하여 CSPRNG 상태의 미래 상태를 예측할 수 없습니다.

예:고려대상 CSPRNG가 바이너리 확장의 미지의 포인트부터 순서대로 µ의 비트를 계산하여 출력을 산출하는 경우, µ는 랜덤시퀀스로 보이므로 다음 비트테스트를 충분히 만족시킬 수 있고 통계적으로 랜덤할 수 있습니다.(예를 들어, 「」가 통상의 번호인 경우, 이것은 보증됩니다).단, 이 알고리즘은 암호학적으로 안전하지 않습니다.현재 사용되고 있는 pi 비트(알고리즘 상태)를 판별하는 공격자는 앞의 모든 비트도 계산할 수 있습니다.

대부분의 PRNG는 CSPRNG로 사용하기에는 적합하지 않으며 두 가지 점에서 모두 실패합니다.첫째, 대부분의 PRNG 출력은 다양한 통계 테스트에 랜덤으로 나타나지만 결정된 리버스 엔지니어링에 저항하지 않습니다.난수가 진짜 랜덤이 아님을 보여주는 PRNG에 맞게 특별히 조정된 통계 테스트가 발견될 수 있다.둘째, 대부분의 PRNG는 상태가 공개되면 과거의 모든 난수를 소급하여 공격자가 과거의 모든 메시지와 미래의 메시지를 읽을 수 있도록 합니다.

CSPRNG는 이러한 유형의 암호 분석에 저항하도록 설계되어 있습니다.

정의들

점근적 설정에서 결정론적 다항식 $시간$ 계산 가능 $G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}$ G $G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}$ k $G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}$ : $G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}$ { $G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}$ , $G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}$ } k $G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}$ { $G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}$ , $G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}$ p $G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}$ ( $G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}$ ) { $display$ G_ ${k$ } \ $colon$ \ { $0$ , 1 \ }^{ k } \ $to$ \ { 0 , 1 \ }^{ p $($ k ) } \ $to$ \ { 0 , 1 \ p ( k } \ to \ to \ { 0 , 1 } { 0 , 1 \ p ( k $G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}$ } } { 0 , p } { 0 , p ( k } { 0 , p } } } \ to \ to $k$ $($ 의 k에 대해 k\ $displaystyle$ p $(k)>k$ 및 그 출력이 실제 랜덤성과 계산적으로 구별할 수 없는 경우 $p(k)>k$ 즉 구별자로 1 또는 0을 출력하는 확률론적 다항식 $시간$ 알고리즘 A에 대해

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

$($ $x\gets X$ { $displaystyle$ $\mu$ x $\gets$ X} $x\gets X$ 은 $x\gets X$ x가 $집합$ X에서 랜덤으로 균일하게 선택됨을 $의미$ 합니다.)

다음과 같은 동일한 특성이 있습니다.함수 $G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}$ $G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}$ k $G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}$ : $G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}$ { $G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}$ , $G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}$ $G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}$ $G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}$ $G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}$ { $G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}$ , $G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}$ $G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}$ ( $G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}$ ) { $display style$ G_ ${k}$ \ $colon$ \ { $0$ , 1 \ }^{ $k}$ \ $to$ \ { $0$ , 1 \ }^{p $( k$ $G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}$ 에 대해 G의 $다음$ 출력 비트를 다항식 시간 ^[7]알고리즘으로 예측할 수 없는 경우에만 G는 PRNG입니다.

$t(k)$ t $)$ { $displaystyle$ t $(k)}$ { $G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{k}\times \{0,1\}^{t(k)}$ $G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{k}\times \{0,1\}^{t(k)}$ { $G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{k}\times \{0,1\}^{t(k)}$ $G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{k}\times \{0,1\}^{t(k)}$ × { $G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{k}\times \{0,1\}^{t(k)}$ $G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{k}\times \{0,1\}^{t(k)}$ $G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{k}\times \{0,1\}^{t(k)}$ ( $G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{k}\times \{0,1\}^{t(k)}$ ) { $displaystyle G_{k}\colon$ \ { $0,1\}k}$ ~ ${0,1\k}회$ $G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{k}\times \{0,1\}^{t(k)}$ 입니다.출력( $s_{i+1}$ + 1 $s_{i+1}$ { $display$ style $s$ $s_{i+1}$ { $i$ + $s_{i+1}$ $1$ $s_{i+1}$ } , $y_{i}$ { \ $displaystyle$ $y$ _ { $i$ $}$ ) $s_{i+1}$ 、 $s_{i+1}$ i,i 의 pseudorandom 출력 $y_{i}$ y $y_{i}$ { $displaystyle$ $y$ $_$ { $i$ $s_{i+1}$ })로 $y_{i}$ 구성되어 있습니다.이 출력은 다음과 같은 의미에서의 스테이트 $s_{i+1}$ 확장에 견딜 수 있습니다.초기 $s_{1}$ $s_{1}$ {{ $\{0,1\}^{k}$ $s_{1}}$ 이 $s_{1}$ $가$ ) { $\{0,1\}^{k}$ 1 $}$ k $\{0,1\}^{k}$ {{displaystyle $\{0,1$ \}^{ $k$ 에서 랜덤으로 선택되는 경우 $i$ 에 대해 시퀀스 $(y_{1},y_{2},\dots ,y_{i},s_{i+1})$ $(y_{1},y_{2},\dots ,y_{i},s_{i+1})$ , $(y_{1},y_{2},\dots ,y_{i},s_{i+1})$ y $(y_{1},y_{2},\dots ,y_{i},s_{i+1})$ 2, $(y_{1},y_{2},\dots ,y_{i},s_{i+1})$ $(y_{1},y_{2},\dots ,y_{i},s_{i+1})$ $(y_{1},y_{2},\dots ,y_{i},s_{i+1})$ + $(y_{1},y_{2},\dots ,y_{i},s_{i+1})$ 1) $(y_{1},y_{2},\dots ,y_{i},s_{i+1})$ { $displaystyle$ ( $y_{1}, y_i, s+i} computercompute$ { $1})$ 가 $(y_{1},y_{2},\dots ,y_{i},s_{i+1})$ 필요합니다. $r_{i}$ $(r_{1},r_{2},\dots ,r_{i},s_{i+1})$ 2, $(r_{1},r_{2},\dots ,r_{i},s_{i+1})$ $(r_{1},r_{2},\dots ,r_{i},s_{i+1})$ $(r_{1},r_{2},\dots ,r_{i},s_{i+1})$ $(r_{1},r_{2},\dots ,r_{i},s_{i+1})$ i + $(r_{1},r_{2},\dots ,r_{i},s_{i+1})$ $)({displaystyle (r_{1}, r_{2},\display, r_{i$ }, $s_{$ $i$ +1 $}),$ r $({$ i $r_{i}$ })가 { $0,$ 1 $}$ t $(k$ ^[8]에서 랜덤으로 선택됩니다.

PRNG $G\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}$ : { $G\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}$ , $G\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}$ $G\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}$ $G\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}$ { $G\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}$ , $G\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}$ $p$ ( $G\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}$ $k$ $){$ $display$ $style$ $G\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}$ G \ $colon$ \ { $0$ , 1 \ }^{ k $p(k)-k$ }\ $to$ \ { $0$ , 1 \ }^{ $p$ ( $k$ )}는 $G\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}$ 블록 $p(k)-k$ p ( $p(k)-k$ ) - $k$ )의 $p(k)-k$ 출력 상태로 분할함으로써 안전한 PRNG로 변환할 수 있습니다. $G(s)=G_{0}(s)\Vert G_{1}(s)$ 를 수행하려면 $G(s)=G_{0}(s)\Vert G_{1}(s)$ ( s ) $=$ 0 ( s ) $G(s)=G_{0}(s)\Vert G_{1}(s)$ ( $G(s)=G_{0}(s)\Vert G_{1}(s)$ 1 ( s $G(s)=G_{0}(s)\Vert G_{1}(s)$ ){ $display$ G ( s )= $G_{0}(s)\Vert$ G_ ${$ $1}(s$ 입니다 $|G_{0}(s)|=|s|=k$ 서 G0 $s$ ) $|G_{0}(s)|=|s|=k$ $=$ k( $s)$ = s $=$ $|G_{1}(s)|=p(k)-k$ ( $|G_{1}(s)|=p(k)-k$ ) 및 $|G_{1}(s)|=p(k)-k$ $|G_{1}(s)|=p(k)-k$ p $|G_{1}(s)|=p(k)-k$ - k( $s$ $)$ - k $(\디스플레이 스타일$ G_{1}( $s)$ = $|G_{1}(s)|=p(k)-k$ p(k) $|G_{1}(s)|=p(k)-k$ - k(k ; k ; k ; )는 포워드 G입니다.om 현재 기간의 출력 블록

엔트로피 추출

Santha와 Vazirani는 랜덤성이 약한 여러 비트 스트림을 조합하여 고품질의 준랜덤 비트 ^[9]스트림을 생성할 수 있음을 증명했습니다.앞서 John von Neumann은 간단한 알고리즘이 모든 비트 ^[10]스트림에서 상당한 양의 편견을 제거할 수 있다는 것을 증명했으며, 이는 Santha-Vazirani 설계의 변형을 사용하기 전에 각 비트 스트림에 적용되어야 한다.

디자인

다음 설명에서는 CSPRNG 설계는 3가지 클래스로 나뉩니다.

암호나 암호 해시 같은 암호 원형을 기반으로 합니다.
어려운 것으로 생각되는 수학적인 문제에 근거한 것.
특수 목적의 디자인

마지막 엔트로피는 사용 가능한 경우 추가 엔트로피를 발생시키는 경우가 많습니다.또한 출력은 초기 상태에 의해 완전히 결정되지 않기 때문에 엄밀히 말하면 순수한 의사난수 생성기가 아닙니다.이것에 의해, 초기 상태가 저하하는 경우에서도, 공격을 방지할 수 있습니다.

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

시큐어 블록 암호는 카운터^{[dubious – discuss]} 모드로 실행함으로써 CSPRNG로 변환할 수 있습니다.이것은 임의의 키를 선택하고 0을 암호화한 후 1을 암호화하고 2를 암호화하는 방식으로 이루어집니다.카운터는 0 이외의 임의의 번호에서도 기동할 수 있습니다.n비트 블록암호에서는 생일 문제 이후 블록 충돌 가능성이 높아지지만 CTR 모드의 블록암호에서는 동일한 블록이 출력되지 않기 때문에 약 2블록^n/2 후에 출력을 랜덤데이터와 구별할 수 있습니다.64비트 블록 암호의 경우 안전 출력 크기가 수 기가바이트로 제한되며 128비트 블록은 일반 애플리케이션에 영향을 미치지 않을 정도로 제한이 큽니다.다만, 단독으로 사용하는 경우는, CSPRNG 의 모든 기준(상기)을 만족시키는 것은 아닙니다.이것은, 「스테이트 타협 확장」에 강하지 않기 때문입니다.상태(이 경우는 카운터 및 키)를 알면, 과거의 모든 출력을 예측할 수 있습니다.
암호화로 보호된 카운터의 해시는 경우에 따라서는 양호한 CSPRNG로도 기능할 수 있습니다.이 경우 이 카운터의 초기값은 랜덤으로 비밀이어야 합니다.그러나 이러한 방식으로 사용하기 위한 알고리즘에 대한 연구는 거의 없었으며, 적어도 일부 저자는 ^[vague]^[11]이러한 사용에 대해 경고한다.

대부분의 스트림 암호는 플레인텍스트와 조합된(대부분 XORed) 비트의 의사 난수 스트림을 생성함으로써 동작합니다.카운터에서 암호를 실행하면 새로운 의사 난수 스트림이 반환되며, 시간이 길어질 수 있습니다.암호는 원래 스트림이 양호한 CSPRNG일 경우에만 보호됩니다.다만, 반드시 그렇지만은 않습니다(RC4 암호 참조).다시 말씀드리지만 초기 상태는 비밀로 해야 합니다.

수이론 설계

Blum Blum Shub 알고리즘에는 2차 잔존도 문제의 난이도에 기초한 보안 증거가 있습니다.이 문제를 해결하는 유일한 방법은 계수를 인수화하는 것이기 때문에 일반적으로 정수 인수 분해의 난이도는 Blum Blum Shub 알고리즘의 조건부 보안 증명을 제공하는 것으로 간주됩니다.그러나 알고리즘은 매우 비효율적이기 때문에 고도의 보안이 필요하지 않는 한 실용적이지 않습니다.
Blum-Micali 알고리즘은 이산 로그 문제의 난이도에 기초한 보안 증명을 가지고 있지만 매우 비효율적입니다.
Certicom의 Daniel Brown은 Dual_의 2006년 보안 증명서를 작성했습니다.EC_DRBG, 가정된 의사결정 디피의 경도에 기초한다.Hellman 가정, x-logm 문제 및 잘린 점 문제.2006년 증명에서는 Dual_보다 낮은^{[clarification needed]} 아웃렌을 명시적으로 상정하고 있습니다.EC_DRBG 표준 및 듀얼_의 P와 QEC_DRBG 표준(2013년에 NSA에 의해 백도어된 것으로 밝혀짐)은 백도어되지 않은 값으로 대체됩니다.

특별한 디자인

다음과 같이 암호학적으로 안전하도록 설계된 실용적인 PRNG가 많이 있습니다.

입력의 엔트로픽 품질을 평가하려는 야로 알고리즘.야로는 2019년 12월까지 맥OS 등 애플 OS에서 사용되고 있다.이후 애플은 Fortuna로 전환했습니다.(/dev/random 참조).
ChaCha20 알고리즘은 OpenBSD(버전 5.4),^[12] NetBSD(버전 7.0)^[13] 및 FreeBSD(버전 12.0)^[14]에서 RC4를 대체했습니다.
ChaCha20은 또한 버전 4.^[15]8의 Linux에서 SHA-1을 대체했습니다.
Fortuna 알고리즘은 입력의 엔트로픽 품질을 평가하지 않습니다.Fortuna는 FreeBSD에서 사용됩니다.애플은 2019년 12월경부터 대부분 또는 모든 애플 OS를 포춘으로 바꿨다.
마이크로소프트의 암호화 애플리케이션 프로그래밍 인터페이스에서 제공되는 CryptGenRandom 함수
RC4 암호의 변형에 기반한 ISAK
NIST Statistical Test ^[16]^[17]Suite에 기반한 진화 알고리즘으로 조정된 선형 피드백 시프트 레지스터.
아아크 4인치
AES-CTR DRBG는 AES ^[18]^[19]암호화를 사용하는 시스템에서 난수 생성기로 자주 사용됩니다.
ANSI X9.17 표준(금융기관 키 관리(도매))도 FIPS 표준으로 채택되었습니다.입력으로 TDEA(키 옵션 2) 키 번들k 및 64비트 랜덤시드(^[20]초기값)를 사용합니다.난수가 필요할 때마다 다음을 수행합니다.
- 현재 날짜/시간 D를 가능한 최대 해상도로 가져옵니다.
- 임시 값 $t$ = $TDEA k (D)$ 를 계산합니다.
- 랜덤 $값$ x = $TDEA k (s µ$ t $)$ 를 계산합니다.여기서 θ는 비트 배타적 또는 를 나타냅니다.
- $시드$ = $TDEA k (x$ † $t)$ 를 업데이트합니다.

분명히 이 기술은 모든 블록 암호에 쉽게 일반화될 수 있습니다.^[21]AES가 권장되고 있습니다.

표준

몇 가지 CSPRNG가 표준화되어 있습니다.예를들면,

이 철회된 표준에는 4개의 PRNG가 있습니다.그 중 Hash_DRBG라는^[22] 이름의 CSPRNG와 HMAC_DRBG라는 이름의 CSPRNG의 ^[23]2개는 논란의 여지가 없고 검증되었습니다.

이 표준의 세 번째 PRNG인 CTR DRBG는 카운터 모드에서 실행되는 블록 암호에 기초하고 있습니다.이 PRNG에서 출력되는 비트 수가 기본 블록 암호의 블록 크기(^[24]비트 단위)의 곱에 대해 2보다 클 경우 기본 블록 암호의 보안 수준보다 공격을 구별하는 데 있어서는 약한 것으로 입증되었습니다.

이 PRNG에서 출력되는 최대 비트 수가 2와^blocksize 같으면 결과 출력은 키 크기가 생성될 것으로 예상되는 수학적으로 예상되는 보안 수준을 제공하지만 출력은 진정한 난수 ^[24]생성기와 구별할 수 없는 것으로 나타납니다.이 PRNG에서 출력되는 최대 비트 수가 이 비트 수보다 작을 경우 예상되는 보안 수준이 전달되고 출력이 진정한 난수 ^[24]생성기와 구별할 수 없는 것으로 보입니다.

다음 리비전에서는 CTR_DRBG의 보안 강도가 생성 요구의 총수와 생성 요구당 제공되는 비트의 제한에 따라 결정된다는 점에 주목하고 있습니다.

이 표준의 네 번째이자 마지막 PRNG는 Dual_입니다.EC_DRBG그것은 암호학적으로 안전하지 않은 것으로 드러났고 도난당한 NSA 백도어가 ^[25]있는 것으로 여겨진다.

NIST SP 800-90A Rev.1: 기본적으로 NIST SP 800-90A와 듀얼_EC_DRBG가 삭제되어 폐지된 표준 대체품입니다.
ANSI X9.17-1985 부록 C
ANSI X9.31-1998 부록 A.2.4
ANSI X9.62-1998 Annex A.4, ANSI X9.62-2005, Annex D(HMAC_DRBG)에 의해 폐지됨

NIST가 좋은 참조를 유지하고 있다.

또한 새로운 CSPRNG 설계의 통계 테스트 표준이 있습니다.

랜덤 및 의사 난수 생성기를 위한 통계 테스트 스위트, NIST 특별 간행물 800-22.

듀얼_의 NSA 백도어 도난EC_DRBG PRNG

가디언과 뉴욕타임스는 2013년 국가안보국(NSA)이 NIST SP 800-90A의 의사난수발생기(PRNG)에 백도어를 삽입해 NSA가 Dual_의 도움을 받아 암호화된 자료를 쉽게 해독할 수 있도록 했다고 보도했다.EC_DRBG두 신문^[26]^[27] 모두 독립 보안 전문가들이 오랫동안 ^[28]의심했듯이 NSA가 CSPRNG 규격 800-90에 취약점을 도입하고 있다고 보도했습니다.이것은 에드워드 스노든이 가디언에 유출한 최고 기밀 문서 중 하나에 의해 처음으로 확인되었습니다.NSA는 2006년 NIST 초안 보안 표준을 전 세계적으로 사용하도록 승인하기 위해 비밀리에 작업을 수행했습니다.유출된 문서에는 "결국 NSA가 단독 편집자가 되었다"고 적혀 있다.Dual_에서는 백도어의 도난이나 기타 중대한 결함이 있을 가능성이 있다고 알려져 있는데도 불구하고EC_DRBG, RSA Security 등의 여러 회사가 Dual_를 계속 사용2013년 ^[29]백도어가 확인될 때까지 EC_DRBG.RSA 시큐리티는 NSA로부터 1000만달러의 지불을 받았습니다.^[30]

보안 결함

DUHK 공격

2017년 10월 23일 펜실베니아 대학과 존스홉킨스 대학의 암호학자인 Sanan Cohney, Matthew Green 및 Nadia Henninger는 하드웨어 벤더가 하드 코드 키 r931 ANSI를 위해 하드 코드된 키를 사용하는 WPA2(Don't Use Hard-Coded Key) 공격에 대한 자세한 내용을 발표했습니다.나머지 암호화 파라미터를 검출하고 웹 세션 또는 가상 프라이빗 네트워크(^[31]^[32]VPN) 접속 암호화에 사용되는 마스터 암호화 키를 추론하는 데 사용됩니다.

일본 PURPLE 암호기

제2차 세계대전 중 일본은 외교 통신에 암호기를 사용했다.미국이 암호를 해독하고 메시지를 읽을 수 있었던 것은 주로 사용된 "핵심 값"이 충분히 무작위적이지 않았기 때문이다.

레퍼런스

^ Huang, Andrew (2003). Hacking the Xbox: An Introduction to Reverse Engineering. No Starch Press Series. No Starch Press. p. 111. ISBN 9781593270292. Retrieved 2013-10-24. [...] the keystream generator [...] can be thought of as a cryptographic pseudo-random number generator (CPRNG).
^ Dufour, Cédric. "How to ensure entropy and proper random numbers generation in virtual machines". Exoscale.
^ "/dev/random Is More Like /dev/urandom With Linux 5.6 - Phoronix". www.phoronix.com.
^ Katz, Jonathan; Lindell, Yehuda (2008). Introduction to Modern Cryptography. CRC press. p. 70. ISBN 978-1584885511.
^ 앤드류 치치야오트랩도어 기능의 이론과 응용.1982년 제23회 IEEE 컴퓨터 사이언스 기초 심포지엄의 속행.
^ Goldreich, Oded (2001), Foundations of cryptography I: Basic Tools, Cambridge: Cambridge University Press, ISBN 978-0-511-54689-1, def 3.3.1.
^ Goldreich, Oded (2001), Foundations of cryptography I: Basic Tools, Cambridge: Cambridge University Press, ISBN 978-0-511-54689-1, 정리 3.3.7.
^ Dodis, Yevgeniy, Lecture 5 Notes of Introduction to Cryptography (PDF), retrieved 3 January 2016, def 4.
^ Miklos Santha, Umesh V. Vazirani (1984-10-24). "Generating quasi-random sequences from slightly-random sources" (PDF). Proceedings of the 25th IEEE Symposium on Foundations of Computer Science. University of California. pp. 434–440. ISBN 0-8186-0591-X. Retrieved 2006-11-29.
^ John von Neumann (1963-03-01). "Various techniques for use in connection with random digits". The Collected Works of John von Neumann. Pergamon Press. pp. 768–770. ISBN 0-08-009566-6.
^ Adam Young, Moti Yung (2004-02-01). Malicious Cryptography: Exposing Cryptovirology. sect 3.2: John Wiley & Sons. p. 416. ISBN 978-0-7645-4975-5.{{cite book}}: CS1 유지보수: 위치(링크)
^ "CVS log of arc4random.c". CVS. October 1, 2013.
^ "CVS log of arc4random.c". CVS. November 16, 2014.
^ "FreeBSD 12.0-RELEASE Release Notes: Runtime Libraries and API". FreeBSD.org. 5 March 2019. Retrieved 24 August 2019.
^ "Github commit of random.c". Github. July 2, 2016.
^ "A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications" (PDF). Special Publication. NIST. April 2010.
^ Poorghanad, A.; Sadr, A.; Kashanipour, A. (May 2008). "Generating High Quality Pseudo Random Number Using Evolutionary Methods" (PDF). IEEE Congress on Computational Intelligence and Security. 9: 331–335.
^ Kleidermacher, David; Kleidermacher, Mike (2012). Embedded Systems Security: Practical Methods for Safe and Secure Software and Systems Development. Elsevier. p. 256. ISBN 9780123868862.
^ Cox, George; Dike, Charles; Johnston, DJ (2011). "Intel's Digital Random Number Generator (DRNG)" (PDF). {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
^ Menezes, Alfred; van Oorschot, Paul; Vanstone, Scott (1996). "Chapter 5: Pseudorandom Bits and Sequences" (PDF). Handbook of Applied Cryptography. CRC Press.
^ Young, Adam; Yung, Moti (2004-02-01). Malicious Cryptography: Exposing Cryptovirology. sect 3.5.1: John Wiley & Sons. ISBN 978-0-7645-4975-5.{{cite book}}: CS1 유지보수: 위치(링크)
^ Kan, Wilson (September 4, 2007). "Analysis of Underlying Assumptions in NIST DRBGs" (PDF). Retrieved November 19, 2016.
^ Ye, Katherine Qinru (April 2016). "The Notorious PRG: Formal verification of the HMAC-DRBG pseudorandom number generator" (PDF). Retrieved November 19, 2016.
^ ^a ^b ^c Campagna, Matthew J. (November 1, 2006). "Security Bounds for the NIST Codebook-based Deterministic Random Bit Generator" (PDF). Retrieved November 19, 2016.
^ Perlroth, Nicole (September 10, 2013). "Government Announces Steps to Restore Confidence on Encryption Standards". The New York Times. Retrieved November 19, 2016.
^ James Borger; Glenn Greenwald (6 September 2013). "Revealed: how US and UK spy agencies defeat internet privacy and security". The Guardian. Retrieved 7 September 2013.
^ Nicole Perlroth (5 September 2013). "N.S.A. Able to Foil Basic Safeguards of Privacy on Web". The New York Times. Retrieved 7 September 2013.
^ Bruce Schneier (15 November 2007). "Did NSA Put a Secret Backdoor in New Encryption Standard?". Wired. Retrieved 7 September 2013.
^ Matthew Green. "RSA warns developers not to use RSA products".
^ Joseph Menn (20 December 2013). "Exclusive: Secret contract tied NSA and security industry pioneer". Reuters.
^ Shaanan Cohney; Matthew D. Green; Nadia Heninger. "Practical state recovery attacks against legacy RNG implementations" (PDF). duhkattack.com.
^ "DUHK Crypto Attack Recovers Encryption Keys, Exposes VPN Connections". slashdot.org. Retrieved 25 October 2017.

외부 링크

RFC 4086, 보안을 위한 랜덤성 요건
Java "엔트로피 풀"은 예측 불가능한 난수를 암호화로 보호합니다.
암호학적으로 강력한 의사 난수 생성기(PRNG)를 제공하는 Java 표준 클래스.
CryptoA를 사용하지 않는 Windows에서의 암호화 보안 랜덤 번호PI
ANSI-NIST 타원곡선 RNG의 추정 보안, Daniel R. L. Brown, ICR ePrint 2006/117.
NIST SP 800-90 타원곡선 난수 생성기의 보안 분석, Daniel R. L. Brown 및 Christian Gjosteen, ICR ePrint 2007/048.CRYPTO 2007에 표시됩니다.
Dual Elliptic Curve Pseudorandom Generator, Berry Schoenmakers 및 Andrey Sidorenko, ICR ePrint 2006/190의 암호화 분석.
DDH 가정, Reza Rezaeian Farashahi, Berry Schoenmakers 및 Andrey Sidorenko, ICR ePrint 2006/321에 기반한 효율적인 의사랜덤 생성기.
Linux 난수 생성기, Zvi Gotterman, Benny Pinkas 및 Tzachy Reinman 분석.
NIST Statistical Test Suite 문서 및 소프트웨어 다운로드.

[1] Huang, Andrew (2003). Hacking the Xbox: An Introduction to Reverse Engineering. No Starch Press Series. No Starch Press. p. 111. ISBN 9781593270292. Retrieved 2013-10-24. [...] the keystream generator [...] can be thought of as a cryptographic pseudo-random number generator (CPRNG).

[2] Dufour, Cédric. "How to ensure entropy and proper random numbers generation in virtual machines". Exoscale.

[3] "/dev/random Is More Like /dev/urandom With Linux 5.6 - Phoronix". www.phoronix.com.

[katz-4] Katz, Jonathan; Lindell, Yehuda (2008). Introduction to Modern Cryptography. CRC press. p. 70. ISBN 978-1584885511.

[yao82-5] 앤드류 치치야오트랩도어 기능의 이론과 응용.1982년 제23회 IEEE 컴퓨터 사이언스 기초 심포지엄의 속행.

[6] Goldreich, Oded (2001), Foundations of cryptography I: Basic Tools, Cambridge: Cambridge University Press, ISBN 978-0-511-54689-1, def 3.3.1.

[7] Goldreich, Oded (2001), Foundations of cryptography I: Basic Tools, Cambridge: Cambridge University Press, ISBN 978-0-511-54689-1, 정리 3.3.7.

[8] Dodis, Yevgeniy, Lecture 5 Notes of Introduction to Cryptography (PDF), retrieved 3 January 2016, def 4.

[santha-vazirani-9] Miklos Santha, Umesh V. Vazirani (1984-10-24). "Generating quasi-random sequences from slightly-random sources" (PDF). Proceedings of the 25th IEEE Symposium on Foundations of Computer Science. University of California. pp. 434–440. ISBN 0-8186-0591-X. Retrieved 2006-11-29.

[neumann-random-10] John von Neumann (1963-03-01). "Various techniques for use in connection with random digits". The Collected Works of John von Neumann. Pergamon Press. pp. 768–770. ISBN 0-08-009566-6.

[Malicious_Cryptography-11] Adam Young, Moti Yung (2004-02-01). Malicious Cryptography: Exposing Cryptovirology. sect 3.2: John Wiley & Sons. p. 416. ISBN 978-0-7645-4975-5.{{cite book}}: CS1 유지보수: 위치(링크)

[12] "CVS log of arc4random.c". CVS. October 1, 2013.

[13] "CVS log of arc4random.c". CVS. November 16, 2014.

[14] "FreeBSD 12.0-RELEASE Release Notes: Runtime Libraries and API". FreeBSD.org. 5 March 2019. Retrieved 24 August 2019.

[15] "Github commit of random.c". Github. July 2, 2016.

[16] "A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications" (PDF). Special Publication. NIST. April 2010.

[17] Poorghanad, A.; Sadr, A.; Kashanipour, A. (May 2008). "Generating High Quality Pseudo Random Number Using Evolutionary Methods" (PDF). IEEE Congress on Computational Intelligence and Security. 9: 331–335.

[18] Kleidermacher, David; Kleidermacher, Mike (2012). Embedded Systems Security: Practical Methods for Safe and Secure Software and Systems Development. Elsevier. p. 256. ISBN 9780123868862.

[19] Cox, George; Dike, Charles; Johnston, DJ (2011). "Intel's Digital Random Number Generator (DRNG)" (PDF). {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)

[20] Menezes, Alfred; van Oorschot, Paul; Vanstone, Scott (1996). "Chapter 5: Pseudorandom Bits and Sequences" (PDF). Handbook of Applied Cryptography. CRC Press.

[Malicious_Cryptography2-21] Young, Adam; Yung, Moti (2004-02-01). Malicious Cryptography: Exposing Cryptovirology. sect 3.5.1: John Wiley & Sons. ISBN 978-0-7645-4975-5.{{cite book}}: CS1 유지보수: 위치(링크)

[22] Kan, Wilson (September 4, 2007). "Analysis of Underlying Assumptions in NIST DRBGs" (PDF). Retrieved November 19, 2016.

[23] Ye, Katherine Qinru (April 2016). "The Notorious PRG: Formal verification of the HMAC-DRBG pseudorandom number generator" (PDF). Retrieved November 19, 2016.

[CTR_DRBG-24] Campagna, Matthew J. (November 1, 2006). "Security Bounds for the NIST Codebook-based Deterministic Random Bit Generator" (PDF). Retrieved November 19, 2016.

[25] Perlroth, Nicole (September 10, 2013). "Government Announces Steps to Restore Confidence on Encryption Standards". The New York Times. Retrieved November 19, 2016.

[Guardian-26] James Borger; Glenn Greenwald (6 September 2013). "Revealed: how US and UK spy agencies defeat internet privacy and security". The Guardian. Retrieved 7 September 2013.

[27] Nicole Perlroth (5 September 2013). "N.S.A. Able to Foil Basic Safeguards of Privacy on Web". The New York Times. Retrieved 7 September 2013.

[28] Bruce Schneier (15 November 2007). "Did NSA Put a Secret Backdoor in New Encryption Standard?". Wired. Retrieved 7 September 2013.

[green-29] Matthew Green. "RSA warns developers not to use RSA products".

[reuters-30] Joseph Menn (20 December 2013). "Exclusive: Secret contract tied NSA and security industry pioneer". Reuters.

[31] Shaanan Cohney; Matthew D. Green; Nadia Heninger. "Practical state recovery attacks against legacy RNG implementations" (PDF). duhkattack.com.

[32] "DUHK Crypto Attack Recovers Encryption Keys, Exposes VPN Connections". slashdot.org. Retrieved 25 October 2017.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

Search