☰

Random.c에서 사용되는 엔트로피 추정을 설명할 수 있습니까?

tag-icon • tag-icon linux kernel random
Random.c에서 사용되는 엔트로피 추정을 설명할 수 있습니까?

/dev/random커널 인터럽트 타이밍을 사용하여 엔트로피 풀에 추가합니다. 풀의 엔트로피 양은 라는 변수에서 추적됩니다 entropy_count.

다음은 의 관련 코드 조각입니다 random.c. 이는 변수의 마지막 두 중단 사이의 시간(제 생각에는 jiffies 단위) delta과 delta 의 차이를 나타냅니다 delta2.

delta = time - state->last_time;
state->last_time = time;

delta2 = delta - state->last_delta;
state->last_delta = delta;

if (delta < 0) delta = -delta;
if (delta2 < 0) delta2 = -delta2;
delta = MIN(delta, delta2) >> 1;
for (nbits = 0; delta; nbits++)
  delta >>= 1;

r->entropy_count += nbits;

/* Prevent overflow */
if (r->entropy_count > POOLBITS)
  r->entropy_count = POOLBITS;

추가된 엔트로피의 추정치는 기본적으로 델타의 밑이 2인 로그의 하한인 것처럼 보입니다(루프 이전의 초기 변위로 인해 천장이 아님). 공식적으로 올바른 것으로 만들기 위해 어떤 가정이 필요한지는 잘 모르겠지만 이는 어느 정도 직관적인 의미가 있습니다.

그래서 내 첫 번째 질문은"이러한 추정의 근거는 무엇입니까?"

두 번째 질문은 delta = MIN(delta, delta2) ...이것이 무엇을 하는가에 관한 것입니다. 이 증분과 마지막 증분의 최소값을 취하는 이유는 무엇입니까? 이것이 무엇을 달성하기로 되어 있는지는 모르겠습니다. 어쩌면 추정치를 더 좋게 만들 수도 있고, 더 보수적으로 만들 수도 있습니다.

편집하다:내가 하나 찾았어추정치를 지정하는 파일, 그러나 이는 실제로 건전한 주장을 제공하지 않습니다(비록 추정자가 충족해야 하는 일부 비공식 조건을 간략하게 설명하지만).

의견에 포함된 기타 리소스:

답변1

delta2이전 것은 아니지만 delta,차이점두 개의 연속 값 사이 delta. 이는 미분입니다. delta속도를 측정 하면 delta2가속도입니다.

이 추정의 이면에 있는 직관적인 아이디어는 중단이 물리적 세계에서 예측할 수 없는 이벤트(예: 키 입력 또는 네트워크 패킷 도착)에 의해 결정되는 다소 무작위 간격으로 발생한다는 것입니다. 지연 시간이 길어질수록 예측할 수 없는 사건이 더 많이 발생합니다. 그러나 일부 물리적 시스템은 고정된 속도로 인터럽트를 트리거합니다. 이 delta2조치는 이러한 이벤트의 발생을 감지하기 위한 보호 메커니즘입니다(인터럽트가 고정된 간격으로 발생하여 명확하게 예측 가능한 경우 모든 인터럽트는 delta동일한 값을 가지므로 delta20이 됩니다). ).

"직관적"이라고 하면 별로 할 말이 없습니다. 실제로 "임의의 물리적 이벤트" 모델에서는 하드웨어 이벤트가 확률적으로 발생하는 경우 비트 계산이 잘못됩니다.피각 시간 단위에 대해 다음과 같이 표시되는 값을 얻게 됩니다.N비트이면 엔트로피 기여도는 다음과 같이 계산되어야 합니다.n/2조금, 아니N조금. 그러나 우리는 실제로 물리적 사건이 완전히 무작위로 발생하지 않는다는 것을 알고 있습니다. 메커니즘 delta2도 이를 인식합니다.

따라서 실제로 "엔트로피 추정치"는 정확히 다음과 같습니다.추정. 보안 가치는 건전하고 수학적으로 정확한 이유가 아니라 일반적인 보안 소스에서 비롯됩니다. 지금까지 아무도 이를 남용할 방법을 찾지 못한 것 같습니다.

이 페이지엔트로피 추정기에 대한 미신 에 지친 누군가가 쓴 이 /dev/random책은 내용을 충분히 자세하게 설명하고 있다고 생각합니다. RNG를 다룰 때는 몇 가지 기본 개념을 올바르게 이해하는 것이 중요합니다.

관련 정보