Kryptologie (Vorlesung 11)

Skript-Anfang	Skript – Seite 43
Skript-Ende	Skript – Seite 45

Zufallszahlengeneratoren

Zweck

• Schlüsselgenerierung
• Asymmetrischen Verschlüsselungsverfahren (Padding für RSA)
• Zufall im Challenge-Response-Verfahren

Wichtig

• Die Güte des Zufalls, die Unvorhersagbarkeit → mit x₁, … , x₁₂₈ ∈ {0,1}
• Sicherheitsniveau ist 2¹⁰⁰ Versuche = 1/2¹⁰⁰

Entropie

• Wird in Bit gemessen
• „Entropie von n Bit“ bedeutet die Wahrscheinlichkeit den Zufallswert zu erraten, ist 1 / (2ⁿ)
• Schlüssel (x₁ , … , x₁₂₈) benötigt eine Entropie von 100 Bit
• Schlüssel der Länge 128 Bit mit Entropie von 128 Bit bedeutet, dass jedes Bit im Schlüssel hat Entropie von 1 Bit
  • Pr(x₁=0) = 1/2
  • Pr(x₁=1)=1/2
• Wir unterscheiden hier zwischen physikalischen und deterministischen Zufallsgeneratoren

Physikalische Generatoren

Zufall aus physikalischen Rauschquellen

• Impulsschwankungen elektromagnetischer Schaltungen
• radioaktiver Zerfall
• Atmosphärenrauschen

Probleme

• Nicht immer verfügbar
• Häufig langsam, die Zeit bis genug Zufall gesammelt wurde ist lang
• Häufige Schiefen (mehr Einsen als Nullen oder umgekehrt → Keine Gleichverteilung)
• Eine Schiefe, die Wahrscheinlichkeit aufzutreten, bedeutet, dass die Wahrscheinlichkeit größer als 1/2 ist

Lösung

• Deterministische Nachbearbeitung

Sicherheit (BSI-Empfehlung)

1. Beschreiben der Rauschquellen durch ein stochastisches Modell
2. Der durchschnittliche Entropiezuwachs pro Zufallsbit liegt oberhalb einer gegebenen Mindestschranke

Beispiel

• Erzeugt wird eine Zufallsfolge x₁ , … , x_n ∈ {0,1}
• Entropiezuwachs pro Bit → Ideal = 1
• Wahrscheinlichkeit x₁ zu erraten = 1/2
• Wahrscheinlichkeit alles zu erraten = 1/(2ⁿ)
• Häufige Schiefen:
  • Pr(x₁=0)=0,2
  • Pr(x₁=1)=0,8
• Entropie von x₁:
  • Wahrscheinlichkeit x₁ zu erraten ist 0,8
  • Ausgedrückt in Entropie: 1/2^x = 0,8
  • x = 0,322 ≈1/3
  • Um 100 Bit Entropie zu erhalten, müssen x₁ bis x₃₀₀ erzeugt werden
• Deterministische Nachbearbeitung:
  • Aus 300 Bit mit Entropie 100 mache 100 Bit mit Entropie 100

Deterministische Zufallsgeneratoren

• Werden auch Pseudozufallsgeneratoren genannt
• Berechnen aus einem Zufallswert mit fester Länge, auch Seed genannt
• Der Seed ist eine Pseudozufällige Bitfolge praktisch beliebiger Länge

Hinweis

• Durch einen deterministischen Zufallsgenerator bzw. Nachbearbeitung kann die Entropie, die Zufälligkeit, nicht erhöht werden
• Je komplizierter der Generator ist, desto schwieriger ist es nachzuweisen, ob dieser wirklich funktioniert und sicher ist
• Wiederverwendbarkeit:
  • „Die Wiederverwendbarkeit des Seeds tritt ab zweitem Schritt auf.“
  • Für hashfunktion h : {0,1}^* → {0,1}²⁰⁰ erzeugt dieser deterministischer Zufallsgenerator in jedem Schritt 200 Bit Zufall mit Entropie min {200, Entropie (SEED)}

Sicherheit

• Entropieerhaltend
• Aus bekannter Zufallsfolge dürfen Vorgänger und Nachfolger nicht berechnet werden

Seedgenerierung

• Seed durch phyiskalische Zufallsgeneratoren generieren
• Am Computer durch mehrere unabhängige Systemaufrufe zusammen setzen
• Linux /dev/random:
  • Liefert mindestens 100 Bit Entropie (laut BSI)
  • Systemzeit, Nutzeraktivitäten (Programm öffnen, Fenster schließen, Mausposition)
• Windows:
  • Kombination verschiedener Systemaufrufe
  • Read Time Stamp Counter() = Prozessorzyklen seit Systemstart
  • Bei Taktfrequenz ≥ 1 GHz → 2³⁰ mögliche Werte pro Sekunde (Nicht 2³⁰ lang!)
  • KeQuerySystemTime() = Aktuelle Systemzeit (relativ zu 1970)
  • Auflösung beträgt 100ms → 2²³ verschiedene Werte pro Sekunde

Erzeugung

1. Starte Rechner
2. Starte Programm
   • A = RTSC();
   • B = KQST();
3. Verifizieren eines Logins
   • C = RTSC();
   • C‘ = KQST(); ← Lässt sich aus den anderen Aufrufen berechnen und bringt nichts mehr
4. Erzeugen des SEEDs
   • D = RTSC();
   • A||B||C||D = SEED
5. Erzeugter Seed hat eine Entropie von
   • 30+23+30+30 = 113