MD4

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 16. oktober 2021; verifikation kræver 1 redigering .

MD4
Oprettet	1990 _
offentliggjort	oktober 1990 _
Forgænger	MD2
Efterfølger	MD5
Hash størrelse	128 bit
Antal runder	3
Type	hash funktion

MD4 ( Message Digest 4 ) er en kryptografisk hashfunktion udviklet af University of Massachusetts professor Ronald Rivest i 1990 og først beskrevet i RFC 1186 . Givet en vilkårlig inputmeddelelse genererer funktionen en 128-bit hashværdi kaldet beskedsammendraget . Denne algoritme bruges i MS-CHAP- godkendelsesprotokollen udviklet af Microsoft til at udføre godkendelsesprocedurer på eksterne Windows - arbejdsstationer . Det er forgængeren til MD5 .

MD4 algoritme

Det antages, at inputtet er en meddelelse bestående af bits, hvis hash vi skal beregne. Her er et vilkårligt ikke-negativt heltal ; det kan være nul, behøver ikke at være et multiplum af otte og kan være vilkårligt stort. Lad os skrive beskeden lidt efter lidt i formen: $b$ $b$

m_0 m_1 \ldots m_{b-1}

Følgende er de 5 trin, der bruges til at beregne hash for en besked.

Trin 1. Tilføjelse af manglende bits.

Meddelelsen udvides således, at dens længde i bit modulo 512 er 448. Som et resultat af udvidelsen er meddelelsen således 64 bit mindre end et længdemultiplum på 512 bit. Udvidelsen udføres altid, selvom beskeden oprindeligt har den korrekte længde.

Udvidelsen sker på følgende måde: Der tilføjes en bit lig med 1 til beskeden, og derefter tilføjes bits lig med 0 indtil længden af beskeden er 448 modulo 512. I alt tilføjes mindst 1 bit til beskeden. og maksimalt 512.

Trin 2. Tilføjelse af beskedens længde.

64-bit repræsentationen (længden af meddelelsen før udfyldningsbits tilføjes) føjes til resultatet af det foregående trin. I det usandsynlige tilfælde, der er større end , bruges kun de mindst signifikante 64 bits. Disse bits tilføjes som to 32-bit ord, hvor ordet indeholder de mindst signifikante bit tilføjet først. $b$ $b$ $2^{64}$

På dette stadium (efter tilføjelse af bits og længden af beskeden) får vi en besked med en længde, der er et multiplum af 512 bit. Dette svarer til, at denne meddelelse er et multiplum af 16 32-bit ord lang. Lad betegne en række ord i den resulterende besked (her et multiplum af 16). $M[0 \ldots N-1]$ $N$

Trin 3. Initialiser MD-bufferen.

For at beregne beskedhashen bruges en buffer bestående af 4 ord (32-bit registre): . Disse registre initialiseres med følgende hexadecimale tal (nedre bytes først): $(A,B,C,D)$

ord : 01 23 45 67

EN

ord : 89 ab cd ef

B

ord : fe dc ba 98

C

ord : 76 54 32 10

D

Trin 4. Behandling af beskeden i blokke af 16 ord.

Til at begynde med definerer vi tre hjælpefunktioner, som hver modtager tre 32-bit ord som input, og beregner et 32-bit ord ud fra dem.

F(X,Y,Z)=XY\eller \neg XZ

G(X,Y,Z)=XY\eller XZ\eller YZ

H(X,Y,Z)=X\oplus Y\oplus Z

Det fungerer som et betinget udtryk på hver bitposition : if , then ; ellers . Funktionen kunne defineres ved at bruge i stedet for , da og kan ikke begge være lig . virker på hver bitposition som en funktion af den maksimale værdi: hvis i mindst to ord af de tilsvarende bit er , så vil den returnere i den bit, ellers vil den returnere bit lig med . Det er interessant at bemærke, at hvis bits og er statistisk uafhængige, så vil bits og også være statistisk uafhængige. Funktionen implementerer bitvis , den har samme egenskab som . $F$ $x$ $Y$ $Z$ $F$ $+$ $\lor$ $XY$ $\neg XZ$ $en$ $G$ $X,Y,Z$ $en$ $G$ $en$ $G$ $0$ $x$ $Y$ $Z$ $F(X,Y,Z)$ $G(X,Y,Z)$ $H$ $xor$ $F$ $G$

Hashing-algoritme i abstrakt programmeringssprog :

/* Behandle hver blok på 16 ord */ for i = 0 til N / 16-1 do /* Indtast den i-te blok i variablen X */ for j = 0 til 15 do sæt X [ j ] til M [ i * 16 + j ]. slutning /* slutning af løkke på j */ /* Gem A som AA, B som BB, C som CC og D som DD */ AA = A B.B. = B CC = C DD = D /* Runde 1 */ /* Lad [abcd ks] betyde følgende operation: a = (a + F(b,c,d) + X[k]) <<< s. */ /* Udfør følgende 16 handlinger: */ [ ABCD 0 3 ] [ DABC 1 7 ] [ CDAB 2 11 ] [ BCDA 3 19 ] [ ABCD 4 3 ] [ DABC 5 7 ] [ CDAB 6 11 ] [ BCDA 7 19 ] [ ABCD 8 3 ] [ DABC 9 7 ] [ CDAB 10 11 ] [ BCDA 11 19 ] [ ABCD 12 3 ] [ DABC 13 7 ] [ CDAB 14 11 ] [ BCDA 15 19 ] /* Runde 2 */ /* Lad [abcd ks] angive følgende operation: a = (a + G(b,c,d) + X[k] + 5A827999) <<< s. */ /* Udfør følgende 16 handlinger: */ [ ABCD 0 3 ] [ DABC 4 5 ] [ CDAB 8 9 ] [ BCDA 12 13 ] [ ABCD 1 3 ] [ DABC 5 5 ] [ CDAB 9 9 ] [ BCDA 13 13 ] [ ABCD 2 3 ] [ DABC 6 5 ] [ CDAB 10 9 ] [ BCDA 14 13 ] [ ABCD 3 3 ] [ DABC 7 5 ] [ CDAB 11 9 ] [ BCDA 15 13 ] /* Runde 3 */ /* Lad [abcd ks] betyde følgende operation: a = (a + H(b,c,d) + X[k] + 6ED9EBA1) <<< s. */ /* Udfør følgende 16 handlinger: */ [ ABCD 0 3 ] [ DABC 8 9 ] [ CDAB 4 11 ] [ BCDA 12 15 ] [ ABCD 2 3 ] [ DABC 10 9 ] [ CDAB 6 11 ] [ BCDA 14 15 ] [ ABCD 1 3 ] [ DABC 9 9 ] [ CDAB 5 11 ] [ BCDA 13 15 ] [ ABCD 3 3 ] [ DABC 11 9 ] [ CDAB 7 11 ] [ BCDA 15 15 ] /* Derefter udfører vi følgende tilføjelsesoperationer. (Forøg værdien i hvert register med det beløb, det havde før iteration over i */ A = A + AA B = B + BB C = C + CC D = D + DD slutning /* slutning af løkke på i */

Kommentar. Værdien 5A827999 er en 32-bit hexadecimal konstant, de første bytes er høje. Det er kvadratroden af 2 . Den er også i oktal repræsentation: 013240474631. Værdien 6ED9EBA1 er en hexadecimal 32-bit konstant, de første bytes er høje. Det er kvadratroden af 3. Det er også i oktal: 015666365641. Disse data er givet i Knuth, The Art of Computer Programming , 1981 Edition, bind 2, side 660, tabel 2.

Trin 5. Dannelse af en hash.

Resultatet (hash-funktion) opnås som ABCD. Det vil sige, at vi udskriver 128 bit, startende med den mindst signifikante bit af A og slutter med den mest signifikante bit af D.

C -implementeringen af algoritmen er indeholdt i RFC 1320 .

Eksempler på hashes

128-bit MD4 hashes er et 32-cifret tal i hexadecimalt format. Følgende eksempel viser en hash af en 43-byte ASCII -streng :

MD4(" Den hurtige brune ræv hopper over den dovne hund ") = 1bee69a46ba811185c194762abaeae90

Enhver selv den mindste ændring i de hash-oplysninger resulterer i en helt anden hash, for eksempel ved at ændre et bogstav fra d til c i eksemplet :

MD4("Den hurtige brune ræv hopper over den dovne c og") = b86e130ce7028da59e672d56ad0113df

Et eksempel på en MD4-hash for en "nul"-streng:

MD4("") = 31d6cfe0d16ae931b73c59d7e0c089c0

Sammenligning med MD5

MD4 bruger tre sløjfer med hver 16 trin, mens MD5 bruger fire sløjfer med hver 16 trin.

I MD4 anvendes den ekstra konstant i den første sløjfe ikke. En lignende ekstra konstant bruges til hvert af trinene i den anden sløjfe. En anden ekstra konstant bruges til hvert af trinene i den tredje sløjfe. I MD5 anvendes forskellige yderligere konstanter, T[i], for hvert af de 64 trin.

MD5 bruger fire elementære logiske funktioner, en pr. cyklus, sammenlignet med MD4's tre, en pr. cyklus.

I MD5 føjes det aktuelle resultat ved hvert trin til resultatet af det foregående trin. For eksempel er resultatet af det første trin det modificerede ord A. Resultatet af det andet trin er lagret i D og dannes ved at tilføje A til resultatet af den elementære funktion, cyklisk forskudt til venstre med et vist antal bit . På samme måde lagres resultatet af det tredje trin i C og dannes ved at tilføje D til det cykliske venstreforskydne resultat af den elementære funktion. MD4 inkluderer ikke denne sidste tilføjelse.

Sikkerhed

Sikkerhedsniveauet fastsat i MD4 var designet til at skabe tilstrækkeligt stabile hybride digitale signatursystemer baseret på MD4 og et offentligt nøglekryptosystem. Ronald Rivest mente, at MD4-hash-algoritmen også kunne bruges til systemer med behov for stærk kryptografisk styrke . Men samtidig bemærkede han, at MD4 primært blev skabt som en meget hurtig hashing-algoritme, så den kan være dårlig med hensyn til kryptografisk styrke. Som efterfølgende undersøgelser viste, havde han ret, og til applikationer, hvor kryptografisk styrke er primært vigtig, begyndte MD5- algoritmen at blive brugt .

Sårbarheder

Sårbarheder i MD4 blev demonstreret i et papir af Bert den Boer og Anton Bosselars i 1991. Den første kollision blev fundet af Hans Dobbertin i 1996.

Se også

Links

Find kollisioner

Forbedret kollisionsangreb på MD4

Hash funktioner
generelle formål	Adler-32 CRC Fletcher kontrolsum FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash hash sum
Kryptografisk	Stribog GOST R 34,11-94 Bælte BLAKE bmw CubeHash EKKO edonkey2k FSB Fuge Grostl HAVAL Hamsi JH Kupyna LM hash Luffa MD2 MD4 MD5 MD6 N-hash RIPEMD-128 RIPEMD-160 RIPEMD-256 RIPEMD-320 SHA-1 SHA-2 Keccak (SHA-3) SHABAL SHAvite-3 SIMD SWIFFT Hud Snefru Tiger Whirlpool
Nøglegenereringsfunktioner	bcrypt PBKDF2 krypt Argon 2 Lyra2
Tjek nummer ( sammenligning )	Tjek sum Verhouffs algoritme Månen algoritme Damm algoritme Stregkode bankkonti bankkort ER I SNILS OKPO TIN OKATO ISBN OGRN og OGRNIP VIN
Hashes	Sammenligning af checknumre Autentificeringsprotokoller Stregkode sammenligning Kryptografi Magnet link Merkle signatur ed2k URNE