Häufig verwendete Passwort-Hashing-Algorithmen funktionieren heute so: Salzen Sie das Passwort und geben Sie es in eine KDF ein. Bei Verwendung von PBKDF2-HMAC-SHA1 lautet der Kennwort-Hashing-Prozess beispielsweise DK = PBKDF2(HMAC, Password, Salt, ...). Da es sich bei HMAC um ein 2-Runden-Hashing mit gepolsterten Tasten und bei SHA1 um eine Reihe von Permutationen, Verschiebungen, Rotationen und bitweisen Operationen handelt, handelt es sich bei dem gesamten Prozess im Grunde genommen um einige grundlegende Operationen, die auf eine bestimmte Weise organisiert sind. Grundsätzlich ist nicht ersichtlich, wie schwierig es ist, sie tatsächlich zu berechnen. Das ist wahrscheinlich der Grund, warum Einwegfunktionen immer noch eine Überzeugung sind und wir gesehen haben, dass einige historisch wichtige kryptografische Hash-Funktionen unsicher und veraltet sind.

Ich habe mich gefragt, ob es möglich ist, NP-vollständige Probleme zu nutzen, um Passwörter auf eine brandneue Weise zu hashen, in der Hoffnung, dass es eine solide theoretische Grundlage gibt. Die Schlüsselidee ist, angenommen, P! = NP (wenn P == NP, dann kein OWF, so brechen auch die aktuellen Schemata). Ein NPC-Problem zu sein, bedeutet, dass die Antwort leicht zu verifizieren, aber schwer zu berechnen ist. Diese Eigenschaft passt gut zu den Anforderungen des Passwort-Hashings. Wenn wir das Passwort als Antwort auf ein NPC-Problem betrachten, können wir das NPC-Problem als Hash des Passworts speichern , um Offline-Angriffen entgegenzuwirken: Es ist einfach, das Passwort zu verifizieren, aber schwer zu knacken.

Achtung, dasselbe Passwort kann mehreren Instanzen eines NPC-Problems zugeordnet werden, wahrscheinlich sind nicht alle schwer zu lösen. Als ersten Schritt in dieser Forschung habe ich versucht, eine Binärzeichenfolge als Antwort auf ein 3-SAT-Problem zu interpretieren und eine Instanz des 3-SAT-Problems zu konstruieren, für die die Binärzeichenfolge eine Lösung darstellt. In seiner einfachsten Form hat der Binärstring 3 Bits: x_0, x_1, x_2. Dann gibt es 2 ^ 3 == 8 Klauseln:

000 (    (x_0) v    (x_1) v    (x_2) )
--------------------------------------
001 (    (x_0) v    (x_1) v NOT(x_2) )
010 (    (x_0) v NOT(x_1) v    (x_2) )
011 (    (x_0) v NOT(x_1) v NOT(x_2) )
100 ( NOT(x_0) v    (x_1) v    (x_2) )
101 ( NOT(x_0) v    (x_1) v NOT(x_2) )
110 ( NOT(x_0) v NOT(x_1) v    (x_2) )
111 ( NOT(x_0) v NOT(x_1) v NOT(x_2) )

Angenommen, die Binärzeichenfolge ist 000. Dann ist nur eine der 8 Klauseln falsch (die erste). Wenn wir die erste Klausel und die verbleibenden 7 Klauseln verwerfen, ist 000 eine Lösung der resultierenden Formel. Wenn wir also die Formel speichern, können wir 000 verifizieren.

Das Problem ist, dass bei einer 3-Bit-Zeichenfolge, wenn Sie dort 7 verschiedene Klauseln sehen, Sie sofort wissen, welche fehlt, und das würde die Bits enthüllen.

Deshalb habe ich später beschlossen, 3 davon zu verwerfen und nur die 4 mit 001, 010, 100 und 111 zu kennzeichnen. Dies führt manchmal zu Kollisionen, macht die Lösung des Problems jedoch weniger trivial. Die Kollisionen passieren nicht immer, aber ob sie sicher verschwinden würden, wenn der Eingang mehr Bits hat, ist noch nicht bekannt.

Bearbeiten. In dem allgemeinen Fall, in dem die Binärzeichenfolge eine von (000, 001, ..., 111) sein kann, gibt es noch 8 Klauseln, in denen 7 wahr und 1 falsch ist. Wählen Sie die 4 Klauseln aus, die den Wahrheitswert ergeben (001, 010, 100, 111). Dies spiegelt sich in der folgenden Implementierung des Prototyps wider.

Bearbeiten. Wie die Antwort von @DW unten zeigt, kann diese Methode der Klauselauswahl zu zu vielen Klauseln für einen bestimmten Satz von Variablen führen, wodurch es möglich wird, ihre Werte schnell einzugrenzen. Es gibt alternative Methoden zur Auswahl der Klauseln unter den insgesamt 7 * C (n, 3) Klauseln. Beispiel: Wählen Sie eine andere Anzahl von Klauseln aus einem gegebenen Satz von Variablen aus und tun Sie dies nur für benachbarte Variablen ((x_0, x_1, x_2), (x_1, x_2, x_3), (x_2, x_3, x_4). .) und bilden so einen Kreislauf statt einer Clique. Diese Methode funktioniert wahrscheinlich nicht so gut, da Sie intuitiv mithilfe der Induktion testen können, ob alle Klauseln erfüllt werden können. Um die Erklärung der Gesamtstruktur zu vereinfachen, verwenden wir einfach die aktuelle Methode.

Die Anzahl der Klauseln für eine n-Bit-Zeichenfolge beträgt 4 * C (n, 3) = 4 * n * (n - 1) * (n - 2) / 6 = O (n - 3), was die Größe von bedeutet Hash ist ein Polynom der Größe des Passworts.

Es gibt eine Prototyp - Implementierung in Python hier . Es generiert eine 3-SAT-Probleminstanz aus einer Benutzereingabebinärzeichenfolge.

Nach dieser langen Einführung endlich meine Fragen:

1. Funktioniert die oben beschriebene (im Prototyp implementierte) Konstruktion als sicheres Passwort-Hashing oder sieht sie zumindest vielversprechend aus, kann sie überarbeitet werden usw.? Wenn nicht, wo scheitert es?

2. Ist es möglich, einen anderen Weg zu finden, um eine sichere 3-SAT-Instanz zu erstellen, die zur Verwendung als Passwort-Hash geeignet ist, möglicherweise mithilfe von Randomisierung, da wir 7 * C (n, 3) -Klauseln zur Auswahl haben?

3. Gibt es eine ähnliche Arbeit, die versucht, die NP-Vollständigkeit zu nutzen, um bewährte sichere Passwort-Hashing-Schemata zu entwerfen, und die bereits einige Ergebnisse erzielt hat (entweder positiv oder negativ)? Einige Intros und Links wären sehr willkommen.

Bearbeiten. Ich würde die unten stehende Antwort von @DW akzeptieren, der als erster antwortete und großartige Einblicke in die Problemstruktur sowie nützliche Ressourcen gab. Das hier vorgestellte Auswahlschema für naive Klauseln (wie im Python-Prototyp implementiert) schien nicht zu funktionieren, da es möglich ist, die Variablenzuweisungen in kleinen Gruppen schnell einzugrenzen. Das Problem bleibt jedoch offen, da ich keinen formellen Beweis dafür gesehen habe, dass solche Reduzierungen von NPC zu PasswordHashing überhaupt nicht funktionieren. Selbst für dieses spezielle 3-SAT-Reduktionsproblem gibt es möglicherweise verschiedene Möglichkeiten, Klauseln auszuwählen, die ich hier nicht aufzählen möchte. Daher sind Updates und Diskussionen immer noch sehr willkommen.

Leider scheint dies nicht zu funktionieren (siehe unten für Details), und es scheint schwierig zu sein, einen Weg zu finden, um diese Art von Idee zu einem nachweislich sicheren Schema zu führen.

Das Problem mit Ihrer allgemeinen Idee

Sie sind nicht der erste, der versucht, die Kryptographie auf NP-vollständige Probleme zu stützen. Das Problem ist, dass die NP-Härte nur die Worst-Case-Härte gewährleistet, die Kryptographie jedoch die Durchschnittshärte erfordert. Es gab mehrere Versuche, die Kryptographie auf NP-vollständige Probleme zu stützen (z. B. Rucksack-Kryptosysteme), aber sie haben sich nicht bewährt. Typischerweise entdecken Menschen Algorithmen, die im Durchschnitt (oder mit nicht-trivialer Wahrscheinlichkeit) oft effektiv sind, auch wenn sie im schlimmsten Fall exponentiell sind. Dies reicht aus, um die Krypto zu zerbrechen, obwohl dies nicht der NP-Härte widerspricht.

$\ne$

Ich schlage vor, mehr über das Thema zu lesen. Einige nützliche Ausgangspunkte finden Sie unter Die Bedeutung von NP-harten Problemen in der Kryptographie , Offene Probleme mit durchschnittlicher Komplexität, die keine Einwegfunktionen sind , Status der Impagliazzo-Welten? , Im schlimmsten Fall zur durchschnittlichen Fall Senkungen .

Das Problem mit Ihrem speziellen Schema

Ihr spezifischer Vorschlag ist nicht vollständig spezifiziert. Um ein Schema zu analysieren, müssen Sie vollständig angeben, wie das Schema funktioniert. In Ihrem Fall ist nicht klar, wie Sie 4 der 7 Klauseln im allgemeinen Beispiel auswählen. (Und ein einzelnes Beispiel ist kein Ersatz für eine Spezifikation, die beschreibt, wie Sie es im Allgemeinen tun.)

$x_0,x_1,x_2,x_3,x_4$$2^5$mögliche Zuweisungen zu diesen 5 Variablen, probieren Sie sie alle aus und verwerfen Sie alle Zuweisungen, die durch eine der 40 Klauseln verletzt werden. Ich gehe davon aus, dass Sie nur eine Aufgabe haben, die mit allen Klauseln übereinstimmt.

$1/2$$1/2^{10}$$2^5-1$$7/8$$(7/8)^{40} \approx 2^{-7.7}$$(2^5-1) \times 2^{-7.7} \approx 0.15$

Dies kann für jede Gruppe von 5 Variablen wiederholt werden, wobei die eindeutige befriedigende Zuordnung für jede Variable eindeutig wiederhergestellt wird. Bei Unklarheiten können die Kandidatenzuweisungen mit anderen Klauseln verglichen werden.

Auf diese Weise sehen wir, dass es einen effizienten Algorithmus gibt, der in der Regel die von Ihrer Prozedur generierte Klasse von 3SAT-Instanzen löst. Es werden nicht alle 3SAT-Instanzen aufgelöst, aber die von Ihnen generierten Instanzen haben eine spezielle Struktur und es werden Instanzen mit dieser speziellen Struktur effektiv aufgelöst. Dies verdeutlicht den Punkt: Einige Instanzen von 3SAT sind einfacher als andere, und die Härte von 3SAT (im schlimmsten Fall Komplexität) sagt wenig oder gar nichts über die Härte der von Ihnen generierten Spezialinstanzen oder die Härte einer durchschnittlichen 3SAT-Instanz aus.