MD5

MD5
Allmän
Designers	Ronald Rivest
Först publicerad	april 1992
Serier	MD2 , MD4 , MD5, MD6
Chifferdetalj
Digest storlekar	128 bitar
Blockstorlekar	512 bitar
Strukturera	Merkle–Damgård byggande
Omgångar	4
Bästa offentliga kryptoanalys
	En attack 2013 av Xie Tao, Fanbao Liu och Dengguo Feng bryter MD5- kollisionsmotståndet på 2 18 gånger. Denna attack körs på mindre än en sekund på en vanlig dator. MD5 är benägen för längdextensionsattacker .

MD5 -meddelandesammandragningsalgoritmen är en allmänt använd hashfunktion som producerar ett 128- bitars hashvärde. MD5 designades av Ronald Rivest 1991 för att ersätta en tidigare hashfunktion MD4 och specificerades 1992 som RFC 1321.

MD5 kan användas som en kontrollsumma för att verifiera dataintegriteten mot oavsiktlig korruption. Historiskt sett användes det ofta som en kryptografisk hashfunktion ; men det har visat sig lida av omfattande sårbarheter. Den förblir lämplig för andra icke-kryptografiska ändamål, till exempel för att bestämma partitionen för en viss nyckel i en partitionerad databas , och kan föredras på grund av lägre beräkningskrav än nyare Secure Hash Algorithms .

Historia och kryptoanalys

MD5 är en i en serie meddelandesammandragningsalgoritmer designade av professor Ronald Rivest vid MIT (Rivest, 1992). När analytiskt arbete indikerade att MD5:s föregångare MD4 sannolikt var osäker, designade Rivest MD5 1991 som en säker ersättare. ( Hans Dobbertin hittade faktiskt senare svagheter i MD4.)

1993 gav Den Boer och Bosselaers ett tidigt, om än begränsat, resultat av att hitta en " pseudo-kollision " av MD5- kompressionsfunktionen ; det vill säga två olika initialiseringsvektorer som producerar en identisk sammanfattning.

1996 meddelade Dobbertin en kollision av kompressionsfunktionen hos MD5 (Dobbertin, 1996). Även om detta inte var en attack på den fullständiga MD5-hashfunktionen, var den tillräckligt nära för att kryptografer skulle rekommendera att byta till en ersättning, som SHA-1 (också äventyrad) eller RIPEMD-160 .

Storleken på hashvärdet (128 bitar) är tillräckligt liten för att överväga en födelsedagsattack . MD5CRK var ett distribuerat projekt som startade i mars 2004 för att visa att MD5 är praktiskt taget osäker genom att hitta en kollision med en födelsedagsattack.

MD5CRK upphörde kort efter 17 augusti 2004, när kollisioner för hela MD5 tillkännagavs av Xiaoyun Wang , Dengguo Feng, Xuejia Lai och Hongbo Yu. Deras analytiska attack rapporterades ta bara en timme på ett IBM p690- kluster.

Den 1 mars 2005 demonstrerade Arjen Lenstra , Xiaoyun Wang och Benne de Weger konstruktion av två X.509 -certifikat med olika publika nycklar och samma MD5-hashvärde, en bevisligen praktisk kollision. Konstruktionen innehöll privata nycklar till båda publika nycklar. Några dagar senare beskrev Vlastimil Klima en förbättrad algoritm som kunde konstruera MD5-kollisioner på några timmar på en enda bärbar dator. Den 18 mars 2006 publicerade Klima en algoritm som kunde hitta en kollision inom en minut på en enda bärbar dator, med en metod som han kallar tunnling.

Olika MD5-relaterade RFC-fel har publicerats. Under 2009 USA:s cyberkommando ett MD5-hashvärde för deras uppdragsbeskrivning som en del av deras officiella emblem.

Den 24 december 2010 tillkännagav Tao Xie och Dengguo Feng den första publicerade enkelblocks (512-bitars) MD5-kollisionen. (Tidigare upptäckter av kollisioner hade förlitat sig på flerblocksattacker.) Av "säkerhetsskäl" avslöjade inte Xie och Feng den nya attackmetoden. De utfärdade en utmaning till det kryptografiska samhället och erbjöd en belöning på 10 000 USD till den första som hittade en annan 64-byte-kollision före den 1 januari 2013. Marc Stevens svarade på utmaningen och publicerade kolliderande meddelanden med ett block, såväl som konstruktionsalgoritmen och källor.

Under 2011 godkändes en informativ RFC 6151 för att uppdatera säkerhetsaspekterna i MD5 och HMAC-MD5.

säkerhet

Ett grundläggande krav för alla kryptografiska hashfunktioner är att det ska vara beräkningsmässigt omöjligt att hitta två distinkta meddelanden som hash till samma värde. MD5 misslyckas med detta krav katastrofalt; sådana kollisioner kan hittas på några sekunder på en vanlig hemdator. Den 31 december 2008 CMU Software Engineering Institute slutsatsen att MD5 i huvudsak var "kryptografiskt trasig och olämplig för vidare användning". Svagheterna hos MD5 har utnyttjats på fältet, mest ökända av skadlig programvara Flame 2012. Från och med 2019 fortsätter MD5 att användas i stor utsträckning, trots dess väldokumenterade svagheter och avskrivningar av säkerhetsexperter.

Säkerheten för MD5-hashfunktionen är allvarligt äventyrad. Det finns en kollisionsattack som kan hitta kollisioner inom några sekunder på en dator med en 2,6 GHz Pentium 4-processor (komplexitet 2 ^24,1 ). Vidare finns det också en kollisionsattack med valt prefix som kan producera en kollision för två ingångar med specificerade prefix inom några sekunder, med användning av hårdvara från hyllan (komplexitet 2 ³⁹ ). Möjligheten att hitta kollisioner har fått stor hjälp av användningen av vanliga GPU :er . På en NVIDIA GeForce 8400GS grafikprocessor kan 16–18 miljoner hash per sekund beräknas. En NVIDIA GeForce 8800 Ultra kan beräkna mer än 200 miljoner hash per sekund.

Dessa hash- och kollisionsattacker har visats i allmänheten i olika situationer, inklusive kolliderande dokumentfiler och digitala certifikat . Från och med 2015 visades det att MD5 fortfarande används ganska flitigt, framför allt av säkerhetsforsknings- och antivirusföretag.

Från och med 2019 rapporterades en fjärdedel av de allmänt använda innehållshanteringssystemen fortfarande använda MD5 för lösenordshasning .

Översikt över säkerhetsfrågor

1996 upptäcktes ett fel i designen av MD5. Även om det inte ansågs vara en dödlig svaghet vid den tiden, började kryptografer att rekommendera användningen av andra algoritmer, såsom SHA-1, som sedan dess har visat sig vara sårbart också. 2004 visades det att MD5 inte är kollisionsbeständig . Som sådan är MD5 inte lämplig för applikationer som SSL -certifikat eller digitala signaturer som förlitar sig på den här egenskapen för digital säkerhet. Forskare upptäckte dessutom mer allvarliga brister i MD5 och beskrev en möjlig kollisionsattack - en metod för att skapa ett par ingångar för vilka MD5 producerar identiska kontrollsummor . Ytterligare framsteg gjordes för att bryta MD5 2005, 2006 och 2007. I december 2008 använde en grupp forskare denna teknik för att falska SSL-certifikatets giltighet.

Från och med 2010 anser CMU Software Engineering Institute MD5 som "kryptografiskt trasig och olämplig för vidare användning", och de flesta amerikanska regeringsapplikationer kräver nu SHA-2- familjen av hashfunktioner. 2012 Flame -skadlig programvara svagheterna i MD5 för att förfalska en digital signatur från Microsoft .

Kollisionssårbarheter

1996 hittades kollisioner i MD5:s kompressionsfunktion, och Hans Dobbertin skrev i RSA Laboratories tekniska nyhetsbrev, "Den presenterade attacken hotar ännu inte praktiska tillämpningar av MD5, men den kommer ganska nära ... i framtiden bör MD5 inte längre implementeras ... där en kollisionssäker hash-funktion krävs."

År 2005 kunde forskare skapa par av PostScript -dokument och X.509 -certifikat med samma hash. Senare samma år skrev MD5:s designer Ron Rivest att "md5 och sha1 är båda tydligt trasiga (när det gäller kollisionsmotstånd)".

Den 30 december 2008 tillkännagav en grupp forskare vid den 25:e Chaos Communication Congress hur de hade använt MD5-kollisioner för att skapa ett mellanliggande certifikat från certifikatutfärdare som verkade vara legitimt när det kontrollerades av dess MD5-hash. Forskarna använde ett PS3-kluster vid EPFL i Lausanne , Schweiz för att ändra ett normalt SSL-certifikat utfärdat av RapidSSL till ett fungerande CA-certifikat för den utfärdaren, som sedan kunde användas för att skapa andra certifikat som verkar vara legitima och utfärdade av RapidSSL . VeriSign , utfärdarna av RapidSSL-certifikat, sa att de slutade utfärda nya certifikat med MD5 som sin kontrollsummaalgoritm för RapidSSL när sårbarheten tillkännagavs. Även om Verisign avböjde att återkalla befintliga certifikat signerade med MD5, ansågs deras svar vara adekvat av författarna till exploateringen ( Alexander Sotirov , Marc Stevens , Jacob Appelbaum , Arjen Lenstra , David Molnar, Dag Arne Osvik och Benne de Weger). Bruce Schneier skrev om attacken att "vi visste redan att MD5 är en trasig hashfunktion" och att "ingen borde använda MD5 längre". SSL-forskarna skrev, "Vår önskade effekt är att certifikatutfärdare kommer att sluta använda MD5 för att utfärda nya certifikat. Vi hoppas också att användningen av MD5 i andra applikationer också kommer att omprövas."

Under 2012, enligt Microsoft , använde författarna till Flame malware en MD5-kollision för att förfalska ett Windows-kodsigneringscertifikat.

MD5 använder Merkle–Damgård-konstruktionen , så om två prefix med samma hash kan konstrueras, kan ett gemensamt suffix läggas till båda för att göra kollisionen mer sannolikt att accepteras som giltig data av applikationen som använder den. Dessutom tillåter nuvarande kollisionssökningstekniker att specificera ett godtyckligt prefix : en angripare kan skapa två kolliderande filer som båda börjar med samma innehåll. Allt som angriparen behöver för att generera två kolliderande filer är en mallfil med ett 128-byte datablock, inriktat på en 64-byte gräns, som kan ändras fritt av kollisionssökningsalgoritmen. Ett exempel på MD5-kollision, där de två meddelandena skiljer sig åt i 6 bitar, är:

 d131dd02c5e6eec4 693d9a0698aff95c 2fcab5  8  712467eab 4004583eb8fb7f89 55ad340609f4b302 83e4888325  7  1415a 085125e8f7cdc99f d91dbd  f  280373c5b d8823e3156348f5b ae6dacd436c919c6 dd53e2  b  487da03fd 02396306d248cda0 e99f33420f577ee8 ce54b67080  a  80d1e c69821bcb6a88393 96f965  2  b6ff72a70

0 d131dd02c5e6eec4 693d9a0698aff95c 2fcab5  712467eab 4004583eb8fb7f89 55ad340609f4b302 83e4888325  f  1415a 085125e8f7cdc99f d91dbd  7  280373c5b d8823e3156348f5b ae6dacd436c919c6 dd53e2  3  487da03fd 02396306d248cda0 e99f33420f577ee8 ce54b67080  2  80d1e c69821bcb6a88393 96f965  a  b6ff72a70

Båda producerar MD5-hash 79054025255fb1a26e4bc422aef54eb4 . Skillnaden mellan de två samplen är att den främre biten i varje nibble har vänts. Till exempel är den 20:e byten (offset 0x13) i toppexemplet, 0x87, 10000111 binärt. Den ledande biten i byten (även den ledande biten i den första biten) vänds för att göra 00000111, vilket är 0x07, som visas i det nedre samplet.

Senare visade det sig också vara möjligt att konstruera kollisioner mellan två filer med separat valda prefix. Denna teknik användes vid skapandet av det oseriösa CA-certifikatet 2008. En ny variant av parallelliserad kollisionssökning med MPI föreslogs av Anton Kuznetsov 2014, vilket gjorde det möjligt att hitta en kollision på 11 timmar i ett datorkluster.

Preimage sårbarhet

I april 2009 publicerades en attack mot MD5 som bryter MD5:s förbildsmotstånd . Denna attack är endast teoretisk, med en beräkningskomplexitet på 2 ^123,4 för full förbild.

Ansökningar

MD5-sammandrag har använts i stor utsträckning i mjukvaruvärlden för att ge viss garanti för att en överförd fil har anlänt intakt. Till exempel tillhandahåller filservrar ofta en förberäknad MD5- kontrollsumma (känd som md5sum ) för filerna, så att en användare kan jämföra kontrollsumman för den nedladdade filen med den. De flesta unix-baserade operativsystem inkluderar MD5 sum-verktyg i sina distributionspaket; Windows-användare kan använda den medföljande PowerShell- funktionen "Get-FileHash", installera ett Microsoft-verktyg eller använda tredjepartsprogram. Android ROM använder också denna typ av kontrollsumma.

Diagram showing use of MD5 hashing in file transmission

Eftersom det är lätt att generera MD5-kollisioner är det möjligt för personen som skapade filen att skapa en andra fil med samma kontrollsumma, så denna teknik kan inte skydda mot vissa former av skadlig manipulation. I vissa fall går det inte att lita på kontrollsumman (till exempel om den erhölls över samma kanal som den nedladdade filen), i vilket fall MD5 bara kan tillhandahålla felkontrollfunktioner: den kommer att känna igen en korrupt eller ofullständig nedladdning, vilket blir mer sannolikt när du laddar ner större filer.

Historiskt har MD5 använts för att lagra en enkelriktad hash av ett lösenord , ofta med nyckelsträckning . NIST inkluderar inte MD5 i sin lista över rekommenderade hash för lösenordslagring.

MD5 används också inom området elektronisk upptäckt , för att tillhandahålla en unik identifierare för varje dokument som utbyts under den juridiska upptäcktsprocessen. Denna metod kan användas för att ersätta Bates stämpelnumreringssystem som har använts i decennier under utbytet av pappersdokument. Som ovan bör denna användning avskräckas på grund av det lätta med kollisionsattacker.

Algoritm

Figur 1. En MD5-operation. MD5 består av 64 av dessa operationer, grupperade i fyra omgångar om 16 operationer.

F

är en icke-linjär funktion; en funktion används i varje omgång.

Mi .

betecknar ett 32-bitars block av meddelandeingången, och

Ki betecknar

en 32-bitars konstant, olika för varje operation

<<< s

anger en vänsterbitrotation med

s

platser;

s

varierar för varje operation.

\boxplus

betecknar addition modulo 2 ³² .

MD5 bearbetar ett meddelande med variabel längd till en utgång med fast längd på 128 bitar. Inmatningsmeddelandet är uppdelat i bitar av 512-bitars block (sexton 32-bitars ord); meddelandet är utfyllt så att dess längd är delbart med 512. Utfyllnaden fungerar enligt följande: först läggs en enda bit, 1, till i slutet av meddelandet. Detta följs av så många nollor som krävs för att få längden på meddelandet upp till 64 bitar mindre än en multipel av 512. De återstående bitarna fylls upp med 64 bitar som representerar längden på det ursprungliga meddelandet, modulo 2 ⁶⁴ .

Den huvudsakliga MD5-algoritmen arbetar på ett 128-bitars tillstånd, uppdelat i fyra 32-bitars ord, betecknade $A$ , $B$ , $C$ och $D$ . Dessa initieras till vissa fasta konstanter. Huvudalgoritmen använder sedan varje 512-bitars meddelandeblock i sin tur för att modifiera tillståndet. Behandlingen av ett meddelandeblock består av fyra liknande steg, benämnda rundor ; varje omgång består av 16 liknande operationer baserade på en icke-linjär funktion $F$ , modulär addition och vänsterrotation. Figur 1 visar en operation inom en omgång. Det finns fyra möjliga funktioner; en annan används i varje omgång:

{\begin{aligned}F(B,C,D)&=(B\wedge {C}) \vee (\neg {B}\kil {D})\\G(B,C,D)&=(B\kil {D})\vee (C\kil \neg {D})\\H( B,C,D)&=B\oplus C\oplus D\\I(B,C,D)&=C\oplus (B\vee \neg {D})\end{aligned}}

$\oplus ,\wedge ,\vee ,\neg$ betecknar XOR , AND , OR och NOT- operationerna respektive.

Pseudokod

MD5-hash beräknas enligt denna algoritm. Alla värden är i little-endian .

  
 0 

 
 
 
var  //  : Alla variabler är osignerade 32 bitar och wrap modulo 2^32 vid beräkning av  var  int  s[64], K[64]  var  int  i  //  s anger skiftbeloppen per runda  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 }  //  Använd binär heltalsdel av sinusen för heltal (radianer) som konstanter:  för  i  från  till  63  gör  K[i] := floor(2 ³² × abs(sin(i + 1) )))  slut för  //  (Eller använd bara följande förberäknade tabell):  K[ 0.. 3] := { 0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee } K[ 4.. 7] := { 07aaf 08a, 7c 08f 08f 08f 08f 08f 08f 08f, 0x242070db 304613 , 0xfd469501 } K[ 8..11] := { 0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be } K[12..15] := { 0x6b901122,8e 0x49b40821 } K[16..19] := { 0xf61e2562 , 0xc040b340, 0x265e5a51, 0xe9b6c7aa } K[20..23] := { 0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d2f] de6, 0xc33707d6, 0xf4d50d87, 0x455a14ed } K[28..31] := { 0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a } K[32..35] := { 0xfffa3942, 0x8771f681, 0x6d9d6122, 0x6d9d6122, 0x6d9d6122}=6d9d6122} { 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70 } K[40 ..43] := { 0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05 } K[44..47] := { 0xd9d4d039, 0xe6db99e2, 0xe6db99e5, 7cfac} 51] := { 0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039 } K[52..55] := { 0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1 } K[56..59] := { 0x6fa87e4f, 0xfe2ce6e0, 10xfe2ce6e0, 10xa} ..63] := { 0xf7537e82, 0xbd3af235 , 0x2ad7d2bb, 0xeb86d391 }  //  Initiera variabler:  var  int  a0 := 0x67452301  // A  var  int  b0 := 0xefcdab89  // B  var  int  c0 := 0x98badcfe // 0x98badcfe //  03  int  d0 := 0x10325476   // D

// Pre-processing: adding a single 1 bit
append "1" bit to message<    
 // Notice: the input bytes are considered as bit strings,
 //  where the first bit is the most significant bit of the byte.

// Pre-processing: padding with zeros
append "0" bit until message length in bits ≡ 448 (mod 512)

// Notice: the two padding steps above are implemented in a simpler way
 //  in implementations that only work with complete bytes: append 0x80
 //  and pad with 0x00 bytes so that the message length in bytes ≡ 56 (mod 64).

append original length in bits mod 2⁶⁴ to message

// Process the message in successive 512-bit chunks:
for each 512-bit chunk of padded message do
    break chunk into sixteen 32-bit words M[j], 0 ≤ j ≤ 15
    // Initialize hash value for this chunk:
    var int A := a0
    var int B := b0
    var int C := c0
    var int D := d0
    // Main loop:
    for i from 0 to 63 do
        var int F, g
        if 0 ≤ i ≤ 15 then
            F := (B and C) or ((not B) and D)
            g := i
        else if 16 ≤ i ≤ 31 then
            F := (D and B) or ((not D) and C)
            g := (5×i + 1) mod 16
        else if 32 ≤ i ≤ 47 then
            F := B xor C xor D
            g := (3×i + 5) mod 16
        else if 48 ≤ i ≤ 63 then
            F := C xor (B or (not D))
            g := (7×i) mod 16
        // Be wary of the below definitions of a,b,c,d
        F := F + A + K[i] + M[g]  // M[g] must be a 32-bit block
        A := D
        D := C
        C := B
        B := B + leftrotate(F, s[i])
    end for
    // Add this chunk's hash to result so far:
    a0 := a0 + A
    b0 := b0 + B
    c0 := c0 + C
    d0 := d0 + D
end for

var char digest[16] := a0 append b0 append c0 append d0 // (Output is in little-endian)

Istället för formuleringen från den ursprungliga RFC 1321 som visas, kan följande användas för förbättrad effektivitet (användbart om assemblerspråk används – annars kommer kompilatorn i allmänhet att optimera ovanstående kod. Eftersom varje beräkning är beroende av en annan i dessa formuleringar, detta är ofta långsammare än ovanstående metod där nand/och kan parallelliseras):

 ( 0 ≤ i ≤ 15): F := D  xor  (B  och  (C  xeller  D)) (16 ≤ i ≤ 31): F := C  xor  (D  och  (B  xor  C))

MD5-haschar

128-bitars (16-byte) MD5-hashar (även kallade meddelandesammandrag ) representeras vanligtvis som en sekvens av 32 hexadecimala siffror. Följande visar en 43-byte ASCII- ingång och motsvarande MD5-hash:

 MD5("  Den snabba bruna räven hoppar över den lata hunden  ") = 9e107d9d372bb6826bd81d3542a419d6

Även en liten förändring i meddelandet kommer (med överväldigande sannolikhet) att resultera i en mestadels annorlunda hash, på grund av lavineffekten . Till exempel, lägga till en punkt i slutet av meningen:

 MD5("  Den snabba bruna räven hoppar över den lata hunden  .  ") = e4d909c290d0fb1ca068ffaddf22cbd0

Hashen för nolllängdssträngen är:

MD5("") = d41d8cd98f00b204e9800998ecf8427e

MD5-algoritmen är specificerad för meddelanden som består av valfritt antal bitar; den är inte begränsad till multiplar av åtta bitar ( oktetter , byte ). Vissa MD5-implementationer som md5sum kan vara begränsade till oktetter, eller så kanske de inte stöder streaming av meddelanden med en initialt obestämd längd.

Genomföranden

Nedan är en lista över kryptografibibliotek som stöder MD5:

Se även

Vidare läsning

Berson, Thomas A. (1992). "Differential Cryptanalysis Mod 2 ³² med applikationer till MD5". EUROCRYPT . s. 71–80. ISBN 3-540-56413-6 .
Bert den Boer; Antoon Bosselaers (1993). "Kollisioner för kompressionsfunktionen för MD5". Framsteg inom kryptologi — EUROCRYPT '93 . EUROCRYPT. Berlin; London: Springer. s. 293–304. ISBN 978-3-540-57600-6 .
Hans Dobbertin, Krypteringsanalys av MD5-kompress. Tillkännagivande på Internet, maj 1996. "CiteSeerX" . Citeseer.ist.psu.edu . Hämtad 9 augusti 2010 .
Dobbertin, Hans (1996). "Status för MD5 efter en nyligen attack" . CryptoBytes . 2 (2).
Xiaoyun Wang; Hongbo Yu (2005). "Hur man bryter MD5 och andra hashfunktioner" (PDF) . EUROCRYPT . ISBN 3-540-25910-4 . Arkiverad från originalet (PDF) den 21 maj 2009 . Hämtad 6 mars 2008 .

externa länkar