Zufälligkeit und Pseudozufälligkeit

Zufälligkeit ist das Lebenselixier der Kryptographie – Schlüssel, Nonces und Challenges müssen unvorhersehbar sein – und Pseudozufälligkeit ermöglicht es, einen kurzen, wirklich zufälligen Seed zu langen Sequenzen zu strecken, die für jeden effizienten Angreifer von Zufälligkeit nicht zu unterscheiden sind.

Definition

Pseudozufälligkeit ist die Eigenschaft, rechnerisch von echter Zufälligkeit nicht unterscheidbar zu sein; ein Pseudozufallsgenerator erweitert deterministisch einen kurzen Zufalls-Seed zu einer längeren Ausgabe, die kein effizienter Algorithmus von Zufälligkeit unterscheiden kann.

Scope

Dieses Thema behandelt die Rolle der Zufälligkeit in der Kryptographie: die Anforderungen an Entropiequellen und echte Zufallszahlengeneratoren, die Definitionen und Konstruktionen kryptographisch sicherer Pseudozufallsgeneratoren und Pseudozufallsfunktionen sowie die katastrophalen Folgen schwacher oder wiederverwendeter Zufälligkeit. Es wird erläutert, wie pseudozufällige Objekte symmetrische Primitive formalisieren. Spezifische Chiffren und Härtungsannahmen, die in verwandten Themen behandelt werden, sind ausgeschlossen.

Core questions

• Warum erfordert Kryptographie unvorhersehbare Zufälligkeit, und was geht ohne sie schief?
• Was unterscheidet einen kryptographisch sicheren Generator von einem statistischen?
• Wie kann ein kurzer, wirklich zufälliger Seed zu einer langen pseudozufälligen Ausgabe gestreckt werden?
• Was sind pseudozufällige Funktionen und Permutationen, und wie modellieren sie Chiffren?
• Wie wird hochwertige Entropie in realen Systemen gesammelt und konditioniert?

Key concepts

• Entropie und echte Zufälligkeit
• Zufallszahlengeneratoren
• Pseudozufallsgenerator (PRG)
• Pseudozufallsfunktion (PRF)
• Pseudozufallspermutation (PRP)
• rechnerische Ununterscheidbarkeit
• Seed- und Schlüsselableitung
• Fehler durch Wiederverwendung von Zufälligkeit
• Entropiekonditionierung

Key theories

Pseudozufallsgeneratoren

Ein Pseudozufallsgenerator erweitert einen kurzen Seed zu einer längeren Zeichenkette, die für jeden effizienten Unterscheider von gleichmäßiger Zufälligkeit nicht zu unterscheiden ist; solche Generatoren existieren genau dann, wenn Einwegfunktionen existieren, was die Pseudozufälligkeit mit den Grundlagen der Kryptographie verbindet.

Pseudozufallsfunktionen und Permutationen

Eine Familie pseudozufälliger Funktionen, die aus jedem Pseudozufallsgenerator konstruierbar ist, ist für einen Angreifer, der sie abfragt, von einer wirklich zufälligen Funktion nicht zu unterscheiden; dieses Objekt liegt der Sicherheitsmodellierung von Blockchiffren und Nachrichtenauthentifizierungscodes zugrunde.

Mechanisms

Ein echter Zufallszahlengenerator gewinnt physikalische Entropie (thermisches Rauschen, Timing-Jitter), die konditioniert und zur Initialisierung eines kryptographisch sicheren Pseudozufallsgenerators verwendet wird, der deterministisch alle zufällig aussehenden Bits erzeugt, die ein System benötigt. Pseudozufallsfunktionen werden aus Generatoren (die GGM-Konstruktion) aufgebaut und modellieren schlüsselbasierte Primitive; eine Blockchiffre wird als pseudozufällige Permutation behandelt. Sicherheitsdefinitionen erfordern, dass kein effizienter Angreifer, dem Ausgaben vorliegen, weitere Bits vorhersagen oder von Zufälligkeit unterscheiden kann.

Clinical relevance

Fehler bei der Zufälligkeit sind eine wiederkehrende Ursache für katastrophale reale Brüche: Der Debian OpenSSL-Bug von 2008 beeinträchtigte die Schlüsselgenerierung, vorhersagbare ECDSA-Nonces führten zum Verlust privater Schlüssel (Sony PlayStation 3, einige Bitcoin-Wallets), und schwache Entropie in eingebetteten Geräten führte zu erratbaren Schlüsseln in großem Maßstab. Robuste Zufälligkeit – ordnungsgemäße Entropiesammlung und geprüfte Pseudozufallsgeneratoren – ist daher für jede kryptographische Implementierung unerlässlich.

Evidence & guidelines

NIST SP 800-90A/B/C spezifizieren zugelassene deterministische Zufallsbitgeneratoren, die Validierung von Entropiequellen und Konstruktionsrichtlinien. Best Practice ist die Verwendung des geprüften kryptographischen RNG des Betriebssystems (anstatt einen eigenen zu entwickeln), die Sicherstellung ausreichender Entropie vor der Schlüsselgenerierung und niemals die Wiederverwendung von Nonces. Statistische Testsuiten helfen, grobe Fehler zu erkennen, können aber keine kryptographische Stärke feststellen.

History

Die rechnerische Theorie der Pseudozufälligkeit wurde um 1982 von Blum und Micali sowie von Yao begründet, wobei Unvorhersehbarkeit und Ununterscheidbarkeit definiert wurden. Goldreich, Goldwasser und Micali zeigten 1986, wie Pseudozufallsfunktionen aus Generatoren konstruiert werden können, und Hastad, Impagliazzo, Levin und Luby bewiesen später, dass Pseudozufallsgeneratoren existieren, wenn Einwegfunktionen existieren. Wiederholte praktische Katastrophen aufgrund schwacher Zufälligkeit haben die Qualität von Entropie und RNGs zu einem zentralen technischen Anliegen gemacht.

Key figures

• Oded Goldreich
• Shafi Goldwasser
• Silvio Micali
• Manuel Blum
• Andrew Yao

Seminal works

• goldreich1986
• goldreich2001
• katz2020

Frequently asked questions

Warum kann ich keine normale Zufallsfunktion wie rand() für die Kryptographie verwenden?

Gewöhnliche Zufallszahlengeneratoren sind auf statistische Gleichmäßigkeit und Geschwindigkeit ausgelegt, nicht auf Unvorhersehbarkeit; ihre Ausgabe kann aus wenigen Stichproben vorhergesagt werden. Kryptographie benötigt Generatoren, deren zukünftige Ausgabe selbst bei Kenntnis vergangener Ausgaben nicht vorhersagbar ist, was einen kryptographisch sicheren RNG erfordert, der mit echter Entropie initialisiert wird.

Was ist der Unterschied zwischen echter Zufälligkeit und Pseudozufälligkeit?

Echte Zufälligkeit stammt aus einer physikalischen, unvorhersehbaren Quelle und ist in ihrer Verfügbarkeit begrenzt. Pseudozufälligkeit wird deterministisch aus einem kurzen, echten Zufalls-Seed erzeugt und kann in großen Mengen produziert werden; sie muss nur für jeden effizienten Angreifer von echter Zufälligkeit nicht zu unterscheiden sein, was für kryptographische Zwecke ausreicht.