Ciocnirea funcției hash

O coliziune cu funcția hash este două blocuri de date de intrare diferite și pentru o funcție hash astfel încât $X$ $y$ $H$ $H(x)=H(y).$

Coliziuni există pentru majoritatea funcțiilor hash, dar pentru funcțiile hash „bune”, frecvența apariției lor este apropiată de minimul teoretic. În unele cazuri speciale, când setul de date de intrare diferite este finit , este posibil să se definească o funcție hash injectivă , care, prin definiție, nu are coliziuni. Cu toate acestea, pentru funcțiile hash care preiau o intrare de lungime variabilă și returnează un hash de lungime constantă (cum ar fi MD5 ), trebuie să existe coliziuni, deoarece pentru cel puțin o valoare a funcției hash, setul corespunzător de date de intrare ( preimagine completă ) va fi infinit - și oricare două seturi de date din acest set formează o coliziune.

Exemplu

Luați în considerare ca exemplu o funcție hash definită pe mulțimea de numere întregi . Domeniul său de valori este format din 19 elemente ( inele de reziduuri modulo 19), iar domeniul său de definiție este infinit. Deoarece setul de preimagini este evident mai mare decât setul de valori, trebuie să existe coliziuni. $H(x)=x\ {\bmod \ }19$

Să construim o coliziune pentru această funcție hash pentru valoarea de intrare 38, a cărei sumă hash este zero. Deoarece funcția este periodică cu o perioadă de 19, pentru orice valoare de intrare y , valoarea y + 19 va avea aceeași sumă hash ca y . În special, pentru valoarea de intrare 38, valorile de intrare 57, 76 etc. vor avea aceeași sumă hash. Astfel, perechile de valori de intrare (38.57), (38.76) formează coliziuni cu funcția hash . $H(x)$ $H(x)$

Ciocniri ale funcției hash criptografice

Deoarece funcțiile hash criptografice sunt folosite pentru a confirma imuabilitatea informațiilor originale, abilitatea de a găsi rapid o coliziune pentru ele este de obicei echivalentă cu discreditarea . De exemplu, dacă o funcție hash este utilizată pentru a crea o semnătură digitală , atunci capacitatea de a găsi coliziuni pentru aceasta este de fapt echivalentă cu capacitatea de a falsifica o semnătură digitală. Prin urmare, măsura puterii criptografice a unei funcții hash este complexitatea de calcul a găsirii unei coliziuni. În mod ideal, nu ar trebui să existe o modalitate mai rapidă de a găsi coliziuni decât forța brută . Dacă pentru o anumită funcție hash există o modalitate de a obține coliziuni care este mult mai rapidă decât căutarea exhaustivă, atunci această funcție hash nu mai este considerată criptorezistentă și nu mai este folosită pentru transmiterea și stocarea informațiilor secrete. Problemele teoretice și practice ale găsirii și utilizării coliziunilor sunt discutate anual în cadrul unor conferințe internaționale (cum ar fi CRYPTO sau ASIACRYPT ), pe un număr mare de resurse de pe Internet, precum și în multe publicații.

Proprietăți ale funcțiilor hash criptografice

Pentru ca o funcție hash H să fie considerată sigură din punct de vedere criptografic, trebuie să îndeplinească trei cerințe de bază pe care se bazează majoritatea aplicațiilor funcțiilor hash în criptografie:

Ireversibilitate : Pentru o anumită valoare hash m , ar trebui să fie practic imposibil de găsit un bloc de date pentru care . $X$ $H(X)=m$
Rezistența la coliziune de primul fel : pentru un mesaj M dat , ar trebui să fie practic imposibil de găsit un alt mesaj N pentru care . $H(N)=H(M)$
Rezistența la coliziune de al doilea fel : ar trebui să fie practic imposibil să ridici o pereche de mesaje care au același hash. $(M,M')$

Folosirea coliziunilor pentru a pirata

Ca exemplu, luați în considerare o procedură simplă de autentificare a utilizatorului :

la înregistrarea în sistem, utilizatorul introduce parola, căreia i se aplică o funcție hash , a cărei valoare este înregistrată în baza de date ;
de fiecare dată când introduceți o parolă, i se aplică aceeași funcție hash , iar rezultatul este comparat cu cel înregistrat în baza de date.

Cu această abordare, chiar dacă un atacator obține acces la baza de date, el nu va putea recupera parolele originale ale utilizatorilor (cu condiția ca funcția hash utilizată să fie ireversibilă). Totuși, dacă un atacator știe să găsească coliziuni pentru funcția de hash folosită, nu va fi dificil pentru el să găsească o parolă neoriginală care să aibă aceeași sumă hash ca și parola utilizatorului.

Coliziunile pot fi folosite pentru a falsifica mesaje: informațiile despre tranzacțiile valutare, de exemplu, sunt adesea criptate folosind funcții hash; un atacator, având o metodă de a găsi coliziuni ale acestei funcții hash, poate înlocui mesajul cu unul fals și, prin urmare, poate influența cursul unei tranzacții valutare.

În mod similar, coliziunile pot fi folosite pentru a falsifica semnături și certificate digitale .

Protecție la coliziune

Există o serie de metode de protecție împotriva hackingului , protecție împotriva falsificării parolelor, semnăturilor și certificatelor , chiar dacă atacatorul cunoaște metodele de construire a coliziunilor pentru orice funcție hash .

O metodă este să adăugați o „ sare ”, adică să adăugați o secvență de caractere la datele hashabile, care este folosită, de exemplu, la stocarea parolelor UNIX . În acest caz, aceeași „sare” se adaugă și la hashul rezultat , ceea ce crește semnificativ complexitatea construcției simultane a coliziunilor de primă clasă la un grup de parole, deoarece fiecare din acest grup trebuie să înceapă cu propriul său (unic) valoarea „sare”. Cu toate acestea, „sarea” nu complică atacul asupra fiecărei parole în mod individual .

O altă metodă populară, dar ruptă, este concatenarea hashurilor din două funcții hash diferite. Se crede că în acest caz, pentru a selecta coliziuni pentru funcția hash , care este concatenarea funcțiilor hash și , este necesar să se cunoască metodele de construire a coliziunilor atât pentru , cât și pentru . În același timp, există studii care arată că utilizarea concatenărilor hash crește ușor rezistența hash-ului de reglementare la coliziuni și nu contează cât de mult diferă funcțiile hash una de cealaltă [1] . Dacă una dintre funcțiile hash este suficient de slabă pentru a găsi o coliziune în ea, a doua nu va putea întări hash-ul rezultat. $C(x)=y(x)\|z(x)$ $y(x)$ $z(x)$ $y(x)$ $z(x)$

Metode de detectare a coliziunilor

Una dintre cele mai simple și mai versatile metode de a găsi coliziuni este atacul de ziua de naștere . Cu acest atac, găsirea unei coliziuni pentru o funcție hash cu lungimea de biți va necesita o medie de aproximativ operațiuni. Prin urmare, o funcție hash de n biți este considerată sigură dacă complexitatea de calcul a găsirii coliziunilor pentru aceasta este aproape de . $n$ $2^{{n/2}}$ $2^{{n/2}}$

În plus, există un atac de prelungire a mesajului , care, având în vedere o valoare cunoscută , permite să se calculeze , unde denotă concatenarea lui . Atacul de extensie pentru unele funcții hash funcționează chiar dacă oferă rezistență la coliziune de tip 1 , rezistență la coliziune de tip 2 și proprietatea de ireversibilitate . Se intelege ca nu este necesar sa stii , dar este suficient sa ii cunosti doar hashul . Astfel, de exemplu, puteți adăuga informații suplimentare la mesajul altcuiva. Pentru a preveni acest atac sunt folosite diverse metode: se adaugă o rundă de hashing suplimentară , diferită de cele anterioare; utilizați hashing multiplu; sau utilizați o combinație a celor două metode anterioare. $H(x)$ $H(x\|y)=H(H(x)\|y)$ $\|$ $X$

Dar atacul de extensie poate fi considerat și din cealaltă parte: dacă avem un mesaj , iar funcția hash este vulnerabilă la atacul de extensie, atunci este ușor să găsim o coliziune de primul fel: , , , adică proprietatea de rezistență la ciocniri de primul fel este încălcată. $X$ $M_{1}=X\|Y$ $M_{2}=H(X)\|Y$ $H(M_{1})=H(M_{2})$

Cele mai multe funcții hash moderne au aceeași structură, bazată pe împărțirea textului de intrare în blocuri și apoi repetarea, în care o anumită funcție este utilizată la fiecare iterație , unde x este următorul bloc al textului de intrare și y este rezultatul precedentului. Operațiune. Cu toate acestea, o astfel de schemă nu este perfectă, deoarece, cunoscând funcția , este posibil să se analizeze datele în intervalele dintre iterații , ceea ce facilitează căutarea coliziunilor. $G(x,y)$ $G$

Adesea, găsirea coliziunilor cu funcția hash este precedată de găsirea pseudo -coliziunilor sale , adică două valori diferite ale tamponului inițial, care pentru același mesaj dau valori hash egale.

Coliziuni între funcțiile hash MD4 și MD5

În 1996, Hans Dobbertin a găsit pseudo-coliziuni în MD5 folosind anumiți vectori de inițializare nestandard . S-a dovedit că este posibil să construiți un al doilea mesaj pentru un mesaj cunoscut, astfel încât acesta să aibă același hash ca și cel original. Din punct de vedere al matematicii, aceasta înseamnă că MD5(IV,L1) = MD5(IV,L2) , unde IV este valoarea inițială a tamponului, iar L1 și L2 sunt mesaje diferite.

În 2004, cercetătorii chinezi Wang Xiaoyun și Yu Hongbo au anunțat o vulnerabilitate pe care au descoperit-o într-un algoritm care le-a permis săXuejia Lai , Feng Dengguo,) pentru a găsi coliziuni.

În 2005, cercetătorii Wang Xiaoyun și Yu Hongbo de la Universitatea Shandong din China au publicat un algoritm pentru găsirea coliziunilor în funcția hash MD5 , iar metoda lor funcționează pentru orice vector de inițializare, nu doar pentru vectorul utilizat de standard. Aplicarea acestei metode la MD4 vă permite să găsiți o coliziune în mai puțin de o secundă. Se aplică și altor funcții hash, cum ar fi RIPEMD și HAVAL .

În 2008, Alexander Sotirov, Marc Stevens, Jacob Appelbaum au publicat un articol la cel de-al 25-lea Congres de Comunicare Chaos care arăta posibilitatea generării de certificate digitale false pe baza utilizării coliziunilor MD5.

Ciocniri cu funcția hash SHA-1

În ianuarie 2005, Vincent Rayman și Elisabeth Oswald au publicat un atac asupra unei versiuni trunchiate a SHA-1 (53 de runde în loc de 80 ), care permite găsirea coliziunilor în mai puțin de 280 de operațiuni.

În februarie 2005, Wang Xiaoyun , Lisa Yin Yiqun și Yu Hongbo au prezentat un atac asupra SHA-1 complet care necesită mai puțin de 269 de operațiuni.

În august 2005, la CRYPTO 2005, aceiași experți au prezentat o versiune îmbunătățită a atacului asupra SHA-1 cu drepturi depline, cu o complexitate de calcul de 263 de operațiuni. În decembrie 2007, detaliile acestei îmbunătățiri au fost revizuite de Martin Cochran.

Christophe de Kanier și Christian Rechberg au prezentat mai târziu un atac îmbunătățit asupra SHA-1, pentru care au fost premiați cu cea mai bună lucrare la conferința ASIACRYPT din 2006 . Ei au prezentat o coliziune cu două blocuri pe un algoritm de 64 de runde cu o complexitate de calcul de aproximativ 235 de operații.

Deoarece atacurile teoretice asupra SHA-1 au avut succes, NIST intenționează să elimine complet utilizarea SHA-1 în semnăturile digitale .

Coliziuni cu alte funcții hash

Funcțiile hash RIPEMD și HAVAL sunt, de asemenea, vulnerabile la algoritmul de coliziune MD5 publicat de Wang Xiaoyun, Feng Dengguo, Lai Xuejia și Yu Hongbo în 2004.

Pentru a doua modificare a funcției hash WHIRLPOOL , numită Whirlpool-T, nu sunt propuși algoritmi pentru găsirea coliziunilor sau pseudo-coliziunilor pentru 2009; o limitare semnificativă pentru găsirea acestora este complexitatea funcției în sine și lungimea mare (512 biți) a tastei de ieșire.

Funcția hash GOST R 34.10-2001 în ceea ce privește puterea criptografică diferă puțin de GOST R 34.10-94 , găsirea coliziunilor pentru care se reduce la calcularea unui logaritm discret într-un grup de puncte ale unei curbe eliptice cu complexitate probabil exponențială . De exemplu, pentru parametrii de 256 de biți , logaritmul discret folosind metoda ρ sau metoda λ a lui Pollard va necesita aproximativ 2 operații. ${10}^{{30}}$

Rezoluția coliziunilor în tabelele hash

Coliziunile complică utilizarea tabelelor hash , deoarece întrerup corespondența unu-la-unu dintre codurile hash și date. Cu toate acestea, există tehnici speciale pentru a depăși dificultățile care apar:

Metoda de înlănțuire: Tehnologia înlănțuirii elementelor (înlănțuirea) constă în faptul că elementele mulțimii , care corespund aceleiași valori hash, sunt legate într-o listă de lanț. Numărul de poziție i stochează un pointer către capul listei acelor elemente a căror valoare hash a cheii este egală cu i; daca nu exista astfel de elemente in multime, NULL se scrie in pozitia i .
Adresare deschisă : Spre deosebire de hashing în lanț, cu adresare deschisă nu există liste și toate intrările sunt stocate în tabelul hash în sine. Fiecare celulă de tabel conține fie un element set dinamic, fie NULL.
Eliminarea coliziunilor : Spre deosebire de cele două metode anterioare, prezența coliziunilor în tabelul hash este eliminată în etapa de adăugare a elementelor. Codul hash al elementului adresat este hash-ul informațiilor + o valoare aleatorie. Dacă codul hash este deja în tabel, valoarea aleatoare este regenerată, elementul cu un hash diferit adăugat din nou la tabelul hash. Astfel, prezența coliziunilor este exclusă, iar elementele pot fi găsite prin hashurile lor unice, care le adresează în mod unic în tabelul hash.

Note

↑ Antoine Joux . Consultat la 3 octombrie 2017. Arhivat din original la 19 mai 2017. (nedefinit)

Vezi și

Link -uri

Bruce Schneier, MD5 și SHA Criptanaliză
Cercetare criptografică , Întrebări și răspunsuri privind coliziunea Hash
Crearea unui certificat CA necinstiți , Alexander Sotirov , falsificare de certificate bazată pe MD5
Site-ul web al Asociației Internaționale pentru Cercetare Criptologică
Coliziuni pentru funcțiile Hash MD4, MD5, HAVAL-128 și RIPEMD , Xiaoyun Wang și Dengguo Feng și Xuejia Lai și Hongbo Yu ( ( engleză ) )
Atacul de coliziune îmbunătățit asupra funcției Hash MD5 , foarte tehnic
Comentarii NIST privind atacurile criptoanalitice pe SHA - 1
Tutor de algoritm de computer

Literatură

Bruce Schneier , Criptografie aplicată, ediția a 2-a, ISBN 0-471-11709-9 , cap.18, Funcții hash unidirecționale
Ross Anderson , Inginerie de securitate , Wiley, ISBN 0-471-38922-6