Message-Digest-algoritme 5

Van Wikipedia, de gratis encyclopedie
Spring naar navigatie Spring naar zoeken

Message-Digest Algorithm 5 ( MD5 ) is een veelgebruiktecryptografische 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 diein 1991 zijn ontwikkeld door Ronald L. Rivest van hetMassachusetts 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 jaagt door Beieren in een volledig verwaarloosde taxi") =
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 ("Fran k jaagt door Beieren in een volledig verwaarloosde taxi") =
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 je redden 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. [1]

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. Er zijn geen fouten opgetreden bij het downloaden van het bestand. Dit biedt geen 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

Een MD5-operatie. MD5 bestaat uit 64 operaties van dit type, gegroepeerd in 4 runs met elk 16 operaties. F is een niet-lineaire functie die in de betreffende run wordt gebruikt. Mi staat voor een 32-bit blok van de invoerstroom en Ki een ander 32-bit constante voor elke bewerking; linker shift s geeft de bit-voor-bit rotatie naar links over s plaatsen aan, waarbij s voor elke bewerking varieert. toevoeging geeft de optelling modulo 2 32 aan .

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 werkt met een 128-bits buffer, die is onderverdeeld in vier 32-bits woorden A , B , C en D. 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 op het resultaat aangeroepen met het tweede berichtblok als parameter enzovoort, tot aan 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 definieert een woord van vier bytes * /
typedef unsigned long int UINT4;

worden niet noodzakelijk gegeven. De fout kan worden gecorrigeerd door door deze regels te kijken

 #include <inttypes.h>
...
/ * UINT4 definieert een woord van vier bytes * /
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.

 // Opmerking: alle variabelen zijn niet-ondertekende 32-bits waarden en
// gedraagt ​​zich congruent in berekeningen (≡) modulo 2 ^ 32
// Definitie van de functie voor rotatie naar links, c is de overgedragen waarde van s [i] - zie hoofdlus
linksom draaien (x, c)
    return (x << c) binair of (x >> (32-c));
// s definieert het aantal geroteerde bits per ronde:
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}
// Gebruik het binaire gehele deel van 2 ^ 32 keer het bedrag van de sinus
// van gehele waarden als constanten:
voor alle i van 0 tot 63
(
    K [i]: = vloer (abs (sin (i + 1)) × 2 ^ 32)
)
// Als alternatief kunt u ook de volgende tabel gebruiken:
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}
// Initialiseer de variabelen: (volgens RFC 1321 )
var uint a0: = 0x67452301
var uint b0: = 0xEFCDAB89
var uint c0: = 0x98BADCFE
var uint d0: = 0x10325476
// voorbereiding van het bericht 'bericht':
var uint message_laenge: = bit_length (bericht)
bericht uitbreiden naar bit "1"
verleng bericht met bits "0" tot de lengte van het bericht in bits  448 (mod 512)
breid bericht uit met message_length als een 64-bits little-endian integer
// Verwerk het bericht in opeenvolgende 512-bits blokken:
Voor elke 512-bit blok bericht
(
    verdeel het blok in 16 32-bit little-endian woorden M [i], 0 ≤ i ≤ 15
// Initialiseer de hash-waarde voor dit blok:
    var uint A: = a0
    var uint B: = b0
    var uint C: = c0
    var uint D: = d0
// hoofdlus:
    // niet- operator komt overeen met iemands complement
    voor alle i van 0 tot 63
    (
        als 0 ≤ ik ≤ 15 dan
            F: = (B en C) of (( niet B) en D)
            g: = ik
        anders als 16 ≤ i ≤ 31 dan
            F: = (B en D) of (C en ( niet D))
            g: = (5 × i + 1) mod 16
        anders als 32 ≤ i ≤ 47 dan
            F: = B x of C x of D
            g: = (3 × i + 5) mod 16
        anders als 48 ≤ i ≤ 63 dan
            F: = C xor (B of ( niet D))
            g: = (7 × i) mod 16
        if_end
temperatuur: = D
        D: = C
        C: = B
        B: = B + rotatie naar links ((A + F + K [i] + M [g]), s [i])
        A: = temp
    )
// Voeg de hash-waarde van het blok toe aan de som van de vorige hashes:
    a0: = a0 + A
    b0: = b0 + B
    c0: = c0 + C
    d0: = d0 + D
)
var uint digest: = append a0 b0 append c0 append d0 // representatie 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 en (C xor D))
(16 ≤ i ≤ 31): F: = C xor (D en (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. [2]

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 slaagde een Chinese onderzoeksgroep onder leiding van Xiaoyun Wang erin om systematisch botsingen te genereren als het begin van het bericht naar believen 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 en betrouwbaar CA-certificaat te creëren. 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. [3] 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. [4]

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 is gegenereerd met MD5. In veel gevallen is het echter mogelijk om via 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. [5] Op een IBM P690- cluster duurde hun eerste aanval een uur, ervan uitgaande dat binnen maximaal vijf minuten verdere botsingen konden 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: [6] Een invoerblok (512 bits) wordt aangepast, waarbij getracht wordt om in de uitvoer een bepaald verschil met het origineel te genereren. Een complexe analyse van het algoritme kan het aantal onbekende bits zodanig verminderen dat dit wiskundig succesvol is. Dezelfde methoden worden gebruikt in het volgende 512-bits blok om te proberen het verschil op te heffen. De vervalsing vereist daarom een ​​coherent datablok van 1024 bits = 128 bytes, wat het gebruik ervan ernstig beperkt.

Intussen zijn de collision-aanvallen zo ver gevorderd dat verder gebruik van MD5, vooral in scenario's waarin de gebruiker niet de volledige controle heeft over de te ondertekenen bestanden, moet worden afgewezen. Een test uitgevoerd door het computertijdschrift c't in 2009 met behulp van 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 . [7]

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 M en M' met hash(M) = hash(M') . Bij een pre-image-aanval zoekt men naar een M' voor een gegeven M of hash(M) , zodat hash(M) = hash(M') . Aangezien je M' alleen bestuurt in een pre-image attack, niet ook M , is dit 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

Individueel bewijs

  1. Beschrijving van de Powershell-cmdlet Get-Filehash
  2. ^ 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
  3. 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 .
  4. 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."
  5. Aanvaringsanalyse (PDF; 57 kB)
  6. Verklaring van het botsingsprobleem bij het manipuleren van md5-hashwaarden
  7. Stefan Arbeiter, Matthias Deeg: Bunte Rechenknechte - grafische kaarten versnellen wachtwoordkrakers . In: c't, editie 06/2009, blz. 204. ( downloadbare vergoeding )