Wie wahrscheinlich ist es, dass die MD5-Summen verschiedener Dateien gleich sind?

[hiTCH-HiKER]

Ich schreibe mir gerade ein Skript um mehrfach vorhandene Dateien zu entfernen.
Zum Vergleichen der Dateiinhalte nutze ich MD5.
Wie wahrscheinlich ist es, dass ich auf diese Art und Weise aus Versehen Dateien erfasse, die gar nicht mehrfach vorhanden sind, aber zufällig die gleiche MD5-Summe teilen? Kann man das vernachlässigen oder würdet ihr in Frage kommende Dateien nochmal zeichenweise vergleichen?

[Shutdown]

Das lässt sich ja ausrechnen :D
Eine MD5-Summe ist 32-Stellig, es werden Zahlen und Buchstaben von a-z verwendet.
Zahlen gibt es 10 (0-9), Buchstaben gibt es 26, macht zusammen 36 Möglichkeiten.
Es gibt also 32^36 Möglichkeiten wie eine MD5-Summe aussehen kann, macht also 1.5324955408658889e+54 Möglichkeiten :ugly:
(Die Wahrscheinlichkeit dafür, das 2 x-beliebige Dateien die gleiche MD5-Summe haben, ist also 1:1.5324955408658889e+54)

Ich denke also mal, dass es recht unwahrscheinlich ist, dass man 2 Dateien mit der gleichen Summe hat...ein 6er im Lotto ist wahrscheinlicher! (1:1.3471354624412734e+38)

Ausserdem könntest du gleiche Dateien ja erst in eine Liste packen, die man dann noch mal durchgehen kann...manuelle Kontrolle dürfte da eine recht gute Sicherheit bringen :D

Shutdown

[hiTCH-HiKER]

Eine manuelle Kontrolle ist leider nicht bzw. nur sehr schwer möglich, weil es sich um tausende gleicher Dateien handelt.

[Shutdown]

Was willst du denn machen? Wo hat man denn tausende gleicher Dateien???

Shutdown

[hiTCH-HiKER]

Was willst du denn machen? Wo hat man denn tausende gleicher Dateien???

Shutdown

Das sind alles Digicam Bilder, die durch einen Datenverlust und anschließender Rücksicherung nun mehrfach vorhanden sind.

[NoNeX]

Kleine Idee: erstmal nur die Filesizes vergleichen, das spart MD5-Berechnungen und sollte das ganze um einiges beschleunigen :)

mfg. NoNeX

[Roger Wilco]

Eine MD5-Summe ist 32-Stellig, es werden Zahlen und Buchstaben von a-z verwendet.
Du hast ein komisches MD5 ;)
Der MD5-Algorithmus gibt einen 128 Bit langen Hash zurück. Das hat mit dem Zeichensatz zunächst mal nichts zu tun, aber du hast dich wohl von der hexadezimalen Darstellung verwirren lassen. Dabei wird der Hash eben zur Basis 16 dargestellt, wozu die Ziffern 0 bis 9 und die Buchstaben A-F verwendet werden (16 Werte). Die Länge ist 32 Zeichen, wobei je 2 Zeichen 1 Byte ergeben. Summa Sumarum haben wir dann 16 * 1 Byte, was 16 * 8 = 128 Bit sind.

Die Wahrscheinlichkeit, dass 2 Dateien den gleichen MD5-Hash ergeben, ist dennoch sehr gering. Weiter Verringern kann man die Kollisionswahrscheinlichkeit, indem man noch Dateigröße und Änderungsdatum vergleicht.

[hiTCH-HiKER]

Kleine Idee: erstmal nur die Filesizes vergleichen, das spart MD5-Berechnungen und sollte das ganze um einiges beschleunigen :)

mfg. NoNeX

Die Dateigrößen vergleichen bringt nix, da ich ja keine Datei A und B habe, sondern einen Haufen Dateien wo evtl. die eine oder andere mehrfach vorkommt (vom Inhalt her, nicht unbedingt vom Namen). Was man aber machen kann, ist eine Liste aller Dateien mit Größe und die Zeilen mit Größen die nur einfach vorkommen rausschmeißen :)

Wenn ich bei Dateien mit gleicher MD5-Summe dann noch die Größen vergleiche sollte das wirklich sicher genug sein.

[peschmae]

Als paranoider Mensch könntest du auch noch sha1sum anstellen - aber das wäre dann wirklich übertrieben ;)

MfG Peschmä

[lagalopex]

Ich kann dir fdupes (http://netdial.caribe.net/~adrian2/fdupes.html) empfehlen. Es wird erst die Größe und der MD5-Hash herangezogen, bei gleichheit wird Byte für Byte verglichen...

[Shutdown]

Du hast ein komisches MD5 ;)
Der MD5-Algorithmus gibt einen 128 Bit langen Hash zurück. Das hat mit dem Zeichensatz zunächst mal nichts zu tun, aber du hast dich wohl von der hexadezimalen Darstellung verwirren lassen. Dabei wird der Hash eben zur Basis 16 dargestellt, wozu die Ziffern 0 bis 9 und die Buchstaben A-F verwendet werden (16 Werte). Die Länge ist 32 Zeichen, wobei je 2 Zeichen 1 Byte ergeben. Summa Sumarum haben wir dann 16 * 1 Byte, was 16 * 8 = 128 Bit sind.

Die Wahrscheinlichkeit, dass 2 Dateien den gleichen MD5-Hash ergeben, ist dennoch sehr gering. Weiter Verringern kann man die Kollisionswahrscheinlichkeit, indem man noch Dateigröße und Änderungsdatum vergleicht.

Stimmt, manchmal ist man echt blöder als man es für Möglich halten würde... :ugly:
Danke für die Berichtigung!

Shutdown

[ChandlerBing]

Also ist P = 1 : 2^128 ?

[Der Untergeher]

Wie wahrscheinlich ist es, dass die MD5-Summen verschiedener Dateien gleich sind?

Also ist P = 1 : 2^128 ?
Wenn man zu zwei beliebige, verschiedene Dateien die Hashwerte berechnet ist die Wahrscheinlichkeit das diese gleich sind 1/2^128 . Wenn man mehr als zwei Dateien miteinander vergleichen will wird die Kollisionswahrscheinlichkeit natürlich größer. Die Wahrscheinlichkeit das keine Kollision auftritt ist etwa exp(- i^2/2n), wobei i die Anzahl der Dateien und n die Anzahl der Hashwerte ist (hier also 2^128).

@hiTCH-HiKER: Funktioniert das oben verlinkte Programm? Ansonsten: Ich hab mal ein C++ Programm geschrieben mit dem man das bewerkstelligen kann.

Grüße

Untergeher

[hiTCH-HiKER]

Danke, ich hab mir ein Skript dafür geschrieben, ich traue fremden Programmen nicht ;)
Bzw. ich will mir schon selbst meine Dateien zerschießen :D

[Kwitchibo]

Warum benutzt Du nicht einfach ein Programm das Bilderduplikate finden kann?
Dabei werden nicht nur absolut identische Duplikate gefunden, sondern je nach Einstellung auch Bilder mit ähnlichem Inhalt. Dadurch kann man z.B. auch Bilder mit demselben Inhalt aber unterschiedlichen Ausmaßen finden.


GQView kann das zum Beispiel.

[Der Untergeher]

Danke, ich hab mir ein Skript dafür geschrieben, ich traue fremden Programmen nicht ;)
Na, die wenigten Skripte laufen ohne fremde Programme ;)

Bzw. ich will mir schon selbst meine Dateien zerschießen :D
Das verstehe ich allerdings, das mach' ich nämlich auch immer selber :)