/dev/random
Verwendet die Zeitabläufe von Kernel-Interrupts, um den Entropiepool zu erweitern. Der Entropiebetrag im Pool wird in einer Variablen namens verfolgt entropy_count
.
Hier ist der relevante Codeausschnitt von random.c
. Es repräsentiert die Zeit (in Sekunden) zwischen den letzten beiden Unterbrechungen in Variable delta
und den Unterschieden in Deltas als 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 der Grundwert (nicht Ceil aufgrund der anfänglichen Bitverschiebung vor der Schleife) des Logarithmus zur Basis 2 von Delta ist. Das ergibt einen intuitiven Sinn, obwohl ich nicht sicher bin, welche Annahmen erforderlich wären, um dies formal korrekt zu machen.
Meine erste Frage lautet also: "Was ist die Begründung für diese Schätzung?"
Meine zweite Frage betrifft delta = MIN(delta, delta2) ...
. Was macht das? Warum das Minimum dieses Deltas und das letzte nehmen? Ich weiß nicht, was damit erreicht werden soll - vielleicht verbessert es die Schätzung, vielleicht ist es nur konservativer.
Bearbeiten: Ich habe ein Dokument gefunden , in dem die Schätzung angegeben ist, das jedoch kein begründetes Argument enthält (obwohl es einige informelle Bedingungen enthält, die der Schätzer erfüllen sollte).
Andere Ressourcen, die in den Kommentaren erwähnt wurden:
- Wikipedia auf
/dev/random
und/dev/urandom
- Ein Papier, das versucht, es zu erklären (ich bin skeptisch, siehe Kommentare)
- Ein Blogeintrag
/dev/random
mit Kommentaren von dem Typ, der den obigen Code geschrieben hat. - Eine secutity.SE-Antwort zum
/dev/random
Entropiepool.
/dev/random
auf einem verwackelten Fundament liegt - siehe Feeding / dev / random entropy pool? . Ich habe Thomas angerufen, in der Hoffnung, dass er Ihre Frage beantwortet.Antworten:
delta2
ist nicht der vorherigedelta
, sondern der Unterschied zwischen zwei aufeinanderfolgenden Werten vondelta
. Es ist eine Art Ableitung: Wenn mandelta
die Geschwindigkeit misst,delta2
ist das 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 (z. B. Tastenanschläge oder Eintreffen von Netzwerkpaketen) bestimmt werden. Je länger die Verzögerung ist, desto unvorhersehbarer sind die Ereignisse. Es gibt jedoch physische Systeme, die einen Brand mit einer festgelegten Rate auslösen. Die
delta2
Maßnahme ist ein Schutzmechanismus, der solche Vorkommnisse erkennt (wenn Interrupts in festen Intervallen auftreten und somit eindeutig vorhersehbar sind, haben alledelta
den gleichen Wert und sind daherdelta2
Null).Ich sagte "intuitiv" und es gibt nicht viel mehr zu sagen. Tatsächlich ist das Zählen der Bits im Modell "zufällige physikalische Ereignisse" falsch; Wenn ein Hardwareereignis mit der Wahrscheinlichkeit p für jede Zeiteinheit auftritt und Sie eine Verzögerung erhalten, die über n Bits ausgedrückt wird, sollte der Entropiebeitrag als n / 2 Bits und nicht als n Bits berücksichtigt werden . Wir wissen jedoch, dass die physischen Ereignisse in Wirklichkeit nicht zu genau zufälligen Zeitpunkten stattfinden. Der
delta2
Mechanismus gibt so viel zu.In der Praxis ist die "Entropieschätzung" genau das: eine Schätzung . Sein Sicherheitswert beruht nicht auf einer gut begründeten, mathematisch genauen Begründung, sondern auf der üblichen Sicherheitsquelle: Niemand scheint (noch) einen Weg gefunden zu haben, ihn zu missbrauchen.
Diese Seite wurde von jemandem geschrieben, der die Mythen
/dev/random
und den Entropieschätzer satt hat , und ich denke, sie erklärt die Dinge gut und mit genügend Details. Beim Umgang mit RNG ist es wichtig, einige grundlegende Ideen richtig zu machen.quelle