Pouvez-vous expliquer l'estimation d'entropie utilisée dans random.c

/dev/randomutilise les timings des interruptions du noyau pour ajouter au pool d'entropie. La quantité d'entropie dans le pool est suivie dans une variable nommée entropy_count.

Voici l'extrait de code pertinent de random.c. Il représente le temps (en jiffies je pense) entre les deux dernières interruptions en variable deltaet les différences de deltas en tant que 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;

Il semble que l'estimation de l'entropie ajoutée soit essentiellement le plancher (pas le plafond en raison du décalage initial avant la boucle) du logarithme de base 2 du delta. Cela a un certain sens intuitif, bien que je ne sois pas sûr des hypothèses qui seraient nécessaires pour que cela soit formellement correct.

Donc, ma première question est "quel est le raisonnement derrière cette estimation?"

Ma deuxième question concerne delta = MIN(delta, delta2) .... Qu'est-ce que cela fait? Pourquoi prendre le minimum de ce delta et du dernier? Je ne sais pas ce que cela est censé accomplir - peut-être que cela améliore l'estimation, peut-être juste plus conservateur.

Edit: J'ai trouvé un article qui spécifie l'estimation , mais il ne donne pas vraiment d'argument raisonné pour cela (même s'il décrit certaines conditions informelles que l'estimateur devrait remplir).

Autres ressources évoquées dans les commentaires:

• Wikipédia sur /dev/randomet/dev/urandom
• Un papier qui essaie de l'expliquer (je suis sceptique à ce sujet, voir commentaires)
• Un article de blog sur les/dev/random commentaires du gars qui a écrit le code ci-dessus.
• Une réponse secutity.SE sur le /dev/randompool d'entropie.

delta2n'est pas la précédente delta, mais la différence entre deux valeurs successives de delta. C'est une sorte de dérivée: si deltamesure la vitesse, delta2c'est l'accélération.

L'idée intuitive derrière cette estimation est que les interruptions se produisent à des intervalles plus ou moins aléatoires, dictés par des événements imprévisibles du monde physique (par exemple, frappes de touches ou arrivée de paquets réseau). Plus le délai est long, plus les événements imprévisibles sont impliqués. Cependant, il existe des systèmes physiques qui déclenchent des interruptions à un taux fixe; la delta2mesure est un mécanisme de protection qui détecte de telles occurrences (si des interruptions se produisent à intervalles fixes, donc décidément prévisibles, toutes deltaauront la même valeur, donc delta2seront nulles).

J'ai dit "intuitif" et il n'y a pas grand chose à dire. En fait, dans le modèle des "événements physiques aléatoires", le comptage des bits est faux; si un événement matériel se produit avec une probabilité p pour chaque unité de temps et que vous obtenez un retard exprimé sur n bits, alors la contribution d'entropie doit être comptabilisée comme n / 2 bits, pas n bits. Mais nous savons qu'en réalité les événements physiques ne se produisent pas à des moments exactement aléatoires; le delta2mécanisme l'admet.

Donc, dans la pratique, "l'estimation d'entropie" est exactement cela: une estimation . Sa valeur de sécurité ne vient pas d'une justification raisonnée et mathématiquement exacte, mais de la source habituelle de sécurité: personne ne semble (encore) avoir trouvé le moyen d'en abuser.

Cette page a été écrite par quelqu'un qui en a marre des mythes /dev/randomet de son estimateur d'entropie, et je pense que cela explique bien les choses, avec suffisamment de détails. Il est important de bien comprendre certaines idées de base lorsqu'il s'agit de RNG.