[Hypothetisch] Implikationen einer hash Umkehrfunktion

[DPA (Gast)]

Hallo,

Ich hatte vor kurzem mal einen hypothetischen absurd-interessanten 
Gedanken.

Hash Funktionen haben ja gewisse interessante Eigenschaften, nämlich:
 * Einwegfunktion, keine Umkehrfunktion bekannt
 * Selbst kleine Änderungen am Input ändern den Output komplett

Deshalb werden diese auch oft als Prüfsummen verwendet. Manche Programme 
gehen sogar so weit, dass wenn sie einen Block/eine Datei mit einer 
gewissen Checksumme nicht nochmal übertragen und ganz Vergleichen, 
sondern einfach annehmen, das es das Selbe ist.

Technisch gesehen ist es ja falsch, anzunehmen, dass z.B. 
sha256(A)=sha256(B) dann A=B. sha256 erzeugt einen 256bit (=32byte) 
langen Hash. Falls A nur schon 33bytes lang ist, müsste es also für ein 
A ungefähr 256 Lösungen für B (bei gleicher Länge), geben. Also immer 
ungefähr 256 hoch (sizeof(B)-sizeof(h)) Möglichkeiten. Also sehr schnell 
sehr viele.

Interessanterweise scheint es in der Wildbahn aber praktisch keine 
bekannten sha256 Kollisionen zu geben. Das bringt mich zu der folgenden 
Hypothetischen Frage/Überlegung.

Nehmen wir jetzt einfach mal an man könnte eine Umkehr-Funktion F(H,h) 
definieren, die, gegeben eine Hashfunktion H, und einen Hash h, ein Set 
aller möglichen Eingaben X für H zurück gibt, für die das Erlebnis von H 
dem hash h entspricht. Danach, filtern wir X nach weiteren Kriterien, 
wie z.B. die Anzahl Bytes an Speicher, welches es verbrauchen würde, ob 
es einen gültigen Dateiheader enthält, ob es eine Gültige Bilddatei mit 
Prüfsummen usw. beschreibt, etc. Nehmen wir des weiteren an, man könnte 
einen Algorithmus konstruieren, der anhand des Hash in endlicher Zeit 
alle verbleibenden Möglichkeiten sortiert ermitteln, und über diese 
Iterieren könnte, oder einfach die i-te ermitteln könnte, wobei i frei 
wählbar ist.

Die Frage ist nun, wüsste man einen Hash, und zu was er gehört, wäre es 
einem Menschen, unter den oberen Annahmen,  möglich, das gesuchte 
ausreichend gut zu Beschreiben, um die Möglichen Ergebnisse stark genug 
einzuschränken, dass dieser aus den verbleibenden die gesuchte Datei 
finden kann?

Ich weis, das ganze ist praktisch nicht machbar, aber eben, jetzt mal 
rein Hypothetisch.

[sid (Gast)]

Naja wenn man alle Fallen weg-hypothetisiert,
dann muss man zwangsläufig an ein Ergebniss kommen.

Die Sache mit solchen EinwegFunktionen beruht zumeist
auf dem Lawinen Effekt, der durch modulare Addition entsteht
(overflow wird schlicht ignoriert)
Nehmen wir einfach mal an es seien nur 8 bit (sind meist 32 oder 64)

dann käme an einer stelle des Ablaufs  m + n = x (x <=255)
m und n aber sind ebenfalls <= 255
Deine Liste für diesen einzelnen Schritt müsste also
ALLE möglichen Kombinationen von m und n enthalten, die
das Ergebniss x erzeugen.

Sagen wir einfach mal x sei 200;
selbst wenn man annimmt es hätte keinen overflow gegeben
kann m = 200 und n = 0
oder m = 199 und n = 1
....
oder m = 1 und n = 199
oder m = 0 und n = 200

und das müsste man für jeden möglichen Grund für den Overflow 
wiederholen
um es zu Liste hinzuzufügen
also m=201 und n=255 ....
oder m=202 und n=254 ....
....
oder m=254 und n=254 ....
oder m=255 und n=201 ....

man käm also schon jetzt an eine recht lange Liste von Möglichkeiten.
um genau zu sein schon jetzt findest Du zu jedem m (0-255)
ein passendes n (ebenfalls 0-255) dass dir x = 200 erzeugt.

Hizukommt das solche Hashfunktionen solche rechenoperationen in 
schleifen stehen haben
und mit jedem Durchgang einer Schleife potenzierst Du die
Anzahl der Werte in Deiner Liste
für jedes Deiner notierten m müsstest Du also
a + b = m exakt so behandeln, und c + d = n ebenfalls
und auch hier fändest Du zu jedem a im Wertebereich (0-255) ein b das 
Dir jeden wert m (0-255) erzeugt und so weiter und so fort.
Du siehst also das keine Einschränkung sinnvoll möglich ist anhand 
solcher modularen addition.

hypothetisch kannst Du vermutlich
versuchen jeweils erste Wertepaar zu verfolgen und alleine zu 
betrachten,
irgendwann allerdings da hashes zwischenwerte nichtnur addieren sondern 
auch XOR-en oder multiplizieren oder invertieren können
kommt es zu einem Widerspruch, dann kannst Du diese Option streichen und 
fängst mit dem nächsten Paar von vorne an.

Besonders schnell wird das nicht sein, vermutlich sogar länger dauern 
als
klassisches brute forcing, da du für jede addition bis zu 256 mal 
ausprobieren müsstest in unserem Beispiel mit nur 8bit;
(mit 32 bit ein klein wenig öfter ;))

Ich hab vor 20 Jahren etwa mal etwas nicht unähnliches versucht mit md5
(einfach weil's ein schlichter algo ist der mir überschaubare 
komplexität zu haben schien)
hab da einen regnerischen Samstag nachmittag mit verbracht und danach 
nie wieder ersnthaft drüber nachgedacht; es ist schlicht realer irrsinn,
die Lawine vergräbt dich sehr schnell sehr tief sagen wir mal ;)

Aber sicher, hypothetisch kann man potentielle Treffer auflisten,
mit begrenzter Anzahl an input-bits sollte auch die Liste und Anzahl der 
Kandidaten überschaubar bleiben;
das erstellen solcher Liste allerdings ist unfassbar aufwändig.
reell wird das vermutlich nichteinmal dazu reichen auch nur den ersten 
Schleifendurchlauf zu überstehen (rückwärts also den vorletzten bei sha)

'sid