Zufallserzeugung

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

Anwendungen

• Startwerte für »perfekte« (= kryptographisch sichere) Zufallsgeneratoren,
• Probabilistische Verschlüsselung [Klartext + Zufallszahl -----------> Geheimtext],
• Schlüsselerzeugung für kryptographische Verfahren,
• 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 40 M)]
   
   • Echter Suchraum ziemlich klein (~ 5 × 10⁹ bei der CD, also etwa 32 Bits »Zufall«).

[---> Beispiele für Suchräume]

Design-Gesichtspunkte

• Mit einem perfekten 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.
• Effizienz muß nicht besonders hoch sein; pro »Vorgang« werden höchstens ein paar hundert Bits benötigt, und diese Vorgänge sind selten.
• Ungleichmäßig verteilte oder sonst gestörte »echte« Zufallsfolgen können durch Kompressions- oder Verschlüsselungsalgorithmen (z. B. DES 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 (MDx, SHS, DES).

Geeignete Zufallsquellen

1. Rauschen (`jitter') auf einem geeigneten Oszillator.
   • Als Standard-Bauteil für Computer geeignet (billig und schnell).
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 (auf SPARCstation),
   • wenn kein Mikrophon angeschlossen ist;
   • durch Kompression Gleichverteilung herstellen.
   cat /dev/audio | compress > random-bits-file [nicht verifiziert]
4. Rauschen von Videokamera mit abgedeckter Linse.
5. Radioaktiver Zerfall.

Portable Notlösung: Guter Mix von mehreren Benutzer- und Systemereignissen.

Beispiel &endash; DoD-Empfehlung zur Erzeugung sicherer Paßwö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.

The password can then be calculated from the 64 bit `cipher text' generated in 64-bit Output Feedback Mode (DES). (As many bits as are needed can be taken from these 64 bits and expanded into a pronounceable word, phrase, or other format if a human being needs to remember the password.)

[United States of America, Department of Defense, Computer Security Center, Password Management Guideline, CSC-STD-002-85.]

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 &endash; 120 Bits physikalisch erzeugen; bei Mehrbedarf expandieren mit Hilfe von perfektem Zufallsgenerator.

Zurück zum Inhaltsverzeichnis

E-Mail an Pommerening@imsd.uni-mainz.de.