암호화 보안 난수 생성기는 어떻게 작동합니까?

암호화 보안 난수 생성기는 어떻게 작동합니까?

---

표준 난수 생성기가 어떻게 작동하는지 이해합니다. 그러나 암호 술을 사용할 때 난수는 실제로 무작위 여야합니다.

보안 해시를 생성하는 데 도움이되는 우주 백색 잡음 을 읽는 도구가 있다는 것을 알고 있지만 표준 PC에는이 기능이 없습니다.

암호화 보안 난수 생성기는 반복 가능한 패턴이없는 값을 어떻게 얻습니까?

---

암호화 키를 생성하는 데 사용할 수있는 암호화 보안 숫자 임의 생성기는 다른 사람이 관찰 할 수없는 소스에서 엔트로피 (예측할 수없는 입력)를 수집하여 작동합니다.

예를 들어, Linux의 / dev / random (4)은 데이터를 반환하는 하드 디스크, 키 누르기 및 들어오는 네트워크 패킷과 같은 소스에서 하드웨어 인터럽트 타이밍의 변화에서 정보를 수집합니다. 이 접근 방식은 커널이 수집 한 엔트로피의 양을 과대 평가하지 않는 한 안전합니다. 몇 년 전부터는 다양한 소스의 엔트로피 추정이 모두 감소하여 훨씬 더 보수적이었습니다. 다음은 Linux가 엔트로피를 추정하는 방법에 대한 설명입니다 .

위의 어느 것도 특히 높은 처리량은 아닙니다. / dev / random (4)은 아마도 안전 할 수 있지만 데이터가 안전하게 무작위인지 확신 할 수 없으면 데이터 제공을 거부하여 보안을 유지합니다. 예를 들어 많은 암호화 키와 임시 값을 생성하려는 경우 하드웨어 난수 생성기를 사용하는 것이 좋습니다.

종종 하드웨어 RNG는 동일한 속도에 가깝게 실행되지만 열 잡음에 따라 속도가 약간 씩 달라지는 한 쌍의 발진기 간의 차이에서 샘플링하도록 설계됩니다. 내가 올바르게 기억한다면 영국의 프리미엄 채권 복권 ERNIE에 사용되는 난수 생성기는 이런 방식으로 작동합니다.

다른 방법으로는 CCD ( lavaRND 참조 ), 방사성 붕괴 ( hotbits 참조 ) 또는 대기 소음 ( random.org 참조) 에서 잡음 샘플링 ( 또는 방송국 이외의 곳에서 튜닝 된 AM 라디오를 사운드 카드에 연결)이 포함됩니다. 또는 컴퓨터 사용자에게 배를 떠 다니는 것이 무엇이든간에 이상한 침팬지처럼 키보드 를 1 분 동안 두드 리도록 직접 요청할 수 있습니다 .

안드라스가 지적했듯이, 저는 가장 일반적인 엔트로피 수집 방식에 대해서만 이야기하려고했습니다. Thomas Pornin의 답변 과 Johannes Rössel의 답변은 모두 다시 일부를 전달하기 위해 수집 된 엔트로피를 맹 글링하는 방법을 설명하는 좋은 작업을 수행합니다.

---

암호화 목적을 위해 필요한 것은 스트림이 "일률적으로 임의의 비트와 계산적으로 구별 할 수없는"것입니다. "계산적으로"는 그것이 진정한 무작위 일 필요가없고, 하나님 자신의 컴퓨터에 접근 할 수없는 누구에게나 그렇게 보일뿐임을 의미합니다.

실제로 이것은 시스템이 먼저 n 개의 진정한 랜덤 비트 시퀀스를 수집해야 함을 의미합니다 . n은 철저한 검색을 방해 할만큼 충분히 커야합니다. 즉, n 비트 의 모든 2 ^ n 조합 을 시도하는 것은 불가능합니다 . 이것은 오늘날의 기술과 관련하여 n 이 90 이상이면 달성되지만 암호학 자는 2의 거듭 제곱을 좋아 하므로 n = 128 을 사용하는 것이 일반적 입니다.

이러한 n 개의 임의 비트는 물리학에 관한 한 예측할 수없는 "물리적 이벤트"를 수집하여 얻습니다. 일반적으로 타이밍이 사용됩니다. CPU에는 초당 수십억 번 업데이트되는 사이클 카운터가 있으며 일부 이벤트는 불가피한 양의 지터 (수신 네트워크 패킷, 마우스 움직임, 키 입력 ...)로 발생합니다. 시스템은 이러한 이벤트를 인코딩 한 다음 SHA-256과 같은 암호화 보안 해시 함수를 적용하여이를 "압축"합니다 (그런 다음 n 비트 를 생성하기 위해 출력이 잘립니다 ). 여기서 중요한 것은 물리적 이벤트의 인코딩에 충분한 엔트로피가 있다는 것입니다 . 대략적으로 말하면, 해당 이벤트가 집합 적으로 최소 2 ^ n을 가정 할 수 있습니다.조합. 해시 함수는 정의에 따라 해당 엔트로피를 n 비트 문자열 로 집중시키는 데 효과적 입니다.

n 비트 가 있으면 PRNG (Pseudo-Random Number Generator)를 사용하여 필요한만큼 비트를 생성합니다. PRNG는 충분히 넓은 알 수없는 n 비트 키에 대해 작동한다고 가정 할 때 해당 출력이 균일 한 임의의 비트와 계산적으로 구별 할 수없는 경우 암호화 적으로 안전하다고합니다 . 90 년대에 인기있는 선택은 RC4 였습니다 . 이는 구현이 매우 간단하고 매우 빠릅니다. 그러나 측정 가능한 편향이있는 것으로 밝혀졌습니다. 즉, 처음에 원했던 것만 큼 구별 할 수 없었습니다. E 스트림 프로젝트PRNG (대부분의 스트림 암호는 출력이 암호화 할 데이터와 함께 XOR 된 PRNG로 구성되기 때문에 실제로 스트림 암호)를 수집하고 문서화하고 암호화 전문가의 분석을 촉진하는 것으로 구성되었습니다. eSTREAM 포트폴리오에는 충분히 안전한 것으로 간주되는 7 개의 PRNG 디자인이 포함되어 있습니다 (즉, 분석에 저항하고 암호학자는 왜 저항 했는지 잘 이해하는 경향이 있음 ). 그중 4 개는 "소프트웨어에 최적화"되어 있습니다. 좋은 소식은이 새로운 PRNG가 RC4보다 훨씬 더 안전 해 보이지만 눈에 띄게 빠르다는 것입니다 (여기서는 초당 수백 메가 바이트에 대해 이야기하고 있습니다). 그 중 3 개는 "모든 용도에 대해 무료"이며 소스 코드가 제공됩니다.

디자인 관점에서 PRNG는 블록 암호의 많은 요소를 재사용합니다. 눈사태와 넓은 내부 상태로의 비트 확산에 대한 동일한 개념이 사용됩니다. 대안 적으로, 흉 PRNG는 블록 암호에서 내장 될 수 단순히 사용 N 개의 A와 표현되는 상대 (의 블록 암호로 키 및 암호화 연속적인 값으로 비트 시퀀스를 M 개의 블록 암호가 사용하는 경우에, 비트 시퀀스 해요 - 비트 블록). 이것은 블록 암호가 안전하고 생성 된 스트림이 m * 2 ^ (m / 2) 비트 ( m = 128 인 경우 ) 보다 길지 않는 한 무작위와 계산적으로 구별 할 수없는 비트의 의사 랜덤 스트림을 생성합니다., 이것은 약 3 천억 기가 바이트를 의미하므로 대부분의 목적에 충분합니다). 이러한 종류의 사용을 카운터 모드 (CTR)라고 합니다.

일반적으로 CTR 모드의 블록 암호는 전용 스트림 암호만큼 빠르지 않습니다 (스트림 암호의 요점은 블록 암호의 유연성을 상실함으로써 더 나은 성능이 기대된다는 것입니다). 그러나 AES-NI 명령 (기본적으로 CPU에 통합 된 하드웨어의 AES 구현)을 사용 하는 Intel의 최신 CPU 중 하나를 사용하는 경우 CTR 모드를 사용하는 AES는 탁월한 속도 (당 수 기가 바이트)를 제공합니다. 둘째).

---

우선, 암호화 보안 PRNG의 요점은 완전히 예측할 수없는 시퀀스를 생성 하지 않는 것입니다. 당신이 언급 한 바와 같이, 무언가의 부재 (자세한 이하) 진정한 난수의 대량 생성하는 ^{1 개} 차종 불가능 것을.

그래서 당신은 예측하기 어려운 것에 의지합니다 . 여기서 "하드"는 필요한 것이 무엇이든 어쨌든 쓸모 없게 될 시간이 오래 걸리는 것을 의미합니다. 여기에 중요한 역할을하는 수학적 알고리즘이 많이 있습니다. 잘 알려진 CSPRNG를 사용하여 작동 방식을 살펴보면 알 수 있습니다.

이러한 PRNG를 구축하는 가장 일반적인 변형은 다음과 같습니다.

• 이미 안전한 의사 랜덤 비트 스트림을 출력하는 스트림 암호를 사용합니다.
• 카운터 모드에서 블록 암호 사용

카운터의 해시 함수도 때때로 사용됩니다. Wikipedia는 이것에 대해 더 많은 것을 가지고 있습니다 .

일반적인 요구 사항은 생성기의 비트 스트림에서 원래 초기화 벡터를 결정하는 것이 실행 불가능하고 다음 비트를 쉽게 예측할 수 없다는 것입니다.

초기화와 관련하여 대부분의 CSPRNG는 라인 노이즈, 인터럽트 또는 시스템의 기타 이벤트와 같은 진정한 무작위 항목부터 특정 메모리 위치 & c와 같은 다른 항목에 이르기까지 시스템에서 사용할 수있는 다양한 소스를 사용합니다. 초기화 벡터는 바람직하게는 실제로 무작위이며 수학적 알고리즘에 의존하지 않습니다. 이 초기화는 데비안의 OpenSSL 구현에서 한동안 손상되어 심각한 보안 문제가 발생했습니다.

---

¹ 역시 문제가 있고 열 노이즈와 같은 것들은 온도에 따라 다른 특성을 가지므로 바이어스를 제거하는 데주의해야합니다. 거의 항상 바이어스가 있으므로 제거해야합니다. 그리고 그것은 그 자체로 사소한 작업이 아닙니다.

---

난수 생성기가 암호 학적으로 안전한 것으로 간주 되려면 알고리즘과 이전에 생성 된 (많은) 비트 수를 알고있는 적의 공격으로부터 안전해야합니다. 이것이 의미하는 바는 해당 정보를 가진 사람이 생성기의 숨겨진 내부 상태를 재구성 할 수 없으며 생성 된 다음 비트가 50 % 이상의 정확도로 무엇인지 예측할 수 없다는 것입니다.

일반 의사 난수 생성기는 일반적으로 이전 출력 비트에서 내부 상태를 재구성하는 것이 일반적으로 사소하기 때문에 (종종 전체 내부 상태가 직접 생성 된 마지막 N 비트 일 뿐이므로) 일반적으로 암호 학적으로 안전하지 않습니다. 좋은 통계적 속성이없는 난수 생성기는 내부 상태를 알지 못하더라도 그 출력이 적어도 당사자를 예측할 수 있기 때문에 암호 학적으로 안전하지 않습니다.

따라서 작동 방식에 관해서는 좋은 암호화 시스템을 암호화 보안 난수 생성기로 사용할 수 있습니다. 암호화 시스템을 사용하여 '일반'난수 생성기의 출력을 암호화하십시오. 공격자는 일반 난수 생성기의 일반 텍스트 출력을 재구성 할 수 없으므로 직접 공격 할 수 없습니다. 이것은 암호화 시스템을 안전하게 유지하기 위해 어떻게 키를 입력하는지에 대한 질문을 던지는 다소 순환적인 정의이며, 이는 완전히 다른 문제입니다.

---

각 생성기는 자체 시드 전략을 사용하지만 여기 에 CryptGenRandom 의 Windows API 문서에서 약간의 내용이 있습니다.

With Microsoft CSPs, CryptGenRandom uses the same random number generator used by other security components. This allows numerous processes to contribute to a system-wide seed. CryptoAPI stores an intermediate random seed with every user. To form the seed for the random number generator, a calling application supplies bits it might have—for instance, mouse or keyboard timing input—that are then combined with both the stored seed and various system data and user data such as the process ID and thread ID, the system clock, the system time, the system counter, memory status, free disk clusters, the hashed user environment block. This result is used to seed the pseudorandom number generator (PRNG).

In Windows Vista with Service Pack 1 (SP1) and later, an implementation of the AES counter-mode based PRNG specified in NIST Special Publication 800-90 is used. In Windows Vista, Windows Storage Server 2003, and Windows XP, the PRNG specified in Federal Information Processing Standard (FIPS) 186-2 is used. If an application has access to a good random source, it can fill the pbBuffer buffer with some random data before calling CryptGenRandom. The CSP then uses this data to further randomize its internal seed. It is acceptable to omit the step of initializing the pbBuffer buffer before calling CryptGenRandom.

참고URL : https://stackoverflow.com/questions/2449594/how-does-a-cryptographically-secure-random-number-generator-work