Movatterモバイル変換


[0]ホーム

URL:


Spring til indhold
WikipediaDen frie encyklopædi
Søg

MD4

Fra Wikipedia, den frie encyklopædi

MD4 er enkryptografiskhashfunktion designet afR. Rivest i 1990.[1] Som andre lignende funktioner anvendes MD4 til beskyttelse af elektroniske data, f.eks. i forbindelse med transmissioner over åbne netværk.

Funktionen tager som input beskeder af størrelse op til 264 bits og returnerer en 128-bits hash-værdi. Allerede i 1991 blev det første angreb på en reduceret udgave af MD4 publiceret. Dette medførte at designeren samme år publicerede en ny, forstærket udgave, kaldetMD5.

Beskrivelse

[redigér |rediger kildetekst]

MD4 opererer med en 128-bits tilstand, som iterativt opdateres af en 512-bits besked-blok i det, der kaldes 'kompressionsfunktionen'.

Kompressionsfunktionen

[redigér |rediger kildetekst]

Kompressionsfunktionen tager en tilstand på 128 bits og en beskedblok på 512 bits, og returnerer en ny tilstand på 128 bits. Den kan beskrives på følgende måde: Lad input-tilstanden væreh=(a,b,c,d){\displaystyle h=(a,b,c,d)}, hvora,b,c,d{\displaystyle a,b,c,d} er ord af hver 32 bits. Besked-blokken på 512 bits kaldesM=m1,...,m16{\displaystyle M=m_{1},...,m_{16}}. Disse 16 ord udvides til 48 ordw1,...,w48{\displaystyle w_{1},...,w_{48}}, som blot er tre forskellige permutationer afM{\displaystyle M}. Opdateringen af tilstandenh{\displaystyle h} sker over 48 trin, hvorwi{\displaystyle w_{i}} er input til trini{\displaystyle i}. De 48 trin kan opdeles i tre såkaldte runder af 16 trin hver. I hver runde benyttes et ord fraM{\displaystyle M} altså præcist een gang. Odateringen (trini{\displaystyle i}) ser ud som følger:

a(fi(d,c,b)+a+wi+ki)si,{\displaystyle a\gets (f_{i}(d,c,b)+a+w_{i}+k_{i})\lll s_{i},}

hvorfi{\displaystyle f_{i}} er en funktion som er unik for hver runde,ki{\displaystyle k_{i}} er en 32-bits konstant som er unik for hver runde,si{\displaystyle s_{i}} er en værdi mellem 0 og 31 som skifter for hvert trin,+{\displaystyle +} betyder addition modulo 232, ogxs{\displaystyle x\lll s} betyderx{\displaystyle x} roteret bitvists{\displaystyle s} pladser til venstre. Den nævnte operation efterfølges af en flytning af ord således atd{\displaystyle d} får værdien afc{\displaystyle c},c{\displaystyle c} får værdien afb{\displaystyle b},b{\displaystyle b} får værdien afa{\displaystyle a}, oga{\displaystyle a} får den gamle værdi afd{\displaystyle d}. I en praktisk implementation sker denne flytning implicit.

Funktionernefi{\displaystyle f_{i}} er bitvise funktioner. De er defineret som følger:

fi(x,y,z)=(xy)(¬xz){\displaystyle f_{i}(x,y,z)=(x\land y)\lor (\neg x\land z)} fori{\displaystyle i} mellem 1 og 16,

fi(x,y,z)=(xy)(xz)(yz){\displaystyle f_{i}(x,y,z)=(x\land y)\lor (x\land z)\lor (y\land z)} fori{\displaystyle i} mellem 17 og 32, og

fi(x,y,z)=xyz{\displaystyle f_{i}(x,y,z)=x\oplus y\oplus z} fori{\displaystyle i} mellem 33 og 48.

Konstanterneki{\displaystyle k_{i}} er (i hexadecimal) henholdsvis0,5a827999 og6ed9eba1 i henholdsvis runde 1, 2 og 3. Rotationskonstanternesi{\displaystyle s_{i}} er

3, 7, 11, 19, 3, 7, ... i runde 1,

3, 5, 9, 13, 3, 5, ... i runde 2, og

3, 9, 11, 15, 3, 9, ... i runde 3.

Permutationerne afM{\displaystyle M} kan findes i tabellen herunder. I rækkej{\displaystyle j} findes permutationen i rundej{\displaystyle j}.

12345678910111213141516
15913261014371115481216
19513311715210614412816

Padding

[redigér |rediger kildetekst]

Da MD4 accepterer beskeder af næsten vilkårlig længde, og da kompressionsfunktionen som beskrevet ovenfor arbejder med 512-bits blokke ad gangen, er der defineret en metode til at udvide enhver besked til en længde som er et multiplum af 512 bits (dette kaldes 'padding'). Dette gøres ved først at tilføje bit'en1, dernæst tilføjesu{\displaystyle u}0-bits, og til sidst tilføjes en 64-bits repræsentation af længden af den oprindelige besked. Her eru{\displaystyle u} valgt netop således, at den samlede længde af den 'paddede' besked er et multiplum af 512 bits. Denne padding-regel sikrer, at beskeder som er forskellige inden padding, også er forskellige efter padding.

Iteration

[redigér |rediger kildetekst]

Kompressionsfunktionen som beskrevet ovenfor 'spiser' 512 bits ad gangen. For at større beskeder kan behandles må kompressionsfunktionen kaldes flere gange. LadH{\displaystyle H} være kompressionsfunktionen med to inputs, den gamle tilstand og besked-blokken. En initiel tilstandsværdi (IV)h0{\displaystyle h_{0}} er defineret som (67452301,10325476,98badcfe,efcdab89), skrevet i hexadecimal og opdelt i 32-bits ord. For hver 512-bits besked-blokm1,...,mt{\displaystyle m_{1},...,m_{t}}, udføreshi=H(hi1,mi)+hi1{\displaystyle h_{i}=H(h_{i-1},m_{i})+h_{i-1}}, hvor additionen udføres modulo 232 på de fire tilstandsord enkeltvis (denne addition er strengt taget en del af kompressionsfunktionen). Den sidste tilstandht{\displaystyle h_{t}} er hash-værdien af beskeden.

Denne iterative brug af kompressionsfunktionen, samt padding med beskedens oprindelige længde, kaldesMerkle-Damgård-konstruktionen.

Eksempler

[redigér |rediger kildetekst]

Nogle eksempler på hash-værdier (angivet i hexadecimal) af korte tekststrenge er givet herunder.

MD4("") = 31d6cfe0d16ae931b73c59d7e0c089c0MD4("0123456789") = a695ea9f14a89c4e82ca5cf52a28d45dMD4("Wikipedia") = e2a059b14fc07a3c78c7b74027a323ec

Enhver ændring af beskeden medfører at gennemsnitligt ca. 64 bits af hash-værdien ændres. Eksempel:

MD4("Wikipedib") = 2cf896ca02711a90ef58ea10878a32ee

Betydning

[redigér |rediger kildetekst]

MD4 har dannet baggrund for en lang række ofte anvendte hashfunktioner. Den umiddelbare efterfølgerMD5 er et godt eksempel, men ogsåSHA-familien, designet og standardiseret af de amerikanske myndigheder, er baseret på MD4. Herudover er den europæiskeRIPEMD en variant af MD4. Som følge af en lang række angreb på stort set samtlige hashfunktioner baseret på MD4 er der dog opstået usikkerhed om hvorvidt det grundlæggende design er fornuftigt.

Angreb

[redigér |rediger kildetekst]

De første angreb på MD4 så dagens lys allerede året efter hashfunktionen blev publiceret.B. den Boer ogA. Bosselaers fandt en metode til at finde kollisioner (dvs. to forskellige beskeder med samme hash-værdi) i en variant af MD4, hvor kun de sidste to runder er medtaget.[2]S. Vaudenay beskrev en metode til at finde kollisioner i en variant hvor sidste runde er udeladt.[3] Det første succesfulde angreb på den egentlige MD4-algoritme blev publiceret i 1996 afH. Dobbertin, som fandt kollisioner på få sekunder.[4] Senere er en endnu hurtigere metode blevet beskrevet afX. Wang et al.[5] På baggrund af disse angreb må MD4 betragtes som uegnet til brug i applikationer som kræver kryptografisk sikkerhed.

Referencer

[redigér |rediger kildetekst]
  1. ^R. L. Rivest. The MD4 Message Digest Algorithm. In A. Menezes and S. A. Vanstone, editors, Advances in Cryptology – CRYPTO '90, Proceedings, volume 537 of Lecture Notes in Computer Science, pages 303-311. Springer, 1991.
  2. ^B. den Boer and A. Bosselaers. An Attack on the Last Two Rounds of MD4. In J. Feigenbaum, editor, Advances in Cryptology – CRYPTO '91, Proceedings, volume 576 of Lecture Notes in Computer Science, pages 194-203. Springer, 1992.
  3. ^S. Vaudenay. On the Need for Multipermutations: Cryptanalysis of MD4 and SAFER. In B. Preneel, editor, Fast Software Encryption 1994, Proceedings, volume 1008 of Lecture Notes in Computer Science, pages 286-297. Springer, 1995.
  4. ^H. Dobbertin. Cryptanalysis of MD4. In D. Gollmann, editor, Fast Software Encryption 1996, Proceedings, volume 1039 of Lecture Notes in Computer Science, pages 53-69. Springer, 1996.
  5. ^X. Wang, X. Lai, D. Feng, H. Chen, and X. Yu. Cryptanalysis of the Hash Functions MD4 and RIPEMD. In R. Cramer, editor, Advances in Cryptology – EUROCRYPT 2005, Proceedings, volume 3494 of Lecture Notes in Computer Science, pages 1-18. Springer, 2005.
Hentet fra "https://da.wikipedia.org/w/index.php?title=MD4&oldid=11421784"
Kategorier:

[8]ページ先頭

©2009-2025 Movatter.jp