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. (USENIX 98)
• P. Gutmann: Random Number Generation.
• 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

Wozu braucht der Kryptologe Zufall (Entropie)?

• 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 [Schlüssel sollen nicht erratbar sein].
• Startwerte für »perfekte« (= kryptographisch sichere) algorithmische Zufallsgeneratoren.
• Zufallswerte für kryptographische Protokolle (»Nonces«).

• Der Gegner soll keine Möglichkeit haben, die Zufallsbits, -zahlen, -strings zu erraten ...
• ... oder wenigstens den Suchraum einzuschränken.

Achtung: Viele Attacken auf kryptographische Protokolle nutzen Mängel bei der Zufallserzeugung aus.

Häufig verwendete ungenügende Methoden

1. 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«).

2. Systemuhren

• Z. B. Millisekunden zum Zeitpunkt der Abfrage;
• Zufallsausbeute gering, von fraglicher Qualität,
• Suchraum sehr klein.

3. Systemereignisse (Zeitpunkt, Dauer, Inhalt)

• Benutzer-Ereignisse wie Mausbewegungen und Tastenbetätigung,
  • echte Zeiten schwer zugänglich, besonders bei gepufferter Eingabe,
  • Inhalte oft wenig zufällig, Suchraum eingeschränkt.
• Externe Ereignisse wie Ankunft von Netzpaketen oder Systempuffer von Mehrbenutzersystemen -
  • könnten vom »Gegner« manipuliert werden.

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 > 90 Bits 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 -
  • »Zusammenkratzen« verfügbarer Entropie - so füllen UNIX-Systeme ihren Entropie-Pool.

Fazit: Man braucht nur wenig echten Zufall, aber der muss von hoher Qualität sein.

Implementation in Linux (und anderen Unix-Varianten)

• /dev/random: »echte« (physikalische) Zufallsbits.
  • »Entropie-Pool« wird im Hintergrund aufgefüllt,
  • falls Pool leer, muss die anfordernde Anwendung warten.
• /dev/urandom: echte Zufallsbits, falls vorhanden, sonst Pseudozufallsbits.
  • Gleicher Pool,
  falls Pool leer, werden die echten Zufallsbits algorithmisch fortgesetzt.
  • Anfordernde Anwendung muss nicht warten.

Geeignete Zufallsquellen

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

• Als Standard-Bauteil für Computer geeignet
  • billig und schnell,
  • kommerzielle Angebote vorhanden.
• In Intel-CPUs bereits enthalten. [Cave: Vertrauensfrage!]

2. Turbulenzen der Luftströmung um eine rotierende Festplatte

• Ebenfalls durch billiges Hardwareteil auszuwerten.
• Durch Fourier-Transformation 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 o. ä.

• ..., 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, s. o.

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 sollte mit genormter Schnittstelle Bestandteil jedes Systems sein.
5. Praktische Empfehlung:
   • Entropiepool im Hintergrund laufend füllen mit physikalisch erzeugten Zufallsbits.
   • Pro Anforderung ca. 100 - 120 Bits entnehmen; bei Mehrbedarf expandieren mit Hilfe von perfektem Zufallsgenerator.