MD5-Hashes[Bearbeiten | Quelltext bearbeiten] Die 128 Bit langen MD5-Hashes (englisch auch „message-digests“) werden normalerweise als 32-stellige Hexadezimalzahl notiert. Folgendes Beispiel zeigt eine 59 Byte lange ASCII-Eingabe und den zugehörigen MD5-Hash: md5("Franz jagt im komplett verwahrlosten Taxi quer durch Bayern") = a3cca2b2aa1e3b5b3b5aad99a8529074 Eine kleine Änderung des Textes erzeugt einen komplett anderen Hash. Beispielsweise ergibt sich mit Frank statt Franz (nur ein Buchstabe verändert): md5("Frank jagt im komplett verwahrlosten Taxi quer durch Bayern") = 7e716d0e702df0505fc72e2b89467910 Der Hash einer Zeichenfolge der Länge null ist: md5("") = d41d8cd98f00b204e9800998ecf8427e Verwendung und Verfügbarkeit[Bearbeiten | Quelltext bearbeiten] Unter den meisten Linux-Distributionen wird das Programm md5sum als Bestandteil der coreutils standardmäßig installiert. Auf BSD-abgeleiteten Betriebssystemen wie macOS gibt es das Kommando md5. Auf vielen anderen Unix-Derivaten kann man sich mit dem meist installierten Programm OpenSSL behelfen. Microsoft-Windows-Betriebssysteme verfügen ab Werk nicht über ein Programm zur Berechnung von MD5-Hashes, Microsoft stellt jedoch das Programm File Checksum Integrity Verifier (FCIV.EXE) kostenlos bereit.[4] Überprüfung des MD5-Hashwerts[Bearbeiten | Quelltext bearbeiten] Nach erfolgreichem Download einer Datei oder eines Ordners mit Dateien wird häufig in einer weiteren Datei der dazugehörige MD5-Hashwert zur Verfügung gestellt. Über ein Prüfprogramm kann dann wiederum der Hashwert aus der heruntergeladenen Datei berechnet werden, der dann mit dem zur Verfügung gestellten Hashwert verglichen wird. Sind beide Hashwerte identisch, ist die Integrität der heruntergeladenen Datei bestätigt. Demnach traten beim Download der Datei keine Fehler auf. Dies bietet keine Sicherheit hinsichtlich einer gezielten Datenmanipulation durch einen Angreifer (Man-in-the-Middle-Angriff), da der Angreifer auch die Übertragung des MD5-Hashwertes manipulieren kann. Algorithmus[Bearbeiten | Quelltext bearbeiten] Eine MD5-Operation. MD5 besteht aus 64 Operationen dieses Typs, gruppiert in 4 Durchläufen mit jeweils 16 Operationen. F ist eine nichtlineare Funktion, die im jeweiligen Durchlauf eingesetzt wird. Mi bezeichnet einen 32-Bit-Block des Eingabestroms und Ki eine für jede Operation unterschiedliche 32-Bit-Konstante; left shifts bezeichnet die bitweise Linksrotation um s Stellen, wobei s für jede Operation variiert. Addition bezeichnet die Addition modulo 232. MD5 basiert auf der Merkle-Damgård Konstruktion um aus einer Nachricht variabler Länge eine Ausgabe fester Länge (128 Bit) zu erzeugen. Zuerst wird eine Eins an die Ausgangsnachricht angehängt. Danach wird die Ausgangsnachricht mit Nullen so aufgefüllt, dass ihre Länge 64 Bits davon entfernt ist durch 512 teilbar zu sein. Nun wird eine 64-Bit-Zahl, die die Länge der Ausgangsnachricht codiert, angehängt. Die Nachrichtenlänge ist jetzt durch 512 teilbar. Der Hauptalgorithmus von MD5 arbeitet mit einem 128-Bit-Puffer, der in vier 32-Bit-Wörter A, B, C und D unterteilt ist. Diese werden mit bestimmten Konstanten initialisiert. Auf diesen Puffer wird nun die Komprimierungsfunktion mit dem ersten 512-Bit-Block als Schlüsselparameter aufgerufen. Die Behandlung eines Nachrichtenblocks geschieht in vier einander ähnlichen Stufen, von Kryptografen „Runden“ genannt. Jede Runde besteht aus 16 Operationen, basierend auf einer nichtlinearen Funktion „F“, modularer Addition und Linksrotation. Es gibt vier mögliche „F“-Funktionen, in jeder Runde wird davon eine andere verwendet: {\displaystyle F(X,Y,Z)=(X\wedge {Y})\vee (\neg {X}\wedge {Z})} F(X,Y,Z) = (X\wedge{Y}) \vee (\neg{X} \wedge{Z}) {\displaystyle G(X,Y,Z)=(X\wedge {Z})\vee (Y\wedge \neg {Z})} G(X,Y,Z) = (X\wedge{Z}) \vee (Y \wedge \neg{Z}) {\displaystyle H(X,Y,Z)=X\oplus Y\oplus Z} H(X,Y,Z) = X \oplus Y \oplus Z {\displaystyle I(X,Y,Z)=Y\oplus (X\vee \neg {Z})} I(X,Y,Z) = Y \oplus (X \vee \neg{Z}) {\displaystyle \oplus ,\wedge ,\vee ,\neg } \oplus, \wedge, \vee, \neg stehen jeweils für XOR, AND, OR und NOT-Operationen. Auf das Ergebnis wird dieselbe Funktion mit dem zweiten Nachrichtenblock als Parameter aufgerufen usw., bis zum letzten 512-Bit-Block. Als Ergebnis wird wiederum ein 128-Bit-Wert geliefert – die MD5-Summe. Referenzimplementation[Bearbeiten | Quelltext bearbeiten] RFC1321 enthält auch unter dem Titel "Appendix A Reference Implementation" eine Implementation des Algorithmus in C. Diese Implementation aus dem Jahre 1992 von RSA Data Security, Inc. läuft aber heute fehlerhaft, sie berechnet falsche Hashwerte. Dies liegt daran, dass in der Datei global.h die Zeilen /* UINT4 defines a four byte word */ typedef unsigned long int UINT4; offensichtlich falsch sind. unsigned long int ist heute kein 4-Byte-Datentyp mehr, sondern ein größerer. Der Fehler kann behoben werden, indem man diese Zeilen durch #include <inttypes.h> ... /* UINT4 defines a four byte word */ typedef uint32_t UINT4; ersetzt. Eine andere, lauffähige Implementation des Algorithmus von L Peter Deutsch findet man auf Sourceforge.net. Diese Implementation ist aus der Spezifikation des RFC1321 abgeleitet und nicht aus der vorher erwähnten Referenzimplementation in RFC1321. Darum sind bei Verwendung dieser Implementation keinerlei Verweise auf RSA Data Security, Inc. notwendig. Pseudocode[Bearbeiten | Quelltext bearbeiten] Es folgt der Pseudocode für den MD5-Algorithmus. // Beachte: Alle Variablen sind vorzeichenlose (unsigned) 32-Bit-Werte und // verhalten sich bei Berechnungen kongruent (≡) modulo 2^32 // s definiert die Anzahl der Bits, die pro Runde rotiert werden: var uint[64] s, K s[ 0..15] := { 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22} s[16..31] := { 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20} s[32..47] := { 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23} s[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) // Alternativ kann man auch folgende Tabelle nutzen: K[ 0.. 3] := { 0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee } K[ 4.. 7] := { 0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501 } K[ 8..11] := { 0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be } K[12..15] := { 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821 } K[16..19] := { 0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa } K[20..23] := { 0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8 } K[24..27] := { 0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed } K[28..31] := { 0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a } K[32..35] := { 0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c } K[36..39] := { 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70 } K[40..43] := { 0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05 } K[44..47] := { 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665 } K[48..51] := { 0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039 } K[52..55] := { 0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1 } K[56..59] := { 0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1 } K[60..63] := { 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391 } // Initialisiere die Variablen: (lt. RFC 1321) var uint a0 := 0x67452301 var uint b0 := 0xEFCDAB89 var uint c0 := 0x98BADCFE var uint d0 := 0x10325476 // Vorbereitung der Nachricht 'message': var uint 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 M[i], 0 ≤ i ≤ 15 // Initialisiere den Hash-Wert für diesen Block: var uint A := a0 var uint B := b0 var uint C := c0 var uint D := d0 // 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 := (B and D) or (C and (not D)) 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 := B + linksrotation((A + F + K[i] + M[g]), s[i]) A := temp // Addiere den Hash-Wert des Blocks zur Summe der vorherigen Hashes: a0 := a0 + A b0 := b0 + B c0 := c0 + C d0 := d0 + D var uint digest := a0 anfügen b0 anfügen c0 anfügen d0 // Darstellung als little-endian Anstatt der Originalformulierung 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)) Sicherheit[Bearbeiten | Quelltext bearbeiten]