it-swarm-korea.com

PRNG)에서 수집하는 엔트로피 평가

임베디드 장치에서 난수 생성기 (암호화 품질이 예상 됨)를 검토하고 있습니다. 여기서 내 관점은 운영 체제와 암호화 라이브러리 구현 자입니다. 저는 특히 엔트로피 수집에 대해 걱정합니다. 살펴볼 몇 가지 사항을 확인했습니다.

  • PRNG의 초기 상태는 어떻게 생성됩니까?
  • PRNG 더 많은 엔트로피를 얻을 때까지 전달을 거부해야하는 경우는 언제입니까?)
  • 더 많은 엔트로피를 주입하는 API 호출이 있습니다. 새 엔트로피를 기존 상태와 얼마나 잘 혼합합니까?

(제 경우에는 하드웨어 RNG가있어 체계적으로 사용하기에는 너무 느리지 만 여기에서 엔트로피를 얻을 수 있습니다.)

내 구현이 좋은 경우 이러한 질문에 대한 답변은 어떻게됩니까? 다른 어떤 질문에 답해야합니까?

"엔트로피"는 일부 데이터 요소가 무엇 이었을지에 대한 척도입니다. 우리는 이러한 비트가 집합 적으로 가정 될 수 있다면 비트 묶음에 n 비트의 엔트로피가 있다고 말합니다 .2 균일 한 확률을 가진 고유 한 값 ( "균일 한"용어 아래에 숨겨지는 많은 복잡성이 있습니다). 암호화 보안 PRNG를 만들려면 다음을 수행해야합니다.

  1. 128 비트 이상의 엔트로피에 도달 할 수 있도록 임의의 소스에서 충분한 데이터를 수집합니다. 아이디어는 공격자가 2) 공간의 무시할 수없는 부분을 "시도"하는 것이 실행 가능하지 않아야한다는 것입니다. 가능한 내부 상태. n = 8 전통적 가치 였지만, 80 년대 이후의 기술 발전을 감안할 때 이제는 2의 거듭 제곱 인 n = 128을 선호합니다. 그러므로 신들의 축복을 받았습니다.
  2. 적절한 스트림 암호와 같은 함수에서 엔트로피가 포함 된 시드를 사용하십시오. 이것은 초기 키를 기반으로 의사 랜덤 비트를 출력하는 함수입니다. 여기서 키는 고정 길이 출력 (즉, 해시 함수)이있는 단방향 함수를 통해 시드에서 파생됩니다. 여기서 찾는 보안 특성은 연속적인 출력 비트 시퀀스가 ​​주어지면 성공 확률이 0.5보다 훨씬 더 큰 다른 과거 또는 미래 출력 비트를 추측 할 수 없어야한다는 것입니다. "미래의 비트"부분을 염두에 두십시오. 이것은 생각만큼 즉각적이지 않습니다.

두 번째 요점은 쉽지 않습니다. 기본적으로 stream-cipher-like 함수가 일부 표준에 정확하게 설명되어 있고 수십 명의 암호학자가 분석 한 게시 된 구성이 아니라면 PRNG)를 다음과 같이 고려해야합니다. 모호한 품질입니다. 수제 PRNG 수제 블록 암호만큼 나쁩니다 : 그것은 가능 강하지 만 수제 PRNG =은 not ​​강력하며 암호화 강도에 대한 확실한 테스트가 없습니다.

NIST는 일부 "승인 된"PRNG 에 대한 완전한 설명을 게시했습니다. 당신이 사용하는 PRNG 당신이 사용하는 것이 그 중 하나라면, 그것은 좋은 것입니다. 그렇지 않으면 정말로 경고 플래그를 올려야합니다.

정확한 질문 :

  • 초기 PRNG 상태는 "좋은 정보 출처"에서 수집해야합니다. 즉, 출처가 "변경"데이터를 생성 할뿐만 아니라 공격자가 변경 사항을 관찰 할 수없는 방식으로 생성해야 함을 의미합니다. 예를 들어, 외부 네트워크 호스트에 "ping"요청을 보내고 응답이 돌아 오는 데 걸린 시간을 측정하는 것은 아님 좋은 소스입니다. 확실히 무작위로 보이지만 가정해야합니다. 공격자가 나가는 ICMP 요청과 해당 답변을 관찰하여 동일한 타이밍 측정을 얻을 수 있습니다. 이러한 질문에 대한보다 자세한 처리 방법은 이 답변 (예, 인용하고 있습니다. 자기).

  • 추가 엔트로피 주입은 초기 상태 주입과 매우 유사합니다. "무작위 데이터"는 종종 부피가 크면 시드로 사용되므로 높은 엔트로피를 생성하기 위해 약간의 혼합 단계가 있어야합니다. short 순서. 여기서 도구는 보안 해시 함수입니다. 간단하게하기 위해 주입은 다음과 같아야합니다. 현재 내부 상태를 취하고 추가 "엔트로피"를 연결하고 모든 것을 해시합니다. 해시 출력은 새로운 상태입니다. 주의 : 이런 종류의 것은 주어진 해시 함수에 대해 정확히 보장되지 않는 보안 속성에 의존합니다. 여기에서 의미하는 바는 이러한 사용에 대해 보안이 유지되는 것이 충돌 또는 사전 이미지에 대한 내성이라는 결과가 아니라는 것입니다. 따라서 해시 함수를 사용할 때 일종의 믿음이 있습니다 (예를 들어 SHA-256을 사용하는 것보다 더 나쁠 수는 있지만). NIST PRNG에서는 이러한 종류의 작업에 HMAC 를 사용하는 HMAC-DRBG를 잘 살펴볼 것을 권장합니다. HMAC는 유사한 이유로 더 나은 "보안 증명"을 허용하는 방식으로 기본 해시 함수를 사용하는 메시지 인증 코드 입니다.

  • PRNG 더 많은 엔트로피를 얻을 때까지 더 많은 데이터를 제공하는 것을 거부하는 것은 일종의 부두 의식입니다. 그것을 믿는 경우에만 중요합니다. PRNG 충분히 임의의 초기 시드를 사용하고 적절한 데이터 생성 기능을 사용하면 이로부터 페타 바이트의 의사 알레 아를 생성하는 데 보안 문제가 없을 것입니다. PRNG 구현에는 블로킹 동작이 포함되며, 여기서 PRNG는 128 비트 초기 엔트로피에서 1MB 이상의 데이터 출력을 거부합니다. 연습, 차단 PRNG (초기화 이후-충분한 initial 엔트로피가 수집 될 때까지 차단해야 함) 배포 문제 (예 : Linux OS 자동 설치)가 발생합니다. 사용자로부터 엔트로피를 수집 할 키보드 나 마우스가 없기 때문에 SSH 키를 생성 할 때 서버에서 차단됩니다.

    ㅏ. PRNG 표준 상태 참조 ( NIST SP 800-9 );

    비. 표준에 명시 적으로 달리 명시되어 있지 않는 한 완전한 초기 시드가있는 한 차단하지 마십시오.

    Linux의 /dev/random/dev/urandom 둘 다 실패합니다 : /dev/random는 너무 자주 차단되며 /dev/urandom 전혀 차단하지 않습니다. even 좋은 초기 시드를 얻지 못한 경우. 다행히도 괜찮은 Linux 배포판은 /dev/urandom는 부팅 스크립트의 일부로 충분한 시드로 초기화됩니다 (이전 종료시 생성 된 숨겨진 파일에 임의 시드 유지 포함). FreeBSD의 /dev/urandom 내가 설명하는 방식대로 작동하고 좋습니다.

19
Thomas Pornin

주요 질문은 이미 답변되었으므로 답변의 일부를 확장하고 있습니다.

일부 엔트로피 소스가 도청되거나 공격자에 의해 완전히 제어되는 동안 엔트로피 수집은 올바르게 수행하기가 다소 까다로운 작업입니다. 수집 된 엔트로피의 양을 추정하는 것은 실패 할 가능성이 높습니다.

이러한 문제를 해결하기위한 좋은 구현은 Fortuna 입니다. Bruce Schneier 등이 설계했습니다.

1
Nakedible