☰

¿Puedes explicar la estimación de entropía utilizada en random.c?

tag-icon • tag-icon linux kernel random
¿Puedes explicar la estimación de entropía utilizada en random.c?

/dev/randomutiliza los tiempos de las interrupciones del kernel para agregar al grupo de entropía. La cantidad de entropía en el grupo se rastrea en una variable denominada entropy_count.

Aquí está el fragmento de código relevante de random.c. Representa el tiempo (en santiamén, creo) entre las dos últimas interrupciones en variable deltay las diferencias en deltas como 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;

Parece que la estimación de la entropía agregada es esencialmente el piso (no el techo debido al desplazamiento de bits inicial antes del bucle) del logaritmo de base 2 de delta. Esto tiene cierto sentido intuitivo, aunque no estoy seguro de qué suposiciones serían necesarias para que esto sea formalmente correcto.

Entonces mi primera pregunta es"¿Cuál es el razonamiento detrás de esta estimación?"

Mi segunda pregunta es sobre delta = MIN(delta, delta2) .... ¿Qué hace esto? ¿Por qué tomar el mínimo de este delta y el último? No sé qué se supone que se debe lograr con esto; tal vez mejore la estimación, tal vez simplemente sea más conservadora.

Editar:he encontrado unpapel que especifica la estimación, pero en realidad no proporciona un argumento razonado (aunque sí describe algunas condiciones informales que el estimador debe cumplir).

Otros recursos que han surgido en los comentarios:

Respuesta1

delta2no es el anterior delta, sino eldiferenciaentre dos valores sucesivos de delta. Es una especie de derivada: si deltase mide la velocidad, delta2es la aceleración.

La idea intuitiva detrás de esa estimación es que las interrupciones ocurren en intervalos más o menos aleatorios, dictadas por eventos impredecibles del mundo físico (por ejemplo, pulsaciones de teclas o llegada de paquetes de red). Cuanto mayor sea el retraso, más acontecimientos impredecibles se producirán. Sin embargo, existen sistemas físicos que disparan interrupciones a un ritmo fijo; la delta2medida es un mecanismo de protección que detecta tales sucesos (si las interrupciones ocurren a intervalos fijos, por lo tanto decididamente predecibles, todas deltatendrán el mismo valor, por lo tanto delta2serán cero).

Dije "intuitivo" y no hay mucho más que decir. De hecho, en el modelo de "eventos físicos aleatorios", contar los bits es incorrecto; si un evento de hardware ocurre con probabilidadpagpara cada unidad de tiempo, y obtienes un retraso expresado sobrenortebits, entonces la contribución de entropía debe contabilizarse comon/2bits, nonortebits. Pero sabemos que en realidad los acontecimientos físicos no ocurren en momentos exactamente aleatorios; el delta2mecanismo lo admite.

Entonces, en la práctica, la "estimación de entropía" es exactamente eso: unaestimar. Su valor de seguridad no proviene de una justificación matemáticamente exacta y bien razonada, sino de la fuente habitual de seguridad: nadie parece haber encontrado una manera de abusar de ella (todavía).

Esta páginaFue escrito por alguien que se hartó de los mitos sobre /dev/randomsu estimador de entropía, y creo que explica bien las cosas, con bastantes detalles. Es importante tener algunas ideas básicas correctas cuando se trata de RNG.

información relacionada