MD5

I kryptografi er MD5 (forkortelse for Message-Digest Algorithm 5) en mye brukt 128- bits kryptografisk forkortelsesalgoritme . En av dens bruk er å sjekke at en fil ikke er endret.

Historikk

MD5 er en av de kryptografiske forkortingsalgoritmene designet av professor Ronald Rivest fra MIT ( Massachusetts Institute of Technology ). Den ble utviklet i 1991 som en erstatning for MD4 -algoritmen etter at Hans Dobbertin oppdaget dens svakhet.

Til tross for den nåværende brede spredningen, reiser rekken av sikkerhetsproblemer oppdaget siden Hans Dobbertin annonserte en hasjkollisjon i 1996 en rekke tvil om dens fremtidige bruk.

Koding

128-biters MD5-koding er typisk representert som et antall på 32 heksadesimale symboler. Følgende 28-byte ASCII-kode vil bli behandlet med MD5, og vi vil se dens tilsvarende utgangshash :

MD5("Genererer en MD5 fra en tekst") = 5df9f63916ebf8528697b629022993e8

En liten endring i teksten (endre '5' til 'S') gir en helt annen utgang.

MD5("Genererer en MDS fra en tekst") = e14a3ff5b5e67ede599cac94358e1028

Et annet eksempel kan være å kode et tomt felt:

MD5("") = d41d8cd98f00b204e9800998ecf8427eeee

Algoritme

I dette dokumentet er "ord" en 4-byte enhet og en byte er en 8-bit enhet. En sekvens av bytes kan naturlig tolkes som en sekvens av biter, der hver påfølgende gruppe på åtte biter tolkes som en byte med den mest signifikante biten først. På samme måte kan en sekvens av byte tolkes som en sekvens på 32 biter (ord), der hver påfølgende gruppe på fire byte tolkes som et ord der den minst signifikante byten er i begynnelsen (dette er hvordan plattformer som Intel, dette egenskap er kjent som endianness ).

Symbolet "+" betyr summen av ord. X <<< s tolkes av en venstre bitrotasjon om 'X', 's' posisjoner not(x) forstås som komplementet til x

Det starter med å anta at vi har en melding med 'b'-inndatabiter hvis sammendrag er nødvendig. Her er 'b' en vilkårlig ikke-negativ heltallsverdi, men den kan være null, den trenger ikke være et multiplum av åtte, og den kan være så lang som nødvendig. Anta at delene av meldingen er skrevet slik:

m0 m1 ... m{b-1}

De følgende fem trinnene utføres for å beregne meldingssammendraget.

Trinn 1. Legge til biter

Meldingen vil bli forlenget til dens lengde i bit er konsistent med 448, modulo 512. Det vil si at hvis 448 trekkes fra meldingslengden etter dette trinnet, oppnås et multiplum av 512. Denne utvidelsen utføres alltid, selv om lengden av meldingen er allerede i samsvar med 448, modulo 512.

Utvidelsen gjøres som følger: en enkelt "1"-bit legges til meldingen, og deretter legges "0"-biter til inntil lengden i biter av den utvidede meldingen er gjort konsistent med 448, modulo 512. I alle meldinger, kl. minst én bit og høyst 512.

Trinn 2. Meldingslengde

Et 64-bits heltall som representerer lengden 'b' til meldingen (lengde før biter legges til) er sammenkoblet med resultatet av forrige trinn. I den utilsiktede antakelsen om at 'b' er større enn 2^64, vil bare de minst signifikante 64 bitene av 'b' bli brukt.

På dette tidspunktet vil den resulterende meldingen (etter utfylling med y-bitene med 'b') ha en lengde som er et eksakt multiplum av 512 biter. I sin tur er lengden på meldingen et multiplum av 16 ord (32 biter per ord). Med M[0 ... N-1] vil vi betegne ordene i den resulterende meldingen, der N er et multiplum av 16.

Trinn 3. Initialiser MD-bufferen

En buffer på fire ord (A, B, C, D) brukes til å beregne meldingssammendraget. Her representerer hver av bokstavene A, B, C, D et 32-bits register. Disse registrene initialiseres med følgende heksadesimale verdier, minst signifikante byte først:

ord A: 01 23 45 67 ord B: 89 ab cd ef C-ord: fe dc ba 98 D-ord: 76 54 32 10

Trinn 4. Meldingsbehandling i blokker med 16 ord

Først defineres fire hjelpefunksjoner som tar tre 32-bits ord som input og utdata et 32-bits ord.

Operatorene er henholdsvis XOR, AND, OR og NOT-funksjonene.

Ved hver posisjon av hver bit fungerer F som en betinget: hvis X, så Y; hvis ikke, Z. Funksjonen F kunne vært definert med + i stedet for v siden XY og ikke(x) Z aldri vil ha enere ('1') i samme bitposisjon. Det er interessant å merke seg at hvis bitene til X, Y og Z er uavhengige og upartiske, vil hver bit av F(X,Y,Z) være uavhengig og upartisk.

Funksjonene G, H og I ligner på funksjon F, ved at de virker " bitvis parallelt" for å produsere utgangene sine fra bitene til X, Y og Z, så lenge hver tilsvarende bit av X, Y og Z er uavhengig og upartisk, da vil hver bit av G(X,Y,Z), H(X,Y,Z) og I(X,Y,Z) være uavhengig og objektiv. Merk at funksjon H er den bitvise sammenligningen "xor" eller "paritet" funksjonen til inngangene.

Dette trinnet bruker en 64-elements tabell T[1 ... 64] bygget med Sine -funksjonen . T[i] angir det i-te elementet i denne tabellen, som vil være lik heltallsdelen av den absolutte verdien av sinusen til 'i' 4294967296 ganger, hvor.....

MD5-kode:

/* Behandle hver blokk med 16 ord. */ for i = 0 til N/16-1 do /* Kopier 'i'-blokken til X. */ for j = 0 til 15 do lag X[j] av M[i*16+j]. slutt for /* av loop 'j' */ /* Lagre A som AA, B som BB, C som CC og D som DD. */ /* Runde 1. */ /* [abcd ksi] vil betegne operasjonen a = b + ((a + F(b, c, d) + X[k] + T[i]) <<< s). */ /* Gjør de neste 16 operasjonene. */ [ABCD 0 7 1] [DABC 1 12 2] [CDAB 2 17 3] [BCDA 3 22 4] [ABCD 4 7 5] [DABC 5 12 6] [CDAB 6 17 7] [BCDA 7 22 8] [ABCD 8 7 9] [DABC 9 12 10] [CDAB 10 17 11] [BCDA 11 22 12] [ABCD 12 7 13] [DABC 13 12 14] [CDAB 14 17 15] [BCDA 15 22 16] /* Runde 2. */ /* [abcd ksi] vil betegne operasjonen a = b + ((a + G(b, c, d) + X[k] + T[i]) <<< s). */ /* Gjør de neste 16 operasjonene. */ [ABCD 1 5 17] [DABC 6 9 18] [CDAB 11 14 19] [BCDA 0 20 20] [ABCD 5 5 21] [DABC 10 9 22] [CDAB 15 14 23] [BCDA 4 20 24] [ABCD 9 5 25] [DABC 14 9 26] [CDAB 3 14 27] [BCDA 8 20 28] [ABCD 13 5 29] [DABC 2 9 30] [CDAB 7 14 31] [BCDA 12 20 32] /* Runde 3. */ /* [abcd kst] vil betegne operasjonen a = b + ((a + H(b, c, d) + X[k] + T[i]) <<< s). */ /* Gjør de neste 16 operasjonene. */ [ABCD 5 4 33] [DABC 8 11 34] [CDAB 11 16 35] [BCDA 14 23 36] [ABCD 1 4 37] [DABC 4 11 38] [CDAB 7 16 39] [BCDA 10 23 40] [ABCD 13 4 41] [DABC 0 11 42] [CDAB 3 16 43] [BCDA 6 23 44] [ABCD 9 4 45] [DABC 12 11 46] [CDAB 15 16 47] [BCDA 2 23 48] /* Runde 4. */ /* [abcd kst] vil betegne operasjonen a = b + ((a + I(b, c, d) + X[k] + T[i]) <<< s). */ /* Gjør de neste 16 operasjonene. */ [ABCD 0 6 49] [DABC 7 10 50] [CDAB 14 15 51] [BCDA 5 21 52] [ABCD 12 6 53] [DABC 3 10 54] [CDAB 10 15 55] [BCDA 1 21 56] [ABCD 8 6 57] [DABC 15 10 58] [CDAB 6 15 59] [BCDA 13 21 60] [ABCD 4 6 61] [DABC 11 10 62] [CDAB 2 15 63] [BCDA 9 21 64] /* Utfør nå følgende summer. (Dette er økningen av hver ett av de fire registrene etter verdien de hadde før denne blokken ble initialisert.) */ A = A + AA B = B + BB C = C + CC D = D + DD slutt for /* av loop på 'i' */

Trinn 5. Utdata

Meldingssammendraget er utdataene som produseres av A, B, C og D. Det vil si at den starter med lavordensbyten til A og slutter med høyordensbyten til D.

Sikkerhet

Til tross for at de først ble ansett som kryptografisk sikre, har visse undersøkelser avdekket sårbarheter som gjør fremtidig bruk av MD5 tvilsom. I august 2004 kunngjorde Xiaoyun Wang, Dengguo Feng, Xuejia Lai og Hongbo Yu oppdagelsen av hasjkollisjoner for MD5. Angrepet hans ble fullført på en times beregning med en IBM P690-klynge. [ 1 ]

Selv om dette angrepet var analytisk, er størrelsen på hashen (128 biter) liten nok til å gjøre den sårbar for bursdags brute force-angrep . Det distribuerte databehandlingsprosjektet MD5CRK ble startet i mars 2004 med det formål å demonstrere at MD5 er usikkert mot et slikt angrep, selv om det ble avsluttet kort tid etter Wangs teams publisering av sårbarhetsvarselet.

På grunn av oppdagelsen av enkle metoder for å generere hasjkollisjoner , anbefaler mange forskere at de erstattes med alternative algoritmer som SHA-256 eller RIPEMD-160 . Noen av disse metodene for å generere kollisjoner (som Wangs) har sin implementering tilgjengelig på nettet: MD5 kollisjonsimplementering .

Applikasjoner

MD5-sammendrag er mye brukt i programvareverdenen for å sikre at en fil lastet ned fra Internett ikke har blitt tuklet med. Ved å sammenligne en publisert MD5-sjekksum med den nedlastede filens kontrollsum, kan en bruker være trygg nok på at filen er den samme som den publisert av utviklerne. Dette beskytter brukeren mot "trojanske hester" eller "trojanske hester" og virus som en annen ondsinnet bruker kan inkludere i programvaren. Å sjekke en nedlastet fil mot MD5-sjekksummen oppdager ikke bare skadelig endrede filer, den gjenkjenner også en korrupt eller ufullstendig nedlasting.

For å sjekke integriteten til en fil som er lastet ned fra Internett, kan et MD5-verktøy brukes til å sammenligne MD5-summen av den filen med en MD5SUM-fil med MD5-summen til den første filen. På UNIX -systemer er kommandoen md5sum et eksempel på et slikt verktøy. Videre er den også implementert i PHP - skriptspråket som blant annet MD5("").

På UNIX- og GNU / Linux-systemer brukes MD5-algoritmen til å beregne hashen av brukernøkler. Resultatet av MD5 til nøkkelen som legges inn ved registrering av en bruker lagres på disken, og når brukeren ønsker å gå inn i systemet, sammenlignes MD5-hashen til nøkkelen som legges inn med hashen som er lagret på harddisken . Hvis de samsvarer, er det samme nøkkel, og brukeren vil bli autentisert. Gjeldende GNU / Linux-systemer bruker sikrere hash-funksjoner, for eksempel SHA-2 eller SHA-3.

MD5 kan også brukes til å sjekke at e-post ikke er tuklet med ved bruk av offentlige og private nøkler.

Se også

Referanser

  1. ^ "Raskt kollisjonsangrep på MD5 " . IACR.org . Hentet 10. august 2018 . 

Eksterne lenker