STP044: Zufall

Schlüsseltechnologie

Wir befassen uns unter anderem mit der Erstellung, Bewertung und dem Verbrauch von Zufall. Außerdem in dieser Folge: Quantenmechanik, wildes Tastendrücken und Schiffe versenken.

Shownotes

Wir haben ein Errata zu STP019. Alex schreibt:

DMA kenne ich anders, nicht das der Prozess direkt über die MMU auf ein Peripheriegerät durchgreift, sondern dass ein Peripheriegerät ohne Beteiligung der CPU Daten vom/zum Hauptspeicher übertragen kann. Man muss dem Kernel allerdings beim Reservieren von Speicher für DMA sagen, dass das ein DMA Buffer sein soll, weil DMA selbst nicht über die MMU läuft sondern vom Peripheriegerät direkt von/zur physikalischen Adresse. Den eigentlichen Transfer zwischen Buffer und Peripherie muss man dann aber per Software entsprechend aktivieren.

Xyrill antwortet: Ja, stimmt. Nun zur eigentlichen Folge:

• Intro-Intro: in Referenz auf den klassischen Dilbert-Cartoon, den man zum Beispiel hier sieht

• Warum sind hochwertige Zufallszahlen wichtig?

  • siehe STP043: Erzeugung eines RSA-Schlüsselpaars benötigt zwei große und geheime Primzahlen
  • geheim = niemand anders kann es raten = zufällig
  • oder zumindest von Zufall nicht zu unterscheiden (Pseudozufall)

• Was ist "guter" Zufall?

  • erstaunlich schwer zu definieren
  • vielleicht Periodenlänge (Dauer, bis sich die Zahlenfolge wiederholt)
  • vielleicht Gleichverteilung der Auftrittshäufigkeit von Teilfolgen (jede einstellige/zweistellige/dreistellige/etc. Zahl sollte gleich oft in der Folge vorkommen)
  • Problem: die Folge "2236067977499789805051478..." ist nach all diesen Maßstäben guter Zufall -- bis man bemerkt, dass das die Dezimalstellen der Quadratwurzel von 5 sind
  • guter (aber unpraktikabler) Test: hohe Kolmogorow-Komplexität (siehe STP025)
  • Errata: Beim Nachhören ist mir aufgefallen, dass die Kolmogorow-Komplexität eines Pseudozufallszahlengenerators nie besonders groß sein kann, da der Zufallszahlengenerator ja gerade ein Programm ist, was die entsprechende Zahlenfolge erzeugen kann. Das ist kein praktisches Problem, da das Programm im Kolmogorow-Sinne auch die Startwerte des Zufallszahlengenerators umfassen müsste, die aber gerade geheim sind.

• "echter" Zufall kommt aus physikalischen Zufallszahlengeneratoren (Hardware-RNG)

  • z.B. thermisches Rauschen eines elektrischen Widerstandes
  • z.B. radioaktive Zerfallsvorgänge
  • z.B. atmosphärisches Rauschen (Empfang auf einem Frequenzband, auf dem keiner sendet)
  • z.B. Abfilmen eines Aquariums :)
  • siehe auch: Würfeln, Lottozahlen
  • Probleme: nicht in jedem Computer verfügbar, pro Zeiteinheit begrenzte Menge von Zufall
  • Idee: Erzeugung beliebiger Mengen von Pseudozufall aus einem festen Algorithmus

• Beispiel: Linearer Kongruenzgenerator

  • Parameter: geheime Ganzzahlen a, b, m; Startwert y
  • Erzeugung einer Folge von Pseudozufallszahlen durch die Formel y' = (a * y + b) mod m
  • Problem: bereits aus wenigen aufeinander folgenden y-Werten kann man auf die geheimen Zahlen zurückschließen (Ansatz vergleichbar mit Kryptoanalyse)
  • in besseren Pseudozufallszahlengeneratoren wird nach jedem Schritt nur ein kleiner Teil des Zustands herausgegeben, um Analyse zu erschweren
  • Anwendungsbereich für einfache Pseudozufallszahlengeneratoren: nicht sicherheitsrelevanter Pseudozufall, z.B. Ereignisse in Computerspielen oder Randomisierung von automatisierten Tests (hier kann Reproduzierbarkeit aus einem Startwert für spätere Nachvollziehung hilfreich sein)

• für sicherheitsrelevante Anwendungen: Kryptografisch sichere Zufallszahlengeneratoren

  • Beispielidee: mit einem Hardware-RNG ein paar Bytes als Startwerte erzeugen, wiederholt mit AES-CTR (siehe STP043) verschlüsseln und die verschlüsselten Bits (oder Teile davon) als Ausgabe nehmen
  • wenn man keinen Hardware-RNG hat, kann man Zufallsbits auch aus Beobachtung des normalen Betriebs extrahieren (z.B. Mikrosekundenbruchteile der Zeitstempel von Ereignissen wie Tastaturdrücken oder dem Empfang von Datenpaketen übers Netzwerk)
  • unter Unix: /dev/random vs. /dev/urandom ; ist aber unter Linux mittlerweile so gut wie synonym (siehe auch); Probleme nur beim Systemstart, wenn noch nicht genug Entropie vorliegt (siehe auch: haveged, VirtIO RNG, systemd-random-seed.service)

• im Gespräch erwähnt:

  • Video: "How we solved the worst minigame in Zelda's history" (Errata: Xyrill hatte im Gespräch behauptet, dass das Video von Lowest Percent sei. Es ist aber von Linkus7.)