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

/dev/randomusa los tiempos de interrupciones del núcleo 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 jiffies, creo) entre los dos últimos 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 delta. Esto tiene un sentido intuitivo, aunque no estoy seguro de qué suposiciones serían necesarias para hacer esto 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 esto debe lograr, tal vez mejore la estimación, tal vez solo sea más conservador.

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

Otros recursos que han surgido en los comentarios:

• Wikipedia en /dev/randomy/dev/urandom
• Un documento que trata de explicarlo (soy escéptico al respecto, ver comentarios)
• Una publicación de blog acerca/dev/random de los comentarios del tipo que escribió el código anterior.
• Una seguridad. Respuesta de SE sobre el /dev/randomgrupo de entropía.

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

La idea intuitiva detrás de esa estimación es que las interrupciones ocurren a intervalos más o menos aleatorios, dictados por eventos impredecibles del mundo físico (por ejemplo, pulsaciones de teclas o llegada de paquetes de red). Cuanto mayor es la demora, más eventos impredecibles están involucrados. Sin embargo, hay sistemas físicos que disparan interrupciones a una velocidad fija; la delta2medida es un mecanismo de protección que detecta tales ocurrencias (si se producen interrupciones a intervalos fijos, por lo tanto, previsiblemente decidibles, todas deltatendrán el mismo valor, por delta2lo tanto , será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 se produce un evento de hardware con probabilidad p para cada unidad de tiempo, y obtiene un retraso expresado en n bits, la contribución de entropía debe contabilizarse como n / 2 bits, no n bits. Pero sabemos que en realidad los eventos 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: una estimación . Su valor de seguridad no proviene de una justificación matemáticamente precisa y bien razonada, sino de la fuente habitual de seguridad: nadie parece haber encontrado una manera de abusar de ella (todavía).

Esta página fue escrita por alguien que se hartó de los mitos /dev/randomy su estimador de entropía, y creo que explica bien las cosas, con suficientes detalles. Es importante tener algunas ideas básicas correctas cuando se trata de RNG.