Diskussion:Message-Digest Algorithm 5

Der Abschnitt "Sicherheitsüberlegungen" muss mal neu durchstrukturiert und aktualisiert werden. Teilweise widerspricht sich der Inhalt des Artikels inzwischen selbst. Insbesondere ist MD5 ja nun geknackt worden, man kann auf entsprechender Hardware im Minutentakt Kollisionen finden. Der gestern Abend neu eingefügte Satz "Insbesondere ist es noch nie gelungen, aus einer gegebenen MD5-Summe die Ursprungsnachricht zu rekonstruieren" ist irgendwie sachlich verkehrt. Aus einem 128-Bit-Hash kann ich wohl kaum "die" Ursprungsnachricht rekonstruieren, sondern nur per Kollision eine (möglicherweise Garbage enthaltende) Nachricht finden, die den gleichen Hash hat. --Echoray 15:28, 7. Sep 2004 (CEST)

Wahrscheinlichkeit zwischen Verschiedenen Zeichenketten

Kann mir jemand erzählen wie man die Wahscheinlichkeit eines doppelten Vorkommens berechnet? Als Beispiel die Zeichenkette:

"Franz jagt im komplett verwahrlosten Taxi quer durch Bayern" ergibt a3cca2b2aa1e3b5b3b5aad99a8529074

Wann kommt es vor, das eine andere Zeichenreihenfolgen (die vielleicht sogar kürzer ist) die gleiche MD5 Summe ergibt? z.B.

"%(/&$$&DFD$$" wäre dann a3cca2b2aa1e3b5b3b5aad99a8529074

Denn die Aussage "(mit sehr großer Wahrscheinlichkeit)" im Artikel reicht mir nicht aus,

Vielen Danke im Voraus Anregungen -- Anonymous

Wenn du einen Hash hast und du nimmst irgendeinen zufälligen String, von dem du den Hash berechnest, dann ist die Chance nach "Gute Lösungen" durch "Mögliche Lösungen" (siehe Wahrscheinlichkeitsrechnung#Laplace-Experimente) 1/2^128 ~= 3E-39, dass beide Strings gleich sind. So wäre meine Sichtweise, ich lasse mich natürlich auch geren korrigeren, aber ich denke, dass es schon richtig sein sollte. --Martinpre 19:52, 25. Jun. 2007 (CEST)

Danke, das macht es schonmal nicht unmöglich. Aber bis morgen bekomme ich dann wohl nicht raus welcher stringwert == a3cca2b2aa1e3b5b3b5aad99a8529074 ist :-D. Nochmal frage zu der Berechnung: 1/2^128 ~= 3E-39. Die 128 sind ja 128bit, warum aber 1/2?. Wann wäre 1/2 denn 1/4? ;-). Dann hätte ich gerne noch 3E-39 in Tage umgerechnet *scherz*. -- Anonymous

Naja die Chance, dass ein Bit "stimmt" ist 1/2. Die Chance, dass zwei Stimmen ist 1/2^2 ...

Die 3E-39 sind hierbei nur die Chance, dass wenn du einen Hash hast und du einen zweiten aus einem zufälligen String berechnest gleich ist. lg noch ;) --Martinpre 19:04, 2. Jul. 2007 (CEST)

Einige Fragen

Ein sehr schöner Artikel, ich habe einige Fragen dazu, vielleicht können Sie beantwortet und dann in den Artikel übernommen werden:

warum sind überlegungen über die sicherheit von md5 wichtig? ich habe gedacht, dass md5 nur den zweck hat, dass man schnell überprüfen kann, ob eine datei/information, die man erhalten hat, diesselbe ist, wie sie ursprünglich erstellt wurde. das macht das suchen von derselben datei auf mehreren clienten, z.b. bei Edonkey erst möglich.

aus der bekanntgabe von md5 kann ich doch nichts über den inhalt der datei sagen. warum sind dann sicherheitsbedenken bei md5 wichtig?

außerdem: kann es nicht sein, dass zwei total unterschiedliche dateien ein und denselben hash-wert liefern? wie groß ist diese wahrscheinlichkeit? dann könnte es ja z.b. sein, dass beim parallelen downloaden über verteilte netzwerke, z.b. edonkey, auf meinem rechner versehentlich zwei (oder mehr) total unterschiedliche dateien in eine gedownloadete "datei" reingequetsccht werden. diese datei wäre dann datenmüll. ist ein solcher fehler wahrscheinlich?

danke, --Abdull 15:46, 22. Dez 2004 (CET)

Bei einer kryptografischen Hashfunktion wie MD5 geht es darum, möglichst wirkungsvoll zu verhindern, dass eine böswillige Person eine Datei erstellen kann, die den gleichen Hashwert wie eine gegebene Datei hat. Mit einer nicht-kryptografischen Funktion wie zum Beispiel CRC ist es sehr einfach, zum Beispiel zu einem in elektronischer Form vorliegenden Vertragstext ein Dokument zu erfinden, in dem genau das Gegenteil steht. Welchem Dokument soll man dann glauen? Weiterhin werden zum Beispiel Sicherheitszertifikate gerne mit Hashes abgesichert. Wenn die Hashfunktion einfach brechbar ist, kann sich ein Angreifer zum Beispiel für jemand anderen ausgeben. Es geht bei kryptografischen Hashfunktionen also immer darum, dass mit dem Hashwert bewiesen werden muss, dass irgendeine Datei "echt" ist. Dazu muss die Hashfunktion "sicher" sein, was bei MD5 inzwischen nicht mehr der Fall ist. Zu Deiner zweiten Frage: Dass zwei Dateien den gleichen Hashwert haben, ist bei 2¹²⁸ theoretisch möglichen Hashwerten unheimlich unwahrscheinlich. Es sei denn, die Hashfunktion ist nicht sicher und es gelingt, eine Datei so zu "trimmen", dass sie den gleichen Hashwert hat. Bei großen Dateien ist das mit MD5 heute noch immer unmöglich. Die Chinesen haben bei ihren MD5-Brechversuchen IMHO mit 1024-Byte-"Dateien" gearbeitet, in denen dann ein paar wenige Bits differierten. Jetzt bleibt mir noch zu sagen, dass ich kein Kryptograf bin... --Echoray 17:35, 22. Dez 2004 (CET)

http://www.cits.rub.de/MD5Collisions/ <-- zieh dir das rein, da sind 2 pseduo erstellte dokumente mit unterschiedlichen inhalt aber gleicher md5 sum --CHRiSNEW 14:30, 13. Jan 2006 (CET)

RainbowCrack

Für den Fall, dass nicht alle hier das Portal:Mathematik verfolgen: jemand hat einen Link auf eine Software namens RainbowCrack dort abgeladen. Möchte sich das jemand mal ansehen?--Gunther 15:44, 2. Apr 2005 (CEST)

Die Software hat IMHO dort nichts zu suchen. --Qbi 17:19, 4. Apr 2005 (CEST)

Toter Link

Hallo Leute der unterste Link --> http://www.dseitz.de/md5 ist anscheinend tot. lg Tommy

Aufbau von md5 Dateien

Gibt es schon Regeln darüber, wie md5 Dateien aufzubauen sind, in denen dann die md5 Hashes stehen?

Was für Regeln meinst du? In einer .md5 steht in der Regel einfach die MD5-Summe der Ursprungsdatei. Aber man kann dort auch anderes reinschreiben. --Qbi 15:22, 17. Jun 2005 (CEST)

Frage:

Warum ergibt: echo "Frank jagt im komplett verwahrlosten Taxi quer durch Bayern" | md5sum

f98f6704a03727a9585e1ca62bc878e9

Was mache ich falsch ? Bei anderen md5 prüfungen klappt es prima (PHP,perl,online Prüfsummenberechner) --80.134.251.178 09:11, 8. Mai 2006 (CEST)

echo -n "..." --Gunther 09:22, 8. Mai 2006 (CEST)

MD5-Cracker

Eine IP hat gerade einen Link auf einen "MD5-Cracker" eingesetzt. Wie soll denn sowas funktionieren? Es wird doch eine beliebig große Menge von beliebig großen Texten auf einen 128-Bit-Wert abgebildet. Damit ist eine Rückrechnung IMHO komplett ausgeschlossen. Es ist halt doch ein Hash und keine Verschlüsselung... --Eike 12:06, 21. Mai 2006 (CEST)

die üblichen webangebote arbeiten mit einer datenbank, die millionen bis milliarden hashes errechnet und speichert. zum thema cracken empfehle ich http://openwall.com/john Thomas Springer 19:23, 21. Mai 2006 (CEST)

Nett, aber kann für lange Wörter oder gar Sätze unmöglich funktionieren - jedenfalls nicht zuverlässig, höchstens zufällig. --Eike 22:59, 21. Mai 2006 (CEST)

Sicherheit und Einsatzzweck

Sicherheitsaussagen machen i.d.R. nur dann Sinn, wenn die Anwendung dazu genannt wird. Der MD5-Crack geschieht auf zwei hintereinander liegenden Eingabesequenzen, spielt sich also auf 1024 Bit der Nachricht ab. Bezogen auf unterschiedliche Anwendungen lässt das folgende Schlüsse zu:

a) normale Texte: was vorher normales ASCII-Geschehen war, ist nach Erzeugen einer Kollision binäres Durcheinander. Das sollte eigentlich auffallen.

b) Formatierte Texte (Word, usw.): hier bestünde die Möglichkeit, im oft vorhandenen Datenüberhang (nicht von Nutzdaten beaufschlagter Dateibereich) einen Block gegen einen Kollisionsblock auszutauschen. Allerdings sind das nur 1024 Bit an nicht dargestellter Information, von denen <=512 nutzbar wären. Theoretisch ergibt sich daraus allenfalls die Möglichkeit, geheime Informationen in signierten Dokumenten in kleinen Paketen zu exportieren.

c) Programme: in einem signierten selbstauspackenden Programm könnte eine Weiche gestellt werden. Beispiel: Shareware-Programm mit der Aufforderung "zahle 20 Euro an Hersteller" und "zahle 50 Euro an Cracker". Normalerweise wird Meldung 1 gedruckt. Der Cracker (= Hersteller des Packerprogramms) lädt die Shareware herunter, tauscht den Kollisionsblock aus und bietet den Download auf seiner Seite an. Nun wird Meldung 2 ausgedruckt. Der Cracker gewinnt 30 Euro (20 zahlt er an den Sharewarehersteller für die Lizenznummer, die er weitergibt).

d) Zertifikate: da hier Binärkode drinsteht, kann unerkannt ein Kollisionsblock ausgetauscht werden. Allerdings: Bei RSA-Parametern kann der öffentliche Schlüssel ausgetauscht werden, was aber nichts nützt, da der dazu passende Geheimschlüssel vom Cracker nicht erzeugt werden kann, oder das Modul, was aber voraussichtlich auch wenig nützt, da die Faktorisierung für einen weiteren Betrug bekannt sein muss, die Kollision aber in weiten Teilen Zufallscharakter aufweist, was dem entgegensteht. Bei gleichzeitigem Austausch von Modul und Schlüssel wird mit hoher Wahrscheinlichkeit die ASN.1-Struktur beschädigt, der komplette Datensatz also ungültig. Bei DH-Parametern läuft ein Austausch auf das Problem hinaus, den diskreten Logarithmus lösen zu müssen, was dem Cracker auch nicht gelingt. Aller Voraussicht nach kann ein Angriff auf Zertifikate nur DoS (Denial of Service) zur Folge haben, nicht aber ein gefälschtes nutzbares Zertifikat (d.h. eine Signatur kann nicht verifiziert werden, eine verschlüsselte Nachricht kann nicht entschlüsselt werden, der Cracker gelangt aber nicht in Besitz vertraulicher Informationen oder kann Sigaturen fälschen).

e) MAC (Message Authentication Code): nicht nutzbar, da Geheimschlüssel unbekannt.

Weitere Hinweise auf meiner Seite

Unlogisch?

"MD5 ist ein Vertreter aus einer Reihe von Hash-Funktionen, die von Professor Ronald L. Rivest am Massachusetts Institute of Technology entwickelt wurden. Als Analysen ergaben, dass der Vorgänger MD4 wahrscheinlich unsicher ist, wurde MD5 1991 als sicherer Ersatz entwickelt."

Dieser Satz ist finde ich ein wenig unlogisch - der Vorgänger (von MD5?!) MD4 ist unsicherer und deshalb wurde MD5 entwickelt? - Ist da eventuell von MD3 oder so die Rede?

Abschnitt Sicherheitsüberlegungen / Unterpunkt Die Analyse-Methode

Die Überschriften haben mich etwas stutzig gemacht. Eventuell sollte "Sicherheitsüberlegungen" noch irgendwie mit "Angriffsmöglichkeiten" oder "Angiffsmethoden" in Verbindung gebracht werden, um einen besseren Zusammenhang zu den Unterpunkten herzustellen oder ein komplett neuer treffenderer Begriff für die Absatzüberschrift gesucht werden.

Ebenfalls sollte am Anfang des Abschnitts mit einem (einzigen) Satz deutlich gemacht werden was genau "kryptografisch (un)sicher" bedeutet oder ein Artikel der das klärt dazu verlinkt werden.

Außerdem hat mich folgender Satz irretiert: "Kollisionen finden heißt, man kennt ein M (Text) und sucht ein M' (Kollision), so dass hash(M) = hash(M') (dies wäre eine Fälschung)." Handelt es sich bei dieser Formulierung nicht schon um einen einen Preimage-Angriff und nicht nur um einen Kollisionsangriff? Die genaue Abgrenzung der beiden Angriffen scheint schwierig zu sein. Soweit ich das Verstanden habe hat das chinesische Wissenschaftlerteam keine Preimage-Angriffe durchgeführt.

Ohne Extrasoftware unter XP?

Muss man sich zur Prüfung von md5sum eine Extrasoftware laden oder geht das bei Windows XP mit Bordmitteln? --134.155.99.41 11:09, 17. Apr. 2007 (CEST)

Lies den Artikel nochmal, dann weist du's ;-) Ok, XP bring sowas nicht mit 23:09, 28. Apr. 2007 (CEST)

Pseudocode

Folgender Pseudocode, welcher vormals in den Artikel eingebunden war, beschreibt SHA-1 und nicht MD5 (Initialisierungswerte habe ich jetzt schon ausgebessert). Aber K(i) kommt sicherlich nicht vor in MD5. Siehe RFC1321MD5

Pseudocode

Es folgt der Pseudocode für den MD5-Algorithmus.

// Beachte: Alle Variablen sind vorzeichenlose 32 Bit-Werte und
// verhalten sich bei Berechnungen kongruent (≡) modulo 2^32

// Definiere r wie folgt:
var int[64] r, k
r[ 0..15] := {7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22}
r[16..31] := {5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20}
r[32..47] := {4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23}
r[48..63] := {6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21}

// Verwende den binären Vorkommateil vom 2^32-fachen Betrag des Sinus
// von Integerwerten als Konstanten:
für alle i von 0 bis 63
    k[i] := floor(abs(sin(i + 1)) × 2^32)

// Initialisiere die Variablen:
var int h0 := 0x01234567
var int h1 := 0x89ABCDEF
var int h2 := 0xFEDCBA98
var int h3 := 0x76543210

// Vorbereitung der Nachricht 'message':
var int message_laenge := bit_length(message)
erweitere message um bit "1"
erweitere message um bits "0" bis Länge von message in bits ≡ 448 (mod 512)
erweitere message um message_laenge als 64-Bit little-endian Integer

// Verarbeite die Nachricht in aufeinander folgenden 512-Bit Blöcken:
für alle 512-Bit Block von message
    unterteile Block in 16 32-bit little-endian Worte w(i), 0 ≤ i ≤ 15

    // Initialisiere den Hash-Wert für diesen Block:
    var int a := h0
    var int b := h1
    var int c := h2
    var int d := h3

    // Hauptschleife:
    für alle i von 0 bis 63
        wenn 0 ≤ i ≤ 15 dann
            f := (b and c) or ((not b) and d)
            g := i
        sonst wenn 16 ≤ i ≤ 31 dann
            f := (d and b) or ((not d) and c)
            g := (5×i + 1) mod 16
        sonst wenn 32 ≤ i ≤ 47 dann
            f := b xor c xor d
            g := (3×i + 5) mod 16
        sonst wenn 48 ≤ i ≤ 63 dann
            f := c xor (b or (not d))
            g := (7×i) mod 16
        wenn_ende
 
        temp := d
        d := c
        c := b
        b := ((a + f + k(i) + w(g)) leftrotate r(i)) + b
        a := temp

    // Addiere den Hash-Wert des Blocks zur Summe der vorherigen Hashes:
    h0 := h0 + a
    h1 := h1 + b 
    h2 := h2 + c
    h3 := h3 + d

var int digest := h0 append h1 append h2 append h3 //(Darstellung als little-endian)

Beachte: Anstatt der Original-Formulierung aus dem RFC 1321 kann zur Effizienzsteigerung Folgendes verwendet werden:

(0  ≤ i ≤ 15): f := d xor (b and (c xor d))
(16 ≤ i ≤ 31): f := c xor (d and (b xor c))

Wie überprüfe ich die MD5-Summe?

Hallo!

Ich bin ein Computerlaie, habe also Probleme so einfach mal schnell eine Überprüfung der MD5-Checksumme vorzunehmen. Wie muss ich verfahren um die Prüfung durchzuführen? Welche Programme benötige ich dafür?

Ich habe die Datei (ISO-Image, 314 MB groß) und die MD5-Checksumme.

Ich finde, diese Fragen sind durchaus für die Mehrzahl der Leser interessant, da insbesondere Laien mit Kryptografie und Hash-Werten Schwierigkeiten bei der Anwendung haben. Ich finde, dass in einen Wiki-Artikel auch beschrieben werden sollte, wie die MD5-Prüfung vorzunehmen ist.

Wer kann dies in den Wiki-Artikel einfügen?