Werden theoretisch solide Pseudozufallsgeneratoren in der Praxis eingesetzt?

17

Soweit mir bekannt ist, verwenden die meisten Implementierungen der Erzeugung von Pseudozufallszahlen in der Praxis Methoden wie Linear Shift Feedback Register (LSFRs) oder diese "Mersenne Twister" -Algorithmen. Obwohl sie viele (heuristische) statistische Tests bestehen, gibt es keine theoretischen Garantien dafür, dass sie beispielsweise bei allen effizient berechenbaren statistischen Tests pseudozufällig aussehen. Diese Methoden werden jedoch unterschiedslos in allen Arten von Anwendungen eingesetzt, von kryptografischen Protokollen über wissenschaftliches Rechnen bis hin zu Bankgeschäften (wahrscheinlich). Ich finde es etwas besorgniserregend, dass wir kaum oder gar keine Garantie dafür haben, ob diese Anwendungen wie beabsichtigt funktionieren (da jede Art von Analyse wahrscheinlich echte Zufälligkeit als Eingabe angenommen hätte).

Auf der anderen Seite bieten Komplexitätstheorie und Kryptographie eine sehr reiche Theorie der Pseudozufälligkeit, und wir haben sogar Kandidatenkonstruktionen von Pseudozufallsgeneratoren, die JEDEN effizienten statistischen Test täuschen würden, den Sie sich unter Verwendung von Einwegkandidatenfunktionen ausdenken könnten.

Meine Frage ist: Hat diese Theorie ihren Weg in die Praxis gefunden? Ich hoffe, dass für wichtige Zwecke der Zufälligkeit, wie Kryptographie oder wissenschaftliches Rechnen, theoretisch fundierte PRGs verwendet werden.

Abgesehen davon konnte ich eine eingeschränkte Analyse finden, wie gut populäre Algorithmen wie QuickSort funktionieren, wenn LSFRs als Zufallsquelle verwendet werden, und anscheinend funktionieren sie gut. Siehe Karloff und Raghavan "Randomisierte Algorithmen und Pseudozufallszahlen" .

Henry Yuen
quelle
3
Es gibt sogar ein universelles PRG - es ist sicher, wenn sichere PRGs existieren.
Meinen Sie kryptografische PRGs? Wenn ja, wissen wir dann nicht, dass (kryptografische) PRGs OWFs entsprechen?
Henry Yuen
2
Ja. Teilen Sie den Bit-Startwert in ungefähr √ aufk Blöcke von ungefährkJeweils k Bits laufenkDie ersten [Anzahl der Blöcke] Turing-Maschinen auf den entsprechenden Blöcken für bis zu Schritte, die Ausgänge auf Bits auf und geben das xor dieser TM-Ausgänge aus. (Genau wie bei Levins universeller Suche kann dies in der Praxis nicht verwendet werden.)k2k+1
1
Für die Praxis relevanter sind möglicherweise Ergebnisse in Bezug auf die Zufälligkeit, die für das Hashing erforderlich sind: von den klassischen Familien mit beschränkter Unabhängigkeit bis zu neueren Ergebnissen wie Mitzenmacher-Vadhan (paarweise Unabhängigkeit + eine gewisse Entropie im Eingang führt zu einer ausreichenden Pseudozufälligkeit für lineare Sondierungen und Bloom-Filter) oder Patrascu -Thorup führt zu Tabellierungs-Hashing.
Sasho Nikolov
1
"Diese Methoden werden jedoch unterschiedslos in allen Arten von Anwendungen eingesetzt, angefangen von kryptografischen Protokollen ...". Ich hoffe nicht. Mersenne Twisters sollten nicht für die Kryptografie verwendet werden, da sie nicht kryptografisch stark sind, obwohl es möglicherweise Varianten gibt .
Mike Samuel

Antworten:

13

Der Begriff "theoretisch fundierter" Pseudozufallsgeneratoren ist nicht wirklich klar definiert. Schließlich hat kein Pseudozufallsgenerator einen Sicherheitsnachweis. Ich weiß nicht, dass wir sagen können, dass ein Pseudozufallsgenerator, der auf der Härte der Faktorisierung großer Ganzzahlen basiert, "sicherer" ist, als beispielsweise AES als Pseudozufallsgenerator zu verwenden. (In der Tat gibt es ein Gefühl, dass es weniger sicher ist, da wir Quantenfaktor-Algorithmen kennen, aber keine Quantenalgorithmen, um AES zu brechen.)

Wir haben mathematische Beweise für verschiedene Kompositionsergebnisse, die besagen, dass Sie Pseudozufallsgeneratoren oder Pseudozufallsfunktionen erhalten können, wenn Sie Blockchiffren oder Hash-Funktionen auf bestimmte Weise komponieren. Einige dieser Ergebnisse sind in der Praxis weit verbreitet, z . B. HMAC . Es ist jedoch richtig, dass die Ergebnisse, die eine PRG erzielen und nur davon ausgehen, dass die Basiskomponente eine einfache Einwegfunktion ist, nicht effizient genug sind, um sie für Anwendungen zu verwenden (und dies ist zumindest teilweise inhärent)). In der Regel müssen wir also eine PRG- / Stream-Verschlüsselungs- / Block-Verschlüsselungs- / Hash-Funktion als Grundelement annehmen und andere Dinge daraus erstellen. Es geht nicht wirklich um eine asymptotische Analyse, da im Wesentlichen alle kryptografischen Reduktionen (mit Ausnahme von Levins universellem PRG) konkretisiert werden können und somit unter konkreten Annahmen konkrete Garantien geben.

Obwohl sie nicht auf Einwegfunktionen basieren, sind Konstruktionen wie AES in gewisser Weise "theoretisch fundiert", weil: (1) formale Vermutungen über ihre Sicherheit bestehen. (2) Es wird versucht, diese Vermutungen zu widerlegen und daraus auch Implikationen abzuleiten.

Tatsächlich wissen die Leute, dass es für viele Anwendungen nicht klug wäre, PRGs wie LSFR zu verwenden, die die obigen Punkte (1) und (2) nicht erfüllen.

Boaz Barak
quelle
1
Ich nehme an, Sie wollten einen Link zu einer der Veröffentlichungen von Jonathan Katz auf seiner Webseite erstellen. Übrigens, möchten Sie, dass wir dies mit Ihrem anderen Konto zusammenführen ?
Kaveh
9

Sie scheinen Theorie mit Praxis zu verwechseln. Ein theoretisch solider Pseudozufallsgenerator ist aus mehreren Gründen für den praktischen Gebrauch ungeeignet:

  • Es ist wahrscheinlich sehr ineffizient.
  • Der Sicherheitsnachweis ist nur asymptotisch, und daher kann der Pseudozufallsgenerator für den bestimmten verwendeten Sicherheitsparameter leicht zerstört werden.
  • Alle Sicherheitsnachweise sind an Bedingungen geknüpft, so dass sie in gewisser Weise nicht einmal den theoretischen Sicherheitsgedanken erfüllen.

Im Gegensatz dazu sind tatsächliche Pseudozufallsgeneratoren schnell und kommen abhängig von ihrer Verwendung in unterschiedlichen Geschmacksrichtungen vor. Für den nicht-kryptografischen Gebrauch ist fast alles außer einem einfachen LFSR ausreichend - nicht nachweisbar, aber in der Praxis (was für Leute, die Dinge in der Realität benutzen, wichtiger ist).

Für den kryptografischen Gebrauch versuchen die Leute schlauer zu sein. An dieser Stelle macht Ihre Kritik Sinn: Wir können nicht wissen, dass ein bestimmter verwendeter Pseudozufallsgenerator "sicher" ist, und in der Tat sind einige alte defekte, zum Beispiel RC4, wie er in WEP verwendet wird. Aus den oben genannten Gründen ist die Verwendung eines theoretisch (bedingt) klingenden Pseudozufallsgenerators leider keine realistische Lösung. Stattdessen stützt sich die kryptologische Gemeinschaft auf "Peer Review" - andere Forscher, die versuchen, das System zu "brechen" (ihre Definition, wann eine Chiffre gebrochen wird, ist sehr weit gefasst).

Schließlich wird bei Anwendungen, bei denen das Geld investiert werden kann und Sicherheit wichtig genug ist (beispielsweise bei Nuklearcodes), physisch erzeugtes Rauschen verwendet (das durch einen Zufallsextraktor geleitet wird), auch wenn dies nicht jenseits theoretischer Kritik liegt.


Wenn Forscher Zuschussvorschläge oder Einführungen in Arbeiten schreiben, behaupten sie oft, dass ihre Forschung die Praxis betrifft und informiert. Ob sie daran glauben oder es nur ein Lippenbekenntnis ist, weiß ich nicht (und es kann vom Forscher abhängen), aber Sie sollten sich bewusst sein, dass der Zusammenhang in akademischen Kreisen aus offensichtlichen Gründen stark übertrieben ist.

Eine Sache, die uns als Mathematiker einschränkt, ist unsere dogmatische Bindung an formale Beweise. Sie erwähnen die Analyse randomisierter Algorithmen, die von einfachen Pseudozufallsgeneratoren gespeist werden. Diese Art der Analyse kann nicht auf reale Probleme ausgedehnt werden, da sie einfach zu kompliziert sind. Und doch lösen die Menschen in der Praxis ständig auch NP-schwierige Probleme mit informierten Methoden.

Probleme der realen Welt werden mit einem wissenschaftlicheren und experimentelleren Blick besser verstanden. Sie sind aus technischer Sicht besser zu lösen. Sie inspirieren die theoretische Forschung und werden gelegentlich darüber informiert. Wie Dijsktra sagte, geht es in der (theoretischen) Informatik nicht mehr wirklich um Computer.

Yuval Filmus
quelle
Danke für deine Antwort, Yuval. Ich bin jedoch nicht der festen Überzeugung, dass Pseudozufallsgeneratorkonstruktionen aus der Kryptographie unpraktisch ineffizient sind. Soweit ich sehen kann, hat dies niemand untersucht.
Henry Yuen
2
Ich bin auch nicht einverstanden mit der pauschalen Aussage, dass Standard-Pseudozufallsgeneratoren für "Alltagszwecke" ausreichen. Wie das kürzlich erschienene Papier "Ron hatte Unrecht, Whit hatte Recht" zeigte, hat eine fehlerhafte Pseudozufallsgenerierung zu peinlichen Sicherheitslücken für eine nicht zu vernachlässigende Menge von Menschen geführt. Diese spezielle Analyse war einfach genug; Wie viele "reale" Anwendungen können subtilere Sicherheitslücken aufweisen, weil LSFRs nicht ausreichen? Wenn der zusätzliche Rechenaufwand für theoretisch einwandfreie PRGs nicht so groß ist, warum sollten Sie sie nicht verwenden?
Henry Yuen
1
@HenryYuen-LSFRs werden in keinem vernünftigen, modernen System für kryptografische Anwendungen verwendet. (Natürlich gibt es schlecht konzipierte Systeme, wie zum Beispiel GSM, das in Einführungskursen unterrichtet wird, wie man es nicht macht.) Die Probleme, die im Artikel „Ron war falsch, Whit ist richtig“ festgestellt wurden, waren nicht von der Qualität von PRNG selbst, aber mit der Qualität der Entropiesammlung.
Gilles 'SO - hör auf böse zu sein'