☰

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

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

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

다음은 의 관련 코드 조각입니다 random.c. 이는 변수의 마지막 두 인터럽트 delta와 델타의 차이 사이의 시간(제 생각에는 jiffies)을 나타냅니다 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를 다룰 때는 몇 가지 기본 아이디어를 올바르게 얻는 것이 중요합니다.

관련 정보