Masă curcubeu
Se crede că acest element sau secțiune despre subiectul Criptare este verificat . |
În criptarea unei tabele curcubeu (în engleză : rainbow table) este o tabelă de asociere care oferă un compromis spațiu-timp utilizat pentru recuperarea cheilor de criptare în mod clar pornind de la chei în format hash generate de o funcție hash criptografică . Ideea este să folosești o cantitate mare de memorie pentru a păstra informațiile calculate odată pentru totdeauna, în loc să folosești timpul CPU. O aplicație obișnuită a unei mese curcubeu este de a ataca protecțiile bazate pe parolă stocate cu hash-ul lor. Adesea, înainte ca o parolă să fie hashată, aceasta este „sărată” adăugând o sare pentru a face acest tip de atac mai dificil.
Martin Hellman , informatician și criptograf, și-a fondat teoria pe baza unei tehnici numite compromisul timp-memorie . Considerația lui Hellman a fost crearea unei arhive de parole pentru a stoca toate hashurile posibile. Cu toate acestea, el nu a considerat că va fi nevoie de prea mult timp și spațiu (zeci de terabyți) pentru ca operațiunea să fie fezabilă.
Ideea lui Hellman a fost preluată de Philippe Oechslin , un expert în securitate, care a perfecționat conceptul exprimat de Hellman. Soluția găsită de Oechslin a fost crearea unui tabel care are mese curcubeu sub formă de rânduri și hashuri ca coloane. Fiecare masă este alcătuită din lanțuri variind de la un hash la următorul stocat în tabel. În acesta din urmă, se aplică diferite funcții de reducere pentru fiecare coloană, dar aceleași funcții hash. În plus, doar parolele inițiale și finale sunt stocate pentru fiecare tabel curcubeu.
Funcția Hash și funcția de reducere
Funcțiile care gestionează tabelele sunt următoarele:
- funcție hash: ia o parolă ca argument și returnează un hash format în general din 15 caractere alfanumerice, indiferent de lungimea parolei.
- funcție de reducere: ia ca argument hash-ul produs de funcția anterioară și generează o parolă, strict diferită de cea de pornire.
Funcțiile hash sunt construite în așa fel încât este extrem de dificil să urmăriți parola originală, astfel încât funcția de reducere să nu returneze parola originală, ci să genereze alta. O posibilă succesiune de pași este după cum urmează:
parola originală -> hash -> altă parolă -> alt hash -> și așa mai departe
de exemplu:
![{\ displaystyle \ mathbf {aaaaaa} \, {\ xrightarrow [{\; H \;}] {}} \, \ mathrm {281DAF40} \, {\ xrightarrow [{\; R \;}] {}} \ , \ mathrm {sgfnyd} \, {\ xrightarrow [{\; H \;}] {}} \, \ mathrm {920ECF10} \, {\ xrightarrow [{\; R \;}] {}} \, \ mathbf {kiebgt}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bbacb4ee3811ce261fa6023c6de90718e22c7b49)
Funcționarea algoritmului
- Pornind de la hash-ul re3xes din imaginea de mai jos, calculăm ultima reducere utilizată în tabel și verificăm dacă parola este prezentă în ultima coloană a tabelului.
- Dacă verificarea eșuează ( rambo nu este prezent în tabel), lanțul este calculat cu ultimele 2 reduceri. Continuați cu reduceri succesive până când găsiți parola sau ajungeți la capătul lanțului. Dacă parola nu este găsită, atacul a eșuat.
- Dacă verificarea are succes (tabelul linux23 este prezent și la sfârșitul lanțului), parola este recuperată de la începutul lanțului pe care îl produce linux23 .
- La începutul lanțului corespunzător găsim passwd. În acest moment, este generat un lanț și hash-ul este comparat cu hash-ul inițial ( re3xes ) la fiecare iterație. Testul este reușit, deoarece găsim hash re3xes în lanț, iar parola curentă ( cultura ) este cea care a produs întregul lanț. Atacul are succes.
Secvența de calcule efectuată de algoritm economisește timp în căutare. De fapt, din când în când se calculează un singur lanț, cel al hashului și de îndată ce parola este găsită, algoritmul se termină.
Eficienţă
Algoritmul conceput de Hellman a fost ulterior reformulat prin introducerea unui nou criteriu pentru stocarea hashurilor de parole în tabele. Prin urmare, tabelele curcubeu primesc acest nume datorită faptului că sunt utilizate funcții de reducere diferite pentru fiecare coloană a fiecărui tabel, cam asemănătoare culorilor curcubeului, cu argumente diferite pentru fiecare dintre ele. Principalele îmbunătățiri aduse cu noua metodă sunt:
- reducerea numărului de fuziuni (fuziuni) în comparație cu metodele anterioare bazate pe schimbul de memorie de timp;
- coliziunile (cazuri în care există două hashuri identice pentru parole diferite) care apar la niveluri diferite nu implică îmbinarea și, prin urmare, lanțurile rămân neschimbate;
- lanțurile nu au cicluri (fiecare funcție de reducere este unică în lanț);
- lanțurile au o lungime fixă (de exemplu, este stocat un hash la fiecare 10 000).
Performanţă
Căutarea prin tabelele curcubeu se dovedește a fi de aproximativ șapte ori mai rapidă decât metodele anterioare bazate pe compromisul timp-memorie, deoarece în timpul executării algoritmului, un lanț al tabelului este luat în considerare din când în când și când parola este găsită. algoritmul se termină. Odată ce a început căutarea pe tabele, probabilitatea de succes în găsirea parolei este foarte aproape de 100%. Trebuie subliniat faptul că generarea tabelelor curcubeu necesită o mare putere de calcul. În mod normal, este posibil să găsiți tabelele pe web.
Metode analoage
Tabelele curcubeu nu sunt singura modalitate de a căuta parole. Printre cei mai cunoscuți algoritmi de acest tip se numără:
- metoda forței brute. Este un algoritm care caută cheia unui sistem încercând toate combinațiile posibile. În practică, un astfel de loc de muncă durează mult, chiar și ani. Timpul poate fi redus prin prelucrarea prin conducte de către mai multe procesoare dacă nu există blocaje, cum ar fi un interval fix între reîncercări succesive;
- atac asupra dicționarului. Este un algoritm care se bazează pe un fișier numit dicționar, deoarece conține un număr imens de cuvinte care sunt candidați la parolele probabile (lista de cuvinte ). Atacul lansat se concentrează pe o serie de încercări de introducere a cheii stocate în dicționar, efectuate complet automat. Caracteristica acestei metode constă în faptul că cuvintele stocate în listă sunt în general obiecte utilizate frecvent de către oameni atunci când își aleg parola.
Avantajul utilizării unui dicționar față de un atac normal de forță brută este că sunt evitate secvențe fără sens, cum ar fi „dhskfler”. Deci, un atac de dicționar este eficient numai dacă parola este prezentă în fișierul de dicționar utilizat, în timp ce un atac de forță brută, chiar dacă durează mult mai mult, are șanse de succes de 100%.
Temeiuri
Tabelele curcubeu permit oricărei persoane să găsească cuvintele cheie corespunzătoare unui hash dat. Cu toate acestea, s-au găsit soluții foarte eficiente în prevenirea metodelor puternice, cum ar fi tabelele, de a obține rezultatele dorite.
O procedură adoptată este cunoscută sub numele de sărare și constă în adăugarea unei cantități suplimentare de informații la parolă, informații care pot fi generate aleatoriu înainte de a utiliza o funcție hash nereversibilă: în acest fel parolele sunt aceleași, dar care au fost codificate cu diferite săruri, au diferite codificări criptate. Sărurile sunt de obicei stocate în text clar pe sistemul de hash, deși există implementări disponibile care utilizează o funcție de codificare reversibilă sau nu o stochează deloc. Un atac cu mese curcubeu nu ar fi practic pentru valori suficient de mari ale cantității de informații adăugate prin sare, deoarece spațiul necesar crește liniar cu numărul de săruri posibile: de exemplu, pentru o sare pe 16 biți, atacatorul ar trebui să aibă suficient spațiu pentru a stoca 2 16 = 65 536 mese. Timpul suplimentar de căutare pe aceste tabele este neglijabil în comparație cu resursele necesare pentru a le compila și stoca, mai ales că analiza ar putea exploata coliziunile dintre săruri (cazuri în care sarea utilizată este aceeași) pentru a accelera căutarea.
O altă procedură este cunoscută sub numele de întindere cheie și este o extensie a sărării : constă în utilizarea unei iterații a funcțiilor hash ca algoritm hash, fiecare dintre care folosește atât ieșirea celei anterioare, cât și o sare constantă. În acest fel, atacatorul nu numai că va avea nevoie de mai mult spațiu pe masă, dar va trebui să petreacă și mai mult timp. De exemplu, MD5-Crypt folosește 1 000 de iterații ale funcției hash MD-5.
