Funcția hash criptografică. Funcția hash: ce este, de ce este necesară și ce este?

Întrebări:

1. Conceptul de funcție hash.

2. Utilizarea algoritmilor de criptare bloc pentru a forma o funcție hash.

3. Revizuirea algoritmilor de generare a funcțiilor hash.

1. Conceptul de funcție hash

Funcția hash(funcția hash) este o funcție matematică sau de altă natură care, pentru un șir de lungime arbitrară, calculează o valoare întreagă sau un alt șir de lungime fixă. Matematic se poate scrie astfel:

h = H(M) ,

Unde M – mesajul original, uneori numit prototip , A h – rezultatul, numit valoarea hash (și de asemenea cod hash sau rezumatul mesajului(din engleza rezumatul mesajului)).

Semnificația funcției hash este de a determina trăsătura caracteristică a preimaginei - valoarea funcției hash. Această valoare are de obicei o dimensiune fixă, cum ar fi 64 sau 128 de biți. Codul hash poate fi analizat în continuare pentru a rezolva orice problemă. De exemplu, hashingul poate fi utilizat pentru a compara datele: dacă două matrice de date au coduri hash diferite, se garantează că matricele sunt diferite; dacă sunt aceleași, matricele sunt cel mai probabil aceleași. În general, nu există o corespondență unu-la-unu între datele sursă și codul hash datorită faptului că numărul de valori ale funcției hash este întotdeauna mai mic decât numărul de opțiuni de date de intrare. În consecință, există multe mesaje de intrare care dau aceleași coduri hash (astfel de situații sunt numite ciocniri ). Probabilitatea de coliziuni joacă un rol important în evaluarea calității funcțiilor hash.

Funcțiile hash sunt utilizate pe scară largă în criptografia modernă.

Cea mai simplă funcție hash poate fi construită folosind operația de sumă modulo-2, după cum urmează: obțineți șirul de intrare, adăugați toți octeții modulo 2 și returnați octetul rezultat ca valoare hash. Lungimea valorii funcției hash în acest caz va fi de 8 biți, indiferent de dimensiunea mesajului de intrare.

De exemplu, să presupunem că mesajul original, tradus în formă digitală, a fost următorul (în hexazecimal):

2 B1 4 A9 5 FE4

Să convertim mesajul în formă binară, să scriem octeții unul sub celălalt și să adăugăm biții în fiecare coloană modulo 2:

0010 1011

0001 0100

1010 1001

0101 1111

1110 0100

——————-

0010 1101

Rezultat: 0010 1101 sau 2 Dși va fi valoarea funcției hash.

Cu toate acestea, o astfel de funcție hash nu poate fi utilizată în scopuri criptografice, cum ar fi generarea unei semnături electronice, deoarece este destul de ușor să schimbați conținutul mesajului semnat fără a modifica valoarea sumei de control.

Prin urmare, funcția hash considerată nu este potrivită pentru aplicațiile criptografice. În criptografie, o funcție hash este considerată bună dacă este dificil să se creeze două preimagini cu aceeași valoare hash și, de asemenea, dacă rezultatul funcției nu are o dependență explicită de intrare.

Să formulăm cerințele de bază pentru funcțiile hash criptografice:

· funcția hash trebuie să fie aplicabilă unui mesaj de orice dimensiune;

· calculul valorii funcției trebuie efectuat suficient de rapid;

· având în vedere o valoare cunoscută a funcției hash, ar trebui să fie dificil (aproape imposibil) să găsești un prototip potrivit M ;

· cu un mesaj cunoscut M trebuie sa fie greu sa gasesti o alta postare M' cu aceeași valoare hash ca și mesajul original;

· Ar trebui să fie dificil să găsești vreo pereche de mesaje distincte aleatoriu cu aceeași valoare hash.

Crearea unei funcții hash care să îndeplinească toate cerințele de mai sus nu este o sarcină ușoară. De asemenea, este necesar să ne amintim că intrarea funcției primește date de dimensiune arbitrară, iar rezultatul hash nu ar trebui să fie același pentru date de dimensiuni diferite.

În prezent, în practică, funcțiile hash sunt funcții care procesează bloc cu bloc mesajul de intrare și calculează valoarea hash Bună pentru fiecare bloc M i mesaj de intrare bazat pe dependențele formularului

h i = H(M i ,h i-1),

Unde h i-1 – rezultatul obținut la calcularea funcției hash pentru blocul anterior de date de intrare.

Ca rezultat, rezultatul funcției hash este h n este o funcție a tuturor n blocuri de mesaje de intrare.

2. Utilizarea algoritmilor de criptare bloc pentru a genera o funcție hash.

Un algoritm de criptare simetrică bloc poate fi utilizat ca funcție hash. Dacă algoritmul de bloc utilizat este puternic criptografic, atunci funcția hash bazată pe acesta va fi sigură.

Cel mai simplu mod de a utiliza un algoritm de blocare pentru a obține un cod hash este criptarea mesajului în modul CBC ( Cipher Block Chaining – Modul de înlănțuire a blocurilor Ciphertext). În acest caz, mesajul este reprezentat ca o secvență de blocuri, a căror lungime este egală cu lungimea blocului algoritmului de criptare. Dacă este necesar, ultimul bloc este captusit în dreapta cu zerouri pentru a crea un bloc de lungimea necesară. Valoarea hash va fi ultimul bloc de text criptat. Cu condiția să fie utilizat un algoritm de criptare a blocurilor de încredere, valoarea hash rezultată va avea următoarele proprietăți:

· este aproape imposibil să se calculeze o valoare hash pentru o anumită matrice deschisă de informații fără a cunoaște cheia de criptare;

· este aproape imposibil să selectați date deschise pentru o anumită valoare hash fără a cunoaște cheia de criptare.

Valoarea hash astfel generată este de obicei numită inserție de imitație sau autentificator și este folosit pentru a verifica integritatea mesajului. Astfel, inserția imitativă este o combinație de control care depinde de datele deschise și informațiile cheie secrete. Scopul utilizării inserției imitative este de a detecta toate modificările accidentale sau intenționate în matricea de informații. Valoarea obținută de funcția hash la procesarea mesajului de intrare este atașată mesajului în momentul în care se știe că mesajul este corect. Destinatarul verifică integritatea mesajului calculând mesajul imitat al mesajului primit și comparându-l cu codul hash primit, care trebuie transmis în mod sigur. Una dintre astfel de metode sigure ar putea fi criptarea inserției imitative cu cheia privată a expeditorului, de exemplu. crearea unei semnături. De asemenea, este posibil să se cripteze codul hash rezultat cu un algoritm de criptare simetric dacă expeditorul și destinatarul au o cheie de criptare simetrică comună.

Procesul specificat de obținere și utilizare a inserțiilor de imitație este descris în standardul intern GOST 28147-89. Standardul propune utilizarea celor 32 de biți inferiori ai blocului obținut la ieșirea întregii operațiuni de criptare a mesajului în modul de înlănțuire a blocurilor de criptare pentru a controla integritatea mesajului transmis. În același mod, orice algoritm de criptare simetrică bloc poate fi utilizat pentru a genera o inserție imitativă.

O altă modalitate posibilă de a utiliza un cifru bloc pentru a genera un cod hash este următoarea. Mesajul original este procesat secvenţial în blocuri. Ultimul bloc este completat cu zerouri, dacă este necesar, uneori lungimea mesajului sub forma unui număr binar este adăugată ultimului bloc. În fiecare etapă, criptăm valoarea hash obținută în etapa anterioară, folosind blocul de mesaj curent ca cheie. Ultima valoare criptată primită va fi rezultatul hash final.

Astfel, dacă schema obișnuită de criptare a mesajelor M folosind un cifru bloc f pe cheie LA am înregistrat ca E= f(M,K) , apoi schema de obținere a codului hash h folosind algoritmul descris mai sus poate fi reprezentat ca

Bună = f ( Bună -1 , M )

Ca cod hash inițial h 0 ia ceva constant. Criptarea se realizează în modul de înlocuire simplă. Când utilizați această metodă, dimensiunea blocului este aceeași cu lungimea cheii, iar dimensiunea valorii hash va fi lungimea blocului.

Este posibilă și o altă modalitate de a utiliza un cifru bloc în modul de înlocuire simplă: elementele mesajului sunt criptate cu valorile hash obținute în pasul anterior:

Bună = f ( M , Bună -1 ,)

De fapt, există mai multe alte scheme posibile pentru utilizarea unui cifru bloc pentru a genera o funcție hash. Lăsa M i - bloc de mesaje original, Bună – valoarea funcției hash activată i - in acea etapa, f – algoritm de criptare bloc utilizat în modul de înlocuire simplă – operație de adăugare modulo 2. Atunci, de exemplu, sunt posibile următoarele scheme de generare a funcției hash;

În toate aceste scheme, lungimea valorii hash generată este egală cu lungimea blocului de criptare. Toate acestea, precum și alte scheme pentru utilizarea unui algoritm de criptare bloc pentru a calcula valorile hash, pot fi utilizate în practică.

Principalul dezavantaj al funcțiilor hash concepute pe baza algoritmilor bloc este viteza relativ scăzută de funcționare. Puterea criptografică necesară poate fi atinsă cu mai puține operațiuni asupra datelor de intrare. Există algoritmi de hashing mai rapizi (cele mai comune dintre ei sunt MD5, SHA-1, SHA-2 și GOST R 34.11-94).

3. Revizuirea algoritmilor de generare a funcțiilor hash.

În prezent, diverși algoritmi speciali pentru calcularea funcției hash au fost propuși și sunt utilizați practic. Cei mai cunoscuți algoritmi sunt MD5, SHA-1, SHA-2 și alte versiuni de SHA, precum și algoritmul intern stabilit în GOST R 34.11-94.

Algoritm MD5 a apărut la începutul anilor 90 ai secolului XX ca urmare a îmbunătățirii algoritmului de generare a funcției hash MD4. Caracterele din numele „MD” reprezintă Message Digest - un rezumat al mesajului. Autorul algoritmilor MD4 și MD5 este R. Rivest. Utilizarea MD5 pentru un mesaj arbitrar produce o valoare hash de 128 de biți. Datele de intrare sunt procesate în blocuri de 512 biți. Algoritmul folosește operații logice elementare (inversie, conjuncție, adunare modulo 2, deplasări ciclice etc.), precum și adunare aritmetică obișnuită. Repetarea complexă a acestor funcții elementare ale algoritmului asigură că rezultatul după procesare este bine amestecat. Prin urmare, este puțin probabil ca două mesaje alese la întâmplare să aibă același cod hash. Algoritmul MD5 are următoarea proprietate: fiecare bit al valorii hash rezultată este o funcție a fiecărui bit al intrării. MD5 este considerată cea mai puternică funcție hash pentru o valoare hash de 128 de biți.

Algoritm SHA(Secure Hash Algorithm) a fost dezvoltat de Institutul Național de Standarde și Tehnologie din SUA (NIST) și publicat ca standard federal de informații din SUA în 1993. SHA-1, ca și MD5, se bazează pe algoritmul MD4. SHA-1 generează o valoare hash de 160 de biți prin procesarea mesajului original în blocuri de 512 de biți. Algoritmul SHA-1 utilizează, de asemenea, operații logice și aritmetice simple. Cea mai importantă diferență dintre SHA-1 și MD5 este că codul hash SHA-1 este cu 32 de biți mai lung decât codul hash MD5. Presupunând că ambii algoritmi sunt egali în dificultate pentru criptoanaliza, atunci SHA-1 este algoritmul mai puternic. Folosind un atac de forță brută (atac de forță brută), este mai dificil să creezi un mesaj arbitrar care are un anumit cod hash și, de asemenea, este mai dificil să creezi două mesaje care au același cod hash.

În 2001, Institutul Național de Standarde și Tehnologie din SUA a adoptat trei funcții hash cu o lungime mai mare a codului hash decât SHA-1 ca standard. Aceste funcții hash sunt adesea numite SHA-2 sau SHA-256, SHA-384 și SHA-512 (numele indică lungimea codului hash generat de algoritmi). Acești algoritmi diferă nu numai prin lungimea codului hash creat, ci și prin funcțiile interne utilizate și lungimea blocului procesat (SHA-256 are o lungime a blocului de 512, în timp ce SHA-384 și SHA-512 au un bloc lungime de 1024 biți). Îmbunătățirile treptate ale algoritmului SHA duc la o creștere a puterii sale criptografice. În ciuda diferențelor dintre algoritmii luați în considerare, toți sunt dezvoltări ulterioare ale SHA-1 și MD4 și au o structură similară.

Rusia a adoptat GOST R34.11-94, care este standardul intern pentru funcțiile hash. Structura sa este destul de diferită de structura algoritmilor SHA-1,2 sau MD5, care se bazează pe algoritmul MD4. Lungimea codului hash creat de algoritmul GOST R 34.11-94 este de 256 de biți. Algoritmul procesează secvenţial mesajul original în blocuri de 256 de biţi de la dreapta la stânga. Parametrul algoritmului este vectorul de pornire al hashingului - o valoare fixă arbitrară de 256 de biți. Algoritmul GOST R 34.11-94 utilizează operațiile de permutare, schimbare, adăugare aritmetică, adăugare modulo 2 Ca funcție auxiliară, GOST 34.11-94 utilizează algoritmul conform GOST 28147-89 în modul de înlocuire simplă.

4. Cerințe pentru funcțiile hash

O funcție hash este o funcție unidirecțională concepută pentru a obține o sinteză sau amprenta unui fișier, mesaj sau un anumit bloc de date.

Codul hash este generat de funcție N :

h = H(M)

Unde M este un mesaj de lungime arbitrară și h este un cod hash cu lungime fixă.

Să ne uităm la cerințele pe care trebuie să le îndeplinească o funcție hash pentru a fi utilizată ca autentificator de mesaje. Să ne uităm la un exemplu foarte simplu de funcție hash. Apoi vom analiza mai multe abordări pentru construirea unei funcții hash.

Funcția hash N , care este utilizat pentru autentificarea mesajelor, trebuie să aibă următoarele proprietăți:

1. Funcția hash N trebuie aplicat unui bloc de date de orice lungime.

2. Funcția hash N creează o ieșire cu lungime fixă.

3. N (M) relativ ușor (în timp polinomial) de calculat pentru orice valoare M .

4. Pentru orice valoare dată de cod hash h imposibil de găsit din punct de vedere computațional M astfel încât H (M) = h .

5. Pentru orice dat X este imposibil din punct de vedere computațional să găsești asta

H (y) = H(x).

6. Este imposibil din punct de vedere computațional să găsiți o pereche arbitrară ( X , y ) astfel încât H(y) = H(x) .

Primele trei proprietăți necesită funcția hash pentru a produce un cod hash pentru orice mesaj.

A patra proprietate definește cerința ca funcția hash să fie unilaterală: este ușor să creați un cod hash dintr-un mesaj dat, dar este imposibil să reconstruiți mesajul dintr-un anumit cod hash. Această proprietate este importantă dacă autentificarea hash implică o valoare secretă. Este posibil ca valoarea secretă în sine să nu fie trimisă, totuși, dacă funcția hash nu este unidirecțională, un adversar poate dezvălui cu ușurință valoarea secretă, după cum urmează. Când o transmisie este interceptată, atacatorul primește un mesaj M și cod hash C = H (SAB || M) . Dacă un atacator poate inversa funcția hash, atunci el poate obține SAB || M=H-1(C) . Din moment ce atacatorul știe acum și M Și SAB || M , obține SAB destul de simplu.

A cincea proprietate asigură că este imposibil să găsiți un alt mesaj a cărui valoare hash se potrivește cu valoarea hash a acestui mesaj. Acest lucru previne falsificarea autentificatorului atunci când utilizați un cod hash criptat. În acest caz, adversarul poate citi mesajul și, prin urmare, își poate crea codul hash. Dar, din moment ce adversarul nu are cheia secretă, el nu are cum să schimbe mesajul fără ca destinatarul să-l detecteze. Dacă această proprietate nu este satisfăcută, atacatorul are posibilitatea de a efectua următoarea secvență de acțiuni: interceptarea mesajului și codul hash criptat al acestuia, calcularea codului hash al mesajului, crearea unui mesaj alternativ cu același cod hash, înlocuirea originalului mesaj cu unul fals. Deoarece hashurile acestor mesaje sunt aceleași, destinatarul nu va detecta falsificarea.

O funcție hash care satisface primele cinci proprietăți se numește funcție hash simplă sau slabă. Dacă în plus a șasea proprietate este îndeplinită, atunci o astfel de funcție se numește funcție hash puternică. A șasea proprietate protejează împotriva unei clase de atacuri cunoscute sub numele de atacul zilei de naștere.

5. Funcții hash simple

Toate funcțiile hash sunt efectuate după cum urmează. Valoarea de intrare (mesaj, fișier etc.) este considerată ca o secvență n -blocuri de biți. Valoarea de intrare este procesată secvenţial bloc cu bloc şi a m -bit valoarea codului hash.

Unul dintre cele mai simple exemple de funcție hash este să XOR fiecare bloc pe biți:

Cu i - i Al doilea bit din codul hash, 1 <= i <= n .

k - număr n -blocuri de intrare de biți.

b ij – i al-lea înăuntru j - al-lea bloc.

Întregul mesaj este apoi criptat, inclusiv codul hash, în modul CBC pentru a crea blocuri criptate Y1, Y2, ..., YN+1. Prin definiția SHS avem:

Dar XN+1 este un cod hash:

Deoarece termenii din egalitatea anterioară pot fi evaluați în orice ordine, codul hash nu va fi modificat dacă blocurile criptate sunt rearanjate.

Standardul original propus de NIST a folosit XOR simplu, care a fost aplicat blocurilor de mesaje pe 64 de biți, apoi întregul mesaj a fost criptat folosind modul CBC.

„Paradoxul zilei de naștere”

Înainte de a analiza funcții hash mai complexe, este necesar să analizăm un atac specific asupra funcțiilor hash simple.

Așa-numitul „paradox al zilei de naștere” este următorul. Să presupunem că numărul de valori de ieșire a funcției hash N egală n . Care ar trebui să fie numărul? k astfel încât pentru o anumită valoare X si valori Y1, ,Yk probabilitatea ca pentru cel puţin un Yi egalitatea

H(X) = H(Y)

ar fi mai mare de 0,5.

Pentru un Y probabilitatea ca H(X) = H(Y) , este egal 1/n .

În consecință, probabilitatea ca , este egal 1 – 1/n .

Dacă creezi k valori, atunci probabilitatea ca niciuna dintre ele să nu existe potriviri este egală cu produsul probabilităților corespunzătoare unei valori, adică. (1 – 1/n)k .

Prin urmare, probabilitatea de cel puțin o potrivire este

1 - (1 - 1/n)k

Astfel, am aflat că pt m -bit cod hash este suficient pentru a alege 2m-1 mesaje astfel încât probabilitatea de potrivire a codurilor hash este mai mare de 0,5.

Acum luați în considerare următoarea problemă: să notăm P(n,k) probabilitatea ca in multimea de k elemente, fiecare dintre ele poate lua n valori, există cel puțin două cu aceleași valori. Cu ce ar trebui să fie egal? k , la P(n,k) ar fi mai mult 0,5 ?

Numărul de moduri diferite de a selecta elementele astfel încât să nu existe duplicate este egal cu

n(n-1) ... (n-k+1)=n!/(n-k)!

Totalul modalităților posibile de selectare a elementelor este n k

Probabilitatea ca să nu existe duplicate este egală cu n!/(n-k)!n k

Probabilitatea ca să existe duplicate este egală în mod corespunzător cu

1 - n!/(n-k)!nk P(n, k) = 1 - n! / ((n-k)! x nk) = 1 - (n x (n-1) x ... x (n-k-1)) / nk = 1 - [ (n-1)/n x (n-2)/n x ... x (n-k+1)/n] = 1 - [(1- 1/n) x (1 - 2/n) x ... x (1 - (k-1)/n)]

Dacă codul hash are lungime m un pic, adică acceptă 2m valori, atunci

Acest rezultat se numește „paradoxul zilei de naștere” deoarece, conform raționamentului de mai sus, pentru ca probabilitatea ca două persoane să aibă aceeași zi de naștere să fie mai mare de 0,5, trebuie să existe doar 23 de persoane în grup. Acest rezultat pare surprinzător, poate pentru că pentru orice individ dintr-un grup, probabilitatea ca ziua lui să fie aceeași cu ziua de naștere a altcuiva din grup este destul de mică.

Să revenim la luarea în considerare a proprietăților funcțiilor hash. Să presupunem că se folosește un cod hash de 64 de biți. Putem considera că aceasta este o lungime suficientă și, prin urmare, sigură pentru un cod hash. De exemplu, dacă codul hash criptat CU transmis cu mesajul necriptat corespunzător M , atunci inamicul va trebui să găsească M' astfel încât

N (M") = N (M) ,

pentru a înlocui mesajul și a înșela destinatarul. În medie, un adversar trebuie să caute prin 263 de mesaje pentru a găsi unul al cărui cod hash este egal cu mesajul interceptat.

Cu toate acestea, sunt posibile diferite tipuri de atacuri bazate pe paradoxul zilei de naștere. Următoarea strategie este posibilă:

1. Inamicul creează 2 m/2 opțiuni de mesaj, fiecare dintre ele având o anumită semnificație. Adversarul pregătește același număr de mesaje, fiecare dintre ele false și menite să înlocuiască mesajul real.

2. Cele două seturi de mesaje sunt comparate pentru a găsi o pereche de mesaje care au același cod hash. Probabilitatea de succes conform „paradoxului zilei de naștere” este mai mare de 0,5. Dacă o pereche potrivită nu este găsită, atunci sunt create mesaje suplimentare originale și false până când este găsită o pereche.

3. Atacatorul oferă expeditorului versiunea originală a mesajului pentru semnătură. Această semnătură poate fi apoi atașată la versiunea contrafăcută pentru a fi transmisă destinatarului. Deoarece ambele opțiuni au același cod hash, va fi creată aceeași semnătură. Inamicul va avea încredere în succes chiar și fără a cunoaște cheia de criptare.

Astfel, dacă se folosește un cod hash pe 64 de biți, complexitatea de calcul necesară este de ordinul a 232.

În cele din urmă, rețineți că lungimea codului hash trebuie să fie suficient de mare. O lungime de 64 de biți nu este considerată în prezent sigură. Este de preferat ca lungimea să fie de ordinul a 100 de biți.

Folosind un lanț de blocuri criptat

Există diverse funcții hash bazate pe crearea unui lanț de blocuri criptate, dar fără a utiliza o cheie secretă. O astfel de funcție hash a fost propusă de Rabin. Mesaj M este împărțit în blocuri de lungime fixă M1, M2, . . . , MN și utilizează un algoritm de criptare simetric, cum ar fi DES, pentru a calcula codul hash G in felul urmator:

H 0 - valoarea initiala N i = E Mi G = H N

Acest lucru este similar cu utilizarea criptării CBC, dar în acest caz nu există o cheie secretă. Ca și în cazul oricărei funcție hash simplă, acest algoritm este susceptibil la un „atac de naștere”, iar dacă algoritmul de criptare este DES și este generat doar un cod hash de 64 de biți, atunci sistemul este considerat destul de vulnerabil.

Pot fi efectuate și alte atacuri de naștere, care sunt posibile chiar dacă adversarul are acces doar la un mesaj și codul hash criptat corespunzător și nu poate obține mai multe perechi de mesaje și coduri hash criptate. Următorul scenariu este posibil: să presupunem că un adversar a interceptat un mesaj cu un autentificator sub forma unui cod hash criptat și se știe că codul hash necriptat are lungimea m biți În continuare, inamicul trebuie să efectueze următoarele acțiuni:

· Folosind algoritmul descris mai sus, calculați codul hash necriptat G .

· Creați un mesaj fals în formular Q1, Q2,. . . , QN-2 .

· Calculati N i = E Qi Pentru 1 <= i <= N-2 .

· Crea 2 m/2 blocuri aleatorii X iar pentru fiecare astfel de bloc X calculati E X . Creați suplimentar 2 m/2 bloc aleatoriu Y si pentru fiecare bloc Y calculati D Y [G] , Unde D – funcţia de decodare corespunzătoare E . Pe baza paradoxului zilei de naștere, este foarte probabil ca această secvență să conțină blocuri X Și Y astfel încât E X = D Y [Y] .

· Creați un mesaj Q1, Q2,. . . , QN-2, X, Y . Acest mesaj are un cod hash G și, prin urmare, poate fi utilizat împreună cu un autentificator criptat.

Această formă de atac este cunoscută sub numele de atac „întâlnire la mijloc”. Diverse studii propun metode mai subtile pentru a îmbunătăți abordarea bazată pe blockchain. De exemplu, Davis și Price au descris următoarele:

O altă opțiune este posibilă:

Cu toate acestea, ambele scheme au și vulnerabilități la diferite atacuri. Mai general, se poate demonstra că o anumită formă de atac de naștere reușește cu orice algoritm hash care implică utilizarea unui lanț de blocuri criptate fără a utiliza o cheie secretă.

Cercetările ulterioare au vizat găsirea altor abordări pentru crearea funcțiilor de hashing.

Funcția hash MD5

Luați în considerare algoritmul de rezumare a mesajelor MD5 (RFC 1321) dezvoltat de Ron Rivest de la MIT.

Logica de execuție MD5

Algoritmul primește un mesaj de lungime arbitrară ca intrare și produce un rezumat al mesajului de 128 de biți ca ieșire. Algoritmul constă din următorii pași:

Orez. 8.1. Logica de execuție MD5

Pasul 1: Adăugați biți lipsă

Mesajul este completat astfel încât lungimea sa devine 448 modulo 512(). Aceasta înseamnă că lungimea mesajului atașat este cu 64 de biți mai mică decât un multiplu de 512. Adăugarea se face întotdeauna, chiar dacă mesajul are lungimea corectă. De exemplu, dacă un mesaj are 448 de biți, acesta este umplut cu 512 biți pentru a-l face de 960 de biți. Astfel, numărul de biți adăugați variază de la 1 la 512.

Adunarea constă dintr-un unu urmat de numărul necesar de zerouri.

Pasul 2: Adăugați lungimea

O reprezentare pe 64 de biți a lungimii mesajului original (înainte de adăugare) în biți este atașată la rezultatul primului pas. Dacă lungimea inițială este mai mare de 2 64 , atunci sunt utilizați numai ultimii 64 de biți. Astfel, câmpul conține lungimea mesajului original modulo 2 64.

Primii doi pași produc un mesaj a cărui lungime este un multiplu de 512 biți. Acest mesaj extins este reprezentat ca o secvență de blocuri de 512 biți Y 0 , Y 1 , . . ., Y L-1, cu lungimea totală a mesajului extins fiind L * 512 biți. Astfel, lungimea mesajului extins primit este un multiplu de șaisprezece cuvinte pe 32 de biți.

Orez. 8.2. Structura extinsă a mesajelor

Pasul 3: Inițializarea MD Buffer

Un buffer de 128 de biți este utilizat pentru a stoca rezultatele intermediare și finale ale funcției hash. Bufferul poate fi reprezentat ca patru registre de 32 de biți (A, B, C, D). Aceste registre sunt inițializate cu următoarele numere hexazecimale:

A = 01234567 B = 89ABCDEF C = FEDCBA98 D = 76543210

Pasul 4: Procesați o secvență de blocuri de 512 biți (16 cuvinte).

Baza algoritmului este un modul format din patru procesări ciclice, denumite HMD5. Cele patru bucle au o structură similară, dar fiecare buclă utilizează o funcție logică elementară diferită, notată f F , f G , f H și, respectiv, f I .

Orez. 8.3. Se procesează următorul bloc de 512 biți

Fiecare buclă ia ca intrare blocul curent de 512 de biți Y q în curs de procesare și valoarea de 128 de biți a tamponului ABCD, care este valoarea intermediară de digest, și modifică conținutul acelui buffer. Fiecare buclă folosește, de asemenea, un sfert din tabelul de 64 de elemente T, construit din funcția sin. I-lea element al lui T, notat T[i], are o valoare egală cu partea întreagă a lui 2 32 * abs (sin (i)), i dat în radiani. Deoarece abs(sin(i)) este un număr între 0 și 1, fiecare element al lui T este un număr întreg care poate fi reprezentat prin 32 de biți. Tabelul oferă un set „aleatoriu” de valori pe 32 de biți care ar trebui să elimine orice regularitate în datele de intrare.

Pentru a obține MD q+1, ieșirea celor patru bucle este adăugată modulo 2 32 la MD q . Adăugarea este efectuată independent pentru fiecare dintre cele patru cuvinte din buffer.

F este una dintre funcțiile elementare f F , f G , f H , f I .

O matrice de cuvinte X pe 32 de biți conține valoarea blocului de intrare curent de 512 biți care este procesat în prezent. Fiecare buclă este executată de 16 ori și, deoarece fiecare bloc de mesaje de intrare este procesat în patru bucle, fiecare bloc de mesaje de intrare este procesat conform schemei prezentate în Fig. 4, 64 de ori. Dacă ne gândim la un bloc de intrare de 512 de biți ca fiind șaisprezece cuvinte de 32 de biți, atunci fiecare cuvânt de intrare de 32 de biți este folosit de patru ori, o dată în fiecare ciclu, și fiecare element al tabelului T, constând din 64 de cuvinte de 32 de biți, este folosit o singura data. După fiecare pas al buclei, cele patru cuvinte A, B, C și D sunt rotite spre stânga La fiecare pas, doar unul dintre cele patru cuvinte ale tamponului ABCD este schimbat. Prin urmare, fiecare cuvânt al bufferului este modificat de 16 ori și apoi a 17-a oară la sfârșit pentru a produce rezultatul final al blocului respectiv.

digera.

2. Viteză: implementarea software a algoritmului trebuie să fie suficient de rapidă. În special, algoritmul trebuie să fie suficient de rapid pe o arhitectură pe 32 de biți. Prin urmare, algoritmul se bazează pe un set simplu de operații elementare pe cuvinte de 32 de biți.

3. Simplitate și compactitate: algoritmul trebuie să fie simplu de descris și simplu de programat, fără programe mari sau tabele de substituție. Aceste caracteristici nu numai că au avantaje software evidente, ci sunt și de dorit din punct de vedere al securității deoarece este mai bine să existe un algoritm simplu pentru a analiza eventualele puncte slabe.

4. Arhitectura Little-endian este de dorit: Unele arhitecturi de procesor (cum ar fi linia Intel 80xxx) stochează octeții din partea stângă ai unui cuvânt în poziția adresei octet little-endian. Alții (cum ar fi SUN Sparcstation) stochează octeții din dreapta cuvântului în poziția adresei octeților mici (nu este utilizată constanta suplimentară mare MD4 în prima buclă. 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ă. Codul hash este o funcție a fiecărui bit al intrării este bine amestecat, adică este puțin probabil ca două mesaje să fie alese la întâmplare, chiar dacă sunt în mod clar similare modele care produc aceeași valoare de ieșire rezultă aceeași ieșire pentru două valori de intrare diferite în tamponul ABCD. Nu există nicio modalitate de a extinde această abordare la un atac de succes.

Sau Funcția hash este funcția, transformă datele de intrare de orice dimensiune (de obicei mare) în date de dimensiune fixă. Hashing(Uneori G Yeshuvanya, engleză hashing)— transformarea unui tablou de date de intrare de lungime arbitrară într-un șir de biți de ieșire de lungime fixă. Astfel de transformări mai sunt numite funcții hash sau funcții de convoluție, iar rezultatele lor se numesc hash, cod hash suma hash, sau rezumatul mesajului(Engleză) Rezumat mesaj).

Funcția hash este utilizată în special în structurile de date - tabele hash și este utilizată pe scară largă în software-ul pentru preluarea rapidă a datelor. Funcțiile hash sunt utilizate pentru a optimiza tabelele și bazele de date, asigurându-se că înregistrările identice au aceeași valoare hash. Această abordare de a găsi duplicate este eficientă în fișierele mari. Un exemplu în acest sens este găsirea unor regiuni similare în secvențele de ADN. O funcție hash criptografică facilitează verificarea faptului că o anumită intrare se potrivește cu o anumită valoare hash, dar dacă intrarea este necunoscută, este intenționat dificil să reconstruiți valoarea de intrare (sau o alternativă echivalentă) cunoscând valoarea hash stocată. Acesta este utilizat pentru a asigura integritatea datelor transmise și este elementul de bază pentru HMAC-urile care oferă autentificarea mesajelor.

Funcțiile hash sunt legate de (și adesea confundate cu) sume, cifre de verificare, amprente, funcții de randomizare, coduri de corectare a erorilor și cifruri. Deși aceste concepte se suprapun într-o oarecare măsură, fiecare are propriul domeniu de aplicare și cerințe și este proiectat și optimizat diferit.

Poveste

Donald Knuth îi atribuie prima idee sistematică de hashing angajatului IBM Hans Peter Luhn, care a propus hashul în ianuarie 1953.

În 1956, Arnold Duma, în lucrarea sa Computers and Automation, a fost primul care a introdus conceptul de hashing așa cum îl cunosc majoritatea programatorilor astăzi. Duma a considerat hashingul ca o soluție la „Problema dicționarului” și a propus, de asemenea, utilizarea restului împărțirii printr-un număr prim ca adresă hash.

Prima lucrare semnificativă care s-a ocupat de căutarea fișierelor mari a fost articolul lui Wesley Peterson în Jurnalul IBM de Cercetare și Dezvoltare 1957 în care a definit adresarea deschisă și, de asemenea, a subliniat degradarea performanței adresei de la distanță. Șase ani mai târziu, a fost publicată lucrarea lui Werner Buchholz, care a explorat în mare măsură funcțiile hash. În următorii câțiva ani, hashingul a fost utilizat pe scară largă, dar nu a fost publicată nicio lucrare semnificativă.

În 1967, hashingul în sensul modern a fost menționat în cartea Principles of Digital Computing Systems de Herbert Hellerman. În 1968, Robert Morris a publicat în Comunicările ACM excelentă prezentare generală despre hashing. Această lucrare este considerată o publicație care introduce conceptul de hashing în circulația științifică și în final consolidează termenul de „haș” în rândul specialiștilor.

La începutul anilor 1990, echivalentul termenului „hashing”, datorită lucrării lui Andrei Ershov, era cuvântul „aranjament” (rusă), iar pentru coliziuni era folosit termenul „conflict” (rusă) (Ershov folosea „aranjamente” din 1956, precum și în ediția în limba rusă a cărții lui Niklaus Wirth „Algoritmi și structuri de date” (1989) acest termen nu este folosit. Cu toate acestea, niciuna dintre aceste opțiuni nu a luat rădăcini, iar în literatură termenul „ hashing” este utilizat în principal.

Descriere

Hashingul este folosit pentru a construi matrice asociative, pentru a căuta duplicate într-o serie de seturi de date, pentru a construi identificatori unici pentru seturile de date, pentru a verifica sumele pentru a identifica erori accidentale sau intenționate în timpul stocării sau transmisiei, pentru a stoca parole în sistemele de securitate (în acest caz, accesul la o zonă de memorie „memorie, în care se află parolele, nu vă permite să recuperați parola în sine), atunci când generați o semnătură electronică (în practică, adesea nu mesajul în sine este semnat, ci imaginea lui hash).

În general, nu există o corespondență unu-la-unu între datele sursă și codul hash datorită faptului că numărul de valori ale funcției hash este mai mic decât numărul de valori variante ale matricei de intrare. Există multe matrice cu conținut diferit, dar dau aceleași coduri hash - așa-numitele coliziuni. Probabilitatea de coliziuni joacă un rol important în evaluarea calității funcțiilor hash.

Există mulți algoritmi de hashing cu proprietăți diferite (capacitate de biți, complexitate de calcul, putere criptografică etc.). Alegerea uneia sau alteia funcții hash este determinată de specificul problemei care se rezolvă. Cele mai simple exemple de funcții hash sunt o sumă de control sau CRC.

Tipuri de funcții hash

O funcție hash bună trebuie să îndeplinească două proprietăți:

să fie calculat rapid;
Minimizați numărul de ciocniri

Să presupunem, pentru claritate, numărul de chei, iar funcția hash nu are mai mult decât valori diferite:

Un exemplu de funcție hash „proastă” este funcția c, care se potrivește unui număr natural de zece cifre cu trei cifre alese din mijlocul pătratului de douăzeci de cifre al numărului. S-ar părea că valorile codului hash ar trebui să fie distribuite uniform între „000” și „999”, dar pentru datele reale această metodă este potrivită numai dacă cheile nu au un număr mare de zerouri la stânga sau la dreapta.

Cu toate acestea, există câteva alte metode simple și de încredere pe care se bazează multe funcții hash.

Funcții hash bazate pe diviziuni

Prima metodă este că folosim ca hash restul împărțirii prin, unde este numărul tuturor hashurilor posibile:

În același timp, este evident că la o pereche, modul de salvare este asociat, cu o pereche. Și impar - când impar, ceea ce poate duce la o schimbare semnificativă a datelor din fișiere. De asemenea, nu ar trebui să utilizați sistemul de numere al unui computer ca bază, deoarece hash-ul va depinde doar de câteva cifre ale numărului situat în dreapta, ceea ce va duce la un număr mare de coliziuni. În practică, de obicei o aleg pe cea simplă - în majoritatea cazurilor această alegere este destul de satisfăcătoare.

Ar trebui spus altceva despre metoda hashing, care se bazează pe împărțirea la un log modulo doi. În această metodă, trebuie să fie și o putere de doi, iar cheile binare () au forma de polinoame. În acest caz, codul hash este luat ca valorile coeficienților polinomului obținuți ca rest de împărțire printr-un polinom de grad preselectat:

Dacă este aleasă corect, această metodă garantează absența coliziunilor între taste aproape identice.

Schema de hashing multiplicativ

A doua metodă este de a selecta o constantă întreagă coprime la, unde este numărul de valori posibile sub forma unui cuvânt de mașină (în computerele IBM PC). Apoi putem lua o funcție hash de forma:

În acest caz, pe un computer cu un sistem de numere binar, este o putere de doi și constă din cei mai semnificativi biți din jumătatea dreaptă a produsului.

Printre avantajele acestor două metode, este de remarcat faptul că ele profită de faptul că cheile reale sunt non-aleatorie. De exemplu, dacă tastele reprezintă o progresie aritmetică (să spunem succesiunea de nume „nume1”, „nume2”, „nume3”). Metoda multiplicativă va mapa o progresie aritmetică într-o progresie aritmetică aproximativă a diferitelor valori hash, reducând numărul de coliziuni în comparație cu o situație aleatorie.

Una dintre variantele acestei metode este hashingul Fibonacci, bazat pe proprietățile raportului de aur. Valoarea aleasă aici este cea mai apropiată de întregul cu care este coprim

Hash-uri de șir de lungime variabilă

Metodele de mai sus se aplică și atunci când trebuie să luăm în considerare chei formate din mai multe cuvinte sau chei cu lungime variabilă. De exemplu, puteți combina cuvinte într-unul singur folosind adăugarea modulo sau adăugarea modulo 2. Unul dintre algoritmii care funcționează pe acest principiu este funcția hash Pearson.

Hashingul Pearson este un algoritm propus de Peter Pearson. Peter Pearson) pentru procesoarele cu registre de 8 biți, a căror sarcină este să calculeze rapid un cod hash pentru un șir de lungime arbitrară. Funcția primește ca intrare un cuvânt format din caractere, fiecare câte 1 octet și returnează o valoare în intervalul de la 0 la 255. Valoarea codului hash depinde de fiecare caracter al cuvântului de intrare.

Algoritmul poate fi descris de următorul pseudocod, care ia un șir ca intrare și utilizează un tabel de permutare

h:=0 Pentru fiecare c în W buclă indice:= h xor ch:=T Sfârșit bucla Întoarcere h

Printre avantajele algoritmului trebuie remarcat:

ușurință de calcul;
nu există date de intrare pentru care probabilitatea de coliziune este cea mai mare;
posibilitatea de modificare într-o funcție hash ideală.

Ca o modalitate alternativă la cheile hash constând din simboluri (), se pot propune calculele

Utilizarea funcțiilor hash

Funcțiile hash sunt utilizate pe scară largă în criptografie, precum și în multe structuri de date - tabele hash, filtre Bloom și arbori cartezieni.

Funcții hash criptografice

Printre numeroasele funcții hash existente, se obișnuiește să se distingă funcțiile hash puternice din punct de vedere criptografic utilizate în criptografie, deoarece le sunt impuse cerințe suplimentare. Pentru ca o funcție hash să fie considerată puternică din punct de vedere criptografic, trebuie să îndeplinească trei cerințe de bază, care stau la baza majorității utilizărilor funcțiilor hash în criptografie:

Ireversibilitate: pentru o valoare hash dată m Trebuie să fie imposibil din punct de vedere computațional să găsiți blocul de date pentru care.
Durabilitate ciocniri de primul fel: pentru un mesaj dat M trebuie să fie imposibil din punct de vedere computațional să găsești altul mesaj N, pentru care.
Durabilitate La ciocniri al doilea fel: Ar trebui să fie imposibil din punct de vedere computațional să găsiți perechi de mesaje care au același hash.

Aceste cerințe depind unele de altele:

Funcția inversă este instabilă la coliziunile de primul și al doilea fel.
O funcție care este instabilă la coliziuni de primul fel, instabilă la coliziuni de al doilea fel; inversul nu este adevărat.

De remarcat că nu a fost dovedită existența funcțiilor hash ireversibile, pentru care calcularea oricărei imagini inverse a unei valori hash date este teoretic imposibilă. De obicei, găsirea valorii inverse este doar o sarcină dificilă din punct de vedere computațional.

Atacul de ziua de naștere vă permite să găsiți coliziuni pentru o funcție hash cu lungimea valorilor n biți în medie pentru calcularea funcției hash. De aceea n — O funcție bit hash este considerată cripto dacă complexitatea de calcul a găsirii coliziunilor pentru aceasta este aproape de.

Pentru funcțiile hash criptografice, este de asemenea important ca, cu cea mai mică modificare a argumentului, valoarea funcției să se modifice foarte mult (efect de avalanșă). În special, valoarea hash nu trebuie să scurgă informații, chiar și despre biți individuali ai argumentului. Această cerință este cheia pentru puterea criptografică a algoritmilor de hashing care codifică parola utilizatorului pentru a obține cheia.

Hashing-ul este adesea folosit în algoritmii de semnătură digitală, unde nu mesajul în sine este criptat, ci hash-ul său, care reduce timpul de calcul și, de asemenea, crește puterea criptografică. De asemenea, în majoritatea cazurilor, în loc de parole, sunt stocate valorile codurilor hash ale acestora.

Hashing geometric

Hashing geometric hashing geometric) este o metodă utilizată pe scară largă în grafica computerizată și geometria computațională pentru rezolvarea problemelor pe un plan sau în spațiu tridimensional, de exemplu, pentru a găsi cele mai apropiate perechi într-un set de puncte sau pentru a găsi imagini identice. Funcția hash din această metodă ia de obicei ca intrare un spațiu metric și îl împarte, creând o grilă de celule. Tabelul în acest caz este o matrice cu doi sau mai mulți indecși și se numește fișier grid. fișier grilă). Hashingul geometric este folosit și în telecomunicații atunci când se ocupă cu semnale multidimensionale.

Accelerează recuperarea datelor

Un tabel hash este o structură de date care vă permite să stocați perechi de formular (cheie, cod hash) și acceptă operațiuni de căutare, inserare și ștergere de elemente. Scopul tabelelor hash este de a accelera căutările, de exemplu, în cazul înregistrărilor în câmpuri text dintr-o bază de date, codul hash al acestora poate fi calculat și datele pot fi plasate într-o secțiune corespunzătoare acestui cod hash. Apoi, atunci când căutați date, va trebui mai întâi să calculați hash-ul textului și veți ști imediat în ce secțiune trebuie să îl căutați, adică va trebui să căutați nu în întreaga bază de date, ci numai în una dintre secțiunile sale (acest lucru accelerează foarte mult căutarea).

Un analog comun al hashingului în acest caz poate fi plasarea cuvintelor în dicționar în ordine alfabetică. Prima literă a unui cuvânt este codul său hash, iar atunci când căutăm, nu ne uităm prin întregul dicționar, ci doar litera dorită.

Și așa mai departe.). Alegerea uneia sau alteia funcții hash este determinată de specificul problemei care se rezolvă. Cele mai simple exemple de funcții hash sunt suma de control sau CRC.

În general, nu există o corespondență unu-la-unu între datele sursă și codul hash. Prin urmare, există multe seturi de date care dau aceleași coduri hash - așa-numitele coliziuni. Probabilitatea de coliziuni joacă un rol important în evaluarea „calității” funcțiilor hash.

Sume de control

Necomplicat, extrem de rapid și ușor de implementat în algoritmii hardware utilizați pentru a proteja împotriva distorsiunilor neintenționate, inclusiv a erorilor hardware.

Viteza de calcul este de zeci și sute de ori mai rapidă decât funcțiile hash criptografice și mult mai simplă în implementarea hardware.

Prețul pentru o viteză atât de mare este lipsa puterii criptografice - o oportunitate ușoară de a ajusta mesajul la o sumă precunoscută. De asemenea, sumele de control (tipic: 32 de biți) sunt de obicei mai mici în lățime decât hashurile criptografice (tipic: 128, 160 și 256 de biți), ceea ce înseamnă că pot apărea coliziuni neintenționate.

Cel mai simplu caz al unui astfel de algoritm este împărțirea unui mesaj în cuvinte de 32 sau 16 biți și însumarea acestora, care este folosit, de exemplu, în TCP/IP.

De regulă, un astfel de algoritm este necesar pentru a urmări erorile hardware tipice, cum ar fi câțiva biți eronați consecutivi la o lungime dată. Așa-numita familie de algoritmi „cod de redundanță ciclică” îndeplinește aceste cerințe. Acestea includ, de exemplu, CRC32, utilizat în echipamentele ZIP.

Funcții hash criptografice

Printre multele funcții hash existente, este obișnuit să se distingă funcțiile hash puternice din punct de vedere criptografic utilizate în criptografie. O funcție hash rezistentă la cripto trebuie să aibă în primul rând rezistent la coliziune doua tipuri:

Folosind hashing

Funcțiile hash sunt, de asemenea, folosite în unele structuri de date - tabele hash și arbori cartezieni. Cerințele pentru funcția hash în acest caz sunt diferite:

mixabilitate bună a datelor
algoritm de calcul rapid

Reconcilierea datelor

În general, această aplicație poate fi descrisă ca verificarea unor informații pentru a fi identice cu originalul, fără a utiliza originalul. Pentru reconciliere, se folosește valoarea hash a informațiilor care sunt verificate. Există două domenii principale ale acestei aplicații:

Verificarea erorilor

De exemplu, suma de control poate fi transmisă prin canalul de comunicare împreună cu textul principal. La capătul de recepție, suma de control poate fi recalculată și comparată cu valoarea transmisă. Dacă este detectată o discrepanță, aceasta înseamnă că a apărut o distorsiune în timpul transmisiei și poate fi solicitată o repetare.

Un analog de uz casnic al hashingului în acest caz poate fi tehnica atunci când, la mutare, numărul de bagaje este păstrat în memorie. Apoi, pentru a verifica, nu trebuie să vă amintiți despre fiecare valiză, ci doar să le numărați. Un meci va însemna că nicio valiză nu este pierdută. Adică, numărul de bagaje este codul său hash.

Verificarea frazei de acces

În cele mai multe cazuri, frazele de acces nu sunt stocate pe ținte, sunt stocate doar valorile hash ale acestora. Nu este recomandabil să stocați fraze de acces, deoarece în cazul accesului neautorizat la un fișier cu fraze, atacatorul va afla toate frazele de acces și le va putea folosi imediat, iar la stocarea valorilor hash, va învăța doar valorile hash. care nu sunt reversibile în datele originale, în acest caz, expresie de acces. În timpul procedurii de autentificare, valoarea hash a frazei de acces introduse este calculată și comparată cu cea salvată.

Un exemplu în acest caz ar fi GNU/Linux și Microsoft Windows XP. Ele stochează doar valori hash ale frazelor de acces din conturile de utilizator.

Accelerează recuperarea datelor

De exemplu, atunci când câmpurile de text sunt scrise într-o bază de date, codul hash al acestora poate fi calculat și datele pot fi plasate într-o secțiune corespunzătoare acelui cod hash. Apoi, atunci când căutați date, va trebui mai întâi să calculați codul hash al textului și veți ști imediat în ce secțiune trebuie să îl căutați, adică va trebui să căutați nu în întreaga bază de date, ci numai într-o secțiune a acesteia (acest lucru accelerează foarte mult căutarea).

Un analog comun al hashingului în acest caz poate fi plasarea cuvintelor într-un dicționar în ordine alfabetică. Prima literă a unui cuvânt este codul său hash, iar atunci când căutăm, nu ne uităm prin întregul dicționar, ci doar litera dorită.

Lista de algoritmi

SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512)
RIPEMD-160
RIPEMD-320
Snefru
Tigru (Vârtej
Sumă de verificare IP Internet (RFC 1071)

Legături

Fundația Wikimedia. 2010.

Heshan Moheyan
Cod hash

Vedeți ce este o „funcție Hash” în alte dicționare:

Funcția hash- o funcție care realizează hashingul unei matrice de date prin maparea valorilor dintr-un set (foarte) mare de valori într-un set (substanțial) mai mic de valori. În engleză: Funcția Hash Vezi și: Algoritmi criptografici Financiar... ... Dicţionar financiar

funcția hash criptografică- O funcție care convertește text de lungime arbitrară în text de lungime fixă (în majoritatea cazurilor mai mică). Aplicația principală a funcțiilor hash este în schema de semnătură digitală. Deoarece funcția hash este calculată mai rapid decât o semnătură digitală, atunci în loc de... ...

Funcție hash într-un singur sens- funcția hash, care este o funcție ireversibilă din punct de vedere computațional. În engleză: Funcția hash unidirecțională Vezi și: Algoritmi criptografici Dicționar financiar Finam... Dicţionar financiar

TIGER - funcție hash- Funcția hash TIGER dezvoltată de Ros Anderson și Eli Beham în 1996. Funcția de hash TIGER este o nouă funcție de hash rapidă care este concepută pentru a fi foarte rapidă pe computerele moderne, în special pe computerele pe 64 de biți. TIGRU...... Wikipedia

funcția hash unidirecțională- Pentru o funcție unidirecțională, este imposibil din punct de vedere computațional să găsiți două argumente diferite pentru care valorile sale sunt aceleași. [] Subiecte securitatea informațiilor RO funcția hash unidirecțională... Ghidul tehnic al traducătorului

Tigru (funcție hash)- Funcția Tiger hash dezvoltată de Ros Anderson și Eli Beham în 1995. Tiger a fost conceput pentru a rula foarte rapid pe computere pe 64 de biți. Tiger nu are restricții de brevet, poate fi folosit liber cu... ... Wikipedia

funcția hash- funcția hash 1. O funcție care controlează procesul de introducere a datelor într-un tabel hash, determinând (adresele celulelor libere. 2. O funcție care reprezintă o mapare a unui fragment dintr-un mesaj deschis într-un șir criptat de lungime fixă. În ...... Ghidul tehnic al traducătorului

Tabel de hash- În programare, un tabel hash este o structură de date care implementează interfața matrice asociativă, și anume, vă permite să stocați perechi (cheie, valoare) și să efectuați trei operații: operația de adăugare a unei noi perechi, operația de căutare și ștergerea operațiune... Wikipedia

Cod hash- Conversia hashing (uneori hashing, hashing în engleză) a unei matrice de date de intrare de lungime arbitrară într-un șir de biți de ieșire de lungime fixă. Astfel de transformări sunt numite și funcții hash sau funcții de convoluție, iar rezultatele lor... ... Wikipedia

Ciocnirea funcției hash- O coliziune cu funcția hash H este două blocuri de date de intrare diferite x și y astfel încât H(x) = H(y). Coliziuni există pentru majoritatea funcțiilor hash, dar pentru funcțiile hash „bune” frecvența apariției lor este aproape de minimul teoretic. În... ... Wikipedia

12 mai 2010 la 01:28

Algoritmi hash

Securitatea informațiilor

După cum cred, mulți oameni știu că din 2007, Institutul Național de Standarde și Tehnologie din SUA (NIST) a organizat o competiție pentru a dezvolta un algoritm hash care să înlocuiască SHA-1 și o familie de algoritmi SHA-2. Cu toate acestea, din anumite motive, acest subiect a fost neglijat pe site. Acesta este de fapt ceea ce m-a adus la tine. Vă aduc în atenție o serie de articole dedicate algoritmilor hash. În această serie, vom studia împreună elementele de bază ale funcțiilor hash, vom lua în considerare cei mai faimoși algoritmi de hash, vom plonja în atmosfera competiției SHA-3 și vom lua în considerare algoritmii care pretind că o câștigă și cu siguranță îi vom testa. De asemenea, dacă este posibil, vor fi luate în considerare standardele rusești de hashing.

Despre mine

Student al Departamentului de Securitate Informațională.

Despre hashing

În zilele noastre, practic nicio aplicație de criptare nu este completă fără utilizarea hashingului.
Funcțiile hash sunt funcții concepute pentru a „comprima” un mesaj arbitrar sau un set de date, de obicei scris în alfabet binar, într-un model de biți cu lungime fixă numit convoluție. Funcțiile hash au o varietate de aplicații atunci când efectuează experimente statistice, testează dispozitive logice și construiesc algoritmi pentru căutări rapide și verificarea integrității înregistrărilor din bazele de date. Principala cerință pentru funcțiile hash este distribuția uniformă a valorilor lor atunci când valorile argumentului sunt selectate aleatoriu.
O funcție hash criptografică este orice funcție hash care este stabilă criptografic, adică satisface o serie de cerințe specifice aplicațiilor criptografice. În criptografie, funcțiile hash sunt utilizate pentru a rezolva următoarele probleme:
- construirea de sisteme de monitorizare a integrității datelor în timpul transmiterii sau stocării acestora;
- autentificarea sursei de date.

Orice funcție se numește funcție hash h:X -> Y, ușor de calculat și astfel încât pentru orice mesaj M sens h(M) = H (convoluție) are o lungime fixă a biților. X- set de toate mesajele, Y- un set de vectori binari de lungime fixă.

De regulă, funcțiile hash sunt construite pe baza așa-numitelor funcții de compresie într-un singur pas y = f(x 1 , x 2) două variabile, unde x 1, x 2Și y- vectori binari de lungime m, nȘi nîn consecință, și n este lungimea circumvoluției și m- lungimea blocului de mesaje.
Pentru a obține valoarea h(M) mesajul este mai întâi împărțit în blocuri de lungime m(în același timp, dacă lungimea mesajului nu este multiplu m apoi ultimul bloc este suplimentat într-un mod special până când este complet), și apoi la blocurile rezultate M 1, M 2,..., M N aplicați următoarea procedură secvențială pentru calcularea convoluției:

H o = v,
H i = f(M i ,H i-1), i = 1,.., N,
h(M) = HN

Aici v- o constantă, numită adesea vector de inițializare. Ea iese
din diverse motive și poate fi o constantă secretă sau un set de date aleatorii (un eșantion de dată și oră, de exemplu).
Cu această abordare, proprietățile funcției hash sunt complet determinate de proprietățile funcției de compresie într-un singur pas.

Există două tipuri importante de funcții hash criptografice - cheie și fără cheie. Funcțiile hash cheie se numesc coduri de autentificare a mesajelor. Acestea fac posibilă, fără mijloace suplimentare, garantarea atât a corectitudinii sursei de date, cât și a integrității datelor în sisteme cu utilizatori care au încredere unii în alții.
Funcțiile hash fără cheie se numesc coduri de detectare a erorilor. Acestea fac posibilă garantarea integrității datelor folosind mijloace suplimentare (criptare, de exemplu). Aceste funcții hash pot fi utilizate în sistemele cu utilizatori atât de încredere, cât și de neîncredere.

Despre proprietăți și cerințe statistice

După cum am spus deja, principala cerință pentru funcțiile hash este distribuția uniformă a valorilor lor atunci când valorile argumentului sunt selectate aleatoriu. De asemenea, pentru funcțiile hash criptografice este important ca cea mai mică modificare a argumentului să facă ca valoarea funcției să se schimbe foarte mult. Acesta se numește efect de avalanșă.

Funcțiile de hashing cheie au următoarele cerințe:
- imposibilitatea de fabricare,
- imposibilitatea modificării.

Prima cerință înseamnă că este foarte dificil să găsești un mesaj cu valoarea de colaps corectă. A doua este complexitatea ridicată a selectării, pentru un mesaj dat cu o valoare de convoluție cunoscută, a unui alt mesaj cu valoarea de convoluție corectă.

Cerințele pentru funcțiile fără cheie sunt:
- unidirecționalitate,
- rezistenta la coliziune,
- rezistenta la gasirea unei a doua preimagine.

Unidirecționalitatea se referă la dificultatea mare de a găsi un mesaj pe baza unei valori de convoluție date. Trebuie remarcat faptul că în acest moment nu există funcții hash în uz cu unidirecționalitate dovedită.
Rezistența la coliziune se referă la dificultatea de a găsi o pereche de mesaje cu aceleași valori de convoluție. De obicei, descoperirea unei modalități prin care criptoanalistii pot construi coliziuni este primul semnal că algoritmul devine învechit și că trebuie înlocuit rapid.
Rezistența la găsirea unei a doua preimagine se referă la dificultatea de a găsi un al doilea mesaj cu aceeași valoare de convoluție pentru un mesaj dat cu o valoare de convoluție cunoscută.

Aceasta a fost partea teoretică, care ne va fi de folos în viitor...

Despre algoritmii hash populari

Algoritmi CRC16/32- sumă de control (nu conversie criptografică).

Algoritmi MD2/4/5/6. Sunt creația lui Ron Rivest, unul dintre autorii algoritmului RSA.
Algoritmul MD5 a fost cândva foarte popular, dar primele condiții preliminare pentru hacking au apărut la sfârșitul anilor 90, iar acum popularitatea sa este în scădere rapidă.
Algoritmul MD6 este un algoritm foarte interesant din punct de vedere al designului. A fost nominalizat la concursul SHA-3, dar, din păcate, autorii nu au avut timp să-l aducă la standard, iar acest algoritm nu se află pe lista candidaților care au trecut de turul doi.

Algoritmi de rigle SHA Algoritmi care sunt folosiți pe scară largă astăzi. Există o tranziție activă de la standardele versiunii SHA-1 la SHA-2. SHA-2 este numele colectiv pentru algoritmii SHA224, SHA256, SHA384 și SHA512. SHA224 și SHA384 sunt în esență analogi ai SHA256 și respectiv SHA512, numai după calcularea convoluției, o parte din informațiile din aceasta sunt aruncate. Acestea ar trebui folosite numai pentru a asigura compatibilitatea cu echipamentele modelelor mai vechi.

standard rusesc - GOST 34.11-94.

În articolul următor

Revizuirea algoritmilor MD (MD4, MD5, MD6).

Literatură

A. P. Alferov, Fundamentele criptografiei.

Bruce Schneier, Criptografie aplicată.

Și așa mai departe.). Alegerea uneia sau alteia funcții hash este determinată de specificul problemei care se rezolvă. Cele mai simple exemple de funcții hash sunt suma de control sau CRC.

Sume de control

Necomplicat, extrem de rapid și ușor de implementat în algoritmii hardware utilizați pentru a proteja împotriva distorsiunilor neintenționate, inclusiv a erorilor hardware.

Viteza de calcul este de zeci și sute de ori mai rapidă decât funcțiile hash criptografice și mult mai simplă în implementarea hardware.

Cel mai simplu caz al unui astfel de algoritm este împărțirea unui mesaj în cuvinte de 32 sau 16 biți și însumarea acestora, care este folosit, de exemplu, în TCP/IP.

Funcții hash criptografice

Folosind hashing

Funcțiile hash sunt, de asemenea, folosite în unele structuri de date - tabele hash și arbori cartezieni. Cerințele pentru funcția hash în acest caz sunt diferite:

mixabilitate bună a datelor
algoritm de calcul rapid

Reconcilierea datelor

Verificarea erorilor

Verificarea frazei de acces

Un exemplu în acest caz ar fi GNU/Linux și Microsoft Windows XP. Ele stochează doar valori hash ale frazelor de acces din conturile de utilizator.

Accelerează recuperarea datelor

Lista de algoritmi

SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512)
RIPEMD-160
RIPEMD-320
Snefru
Tigru (Vârtej
Sumă de verificare IP Internet (RFC 1071)

Legături

Fundația Wikimedia. 2010.

Vedeți ce este „Cod hash” în alte dicționare:

Cod hash- rezultatul unei combinații aritmetice cu toți octeții codului programului sau setului de date. Rezultatul algoritmului de hashing include doar câțiva octeți, iar algoritmul este proiectat în așa fel încât orice modificare a codului programului sau a datelor cu... ... Terminologie oficială

codul de autentificare a mesajului folosind o funcție hash- (ITU T N.235.3, ITU T N.235.1). Subiecte: telecomunicații, concepte de bază RO cod de autentificare a mesajelor hashedHMAC... Ghidul tehnic al traducătorului

În programare, un tabel hash este o structură de date care implementează interfața matrice asociativă, și anume, vă permite să stocați perechi (cheie, valoare) și să efectuați trei operații: operația de adăugare a unei noi perechi, operația de căutare și operația de ștergere. ... Wikipedia

MAC (codul de autentificare a mesajelor) este un mijloc de a oferi protecție împotriva imitației în protocoalele de autentificare a mesajelor cu participanți de încredere reciprocă, un set special de caractere care este adăugat la ... ... Wikipedia

Hashing (uneori hashing, hashing în engleză) este transformarea unei matrice de date de intrare de lungime arbitrară într-un șir de biți de ieșire de lungime fixă. Astfel de transformări sunt numite și funcții hash sau funcții de convoluție, iar rezultatele lor... ... Wikipedia

Acest articol este despre cod. Pentru metoda brainstorming, consultați cardul CRC. Verificarea redundanței ciclice (CRC) este un algoritm pentru calcularea unei sume de control conceput pentru a verifica integritatea... ... Wikipedia

- (Prescurtare pentru codul de autentificare a mesajelor bazat pe hash, codul hash de autentificare a mesajelor). A avea o modalitate de a verifica integritatea informațiilor transmise sau stocate într-un mediu care nu are încredere este o parte integrantă și necesară a lumii... ... Wikipedia

MI 2891-2004: Recomandare. GSOEI. Cerințe generale pentru software-ul instrumentelor de măsură- Terminologie MI 2891 2004: Recomandare. GSOEI. Cerințe generale pentru software-ul instrumentelor de măsurare: Informații de măsurare a datelor prezentate într-o formă adecvată pentru transmitere, interpretare sau prelucrare. Definițiile termenului din... ... Dicționar-carte de referință de termeni ai documentației normative și tehnice