MD5 Kollisionen

fugyl

Grünschnabel
Hallo zusammen :)

Ich habe vor einen Algorithmus zu schreiben, der sich allerdings noch in der Planungsphase befindet.
Da ich einen Hash-Algo brauche, habe ich mich für MD5 entschieden, schon allein wegen der Performance.
Keine Angst, ich will keine Passwörter, sondern größere unsensible Dateien hashen ;)

Nun sagen wir mal eine solche Datei bestehe aus n Bytes (bzw. k=8n bits).

Die Frage ist nun: Gibt es eine MINIMALE Anzahl an Bits, die geflippt werden müssen, sodass eine Kollision entsteht, also dass man auf den gleichen MD5-Hash kommt wie die Originaldatei?

Ich weiß dass eine Kollision selbst bei riesigen Dateien sehr unrealistisch ist (man benötigt im Schnitt 256^31 ~ 10^77 Flips, glaube ich zumindest), trotzdem möchte ich sie unmöglich machen.

Lieben Gruß
Fugyl

PS: Ich hoffe ich hab die richtige Rubrik gewählt, hab nichts passenderes gefunden :p
 

Bratkartoffel

gebratene Kartoffel
Premium-User
Hi,

bei jedem Hash Algorithmus hast du Kollisionen, die kannst du nicht "unmöglich" machen. Jede Funktion, die eine Summe von Daten auf eine kleinere Menge runterbricht muss per Definition Kollisionen haben.

Wenn du Kollisionen möglichst ausschließen willst, dann brauchst du einen Hashing Algorithmus, der eine längere (md5 = 128 Bit, sha512 = 512 Bit) Prüfsumme erzeugt.

Grüße,
BK
 

fugyl

Grünschnabel
Hey, danke für die schnelle Antwort :)

Es geht ja nicht darum beliebige Kollisionen zu vermeiden.

Ich gehe davon aus, dass sich die Größe der Datei nicht ändert, ich also jederzeit n Bytes besitze, ich flippe also nur und lösche nichts bzw. füge keine Bits hinzu.

Ein wichtiger Punkt bei MD5 (bzw. anderen Hash-Algos) ist es ja, dass wenn sich schon ein Bit im Ausgangsobjekt ändert, der gesamte Hash komplett anders aussieht.

Das heißt, es ist unmöglich mit einem einzigen Flip eine Kollision hervorzurufen (soweit ich das verstanden habe).

Ich behaupte jetzt auch mal dreist, dass das für 2, 3 und 4 Flips der Fall ist (ganz gleich wo sich diese Bits befinden). Anders formuliert ist meine Frage also: Wieviele Flips kann ich (max.) machen, sodass mit Sicherheit keine Kollision auftritt?

Sagen wir mal die Antwort auf diese Frage ist z, eine (hoffentlich) recht große Zahl.
Dann würde ich meine riesige Datei in Segmente der Länge z zerlegen und jedes Segment einzeln Hashen, wodurch sichergestellt wäre, dass man mittels der Hashes auf jeden Fall eine Änderung der Datei (also Bitflips) feststellen kann.

Ich hoffe du kannst mir folgen und dass ich keinen zu gravierenden Denkfehler in meiner Interpretation hab :p

Lieben Gruß
Fugyl

PS: Evtl. werde ich auch auf einen anderen Hash-Algo umsteigen, wenn mir MD5 nicht mehr so zusagt. Dann wäre natürlich die Bonusaufgabe die Frage für eine beliebige uniforme Hashfunktion zu beantworten, ich denke aber das ist nicht ganz so trivial ;)
 

fugyl

Grünschnabel
Boah seid ihr schnell mit der Recherche :D Vielen Dank für die Antworten.

6 bzw. 2 Bits sind ja schon recht wenig. Also fällt MD5 raus. Schade ^^

Welchen Hash-Algo könnte ich denn benutzen um eine möglichst große Kollisionsresistenz zu erhalten?
Am allerbesten wäre es, wenn die gesuchte Zahl (z in meinem letzten Beitrag) abhängig von der Dateigröße n wäre, also sowas schönes wie z >= max{log(n), 256^32} oder so. SHA würde da ja auch nicht funktionieren, wie ich herausfinden durfte.

Wäre etwas damit gewonnen, zwei unterschiedliche Hash-Algorithmen zu benutzen und die resultierenden Hashs einfach zu konkatenieren? Intuitiv würde ich sagen nein, aber was weiß ich schon? :p

Bei einer Kollision bei schon einer Code-Distanz von 2 kann ich auch XOR benutzen, das wär noch schneller als MD5.

Auf alle Fälle schonmal vielen Dank für die hilfreichen Antworten :)

Lieben Gruß
Fugyl
 

sheel

I love Asm
Wäre etwas damit gewonnen, zwei unterschiedliche Hash-Algorithmen zu benutzen und die resultierenden Hashs einfach zu konkatenieren?
Etwas besser wäre es schon, die Frage ist nur, ob sich die Verbesserung im Vergleich
im Vergleich zur längeren Verarbeitungszeit etc. lohnt.

Und nachweisen, dass mit <2 bit geändert (bei MD5 zb.) keine Kollision möglich ist,
aber mit >=2 schon, ist ja auch nicht so trivial
(bzw. sehr komplex, wenns erst 2010 herausgefunden wurde).
Durch Kombination von Hashes wird das vermutlich so verkompliziert,
dass man das nicht mehr nachweisen kann :p
(ohne einfach alle Möglichkeiten durchzuprobieren, was eben ein paar Millionen Jahre dauert)

Rein intuitiv würde ich aber sagen, dass es auch bei der SHA-Familie nicht sehr anders sein wird,
also dass es Beispiele gibt, wo man mit 2,3,4 bit anders schon eine Kollision hat,
nur da ist das absichtliche Finden davon noch um einiges schwerer.

Wozu soll das dann in deinem Fall eigentlich gut sein,
wenn es etwas dermaßen Kollisionsresistentes geben würde?
 

fugyl

Grünschnabel
Wozu soll das dann in deinem Fall eigentlich gut sein,
wenn es etwas dermaßen Kollisionsresistentes geben würde?
ComFreak hat gesagt.:
Wie groß sind denn deine Datemengen überhaupt?
Da es mit etwas effizientem wie MD5 nicht "ganz so einfach" funktioniert, hat die Frage jetzt eher theoretischen Gehalt. Da ich persönlich auch eher der Theoretiker bin, gehe ich von einer extrem (und unrealistisch) großen Datenmenge (sagen wir... 5PByte?) aus. In der Praxis handelt es sich um Dateien (bzw. Bitströme) von etwa ~2-30GByte.

Ich hätte meinen Algo gern so gebastelt, dass er nicht nur zu (100-?)%iger Sicherheit eine Änderung der Datei bemerkt, sondern exakt 100%. Auch wenn ich diese Idee (schon aufgrund der Performancegründe) verwerfen werde, interessiert mich die Antwort auf die Frage trotzdem.

Ich bin nicht sehr bewandert mit Hashes, muss ich zugeben, deswegen auch meine Frage. :)

Lieben Gruß
Fugyl
 

sheel

I love Asm
Exakt 100%, also einen totalan kollisionsresistenten krypt. Hash, gibt es leider eben nicht.
Eine Kopie der Datei an einer 100% verlässlichen Stelle haben wäre die einzige Möglichkeit,
nur dass es so eine Stelle auch nicht gibt...

Aber Algorithmen wie SHA2 sind für die nächsten paar Jahre vermutlich unknackbar,
also...zufällig eine Kollision finden ist immer möglich, aber sehr sehr sehr unwahrscheinlich.


Würde mir lieber Gedanken um andere Blickwinkel der Sachen machen.
Um etwas triviales zu nennen: Wenn die Hashes bei den Daten dabei sind,
was hindert mich daran, einfach alles samt Hashes zu ersetzen?
Ergebnis ist auch gültig, nur eben nicht das, was vorher drin war.