Message-Digest Algorithm 5
topic - Kurzbeschreibung
Beschreibung
Message-Digest Algorithm 5 (MD5) ist eine verbreitete kryptographische Hashfunktion, die aus einer beliebigen Nachricht einen 128-Bit-Hashwert berechnet. Sie wurde 1991 von Ronald L. Rivest am Massachusetts Institute of Technology als Nachfolger von MD4 entwickelt. Der englische Begriff „Message Digest“ steht für einen kurzen Zahlenwert fester Länge, der deterministisch aus der gegebenen Nachricht berechnet wird.
Inzwischen ist bekannt, dass MD5 keine Kollisionsresistenz bietet und somit unsicher ist. Auch die Preimage-Resistenz ist theoretisch gebrochen, allerdings ist ein Preimage-Angriff gegen MD5 nicht praktikabel.
MD5-Hashwert
Die 128 Bit langen MD5-Hashwerte werden üblicherweise als 32-stellige Hexadezimalzahl notiert. Beispiel für eine 59 Byte lange ASCII-Eingabe mit zugehörigem MD5-Hashwert:
md5("Franz jagt im komplett verwahrlosten Taxi quer durch Bayern") =
a3cca2b2aa1e3b5b3b5aad99a8529074
Es ist praktisch unmöglich, eine weitere Nachricht, die genau diesen Hashwert ergibt, zu bestimmen. Eine beliebige Änderung des Textes (im Folgenden wird nur ein Buchstabe verändert) erzeugt aufgrund des Lawineneffekts einen komplett anderen Hashwert:
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
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. In Python ist MD5 in der Programmbibliothek (hashlib) enthalten.
Auf vielen anderen Unix-Derivaten ist Python installiert oder man kann sich mit dem meist installierten Programm OpenSSL behelfen. Python kann auch online aufgerufen werden. Microsoft-Windows-Betriebssysteme ab den Versionen Windows 8.1 bzw. Windows Server 2012 R2 verfügen standardmäßig über das PowerShell Cmdlet Get-Filehash.[1]
Prüfsumme einer Datei
Nach erfolgreichem Download einer oder mehrerer Dateien kann der Anbieter der Daten in einer weiteren Datei den dazugehörigen MD5-Hashwert zur Verfügung stellen. Über ein Prüfprogramm kann 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 Übertragungsfehler auf, was dem Anwendungszweck einer Prüfsumme entspricht. Dies bietet keine Sicherheit hinsichtlich einer gezielten Datenmanipulation durch einen Angreifer (Man-in-the-Middle-Angriff), da der Angreifer neben den übertragenen Daten auch den angebotenen MD5-Hashwert manipulieren kann. Bei Verwendung eines Spiegelservers für den Download stellt beispielsweise der Betreiber des Spiegelservers einen möglichen Angreifer dar. Um eine Manipulation durch diesen auszuschließen, muss entweder der MD5-Hashwert aus einer vertrauenswürdigen Quelle über einen sicheren Kanal bezogen werden, oder die Authentizität der Datei muss durch ein anderes Verfahren sichergestellt werden. Dazu eignet sich eine digitale Signatur oder ein Message Authentication Code, der eine Hashfunktion mit einem schlüsselbasierten, kryptographischen Mechanismus kombiniert.
Zufallsgenerator
Wie jede kryptographische Hashfunktion kann MD5 als deterministischer Generator von Pseudo-Zufallszahlen genutzt werden. Dadurch lässt sich zum Beispiel eine Stromverschlüsselung realisieren.
Pseudocode
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
// Definition der linksrotation Funktion, c ist der übergebene Wert von s[i] - siehe Hauptschleife
linksrotation(x, c)
return (x << c)binär or (x >> (32-c));
// 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: (laut 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: // not Operator entspricht dem Einerkomplement 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))
Anhang
Siehe auch
Links
Weblinks
RFC
RFC-Internet |RFC=1321 |Titel=The MD5 Message-Digest Algorithm |Datum=1992-04 |Autor=R. Rivest