MD4

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 16 octombrie 2021; verificarea necesită 1 editare .

MD4
Creată	1990 _
publicat	octombrie 1990 _
Predecesor	MD2
Succesor	MD5
Dimensiunea hash	128 de biți
Numărul de runde	3
Tip de	funcția hash

MD4 ( Message Digest 4 ) este o funcție hash criptografică dezvoltată de profesorul de la Universitatea din Massachusetts Ronald Rivest în 1990 și descrisă pentru prima dată în RFC 1186 . Având în vedere un mesaj de intrare arbitrar , funcția generează o valoare hash de 128 de biți numită mesaj digest . Acest algoritm este utilizat în protocolul de autentificare MS-CHAP dezvoltat de Microsoft pentru a efectua proceduri de autentificare pe stațiile de lucru Windows la distanță . Este predecesorul lui MD5 .

Algoritmul MD4

Se presupune că intrarea este un mesaj format din biți, al căror hash trebuie să-l calculăm. Aici este un întreg nenegativ arbitrar ; poate fi zero, nu trebuie să fie multiplu de opt și poate fi arbitrar mare. Să scriem mesajul bit cu bit, sub forma: $b$ $b$

m_0 m_1 \ldots m_{b-1}

Mai jos sunt cei 5 pași utilizați pentru a calcula hash-ul unui mesaj.

Pasul 1. Adăugarea biților lipsă.

Mesajul este extins astfel încât lungimea sa în biți modulo 512 este de 448. Astfel, ca rezultat al extinderii, mesajul este cu 64 de biți mai mic decât un multiplu de lungime de 512 biți. Extinderea este întotdeauna efectuată, chiar dacă mesajul are inițial lungimea corectă.

Extinderea se face după cum urmează: la mesaj se adaugă un bit egal cu 1, apoi se adaugă biți egali cu 0 până când lungimea mesajului este de 448 modulo 512. În total, la mesaj se adaugă cel puțin 1 bit, și maximum 512.

Pasul 2. Adăugarea lungimii mesajului.

Reprezentarea pe 64 de biți (lungimea mesajului înainte de adăugarea biților de umplutură) este adăugată la rezultatul pasului anterior. În cazul improbabil care este mai mare decât , sunt utilizați doar cei mai puțin semnificativi 64 de biți. Acești biți sunt adăugați ca două cuvinte de 32 de biți, cu cuvântul care conține biții mai puțin semnificativi adăugați primul. $b$ $b$ $2^{64}$

În această etapă (după adăugarea biților și a lungimii mesajului) obținem un mesaj cu o lungime care este un multiplu de 512 biți. Acest lucru este echivalent cu faptul că acest mesaj este un multiplu de 16 cuvinte pe 32 de biți. Să denotăm o matrice de cuvinte în mesajul rezultat (aici, un multiplu de 16). $M[0 \ldots N-1]$ $N$

Pasul 3. Inițializați tamponul MD.

Pentru a calcula hash-ul mesajului se folosește un buffer format din 4 cuvinte (registre de 32 de biți): . Aceste registre sunt inițializate cu următoarele numere hexazecimale (mai întâi octeții mai mici): $(A,B,C,D)$

cuvânt : 01 23 45 67

A

cuvânt : 89 ab cd ef

B

cuvânt : fe dc ba 98

C

cuvânt : 76 54 32 10

D

Pasul 4. Procesarea mesajului în blocuri de 16 cuvinte.

Pentru început, definim trei funcții auxiliare, fiecare dintre ele primește trei cuvinte de 32 de biți ca intrare și calculează un cuvânt de 32 de biți de la ele.

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

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

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

Acționează ca o expresie condiționată pe fiecare poziție de bit : dacă , atunci ; altfel . Funcția ar putea fi definită folosind în loc de , deoarece și nu pot fi egale ambele . acționează asupra fiecărei poziții de bit în funcție de valoarea maximă: dacă în cel puțin două cuvinte din biții corespunzători sunt , atunci se va întoarce în acel bit, în caz contrar va returna bitul egal cu . Este interesant de observat că, dacă biții și sunt independenți statistic, atunci biții și vor fi, de asemenea, independenți statistic. Funcția se implementează pe biți , are aceeași proprietate ca și . $F$ $X$ $Y$ $Z$ $F$ $+$ $\lor$ $X Y$ $\neg XZ$ $unu$ $G$ $X,Y,Z$ $unu$ $G$ $unu$ $G$ $0$ $X$ $Y$ $Z$ $F(X,Y,Z)$ $G(X,Y,Z)$ $H$ $xor$ $F$ $G$

Algoritm de hashing în limbaj de programare abstract :

/* Procesează fiecare bloc de 16 cuvinte */ pentru i = 0 la N / 16-1 do /* Introduceți al-lea bloc în variabila X */ pentru j = 0 până la 15 do setați X [ j ] la M [ i * 16 + j ]. sfârşitul /* sfârşitul buclei pe j */ /* Stocați A ca AA, B ca BB, C ca CC și D ca DD */ AA = A B.B. = B CC = C DD = D /* Runda 1 */ /* Fie [abcd ks] să însemne următoarea operație: a = (a + F(b,c,d) + X[k]) <<< s. */ /* Efectuați următoarele 16 operații: */ [ 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 ] /* Runda 2 */ /* Fie [abcd ks] să notăm următoarea operație: a = (a + G(b,c,d) + X[k] + 5A827999) <<< s. */ /* Efectuați următoarele 16 operații: */ [ 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 ] /* Runda 3 */ /* Fie [abcd ks] să însemne următoarea operație: a = (a + H(b,c,d) + X[k] + 6ED9EBA1) <<< s. */ /* Efectuați următoarele 16 operații: */ [ 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 ] /* Apoi efectuăm următoarele operații de adunare. (Măriți valoarea din fiecare registru cu suma pe care o avea înainte de a repeta peste i */ A = A + AA B = B + BB C = C + CC D = D + DD sfârşitul /* sfârşitul buclei pe i */

Cometariu. Valoarea 5A827999 este o constantă hexazecimală de 32 de biți, primii octeți sunt mari. Este rădăcina pătrată a lui 2 . Este și în reprezentare octală: 013240474631. Valoarea 6ED9EBA1 este o constantă hexazecimală de 32 de biți, primii octeți sunt mari. Este rădăcina pătrată a lui 3. Este, de asemenea, în octal: 015666365641. Aceste date sunt date în Knuth, The Art of Computer Programming , Ediția 1981, Volumul 2, Pagina 660, Tabelul 2.

Pasul 5. Formarea unui hash.

Rezultatul (funcția hash) se obține ca ABCD. Adică scriem 128 de biți, începând cu bitul cel mai puțin semnificativ din A și terminând cu bitul cel mai semnificativ din D.

Implementarea C a algoritmului este conținută în RFC 1320 .

Exemple de hashuri

Hash-urile MD4 de 128 de biți sunt un număr de 32 de cifre în format hexazecimal. Următorul exemplu arată un hash dintr-un șir ASCII de 43 de octeți :

MD4 (" Vulpea maro iute sare peste câinele leneș ") = 1bee69a46ba811185c194762abaeae90

Orice modificare chiar și cea mai mică a informațiilor cu hash are ca rezultat un hash complet diferit, de exemplu, schimbarea unei litere de la d la c în exemplu :

MD4 ("Vulpea maro iute sare peste cogul leneș " ) = b86e130ce7028da59e672d56ad0113df

Un exemplu de hash MD4 pentru un șir „null”:

MD4("") = 31d6cfe0d16ae931b73c59d7e0c089c0

Comparație cu MD5

MD4 folosește trei bucle a câte 16 pași fiecare, în timp ce MD5 utilizează patru bucle a câte 16 pași fiecare.

În MD4, constanta suplimentară din prima buclă nu este aplicată. O constantă suplimentară similară este utilizată pentru fiecare dintre pașii din a doua buclă. O altă constantă suplimentară este utilizată pentru fiecare dintre pașii din a treia buclă. În MD5, diferite constante suplimentare, T[i], sunt aplicate pentru fiecare dintre cei 64 de pași.

MD5 folosește patru funcții logice elementare, una pe ciclu, în comparație cu cele trei ale MD4, una pe ciclu.

În MD5, la fiecare pas, rezultatul curent este adăugat la rezultatul pasului precedent. De exemplu, rezultatul primului pas este cuvântul modificat A. Rezultatul celui de-al doilea pas este stocat în D și se formează prin adăugarea A la rezultatul funcției elementare, deplasat ciclic la stânga cu un anumit număr de biți. . În mod similar, rezultatul celui de-al treilea pas este stocat în C și este format prin adăugarea lui D la rezultatul ciclic deplasat la stânga al funcției elementare. MD4 nu include această ultimă adăugare.

Securitate

Nivelul de securitate stabilit în MD4 a fost conceput pentru a crea sisteme hibride de semnătură digitală suficient de stabile, bazate pe MD4 și un criptosistem cu cheie publică. Ronald Rivest credea că algoritmul de hashing MD4 ar putea fi folosit și pentru sistemele care au nevoie de o putere criptografică puternică . Dar, în același timp, el a remarcat că MD4 a fost creat în primul rând ca un algoritm de hashing foarte rapid, deci poate fi rău în ceea ce privește puterea criptografică. După cum au arătat studiile ulterioare, el a avut dreptate, iar pentru aplicațiile în care puterea criptografică este în primul rând importantă, algoritmul MD5 a început să fie utilizat .

Vulnerabilități

Vulnerabilitățile în MD4 au fost demonstrate într-o lucrare de Bert den Boer și Anton Bosselars în 1991. Prima coliziune a fost găsită de Hans Dobbertin în 1996.

Vezi și

Link -uri

Găsirea coliziunilor

Atacul de coliziune îmbunătățit pe MD4

Funcții hash
scop general	Adler-32 CRC Suma de control Fletcher FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash suma hash
Criptografic	Stribog GOST R 34.11-94 Centura BLAKE BMW CubeHash ECOU edonkey2k FSB Fugă 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 Piele Snefru Tigru Vârtej
Funcții de generare a cheilor	bcrypt PBKDF2 cripta Argon2 Lyra2
Numărul de verificare ( comparație )	Verificați suma Algoritmul lui Verhouff Algoritmul lunii Algoritmul Damm Cod de bare conturi bancare carduri bancare ESTE IN SNILS OKPO STANIU OKATO ISBN OGRN și OGRNIP VIN
Hashes	Comparația numerelor de cec Protocoale de autentificare Comparația codurilor de bare Criptografie Legătură magnetică Semnătura Merkle ed2k URNĂ