☰

Können Sie die in random.c verwendete Entropieschätzung erklären?

tag-icon • tag-icon linux kernel random
Können Sie die in random.c verwendete Entropieschätzung erklären?

/dev/randomverwendet die Zeitpunkte von Kernel-Interrupts, um sie zum Entropiepool hinzuzufügen. Die Entropiemenge im Pool wird in einer Variablen namens verfolgt entropy_count.

Hier ist der entsprechende Codeausschnitt aus random.c. Er stellt die Zeit (in Sekunden, glaube ich) zwischen den letzten beiden Unterbrechungen in der Variablen deltaund die Differenzen in Deltas als dar 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;

Es sieht so aus, als ob die Schätzung der hinzugefügten Entropie im Wesentlichen die Untergrenze (nicht die Obergrenze wegen der anfänglichen Bitverschiebung vor der Schleife) des Logarithmus zur Basis 2 von Delta ist. Das macht intuitiv Sinn, obwohl ich nicht sicher bin, welche Annahmen erforderlich wären, um dies formal korrekt zu machen.

Meine erste Frage ist also"Was ist der Grund für diese Schätzung?"

Meine zweite Frage betrifft delta = MIN(delta, delta2) .... Was bewirkt das? Warum wird das Minimum dieses Deltas und des letzten genommen? Ich weiß nicht, was das bewirken soll – vielleicht wird dadurch die Schätzung besser, vielleicht nur konservativer.

Bearbeiten:Ich habe eine gefundenPapier, das die Schätzung angibt, aber es wird kein wirklich begründetes Argument dafür geliefert (obwohl einige informelle Bedingungen umrissen werden, die der Schätzer erfüllen sollte).

Weitere Ressourcen, die in den Kommentaren aufgetaucht sind:

Antwort1

delta2ist nicht das vorherige delta, sondern dasUnterschiedzwischen zwei aufeinanderfolgenden Werten von delta. Es ist eine Art Ableitung: Wenn deltadie Geschwindigkeit gemessen wird, delta2ist die Beschleunigung.

Die intuitive Idee hinter dieser Schätzung ist, dass Interrupts in mehr oder weniger zufälligen Intervallen auftreten, die durch unvorhersehbare Ereignisse aus der physischen Welt bestimmt werden (z. B. Tastenanschläge oder das Eintreffen von Netzwerkpaketen). Je länger die Verzögerung, desto mehr unvorhersehbare Ereignisse sind beteiligt. Es gibt jedoch physische Systeme, die Interrupts mit einer festen Rate auslösen; die delta2Maßnahme ist ein Schutzmechanismus, der solche Vorkommnisse erkennt (wenn Interrupts in festen Intervallen auftreten und daher eindeutig vorhersehbar sind, deltahaben alle den gleichen Wert und delta2sind daher Null).

Ich sagte "intuitiv" und es gibt nicht viel mehr zu sagen. Tatsächlich ist das Zählen der Bits im Modell der "zufälligen physikalischen Ereignisse" falsch; wenn ein Hardware-Ereignis mit Wahrscheinlichkeit eintrittPfür jede Zeiteinheit, und Sie erhalten eine Verzögerung ausgedrückt überNBits, dann sollte der Entropiebeitrag berücksichtigt werden alsNr. 2Bits, nichtNBits. Aber wir wissen, dass die physikalischen Ereignisse in Wirklichkeit nicht zu genau zufälligen Zeitpunkten auftreten; das delta2lässt der Mechanismus zu.

In der Praxis ist die „Entropieschätzung“ also genau das: eineschätzen. Sein Sicherheitswert beruht nicht auf einer gut durchdachten, mathematisch exakten Begründung, sondern auf der üblichen Quelle der Sicherheit: Niemand scheint (noch) einen Weg gefunden zu haben, es zu missbrauchen.

Diese Seite/dev/randomwurde von jemandem geschrieben, der die Mythen über und seinen Entropieschätzer satt hatte , und ich denke, es erklärt die Dinge gut und mit genügend Details. Es ist wichtig, einige grundlegende Ideen richtig zu verstehen, wenn man mit RNG arbeitet.

verwandte Informationen