Message-Digest-algoritme 5
Message-Digest Algorithm 5 ( MD5 ) is een veelgebruikte cryptografische hashfunctie die een 128-bits hashwaarde van elk bericht genereert. Hierdoor kan bijvoorbeeld een download eenvoudig op juistheid worden gecontroleerd. Het is een van een reeks cryptografische hashfuncties die in 1991 zijn ontwikkeld door Ronald L. Rivest van het Massachusetts Institute of Technology , toen uit analyse bleek dat zijn voorganger, MD4, waarschijnlijk onveilig is. Ondertussen wordt MD5 ook niet meer als veilig beschouwd, aangezien het mogelijk is om met een redelijke inspanning verschillende berichten te genereren die dezelfde MD5-hashwaarde hebben.
MD5-hashes
De 128-bit lange MD5-hashes (ook bekend als "message digests") worden meestal genoteerd als 32-cijferige hexadecimale getallen. Het volgende voorbeeld toont een 59 bytes lange ASCII- invoer en de bijbehorende MD5-hash:
md5("Franz jagt im komplett verwahrlosten Taxi quer durch Bayern") =
a3cca2b2aa1e3b5b3b5aad99a8529074
Een kleine verandering in de tekst zorgt voor een heel andere hash. Bijvoorbeeld met Frank in plaats van Franz (slechts één letter gewijzigd):
md5("Frank jagt im komplett verwahrlosten Taxi quer durch Bayern") =
7e716d0e702df0505fc72e2b89467910
De hash van een string met een lengte van nul is:
md5("") = d41d8cd98f00b204e9800998ecf8427e
Gebruik en beschikbaarheid
De meeste Linux- distributies installeren het md5sum-programma standaard als onderdeel van de coreutils .
De opdracht md5 is beschikbaar op van BSD afgeleide besturingssystemen zoals macOS .
Op veel andere Unix- derivaten kun je het doen met het meestal geïnstalleerde programma OpenSSL .
Microsoft Windows- besturingssystemen vanaf versie Windows 8.1 of Windows Server 2012 R2 hebben standaard de PowerShell- cmdlet Get-Filehash.
De MD5-hashwaarde controleren
Nadat een bestand of een map met bestanden succesvol is gedownload, wordt de bijbehorende MD5-hashwaarde vaak in een ander bestand beschikbaar gesteld. De hash-waarde kan dan op zijn beurt via een testprogramma uit het gedownloade bestand worden berekend, dat vervolgens wordt vergeleken met de beschikbaar gestelde hash-waarde. Als beide hash-waarden identiek zijn, wordt de integriteit van het gedownloade bestand bevestigd. Dienovereenkomstig waren er geen fouten bij het downloaden van het bestand. Dit biedt geen enkele zekerheid met betrekking tot gerichte gegevensmanipulatie door een aanvaller ( man-in-the-middle-aanval ), aangezien de aanvaller ook de overdracht van de MD5-hashwaarde kan manipuleren.
De situatie is iets anders bij het gebruik van een mirror-server om bestanden te downloaden. De operator van de mirror-server is hier een mogelijke aanvaller. Om manipulatie hierdoor uit te sluiten, hoeft de bijbehorende MD5-hashwaarde niet van de mirrorserver te worden geladen, maar van de oorspronkelijke bron.
algoritme
MD5 is gebaseerd op de Merkle-Damgård-constructie om een uitvoer met een vaste lengte (128 bits) te genereren uit een bericht met een variabele lengte. Eerst wordt er een één aan het uitvoerbericht toegevoegd. Het uitvoerbericht wordt vervolgens opgevuld met nullen, zodat de lengte 64 bits verwijderd is van deelbaar door 512. Er wordt nu een 64-bits nummer toegevoegd dat de lengte van het uitvoerbericht codeert. De berichtlengte is nu deelbaar door 512.
Het hoofdalgoritme van MD5 maakt gebruik van een 128-bits buffer die in vier 32-bits woorden A , B , C en D is verdeeld. Deze worden geïnitialiseerd met bepaalde constanten. De compressiefunctie wordt nu op deze buffer aangeroepen met het eerste 512-bits blok als sleutelparameter. Een berichtenblok wordt in vier vergelijkbare fasen afgehandeld, door cryptografen "rondes" genoemd. Elke ronde bestaat uit 16 bewerkingen op basis van een niet-lineaire functie "F", modulaire optelling en rotatie naar links. Er zijn vier mogelijke "F"-functies, in elke ronde wordt een andere gebruikt:
elk staat voor XOR-, AND-, OR- en NOT-bewerkingen.
Dezelfde functie wordt aangeroepen voor het resultaat met het tweede berichtblok als parameter, enzovoort, tot het laatste 512-bits blok. Het resultaat is weer een 128-bits waarde - de MD5-som.
Referentie implementatie
RFC1321 bevat ook een implementatie van het algoritme in C onder de titel "Appendix A Reference Implementation" Deze implementatie uit 1992 door RSA Data Security, Inc. draait op veel 64-bits systemen verkeerd en berekent onjuiste hash-waarden. Dit komt omdat in het global.h- bestand de regels
/* UINT4 defines a four byte word */ typedef unsigned long int UINT4;
worden niet noodzakelijk gegeven. De fout kan worden gecorrigeerd door door deze regels te kijken
#include <inttypes.h> ... /* UINT4 defines a four byte word */ typedef uint32_t UINT4;
vervangen. Een andere uitvoerbare implementatie door L Peter Deutsch is te vinden op Sourceforge.net. Deze implementatie is afgeleid van de specificatie van RFC1321 en niet van de bovengenoemde referentie-implementatie in RFC1321. Daarom zijn er geen verwijzingen naar RSA Data Security, Inc. nodig bij het gebruik van deze implementatie .
Pseudocode
De pseudocode voor het MD5- algoritme volgt .
// 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: (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: // 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
In plaats van de originele formulering uit RFC 1321 kan het volgende worden gebruikt om de efficiëntie te verhogen:
( 0 ≤ i ≤ 15): F := D xor (B and (C xor D)) (16 ≤ i ≤ 31): F := C xor (D and (B xor C))
Aanvallen
Al in 1993 publiceerden Bert de Boer en Antoon Bosselaers een algoritme voor het genereren van pseudocollisions op de compressiefunctie van MD5: twee verschillende initialisatieconstanten resulteren in dezelfde hash-waarde voor hetzelfde bericht.
In 1996 vond Hans Dobbertin een botsing voor twee verschillende berichten. Dit is een echte botsing, d.w.z. twee speciaal voorbereide berichten die verschillen, maar toch dezelfde hash-waarde opleveren. Dobbertin gebruikte echter een gemodificeerde MD5-variant waarin andere initialisatieconstanten (voor A, B, C, D) worden gebruikt. Het was ook niet mogelijk om de inhoud van de conflicterende berichten te specificeren. Praktische aanvallen op MD5 waren niet mogelijk, maar de zwakke punten van MD5 werden duidelijk, zodat cryptologen adviseerden over te stappen op andere hashfuncties.
In 2004 is een Chinese onderzoeksgroep onder leiding van Xiaoyun Wang erin geslaagd om systematisch botsingen te genereren als het begin van het bericht naar wens kan worden gekozen, maar beide berichten zijn identiek (common-prefix collision) . Aan dit begin van het bericht kunnen met redelijke inspanning twee verschillende vervolgen van het bericht worden berekend, die tot dezelfde hash-waarde leiden. Deze botsing blijft behouden, zelfs als hetzelfde achtervoegsel wordt toegevoegd aan beide berichten (elk bestaande uit hetzelfde begin en de ene of de andere voortzetting). Deze aanval is verbeterd door Wang en andere onderzoeksgroepen, zodat een pc nu binnen enkele seconden een MD5-botsing kan berekenen.
De moeite om een collision te vinden is groter als het begin van de twee berichten verschillend is (chosen-prefix collision) . In 2008 slaagde een team onder leiding van Marc Stevens en Alexander Sotirov erin om een dergelijke botsingsaanval uit te voeren om een vervalst CA-certificaat te creëren dat als betrouwbaar wordt erkend. Hiermee waren ze in principe in staat om voor elke URL een SSL- certificaat te vervalsen en zo de beveiligingsmechanismen van HTTPS op het web te omzeilen . Het werk werd voor het eerst gepresenteerd in december 2008 op het 25e Chaos Communication Congress en enkele maanden later gepubliceerd in een wetenschappelijk artikel. Om de botsing te berekenen, gebruikten ze een cluster van 200 Sony PlayStation 3's .
De Windows-malware Flame , die in 2012 werd ontdekt, maakt gebruik van een nepcertificaat voor codeondertekening op basis van een nieuwe en voorheen onbekende variant van een gekozen voorvoegselcollisie voor MD5.
Zelfs met de genoemde methoden kunnen pre-image-aanvallen nog niet binnen een redelijke termijn worden uitgevoerd. Als gevolg hiervan is het nog steeds onmogelijk om achteraf een vervalst document te maken dat overeenkomt met een specifiek certificaat dat met MD5 is gegenereerd . In veel gevallen is het echter mogelijk door middel van botsingsaanvallen twee documenten te creëren die dezelfde MD5-hashwaarde opleveren, vervolgens het eerste, legitieme document te laten ondertekenen en dit vervolgens te vervangen door het tweede, vervalste document. Tegen deze achtergrond is het niet raadzaam om MD5 te blijven gebruiken.
veiligheid
MD5 wordt veel gebruikt en werd oorspronkelijk als cryptografisch veilig beschouwd. Al in 1994 ontdekten Bert den Boer en Antoon Bosselaers pseudo-botsingen in MD5. Fundamenteel werk om echte botsingen te vinden werd ook gedaan door Hans Dobbertin (destijds bij de BSI ), die de succesvolle aanval op MD4 al had ontwikkeld en de gebruikte technieken naar MD5 had overgedragen.
Botsingsweerstand:
In augustus 2004 vond een Chinees team van wetenschappers de eerste botsing in de volledige MD5-functie. Op een IBM P690- cluster duurde hun eerste aanval een uur en op basis daarvan konden binnen maximaal vijf minuten verdere botsingen worden gevonden. Kort nadat het Chinese werk was gepubliceerd, werd MD5CRK stopgezet en probeerde het botsingen te vinden met behulp van brute force-methoden .
Korte beschrijving: Een invoerblok (512 bits) wordt aangepast, waarbij getracht wordt om in de uitvoer een bepaald verschil met het origineel te produceren. Een complexe analyse van het algoritme kan het aantal onbekende bits zodanig verminderen dat dit wiskundig lukt. Dezelfde methoden worden gebruikt in het volgende 512-bits blok om te proberen het verschil op te heffen. De vervalsing vereist daarom een coherent gegevensblok van 1024 bits = 128 bytes, wat het gebruik ervan ernstig beperkt.
Inmiddels zijn de collision-aanvallen zo ver gevorderd dat verder gebruik van MD5, vooral in scenario's waarin de gebruiker de te ondertekenen bestanden niet volledig in handen heeft, moet worden afgewezen. Een test die in 2009 werd uitgevoerd door het computertijdschrift c't met GPGPU, stelt een high-end game-pc, ongeveer een jaar oud, met twee Nvidia GeForce 9800 GX2 (vier grafische processors in totaal ) in staat om een botsing te vinden in iets minder dan 35 minuten .
Eenrichtingsfunctie
Een andere aanvalsmethode wordt weergegeven door regenboogtabellen, deze tabellen bevatten tekenreeksen met de bijbehorende MD5-hashwaarden. De aanvaller doorzoekt deze tabellen op de opgegeven hashwaarde en kan vervolgens geschikte tekenreeksen uitlezen. Deze aanval kan voornamelijk worden gebruikt om wachtwoorden te ontdekken die zijn opgeslagen als MD5-hashes. De regenboogtabellen die hiervoor nodig zijn, zijn echter erg groot en vergen veel rekeninspanning om ze te maken. Daarom is deze aanval over het algemeen alleen mogelijk met korte wachtwoorden. Voor dit geval zijn er vooraf berekende regenboogtabellen waarin in ieder geval de rekeninspanning om de lijst te maken wordt weggelaten. Het gebruik van een salt , d.w.z. een willekeurige, onvoorspelbare waarde die aan de platte tekst wordt toegevoegd, vernietigt echter de effectiviteit van vooraf berekende regenboogtabellen.
Overzicht
Het vinden van botsingen betekent het vinden van twee verschillende teksten Men M'met hash(M) = hash(M'). In het geval van een pre-image-aanval zoekt men naar een gegeven Mof hash(M)een M'zodat hash(M) = hash(M'). Omdat je alleen M'controle hebt, niet ook M, bij een pre-image-aanval , is het veel moeilijker.
Momenteel is MD5 alleen kapot met betrekking tot de botsingsaanvallen.
Voor de veilige opslag van wachtwoorden moeten echter andere algoritmen worden overwogen die speciaal voor dit doel zijn ontwikkeld, b.v. B. bcrypt of PBKDF2 .
Aangezien er geen eerste pre-image-aanval bekend is, zijn in het verleden ondertekende MD5-hashes momenteel (2013) nog steeds veilig.
Zie ook
literatuur
- Hans Dobbertin: Cryptanalyse van MD5-kompres . Aankondiging op internet, mei 1996 (Engels, online )
- Hans Dobbertin: de status van MD5 na een recente aanval . In: CryptoBytes 2 (2), 1996 (Engels)
- Philip Hawkes, Michael Paddon, Gregory G. Rose: mijmeringen over de Wang et al. MD5-botsing . Gedetailleerde analyse van de differentiële aanval op de MD5
- Vlastimil Klima: MD5-botsingen op een notebook vinden met behulp van modificaties voor meerdere berichten . Opnieuw verbeterde aanvalstechniek
web links
- RFC 1321 - Het MD5 Message-Digest-algoritme; R. Rivest, april 1992 (Engels)
- MD5 Collision Demo Twee verschillende programma's met dezelfde MD5-hash en een bibliotheek voor het genereren van andere dergelijke programma's
- papers en demo's tot MD5-botsingen (Engels)
- Jürgen Schmidt: Hash mij, de tweede
- Online generator voor het genereren van MD5-hashes
- Sourceforge.net : RFC1321-gebaseerde (RSA-vrije) MD5-bibliotheek
Individueel bewijs
- ↑ Beschrijving van de Powershell-cmdlet Get-Filehash
- ^ Bert de Boer, Antoon Bosselaers: Botsingen voor de compressiefunctie van MD5 . In: Proceedings of EUROCRYPT '93 Workshop over de theorie en toepassing van cryptografische technieken op Advances in cryptology . Springer-Verlag, New York 1994, ISBN 3-540-57600-2
- ↑ Alexander Sotirov, Marc Stevens, Jacob Appelbaum, Arjen Lenstra, David Molnar, Dag Arne Osvik, Benne de Weger: MD5 wordt tegenwoordig als schadelijk beschouwd. 30 december 2008, geraadpleegd op 30 december 2008 .
- ↑ Marc Stevens: TECHNISCHE ACHTERGROND VAN DE AANVAL VAN DE Vlambotsing. CWI, 7 juni 2012, geraadpleegd op 8 juni 2012 : "de resultaten hebben aangetoond dat niet onze gepubliceerde botsingsaanval met gekozen voorvoegsel werd gebruikt, maar een geheel nieuwe en onbekende variant."
- ↑ Aanvaringsanalyse (PDF; 57 kB)
- ↑ Verklaring van het botsingsprobleem bij het manipuleren van md5-hashwaarden
- ↑ Stefan Arbeiter, Matthias Deeg: Bunte Rechenknechte - grafische kaarten versnellen wachtwoordkrakers . In: c't, editie 06/2009, blz. 204. ( downloadbare vergoeding )
