(Vorsicht: Ich behaupte sicher nicht, dass HAVEGE seinen Ansprüchen gerecht wird. Ich habe ihre Theorie oder Implementierung nicht überprüft.)
Um Zufälligkeit zu erreichen, stützen sich HAVEGE und ähnliche Systeme auf "physikalische Ereignisse", und insbesondere auf das Timing von physikalischen Ereignissen. Zu solchen Ereignissen gehören das Auftreten von Hardware-Interrupts (die wiederum Daten über Tastenanschläge, Mausbewegungen, eingehende Ethernet-Pakete, Zeit für eine Festplatte zum Abschließen einer Schreibanforderung sammeln ...). HAVEGE behauptet auch, sich von allen Arten von Cache-Fehlern zu ernähren, die in einer CPU auftreten (L1-Cache, L2-Cache, TLB, Verzweigungsvorhersage ...); Das Verhalten dieser Elemente hängt davon ab, was die CPU in den letzten paar Tausend Taktzyklen getan hat, daher besteht die Möglichkeit einer gewissen "Zufälligkeit". Dies hängt von der Möglichkeit ab, die aktuelle Zeit mit großer Präzision (nicht unbedingt Genauigkeit) zu messen, wofür der rdtsc Anleitung kommt ins Spiel. Es gibt den aktuellen Inhalt eines internen Zählers zurück, der bei jedem Taktzyklus inkrementiert wird, sodass es eine Genauigkeit von weniger als einer Nanosekunde bietet.
Für ein virtuelles Maschinensystem gibt es bezüglich dieser Anweisung drei Möglichkeiten:
- Lassen Sie die Anweisung direkt an die Hardware gehen.
- Fangen Sie die Anweisung ab und emulieren Sie sie.
- Deaktivieren Sie die Anweisung vollständig.
Wenn der VM-Manager die erste Lösung wählt, dann rdtsc verfügt über die erforderliche Präzision und sollte genauso gut funktionieren wie auf einer physischen Maschine, um Entropie aus Hardwareereignissen zu sammeln. Da es sich jedoch um eine virtuelle Maschine handelt, handelt es sich um eine Anwendung auf dem Hostsystem; es bekommt die CPU nicht die ganze Zeit. Aus Sicht des Gastbetriebssystems mit rdtsc , das sieht so aus, als ob ihm gelegentlich die CPU "gestohlen" wurde:zwei aufeinanderfolgende rdtsc Befehle, die nominell durch einen einzigen Taktzyklus getrennt sind, können eine Erhöhung des Zählers um mehrere Millionen melden . Kurz gesagt, wenn rdtsc wird einfach auf die Hardware angewendet, dann kann das Gastbetriebssystem damit das Vorhandensein eines Hypervisors erkennen.
Die zweite Lösung soll die Emulation "perfekter" machen, indem ein virtueller Zykluszähler pro VM verwaltet wird, der die Zyklen verfolgt, die dieser VM wirklich zugewiesen sind. Der Vorteil ist, dass rdtsc wird aus Sicht des Gastes nicht mehr den „Stolen Cycles“-Effekt aufweisen. Der Nachteil ist, dass diese Emulation durch Auslösen und Abfangen einer CPU-Ausnahme ausgeführt wird, was die Kosten für rdtsc erhöht Opcode von ein paar Dutzend Taktzyklen (es hängt von der CPU-Marke ab; einige führen rdtsc aus in weniger als 10 Zyklen, andere verwenden 60 oder 70 Zyklen) auf mehr als eintausend von Zyklen. Wenn der Gast versucht, viel rdtsc zu tun (wie HAVEGE dazu neigen wird), dann wird es zu einem Kriechen verlangsamen. Darüber hinaus wird der Ausnahmebehandlungscode die Maßnahme unterbrechen; Anstatt das Timing des Hardwareereignisses zu messen, misst der Code die Ausführungszeit des Ausnahmehandlers, was die Qualität der extrahierten Zufälligkeit möglicherweise verringern kann.
Die dritte Lösung (Deaktivieren von rdtsc ) wird HAVEGE einfach daran hindern, eine gute Zufälligkeit zurückzugeben. Da es intern ein PRNG verwendet, kann die Ausgabe immer noch statistische Analysetools täuschen, da es einen großen Unterschied zwischen „zufällig aussehen“ und „unvorhersehbar sein“ gibt (statistische Analysetools folgen dem „zufällig aussehen“-Pfad, aber kryptografische Sicherheit beruht auf Unvorhersehbarkeit ).
Das VirtualBox-Handbuch behauptet, dass VirtualBox standardmäßig der ersten Methode folgt (rdtsc ist bedingungslos erlaubt und wird direkt auf die Hardware angewendet), kann aber so konfiguriert werden, dass die zweite Lösung angewendet wird (was Sie in diesem Fall nicht möchten).
Um zu testen, was Ihre VM tut, können Sie dieses kleine Programm ausprobieren (kompilieren Sie mit gcc -W -Wall -O unter Linux; die -O ist wichtig):
#include <stdio.h>
#if defined(__i386__)
static __inline__ unsigned long long rdtsc(void)
{
unsigned long long int x;
__asm__ __volatile__ (".byte 0x0f, 0x31" : "=A" (x));
return x;
}
#elif defined(__x86_64__)
static __inline__ unsigned long long rdtsc(void)
{
unsigned hi, lo;
__asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi));
return ( (unsigned long long)lo)|( ((unsigned long long)hi)<<32 );
}
#endif
int
main(void)
{
long i;
unsigned long long d;
d = 0;
for (i = 0; i < 1000000; i ++) {
unsigned long long b, e;
b = rdtsc();
e = rdtsc();
d += e - b;
}
printf("average : %.3f\n", (double)d / 1000000.0);
return 0;
}
Auf einer nicht virtuellen Maschine mit dem "wahren" rdtsc , soll dieser je nach CPU-Marke einen Wert zwischen 10 und 100 ausgeben. Wenn der gemeldete Wert 0 ist oder wenn das Programm abstürzt, dann rdtsc ist behindert. Wenn der Wert in Tausend ist, dann rdtsc wird emuliert, was bedeutet, dass die Entropieerfassung möglicherweise nicht so gut funktioniert wie erwartet.
Beachten Sie, dass selbst ein Wert zwischen 10 und 100 keine Garantie dafür ist, dass rdtsc wird nicht emuliert, da der VM-Manager, während er seinen virtuellen Zähler beibehält, davon die erwartete Zeit abziehen kann, die für die Ausführung des Ausnahmebehandlers benötigt wird. Letztendlich sollten Sie sich unbedingt das Handbuch und die Konfiguration Ihres VM-Managers ansehen.
Natürlich ist die ganze Prämisse von HAVEGE fragwürdig. Für jede praktische Sicherheit benötigen Sie ein paar "echte zufällige" Bits, nicht mehr als 200, die Sie als Seed in einem kryptografisch sicheren PRNG verwenden. Der PRNG wird Gigabyte an Pseudo-Alea produzieren, die nicht von echter Zufälligkeit zu unterscheiden sind, und das ist gut genug für alle praktischen Zwecke.
Darauf zu bestehen, für jedes bisschen auf die Hardware zurückzugreifen, sieht aus wie ein weiterer Ausbruch dieser fehlerhaften Idee, die Entropie als eine Art Benzin sieht, das man verbrennt, wenn man es ansieht.
Zum Polarssl-Ratgeber:Eine detaillierte technische Antwort finden Sie in der neuesten Debian-Quelle:
http://bazaar.launchpad.net/~ubuntu-branches/debian/experimental/haveged/experimental/revision/12?start_revid=12#debian/README.Debian
Die Zusammenfassung lautet:polarssl !=haveged !=HAVEGE
Zu den embloms.se-Emulatorexperimenten:
Die haveged Testsuite, NIST und ent , überprüfen Sie, ob ein Quell-Build ein funktionierendes RNG erzeugt hat. Laufzeittests sind erforderlich, um den Haveged-Betrieb in einer virtuellen Umgebung zu überprüfen. Das ist eine relativ neue Ergänzung zu haveged.
Zu statistischen Tests:
Angenommen, Sie haben einen hardware RNG , ein TRNG , woher weißt du, dass es nicht kaputt ist? Hardware bricht. Das deutsche Normungsgremium hat eine Spezifikation, die genau dieses Problem behandelt, AIS31 . Dieser Ansatz wird von haveged übernommen. Eine (voreingenommene) Erörterung der Standards für RNG, wie sie für Haved gelten, finden Sie unter:
http://www.issihosts.com/haveged/ais31.html
Die Unberechenbarkeit von HAVEGE ist genau derselbe Mechanismus, der in Benchmarking-Software zu sehen ist. Dies liegt nicht an der Drift des Zeitgebers, sondern an der Aggregation des asynchronen Verhaltens in einem modernen Prozessor. Es spielt wirklich keine Rolle, ob die Leistungsschwankungen von einem Cache-Miss oder einer an einen anderen Prozessor gelieferten Zeitscheibe stammen. Auch die Timer-Genauigkeit spielt keine Rolle, solange sie „ausreichend“ ist. Wie wird das bestimmt? Durch die Ausgabe. Durch Design (oder vielleicht über Design) /dev/random ist immun gegen schlechte Eingabedaten. Die einzige Möglichkeit, das Design zu untergraben, besteht darin, über die Entropie zu lügen, die dem Entropiepool hinzugefügt wird. Die neuesten Versionen von haveged führen eine Laufzeitentropieschätzung für die erzeugte Ausgabe durch, um sicherzustellen, dass die Ausgabe mit einem idealen TRNG übereinstimmt.
Zusammenfassung:haveged Die Ausgabe ist nicht von einem TRNG zu unterscheiden nach Tests der deutschen Normungsstelle zur Zertifizierung TRNG . Wenn dies nicht der Fall ist, haveged wird heruntergefahren.
(Aktualisiert , mit Dank an gwuertz der aktuelle Autor/Betreuer von haveged , habe ich die Trennung zwischen HAVEGE verpasst und haveged .)
haveged ist eine eigenständige Implementierung der HAVEGE-Methode zum Generieren von Zufallszahlen, sie ist aktuell, gepflegt und hier dokumentiert:http://www.issihosts.com/haveged/ (und verwendet libhavege nicht mehr direkt).
HAVEGE ist nicht sehr aktuell (2006), obwohl jemand es vor kurzem (2009) für Geschwindigkeit und Korrektheit gepatcht hat. Ich wäre vorsichtig, weil es seine Methode nicht dokumentiert, virtuelle Maschinen nicht erwähnt und sich, wie bereits erwähnt, (stark) auf RDTSC stützt (oder Plattformäquivalent). (Auch der Quellcode lässt mich schaudern, aber das ist ziemlich subjektiv.)
Ich werde argumentieren, dass die Host-VM keinen Zustand unbeabsichtigt an die Gäste weitergeben sollte, daher sollte sie bei Verwendung dieser Methode nicht als gute Entropiequelle angesehen werden.
Ein besserer Ansatz unter Linux sind rng-tools mit dem paravirtualisierten rng-Treiber virtio-rng (d. h. einem Gast den Zugriff auf die vom Host gesammelte Entropie zu ermöglichen, wodurch viele potenzielle Probleme mit der Ansicht von "zufälligen" Ereignissen durch einen Gast beseitigt werden), oder Sie finden möglicherweise Entropy Broker nützlicher. Auf neueren Intel-Chips können Sie die RDRAND-Anweisung auch Gästen zur Verfügung stellen und so das Problem umgehen.
Dieser Artikel (aus dem Vortrag von hpa auf der LinuxCon Europe 2012 ) ist eine nützliche Lektüre:http://lwn.net/Articles/525459/ , dort wird auch HAVEGE besprochen /haveged (obwohl die Unterscheidung auch hier nicht klar ist).
In den Antworten auf diese Frage finden Sie einige Gedanken zur Bestimmung von Mangel der Zufälligkeit:Welche Statistiken können verwendet werden, um pseudozufällige Daten zu identifizieren?