Hauptquelle: D. Eastlake, S. Crocker, J. Schiller (MIT): Randomness Recommendations for Security. Request for Comments 1750, December 1994

Siehe auch:

• P. Gutmann: Software Generation of Practically Strong Random Numbers.
• B. Jun and P. Kocher: The Intel Random Number Generator.
• A. G. Reinhold: Hardware Randomness Sources.

Frage: Wie kann man »echten« (physikalischen) Zufall am Computer erzeugen?

Anwendungen

• Bitstrom-Verschlüsselung: One Time Pad [Klartext XOR Zufallsbits = Geheimtext],
• probabilistische Verschlüsselung [f_k(Klartext, Zufallszahl) = Geheimtext],
• Schlüsselerzeugung für andere kryptographische Verfahren,
• Startwerte für »perfekte« (= kryptographisch sichere) algorithmische Zufallsgeneratoren,
• Zufallswerte für kryptographische Protokolle.

Kritik häufig verwendeter Methoden

1. Systemuhren

• Zufallsausbeute gering, von fraglicher Qualität,
• Suchraum sehr klein.

2. Systemereignisse (Zeitpunkt, Dauer, Inhalt)

1. Benutzer-Ereignisse wie Mausbewegungen und Tastenbetätigung
   • Zeiten schwer zugänglich, besonders bei gepufferter Eingabe.
   • Inhalte oft wenig zufällig. [Bei PGP zur Schlüsselerzeugung verwendet.]
2. Externe Ereignisse wie Ankunft von Netzpaketen oder Systempuffer von Mehrbenutzersystemen
   • Könnten vom »Gegner« manipuliert werden.

3. Auswahl aus großer Datenbasis

[z. B. CD (600 M) oder Usenet-News (täglich > 50 M)]

• Echter Suchraum ziemlich klein (~ 5×10⁹ bei der CD, also etwa 32 Bits »Zufall«).

Design-Gesichtspunkte

• Mit einem »perfekten« (algorithmischen) Zufallsgenerator kann man eine »echte« Zufallsfolge beträchtlich verlängern. Man braucht aber einen »echt« zufälligen Startwert aus einer genügend großen Grundmenge (etwa > 2⁸⁰ bei Gleichverteilung nach heutigem Stand der Technik), um vor vollständiger Suche sicher zu sein.
• Die Effizienz muss bei den meisten Anwendungen nicht besonders hoch sein; pro Anforderung werden höchstens ein paar hundert Bits benötigt, und diese Anforderungen sind selten.
• Ungleichmäßig verteilte oder sonst gestörte »echte« Zufallsfolgen können durch Kompressions- oder Verschlüsselungsalgorithmen (z. B. AES oder binäre Addition einer Pseudozufallsfolge) in gleichverteilte umgewandelt werden (bei bekannter Verteilung auch durch einfache Transformationen).
• Genügend viel »echter« Zufall kann durch geeignetes Mixen schwacher Zufallsquellen erzeugt werden, z. B. mit Hilfe kryptographischer Hash-Funktionen.

Geeignete Zufallsquellen

1. Rauschen (`jitter') auf einem geeigneten Oszillator

• Als Standard-Bauteil für Computer geeignet (billig und schnell).
• Intel-CPUs [Cave: Vertrauensfrage!]

2. Turbulenzen der Luftströmung um eine rotierende Festplatte

• Ebenfalls durch billiges Hardwareteil auszuwerten.
• Durch FFT und Kompression Gleichverteilung herstellen.
• Erreichbar über 100 Bits/Sekunde. [Don Davis, Ross Ihaka, and Philip Fenstermacher: Cryptographic Randomness from Air Turbulence in Disk Drives, Crypto '94, Lecture Notes in Computer Science 839 (1994).]

3. Auslesen von /dev/audio

• ..., wenn kein Mikrophon angeschlossen ist;
• durch Kompression Gleichverteilung herstellen.

  cat /dev/audio | compress > random-bits-file

4. Rauschen von Videokamera mit abgedeckter Linse

5. Radioaktiver Zerfall

Portable Notlösung

Guter Mix von mehreren Benutzer- und Systemereignissen.

Auf Unix-Systemen: /dev/random oder /dev/urandom - Ein »Entropie-Pool« wird laufend nachgefüllt und bei Bedarf abgerufen.

• Bei /dev/random wird bei leerem Pool gewartet,
• bei /dev/urandom wird gegebenenfalls mit Pseudozufallszahlen aufgefüllt.

Beispiel - DoD-Empfehlung zur Erzeugung sicherer Passwörter

• Use an initialization vector determined from
  • the system clock,
  • system ID,
  • user ID, and
  • date and time;
• use a key determined from
  • system interrupt registers,
  • system status registers, and
  • system counters; and,
• as plain text, use an external randomly generated 64 bit quantity such as 8 characters typed in by a system administrator.

[United States of America, Department of Defense, Computer Security Center, Password Management Guideline, CSC-STD-002-85 (»Green Book«).]

Zusammenfassung

1. Die existierende Hardware bietet auf vielen Systemen geeignete Zufallsquellen. Diese müssen aber mit Sorgfalt verwendet werden.
2. Durch geeignete Transformationen können auch aus einer schlechten Zufallsquelle einige gute Zufalls-Bits extrahiert werden.
3. Das Problem der Systemabhängigkeit kann durch geeignete Auswertung einer umfangreichen Kombination von Systemereignissen gemildert werden.
4. Vorschlag: Physikalische Zufallsquelle in jedes System integrieren, genormte Schnittstelle anbieten.
5. Praktische Empfehlung: ca. 100 - 120 Bits physikalisch erzeugen; bei Mehrbedarf expandieren mit Hilfe von perfektem Zufallsgenerator.