Kann maschinelles Lernen die SHA256-Hashes dekodieren?

43

Ich habe einen SHA256-Hash mit 64 Zeichen.

Ich hoffe, ein Modell zu trainieren, das vorhersagen kann, ob der zur Generierung des Hashs verwendete Klartext mit einer 1 beginnt oder nicht.

Unabhängig davon, ob dies "Möglich" ist, welcher Algorithmus ist der beste Ansatz?

Meine ersten Gedanken:

  • Generieren Sie eine große Stichprobe von Hashes, die mit einer 1 beginnen, und eine große Stichprobe von Hashes, die nicht mit einer 1 beginnen
  • Legen Sie jedes der 64 Zeichen eines Hashs als Parameter für eine Art unbeaufsichtigtes logistisches Regressionsmodell fest.
  • Trainieren Sie das Modell, indem Sie ihm sagen, wann es richtig / falsch ist.
  • Hoffentlich können Sie ein Modell erstellen, das vorhersagt, ob der Klartext mit einer 1 beginnt oder nicht, mit einer ausreichend hohen Genauigkeit (und mit einem anständigen Kappa).
John
quelle
22
Zu Ihrer Information: Dies ist wahrscheinlich durch Bitcoin-Mining motiviert.
ClojureMostly
55
„Wie würde ich ein Modell trainieren, das mir Zeitreisen ermöglicht, unabhängig davon, ob dies‚ möglich 'ist? “
Konrad Rudolph,
13
@ Joshua OP will SHA-256 invertieren . Ich werde ihn veröffentlichen lassen, selbst wenn es tausendmal so viele Schritte dauert wie SHA-256. Ich werde auch aufhören zu existieren, da die Lösung mit ziemlicher Sicherheit einen Fehler innerhalb der Realität ausnutzt, um die Logik zu besiegen.
Konrad Rudolph
15
Alle SHA256-Hashes können durch eine Zeichenfolge generiert werden, die mit einer "1" beginnt.
Reactgular
8
@cgTag Es tut mir leid, aber das ist einfach falsch. Der Eingang steuert den Ausgang, sonst wäre es überhaupt keine Funktion. Nur weil Sie eine unendliche Liste von Dingen haben, heißt das nicht, dass eine davon mit 1 beginnt. Sie versuchen, eine bekannte Kryptographie-Vermutung in einem SE-Kommentar zu beweisen. Anmerkung: Ich glaube auch, dass es wahr ist, aber zu behaupten, dass es wahr ist, ist irreführend. Wenn Sie Recht haben, wird es sicherlich ein Papier oder eine andere Referenz geben.
Pedro A

Antworten:

98

Dies ist nicht wirklich eine Statistik Antwort, aber:

Nein , Sie können das erste Zeichen des Klartextes nicht aus dem Hash bestimmen, da es für einen bestimmten Hash keinen "Klartext" gibt.

SHA-256 ist ein Hashing-Algorithmus. Unabhängig von Ihrem Klartext erhalten Sie eine 32-Byte-Signatur, die häufig als 64-stellige Hex-Zeichenfolge ausgedrückt wird. Es gibt weit mehr mögliche Klartexte als mögliche Hex-Strings mit 64 Zeichen - der gleiche Hash kann aus einer beliebigen Anzahl unterschiedlicher Klartexte generiert werden. Es gibt keinen Grund zu der Annahme, dass das erste Zeichen, bei dem es sich um eine '1' handelt, über alle Klartexte hinweg einheitlich ist und einen bestimmten Hash erzeugt.

Chris H
quelle
21
Dies ist bisher (meiner Meinung nach) die einzig richtige Antwort. Alle anderen Antworten scheinen sich eher mit dem Problem des Lernens der Hash-Funktion zu befassen als mit dem Lernen, den Hash zu invertieren (die eigentliche Frage). Sie scheinen alle zu ignorieren, dass Hashing keine injizierende Funktion ist.
Luca Citi
7
Könnten Sie nicht vorhersagen, mit welcher Wahrscheinlichkeit der erste Buchstabe eine Eins ist? Der Mangel an Eins-zu-Eins-Verhältnissen ist beim statistischen Lernen kein ungewöhnliches Problem.
Matthew Drury
16
1256±ε
12
Ja, stimme zu. Ich wollte nur erwähnen, dass der Mangel an Injektivität bei der Anwendung des maschinellen Lernens kein wirkliches strukturelles Problem darstellt.
Matthew Drury
6
@IMil Der Grund, warum ich speziell die Tatsache erwähnte, dass es sich um eine Hash-Funktion handelt, ist nicht der Hinweis, dass keine Hash-Funktion diese Informationen jemals enthüllen könnte, sondern die Begründung dafür, dass es keinen "Klartext" gibt. Sicher, eine (schlechte) Hash-Funktion könnte teilweise umkehrbar sein und uns etwas über den gesamten Satz von Klartexten erzählen, der sie erzeugen würde, aber es gibt keinen Grund, das von SHA-256 zu glauben.
Chris H
51

SHA256 soll so zufällig wie möglich sein, daher ist es unwahrscheinlich, dass Sie Hashes, die aus 1-vorangestelltem Klartext stammen, von solchen trennen können, die dies nicht tun. Es sollte einfach keine Funktion der Hash-Zeichenfolge geben, die diese Informationen verraten würde.

Pavel Komarov
quelle
5
"unwahrscheinlich" und "sollte" - das sagt mir der Algorithmus. Auf den ersten Blick scheint es unmöglich zu sein, aber ich würde gerne wissen, welchen Algorithmus und welche Vorgehensweise ich verwenden soll, um diese Hypothese zu testen.
John
24
+1 Es ist garantiert, dass jede Art von "unüberwachtem logistischem Regressionsmodell" nicht besser sein kann als zu raten, es sei denn, es kann eine wirklich astronomische Anzahl von Fällen geliefert werden. Dieses Problem neigt sich bei Windmühlen.
Whuber
44
Sie können es versuchen, aber der Lernende wird versuchen, eine statistische Beziehung zu finden, die absichtlich so angelegt ist, dass sie nicht existiert.
Pavel Komarov
32
"Entworfen, um so zufällig wie möglich zu sein" ist eine Untertreibung. Insbesondere strebt der Entwurf eine maximal nichtlineare Abhängigkeit an, wobei jedes Eingangsbit ungefähr 50% der Ausgangsbits beeinflusst und jedes Ausgangsbit von ungefähr 50% der Eingangsbits abhängt. Dies ist als Verwirrung und Diffusion bekannt . Dies macht die Aufgabe hier (das Wiederherstellen des ersten Bits) genauso schwierig wie das Wiederherstellen der gesamten Nachricht.
MSalters
12
Ich denke, Sie können in dieser Antwort "unwahrscheinlich" stärken. Das OP hat keine Chance, statistikbasierte Techniken anzuwenden, um irgendeinen Teil eines SHA256-Hashes anhand des Inhalts vorherzusagen oder umgekehrt, und sogar eine erkennbare Verbesserung gegenüber dem zufälligen Erraten. Die praktische Lösung besteht im Wesentlichen darin, die gesamte Zielgruppe des ursprünglichen Inhalts vorab zu berechnen.
Neil Slater
43

Unabhängig davon, ob dies "Möglich" ist, welcher Algorithmus ist der beste Ansatz?

Sorry, aber das ist eine unsinnige Frage. Wenn etwas unmöglich ist, können Sie nicht nach dem besten Ansatz für das Problem suchen.

In diesem Fall sollte dies definitiv unmöglich sein, da es sich beim Hashing um eine Einwegfunktion handelt: Mehrere Eingänge (tatsächlich unendlich) können den gleichen Ausgang erzeugen. Wenn das erste Bit der Eingabe alleine die Wahrscheinlichkeit eines bestimmten Hash-Werts beeinflussen würde, würde dies bedeuten, dass der Hash-Algorithmus vollständig fehlerhaft ist.

Sie können sicherlich ein neuronales Netzwerk, einen linearen Klassifikator, SVM und so weiter trainieren, um eine Vorhersage zu versuchen. Und wenn Sie in der Lage sind, die Eingabe von der Ausgabe für einen bestimmten Hashing-Algorithmus zuverlässig vorherzusagen, würde dies beweisen, dass dieser Algorithmus wertlos ist. Ich würde sagen, dass für einen weit verbreiteten Algorithmus wie SHA256 eine solche Möglichkeit verschwindend gering ist. Es ist jedoch ein vernünftiger Ansatz, neue, nicht erprobte und nicht getestete Hashing-Algorithmen schnell auszuschließen.

IMil
quelle
6
sign(x)
11
@KonradRudolph: "Einwegfunktion" hat in diesem Zusammenhang eine bestimmte Bedeutung , die nicht die Bedeutung ist, an die Sie denken. sign(x)ist in diesem Sinne keine Einwegfunktion, da das Auffinden von Vorbildern trivial ist.
user2357112
4
Trotzdem denke ich nicht, dass die Antwort "Einwegfunktion" korrekt verwendet.
user2357112
1
@ user2357112 Danke, das wusste ich nicht. Ich kannte nur die Bedeutung als eine Funktion, die surjektiv, aber nicht bijektiv ist. Das ist auch die Definition in der Antwort, gegen die ich Einwände erhoben habe.
Konrad Rudolph
1
Ja, tut mir leid, ich bin ein bisschen nachlässig mit Definitionen. Ich glaube jedoch, dass Einbahnstraßen für Anfänger verständlicher sind als strengere Begriffe.
IMil
26

Während man mit einem Beispiel kein Negativ beweisen kann. Dennoch denke ich, dass ein Beispiel andeutend sein würde; und vielleicht nützlich. Und es zeigt, wie man ähnliche Probleme lösen würde (versucht).

Für den Fall, dass ich binäre Vorhersagen machen möchte, indem ich Features verwende, die binäre Vektoren sind , ist ein Random Forest eine gute Wahl. Ich denke, diese Art von Antworten ist der zweite Teil Ihrer Frage: Was ist ein guter Algorithmus?

Wir möchten die SHA256-Zeichenfolgen unbedingt in binäre (Boolesche) Vektoren vorverarbeiten, da jedes Bit statistisch unabhängig ist und somit jedes Bit ein gutes Merkmal darstellt. Das macht unsere Eingaben also zu 256-Element-Booleschen Vektoren.

Demo

Hier ist eine Demonstration, wie das Ganze mit der Bibliothek Julia DecisionTree.jl gemacht werden kann .

Du kannst folgendes kopieren und in die julia-Eingabeaufforderung einfügen.

using SHA
using DecisionTree
using Statistics: mean
using Random: randstring

const maxlen=10_000 # longest string (document) to be hashed.

gen_plaintext(x) = gen_plaintext(Val{x}())
gen_plaintext(::Val{true}) = "1" * randstring(rand(0:maxlen-1))
gen_plaintext(::Val{false}) = randstring(rand(1:maxlen))


bitvector(x) = BitVector(digits(x, base=2, pad=8sizeof(x)))
bitvector(x::AbstractVector) = reduce(vcat, bitvector.(x))

function gen_observation(class)
    plaintext = gen_plaintext(class)
    obs = bitvector(sha256(plaintext))
    obs
end

function feature_mat(obs)
    convert(Array, reduce(hcat, obs)')
end

########################################

const train_labels = rand(Bool, 100_000)
const train_obs = gen_observation.(train_labels)
const train_feature_mat = feature_mat(train_obs)

const test_labels = rand(Bool, 100_000)
const test_obs = gen_observation.(test_labels)
const test_feature_mat = feature_mat(test_obs)


# Train the model
const model = build_forest(train_labels, train_feature_mat)
@show model


#Training Set accuracy:
@show mean(apply_forest(model, train_feature_mat) .== train_labels)

#Test Set accuracy:
@show mean(apply_forest(model, test_feature_mat) .== test_labels)

Ergebnisse

Dabei trainierte ich an 100.000 zufälligen ASCII-Zeichenfolgen mit einer Länge von bis zu 10.000. Hier sind die Ergebnisse, die ich gesehen habe:

Trainiere das Modell

julia> const model = build_forest(train_labels, train_feature_mat)
Ensemble of Decision Trees
Trees:      10
Avg Leaves: 16124.7
Avg Depth:  17.9

Genauigkeit des Trainingssatzes:

julia> mean(apply_forest(model, train_feature_mat) .== train_labels)
0.95162

Test Set Genauigkeit:

julia> mean(apply_forest(model, test_feature_mat) .== test_labels)
0.5016

Diskussion

Das ist also im Grunde nichts. Wir sind von 95% beim Training auf knapp über 50% beim Test gestiegen. Jemand könnte geeignete Hypothesentests anwenden, um zu sehen, ob wir die Null zurückweisen können
, aber ich bin ziemlich sicher, dass wir das nicht können. Es ist eine winzige Verbesserung gegenüber der Rate.

Das deutet darauf hin, dass es nicht gelernt werden kann. Wenn ein zufälliger Wald, kann von gut gepasst bis nur die Rate geschlagen werden. Zufällige Wälder sind ziemlich fähig, schwierige Eingaben zu lernen. Wenn es etwas zu lernen gäbe, würde ich mindestens ein paar Prozent erwarten.

Sie können mit verschiedenen Hash-Funktionen herumspielen, indem Sie den Code ändern. Was interessant sein könnte Ich habe im Grunde die gleichen Ergebnisse erzielt, als ich die julia in built hashfunction verwendet habe (die keine kryptografisch sichere hsah ist, aber immer noch ein guter Hash, sollte also in der Tat ähnliche Strings auseinander schicken). Ich habe auch im Grunde die gleichen Ergebnisse für CRC32c.

Lyndon White
quelle
15

Hash-Funktionen sind (von Natur aus) äußerst schlecht geeignet, um damit maschinelles Lernen durchzuführen.

ML ist im Wesentlichen eine Methodenfamilie zur Modellierung / Schätzung lokal kontinuierlicher Funktionen. Sie versuchen also, ein physikalisches System zu beschreiben, das, obwohl es gewisse Diskontinuitäten aufweist, in gewissem Sinne im größten Teil des Parameterraums glatt genug ist, so dass nur eine verstreute Stichprobe von Testdaten verwendet werden kann, um das Ergebnis für andere vorherzusagen Eingang. Dazu müssen die AI-Algorithmen die Daten irgendwie in eine clevere Basisdarstellung zerlegen, für die das Training vorgeschlagen hat, dass es z. B. eine solche oder eine solche Form gibt, die mit dem Ergebnis dieser oder jener Faltung zu korrelieren scheint eine gute Chance, dass die Ausgabe in der entsprechenden Region eine solche und eine solche Struktur haben sollte (die wiederum durch eine Faltung oder so etwas beschrieben werden kann).

(Ich weiß, viele ML-Ansätze sind überhaupt keine Faltung, aber die allgemeine Idee ist immer dieselbe: Sie haben einen Eingaberaum, der so hochdimensional ist, dass es unmöglich ist, eine erschöpfende Abtastung durchzuführen, sodass Sie eine clevere Zerlegung finden, mit der Sie extrapolieren können ergibt sich aus einer vergleichsweise spärlichen Stichprobe.)

Die Idee hinter einer kryptografischen Hash-Funktion ist jedoch, dass jede Änderung des Klartextes zu einem völlig anderen Digest führen sollte. Unabhängig davon, wie Sie die Funktion zerlegen, können Sie mit lokalen Schätzern nicht extrapolieren, wie kleine Schwankungen um diesen Teil das Ergebnis beeinflussen. Es sei denn, Sie verarbeiten tatsächlich alle Informationen eines begrenzten Satzes, aber dies würde nicht als maschinelles Lernen bezeichnet: Sie würden nur eine Regenbogentabelle erstellen .

links herum
quelle
4
Lesen dieses, kam mir der Gedanke , dass a) ein Regenbogen - Tabelle zu erstellen, müssen Sie wissen , was Hash - Funktion zu verwenden, und b) es könnte für eine Maschine Lernalgorithmus möglich sein , zu ermitteln , welcher Algorithmus verwendet wird, da eine ausreichend große Stichprobe von Ein- und Ausgängen (zumindest wenn der Algorithmus erkennbare Fehler aufweist). Wenn sich das ursprüngliche Problem auf eine unbekannte Hash-Funktion bezieht, die identifiziert werden muss, ist dies möglicherweise praktischer interessant.
Senderle
7

Dies ist eine interessante Frage, da sie Fragen darüber aufwirft, was als "maschinelles Lernen" gilt. Es gibt sicherlich einen Algorithmus, der dieses Problem eventuell lösen kann, wenn er gelöst werden kann. Es geht so:

  1. Wählen Sie Ihre bevorzugte Programmiersprache und entscheiden Sie sich für eine Codierung, bei der jeder String einer (möglicherweise sehr großen) Ganzzahl zugeordnet wird.

  2. Wähle eine Zufallszahl und wandle sie in eine Zeichenkette um. Überprüfen Sie, ob es sich um ein gültiges Programm in Ihrer Sprache handelt. Ist dies nicht der Fall, wählen Sie eine andere Nummer und versuchen Sie es erneut. Wenn dies der Fall ist, starten Sie es, halten Sie es sofort an und fügen Sie es einer Liste angehaltener Programme hinzu.

  3. Führen Sie einige Zeit lang alle angehaltenen Programme aus. Wenn einer von ihnen anhält, ohne eine angemessene Lösung zu finden, entfernen Sie ihn aus der Liste. Wenn man eine adäquate Lösung herstellt, ist man fertig! Andernfalls kehren Sie zu 2 zurück, nachdem Sie alle eine Weile laufen gelassen haben.

Es ist keine Frage, dass der obige Algorithmus irgendwann eine gute Lösung finden wird, wenn Sie unendlich viel Speicherplatz und unendlich viel Zeit haben. Aber das ist wahrscheinlich nicht das, was Sie mit "maschinellem Lernen" meinen.

Hier ist der Haken: Wenn Sie alle möglichen Probleme berücksichtigen, kann kein Algorithmus für maschinelles Lernen im Durchschnitt eine bessere Leistung erbringen! Dies ist als das No-Free-Lunch-Theorem bekannt . Es zeigt, dass unter allen möglichen Problemen, die Sie mit einem bestimmten Algorithmus für maschinelles Lernen lösen könnten, die Zahl, die schnell gelöst werden kann, verschwindend gering ist.

Diese Probleme können nur dann schnell gelöst werden, wenn sie von Mustern bestimmt werden, die der Algorithmus vorhersehen kann. Beispielsweise setzen viele erfolgreiche Algorithmen Folgendes voraus:

  1. Lösungen können durch einige komplexe Reihen von Matrixmultiplikationen und nichtlinearen Verzerrungen beschrieben werden, die von einer Reihe von Parametern gesteuert werden.

  2. Gute Lösungen werden im Parameterraum zusammengefasst, sodass Sie lediglich eine Suchumgebung auswählen, dort die beste Lösung finden, Ihre Suchumgebung so verschieben, dass die beste Lösung in der Mitte liegt, und wiederholen müssen.

Offensichtlich gilt keine dieser Annahmen im Allgemeinen. Der zweite ist besonders verdächtig. Und das Nein zum kostenlosen Mittagessen sagt uns, dass diese Annahmen die meiste Zeit nicht einmal zutreffen. Tatsächlich halten sie fast nie! Es ist nur unser Glück, dass sie für bestimmte Probleme halten, die tatsächlich wichtig sind.

Das von Ihnen gewählte Problem wurde von Anfang an so konzipiert, dass es gegen die Annahme 2 verstößt. Hash-Funktionen sind speziell so konzipiert, dass ähnliche Eingaben völlig unterschiedliche Ausgaben ergeben.

Ihre Frage - was ist der beste Algorithmus für maschinelles Lernen, um dieses Problem zu lösen? - hat wahrscheinlich eine sehr einfache Antwort: Zufallssuche.

Senderle
quelle
Ich frage mich, wie sich Quantencomputing auf das No-Free-Lunch-Theorem auswirken wird. Vermutlich wird auch das Quantencomputing dadurch eingeschränkt.
Max Vernon
1
@ MaxVernon oh, interessant. Ich würde erwarten, dass alle Quantenalgorithmen im Vergleich zu anderen Quantenalgorithmen die gleichen Eigenschaften haben . Ich weiß nicht, ob alle Quantenoptimierungsalgorithmen eine Durchschnittsbeschleunigung gegenüber den klassischen Algorithmen aufweisen. Sie könnten! Ich habe eine Frage und eine Selbstantwort , die von einem Satz über "kostenloses Mittagessen" handelt, der relevant sein könnte. (tldr; das Mittagessen ist nur kostenlos, wenn Sie einen Teil der geleisteten Arbeit ignorieren ... aber ich frage mich, ob sich dies im Quantenfall ändert.)
senderle
5

Es ist so gut wie unmöglich. In SHA256 wurden jedoch einige Muster beobachtet, die darauf hindeuten könnten, dass es sich bei SHA256 um ein nicht zufälliges Verhalten handelt, das Bitcoin verwendet (schnelleres Gewinnen auf dem Weg) . Ihr tldr:

"Um zwischen einem idealen zufälligen Permutations-Hash und SHA256 zu unterscheiden, muss eine große Menge (~ 2 ^ 80) von 1024-Bit-Blockkandidaten zweimal wie in Bitcoin gehasht werden. Stellen Sie sicher, dass die Bits der Kandidatenblöcke dünn gesetzt sind (viel weniger als die 512 Mittelwert erwartet) Verwerfen von Kandidatenblöcken, die nicht dem Bitcoin-Schwierigkeitsgrad entsprechen (wobei die resultierenden Hashes mit einer großen Anzahl von Nullen beginnen), gemäß dem Bitcoin-Protokoll Beobachten Sie einen bestimmten Satz von 32 Bits im Eingabeblock (an der Stelle, an der Bitcoin die Nonce hat, Eingabebits 607-639). dh weniger als der erwartete Wert von 16 gesetzten Bits (geschätzter Mittelwert 15,428). "

Siehe eine Diskussion auf lobste.rs . Eine mögliche Erklärung ist eine von den Bergleuten eingeführte Voreingenommenheit.

IndieSolver
quelle
2
Das ist interessant. Aber die Antwort auf lobste.rs ist wahrscheinlich richtig. Das ist eine große Tendenz, die leicht zu entdecken ist. Die Vorstellung, dass es so lange unbemerkt blieb, ist ziemlich weit hergeholt.
Senderle
1
@senderle Um die Verzerrung (falls vorhanden) auszunutzen, sollte man einen Algorithmus (im Wesentlichen einen ML / Optimierungsalgorithmus) entwickeln, der rechnerisch günstig ist, so dass er einen eigenen Overhead hat, wenn er auf modernster Hardware implementiert / gemessen wird wird durch die Beschleunigung kompensiert, die es bietet. Meine sehr grobe Vermutung wäre, dass der Faktor in Bezug auf #hashtrials größer als 10x sein sollte, um Brute Force und seine superoptimierten Implementierungen zu schlagen. Die Auswirkungen können sehr schwerwiegend sein, insbesondere für Personen, die auf Krypto- und Sicherheitsprotokolle setzen.
IndieSolver
4

Ich antworte mit einem Programm. Um den Rechenaufwand zu reduzieren, verwende ich eine Variante von sha256, die ich sha16 nenne. Dies sind nur die ersten 16 Bits von sha256.

#!/usr/bin/python3

import hashlib
from itertools import count

def sha16(plaintext):
    h = hashlib.sha256()
    h.update(plaintext)
    return h.hexdigest()[:4]

def has_plaintext_start_with_1(digest):
    """Return True if and only if the given digest can be generated from a
    plaintext starting with "1" first bit."""
    return True

def plaintext_starting_with_1(digest):
    """Return a plaintext starting with '1' matching the given digest."""
    for c in count():
        plaintext = (b'\x80' + str(c).encode('ascii'))
        d = sha16(plaintext)
        if d == digest:
            return plaintext

for digest in range(0x10000):
    digest = "%04x" % (digest,)
    plain = plaintext_starting_with_1(digest)
    print("%s hashes to %s" % (plain, digest))

Dies erzeugt die Ausgabe:

b'\x8094207' hashes to 0000
b'\x8047770' hashes to 0001
b'\x8078597' hashes to 0002
b'\x8025129' hashes to 0003
b'\x8055307' hashes to 0004
b'\x80120019' hashes to 0005
b'\x8062700' hashes to 0006
b'\x8036411' hashes to 0007
b'\x80135953' hashes to 0008
b'\x8044091' hashes to 0009
b'\x808968' hashes to 000a
b'\x8039318' hashes to 000b
[...]

Ich werde den vollständigen Beweis als Übung für den Leser hinterlassen, aber nehmen Sie mein Wort dafür: Es gibt eine Eingabe, die mit einer "1" für jeden möglichen Digest von 0000 bis ffff beginnt.

Es gibt auch einen Eingang, der nicht mit "1" beginnt. Und es gibt eine, die auch mit den kompletten Werken von Shakespeare beginnt.

Dies gilt für jede einigermaßen gute Hash-Funktion, obwohl mein Brute-Force-Beweis möglicherweise nicht mehr rechnerisch durchführbar ist.

Phil Frost
quelle
In der Mathematik nehme ich Ihr Wort nicht gerne dafür . Ihr Programm zeigt, dass Ihre sha16-Funktion surjektiv ist, aber nicht mehr. Sie haben keinen formalen Beweis dafür erbracht, dass dieses Programm die tatsächliche SHA-256-Funktion nachweisen kann. Nach Ihrem Fazit wäre die Collatz-Vermutung gelöst, da sie bereits für 32 Bit gelöst ist und das Programm problemlos länger ausgeführt werden kann.
Roland Illig
4

Was Sie beschreiben, ist im Grunde ein Pre-Image-Angriff. Sie versuchen, eine Eingabe so zu finden, dass die Ausgabe, wenn sie gehasht wird, eine Eigenschaft wie "eine führende 1" hat. *

Es ist ein explizites Ziel von kryptografischen Hashes, solche Pre-Image-Angriffe zu verhindern. Wenn Sie einen solchen Angriff ausführen können, halten wir diesen Algorithmus in der Regel für unsicher und verwenden ihn nicht mehr.

Während dies bedeutet, dass es nicht unmöglich ist, bedeutet dies, dass Ihr Algorithmus für maschinelles Lernen gleichzeitig einen großen Teil der Mathematiker der Welt und ihre Supercomputer überlisten muss. Es ist unwahrscheinlich, dass Sie dies tun.

Wenn Sie dies jedoch tun, werden Sie als jemand bekannt, der einen wichtigen kryptografischen Hash-Algorithmus durchbrochen hat. Dieser Ruhm ist etwas wert!

* Technisch gesehen versucht ein "erster Preimage-Angriff", eine Übereinstimmung für einen bestimmten Hash zu finden. Um jedoch zu zeigen, dass ein Hash-Algorithmus eine Resistenz gegen Angriffe vor dem Bild aufweist, wird in der Regel angezeigt, dass Sie keine aussagekräftigen Informationen zu den Eingaben aus dem Hash finden können.

Cort Ammon
quelle
2

Die meisten Antworten hier sagen Ihnen, warum Sie dies nicht tun können, aber hier ist die direkte Antwort auf:

Unabhängig davon, ob dies "Möglich" ist, welcher Algorithmus ist der beste Ansatz?

Vorausgesetzt, die Eingabe ist ausreichend groß:

  1. Nimm die Anzahl der gültigen Zeichen.
  2. Nehmen Sie den Kehrwert der Zahl aus Schritt 1.

Das ist die Wahrscheinlichkeit, dass die Eingabezeichenfolge mit '1' beginnt. Sie müssen sich nicht einmal die Eingabe ansehen. Wenn Sie es besser machen können, würde dies bedeuten, dass der Hash sehr kaputt ist. Sie können eine Menge CPU-Zyklen sparen, wenn Sie versuchen, einen Algorithmus für die Auswahl von Zufallszahlen zu trainieren.

Sie könnten einen Algorithmus trainieren und er könnte aufgrund von Überanpassung eine andere Antwort liefern. Es sei denn, mit dem Hash-Algorithmus stimmt etwas wirklich nicht. Die Verwendung dieses Algorithmus schlägt dann häufiger fehl, als wenn Sie einfach einen zufälligen Wert auswählen.

JimmyJames
quelle
1

Hashing-Funktionen sind absichtlich so konzipiert, dass sie schwer zu modellieren sind. Wie bereits erwähnt, ist dies wahrscheinlich sehr schwierig. Dennoch wird jede Schwäche der Hash-Funktion ihre Entropie verringern und sie vorhersehbarer machen.

Unabhängig davon, ob dies "Möglich" ist, welcher Algorithmus ist der beste Ansatz?

Ein nützliches Beispiel ist die Funktion "Physically Unclonable Function" (PUF), die einer Hardware-Hashing-Funktion entspricht. In der Regel werden Herstellungsvarianten gezielt verwendet, um jedem PUF eine leicht unterschiedliche Reaktion zu verleihen, sodass sich die Hash-Ausgabe für eine bestimmte Eingabe unterscheidet. Konstruktionsschwächen begrenzen jedoch die Entropie, und bei genügend Herausforderung-Antwort-Paaren ist es häufig möglich, ein Black-Box-Modell der PUF zu erstellen, damit die Reaktion auf eine neue, zuvor nicht sichtbare Herausforderung vorhergesagt werden kann.

Die logistische Regression ist der am häufigsten verwendete Ansatz für diese Modellierungsangriffe, wie in diesem Artikel von Rührmair .

Genetische Algorithmen (oder allgemeiner evolutionäre Strategien) können ein alternativer Ansatz sein, da sie auf Probleme anwendbar sind, die nicht differenzierbar und / oder linear trennbar sind. Sie werden auch in dem obigen Papier erörtert.

4Oh4
quelle
1

251222562256

26402641

2256264(2256264)!

S=(2256264)
C=90100S
CSC

(1S1S11S2...1S(C1))(SC1SCSC2SC1SC3SC2...12)=(SC1)!S!

=(110(2256264)1)!(2256264)!
2(2263.99184665662260.6509677217)
210.13222373912260.6509677217

22562512

user96549
quelle
1

Das Problem ist, dass "maschinelles Lernen" nicht intelligent ist. Es wird nur versucht, Muster zu finden. In SHA-256 gibt es keine Muster. Es gibt nichts zu finden. Maschinelles Lernen hat keine Chance, die besser ist als rohe Gewalt.

Wenn Sie SHA-256 mit dem Computer knacken möchten, besteht die einzige Möglichkeit darin, echte Intelligenz zu erzeugen , und da viele kluge Menschen keinen Weg gefunden haben, SHA-256 zu erzeugen, müssen Sie künstliche Intelligenz schaffen, die viel höher ist als das vieler kluger Menschen. Zu diesem Zeitpunkt wissen wir nicht, ob eine solche übermenschliche Intelligenz SHA-256 knacken, beweisen würde, dass sie nicht geknackt werden kann, oder entscheiden würde, dass sie nicht klug genug ist, dies auch zu tun (genauso wie Menschen). Die vierte Möglichkeit ist natürlich, dass eine solche übermenschliche künstliche Intelligenz nicht einmal die Mühe macht, sondern über wichtigere Probleme nachdenkt.

gnasher729
quelle