RNG-Implementierungen testen und validieren

Das Testen von Zufallszahlengeneratoren steht vor einer grundlegenden Herausforderung: Wirklich zufällige Folgen und pseudorandomisierte Folgen eines guten PRNG sehen für statistische Tests identisch aus. Kein Test einer endlichen Folge kann beweisen, dass eine Folge zufällig ist — statistische Tests können Nichtzufälligkeit nur mit einer gewissen Sicherheit erkennen. Tests überprüfen, dass ein RNG keine offensichtlichen Verzerrungen oder Muster aufweist, können aber keine kryptografische Sicherheit beweisen. Das Testen kryptografischer RNGs verfolgt zwei unterschiedliche Ziele: (1) statistische Qualität — überprüfen, ob die Ausgabeverteilung gleichförmig und unabhängig erscheint; (2) kryptografische Stärke — überprüfen, ob der DRBG-Algorithmus korrekt implementiert ist und die Sicherheitsbehauptungen zutreffen. Dafür sind unterschiedliche Testansätze erforderlich.

NIST SP 800-22 stellt 15 statistische Tests zur Bewertung von Bitfolgen bereit. Zu den Tests gehören: Frequency-Test (Monobit-Test) — der Anteil der 1en sollte nahe bei 0,5 liegen. Block-Frequency-Test — die Häufigkeit von 1en in jedem m-Bit-Block. Runs-Test — die Anzahl ununterbrochener Folgen identischer Bits. Longest-Run-Test — die Länge der längsten Folge von 1en. Binary-Matrix-Rank-Test — der Rang binärer Matrizen, die aus der Folge gebildet werden. Spektraltest (DFT) — erkennt periodische Muster. Overlapping-Template-Matching — zählt das Auftreten bestimmter Muster. Maurers universeller statistischer Test — komprimiert die Folge und misst, um wie viel sie dadurch kürzer wird. Jeder Test erzeugt einen p-Wert; p < 0.01 deutet auf Nichtzufälligkeit hin. Die Tests werden auf 1 Million bis 1 Milliarde Bits angewendet.

TestU01 (L'Ecuyer und Simard, 2007) ist eine umfassende Testsuite statistischer Tests, die in der RNG-Community weit verbreitet ist. SmallCrush: 10 Tests, etwa 35 Sekunden, geeignet für schnelle Überprüfungen. Crush: 144 Tests, etwa 2 Stunden. BigCrush: 160 Tests, etwa 24 Stunden. BigCrush erkennt subtile Korrelationen, die NIST SP 800-22 übersieht. Gut entwickelte kryptografische DRBGs wie HMAC_DRBG und CTR_DRBG bestehen BigCrush ohne Weiteres — ihre Ausgabe ist für Algorithmen mit polynomialer Laufzeit rechnerisch nicht von Zufall zu unterscheiden. Nichtkryptografische PRNGs wie der Mersenne-Twister und lineare Kongruenzgeneratoren fallen bei einigen BigCrush-Tests durch. Ein Nichtbestehen von BigCrush ist ein starkes Indiz dafür, dass der RNG nicht für kryptografische Zwecke verwendet werden sollte.

SP 800-90B und 90A schreiben Gesundheitstests vor, die DRBGs während des Betriebs kontinuierlich durchführen müssen. Continuous RNG Test (CRNGT): Jeder erzeugte Block wird mit dem vorherigen Block verglichen — sind sie gleich, muss der DRBG in einen Fehlerzustand wechseln und die Erzeugung stoppen. Repetition Count Test: Wenn aufeinanderfolgende Stichproben häufiger denselben Wert aufweisen, als angesichts der Entropieschätzung statistisch zu erwarten wäre, schlägt der Test fehl. Adaptive Proportion Test: Wenn der am häufigsten auftretende Wert in einem Fenster öfter als eine bestimmte Schwellenanzahl vorkommt, schlägt der Test fehl. Diese Gesundheitstests erkennen Ausfälle von Entropiequellen wie einen festhängenden Sensor oder einen HWRNG-Hardwarefehler, bevor sie unbemerkt die Erzeugung kryptografischer Schlüssel beeinträchtigen.

PractRand ist ein modernes Testwerkzeug für RNGs, das für die Online- (Streaming-)Auswertung entwickelt wurde. Es analysiert die Folge während ihrer Erzeugung, statt eine vorab festgelegte Länge zu benötigen. Dabei verwendet es unter anderem Lückentests, Bitverteilungstests und Spektraltests mit adaptiver Genauigkeit. PractRand eignet sich besonders gut, um RNGs zu erkennen, die kurze Folgen von guter Qualität erzeugen, aber über Milliarden von Bits hinweg Muster erkennen lassen. Kryptografische DRBGs erzeugen unabhängig von der Länge eine Ausgabe, die PractRand nicht von Zufall unterscheiden kann — dies ist die operationale Definition der rechnerischen Ununterscheidbarkeit. PractRand wird auch zur Bewertung von Entropiequellen eingesetzt, etwa zum Testen der Ausgaben von /dev/urandom und RDRAND, um Hardwareausfälle oder systematische Verzerrungen zu erkennen.

Das Cryptographic Algorithm Validation Program (CAVP) stellt offizielle Testvektoren für DRBGs aus SP 800-90A bereit. Beim CAVP-Test wird eine Implementierung mit Known-answer-Test- (KAT-)Vektoren an das automatisierte Testsystem von NIST übermittelt: Bei einer bestimmten Entropieeingabe, einem Nonce, einem Personalisierungsstring und additional_input muss die Implementierung exakt die erwarteten Ausgabebits erzeugen. CAVP testet keine statistischen Eigenschaften, sondern die algorithmische Korrektheit. Die FIPS-140-3-Zertifizierung erfordert eine CAVP-Validierung für alle kryptografischen Algorithmen, die innerhalb der Modulgrenze verwendet werden. CAVP-Testvektoren sind öffentlich auf dem ACVP-Server (Automated Crypto Validation Protocol) von NIST verfügbar und in die Testsuiten von OpenSSL, mbedTLS und BoringSSL integriert.

Bevor ein DRBG sicher initialisiert werden kann, muss seine Entropiequelle validiert werden. SP 800-90B definiert: (1) Entropieschätzung — Messung der tatsächlichen Entropie pro Bit mithilfe statistischer Tests (Min-Entropie-Schätzung). (2) Starttests — Überprüfung, dass die Entropiequelle vor der ersten Verwendung gültige Ausgaben erzeugt. (3) Bedarfstests — optionale Tests, die von der Anwendung ausgelöst werden. (4) Gesundheitstests der Rauschquelle — Erkennung von Hardwareverschleiß. Häufige Entropiequellen und ihre geschätzte Entropie pro Bit: CPU-RDRAND/RDSEED (etwa 1 Bit/Bit, hardwarezertifiziert); /dev/urandom (mischt mehrere Quellen, die Entropieschätzung ist konservativ); Ringoszillator-TRNG (0,5–0,9 Bit/Bit je nach Design); ADC-Rauschen (0,1–0,5 Bit/Bit). Die Validierung nach SP 800-90B erfordert Labortests mit Spezialausrüstung.

Virtuelle Umgebungen bringen besondere Herausforderungen beim Testen von RNGs mit sich. VMs können beim Start (keine Hardwareereignisse) oder nach der Wiederherstellung eines Snapshots (zurückgesetzter Zustand) auf Bedingungen mit geringer Entropie stoßen. Docker-Container verwenden den RNG des Host-Kernels gemeinsam — ein Container kann die zugrunde liegende Entropiequalität nicht direkt testen. Tests für VM-Bereitstellungen: (1) Messen Sie die Zeit bis zum Abschluss eines Lesevorgangs aus /dev/random — lange Wartezeiten weisen auf unzureichende Entropie hin. (2) Testen Sie auf doppelte UUIDs oder Schlüssel, die parallel in VM-Instanzen erzeugt werden (ein realer, in Cloud-Bereitstellungen dokumentierter Fehlerfall). (3) Überprüfen Sie, ob VIRTIO-RNG (virtio_rng.ko) in den VMs geladen ist — dadurch wird Entropie vom Host in den Gast eingeschleust. (4) Prüfen Sie die Startsequenz der Anwendung: Findet die Schlüsselerzeugung statt, bevor ausreichend Entropie verfügbar ist?

Das Testen der Fork-Sicherheit eines RNG verhindert eine subtile Schwachstelle: Wenn ein Prozess einen Fork ausführt, verwenden übergeordneter Prozess und Kindprozess denselben DRBG-Zustand und erzeugen dadurch identische Sequenzen. Erkennung: Starten Sie N Kindprozesse, erzeugen Sie in jedem eine UUID und überprüfen Sie, dass alle UUIDs eindeutig sind. Wenn zwei übereinstimmen, ist der RNG nicht fork-sicher. OpenSSL behob 2020 einen Fehler in der Fork-Sicherheit (CVE-2020-1971 betraf nicht direkt den DRBG, aber das Muster ist ähnlich). OpenSSL verwendet derzeit ein PID-basiertes Seed-Update: Wenn sich die PID seit dem letzten Aufruf geändert hat (was auf einen Fork hindeutet), führt der DRBG automatisch ein Reseeding durch. So testen Sie dies: Führen Sie den Test vor und nach einem Fork aus und bestätigen Sie das Reseeding, indem Sie überprüfen, dass die Ausgaben unterschiedlich sind.

Praktische Audit-Checkliste für RNG-Implementierungen: (1) Wird der RNG über das Betriebssystem initialisiert (getrandom, BCryptGenRandom) statt mit zeitbasierten Seeds? (2) Ist der DRBG-Typ ein von NIST SP 800-90A zugelassener Mechanismus (Hash, HMAC, CTR)? (3) Ist die Seed-Länge ausreichend für die behauptete Sicherheitsstärke? (4) Wird regelmäßig oder nach einer festgelegten Anzahl von Generierungsaufrufen ein Reseeding ausgelöst? (5) Bewältigt die Implementierung die Fork-Sicherheit (Reseeding nach einem Fork)? (6) Sind Health Tests aktiviert, und hält die Implementierung das System bei einem Fehler an? (7) Wird der Zustand beim Herunterfahren auf null gesetzt? (8) Werden CAVP-Testvektoren in CI/CD ausgeführt? (9) Sind Entropieschätzungen dokumentiert und validiert? (10) Für FIPS-Anforderungen: Ist das Modul nach FIPS 140-3 zertifiziert?

Historische RNG-Fehler verdeutlichen, wie viel auf dem Spiel steht. Debian OpenSSL (2006–2008): Ein Patch entfernte versehentlich zwei Zeilen zur Entropiesammlung und reduzierte dadurch den Seed-Pool auf einen 15-Bit-PID-Raum — für die gesamte Debian-Benutzerbasis wurden nur 32.767 mögliche SSH-Schlüssel erzeugt. Alle von Debian erzeugten SSH-Hostschlüssel und Benutzerschlüssel mussten ersetzt werden. Bitcoin-Wallets unter Android (2013): Androids SecureRandom verwendete eine Initialisierung auf Java-Ebene, die auf einigen Geräten fehlschlug und dadurch doppelte k-Werte in ECDSA-Signaturen verursachte — damit wurden private Schlüssel direkt offengelegt. Sony PS3 (2010): verwendete eine konstante Nonce für die ECDSA-Firmware-Signierung und ermöglichte dadurch die Extraktion privater Schlüssel aus zwei Signaturen (dasselbe k bei verschiedenen Nachrichten legt den Schlüssel durch einfache Algebra offen).

Welcher der folgenden Tests erkennt, dass ein DRBG möglicherweise festgefahrene Ausgaben erzeugt (wiederholt denselben Wert)?

Statistische Tests (NIST SP 800-22, TestU01 BigCrush, PractRand) überprüfen die Ausgabequalität, können aber keine kryptografische Sicherheit beweisen. CAVP-Known-Answer-Tests überprüfen die algorithmische Korrektheit von Implementierungen nach SP 800-90A. Tests für Entropiequellen nach SP 800-90B (Schätzung der Min-Entropie, Health Tests) validieren die Seed-Eingabe. Der Continuous RNG Test (CRNGT) erkennt festgefahrene Ausgaben in Echtzeit. VM- und Container-Bereitstellungen erfordern eine Entropiezufuhr (VIRTIO-RNG) und Entropieprüfungen beim Start. Tests der Fork-Sicherheit stellen sicher, dass Kindprozesse den DRBG-Zustand des Elternprozesses nicht erben. Reale Fehler (Debian, Android) zeigen, dass RNG-Fehler unmittelbar zur Kompromittierung kryptografischer Schlüssel führen. Audit-Checklisten formalisieren diese Prüfungen für Produktionsbereitstellungen.