Masa curcubeu

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 22 februarie 2021; verificările necesită 4 modificări .

Rainbow table ( în engleză  rainbow table ) este o versiune specială a tabelelor de căutare ( în engleză  tabel de căutare ) pentru inversarea funcțiilor hash criptografice , folosind mecanismul unui compromis rezonabil între timpul de căutare a tabelului și memoria ocupată ( compromis în engleză  timp-memorie ).

Tabelele Rainbow sunt folosite pentru a sparge parole hash greu de reversibile și pentru a ataca cifrurile simetrice bazate pe text simplu cunoscut .

Utilizarea funcției de derivare a tastei de sare face ca acest atac să nu fie fezabil.
Tabelele Rainbow sunt o dezvoltare a unui algoritm mai vechi și mai simplu propus de Martin Hellman [1] .

Condiții preliminare pentru apariția

Sistemele computerizate care folosesc parole pentru autentificare trebuie să determine cumva dacă parola introdusă este corectă. Cel mai simplu mod de a rezolva această problemă este să păstrați o listă cu toate parolele valide pentru fiecare utilizator. Dezavantajul acestei metode este că, în cazul accesului neautorizat la listă, atacatorul va afla toate parolele de utilizator. O abordare mai comună este stocarea valorilor hash criptografice din fraza de acces. Cu toate acestea, majoritatea hashurilor sunt calculate rapid, astfel încât un atacator cu acces la hashuri poate verifica rapid lista de parole posibile pentru valabilitate. Pentru a evita acest lucru, trebuie să utilizați parole mai lungi, crescând astfel lista de parole pe care un atacator trebuie să le verifice. Pentru parolele simple care nu conțin o sare , un atacator poate precalcula valorile hash pentru toate parolele comune și scurte și le poate stoca într-un tabel. Acum puteți găsi rapid o potrivire într-un tabel pre-obținut. Dar cu cât parola este mai lungă, cu atât tabelul este mai mare și cu atât este nevoie de mai multă memorie pentru ao stoca. O alternativă este să stocați doar primele elemente ale lanțurilor hash. Acest lucru va necesita mai multe calcule pentru a căuta parola, dar va reduce foarte mult cantitatea de memorie necesară. Și mesele curcubeu sunt o versiune îmbunătățită a acestei metode care evită coliziunile.

Lanțuri hash precalculate

Lanțurile hash descrise în acest articol sunt diferite de cele descrise în articolul Hash chain .

Să presupunem că avem o funcție hash H cu lungimea hash n și un set finit de parole P. Scopul nostru este să creăm o structură de date care , pentru orice valoare hash h , poate găsi fie un element p al lui P astfel încât H( p )= h , sau determinați că nu există un astfel de element. Cel mai simplu mod de a face acest lucru este să calculați H( p ) pentru toate p din P, dar un astfel de tabel ar necesita memorie Θ (|P| n ), ceea ce este prea mult.

Lanțurile hash sunt o tehnică pentru a reduce această cerință de memorie. Ideea principală este de a defini o funcție de reducere R care mapează valorile hash la valorile din P. Rețineți că R nu este o inversare a funcției hash. Începând cu parola inițială și aplicând alternativ H și R la fiecare valoare rezultată, obținem un lanț de parole și hashuri alternative. De exemplu, pentru un set de parole de 6 caractere și o funcție hash care produce valori pe 32 de biți, lanțul ar putea arăta astfel:

Singura cerință pentru funcția de reducere este să returnați valori din același alfabet ca și parolele.

Pentru a genera tabelul, alegem un set aleatoriu de parole inițiale din P, calculăm lanțuri de o lungime fixă ​​k pentru fiecare parolă și stocăm doar prima și ultima parolă din fiecare lanț.

Pentru fiecare hash h , a cărui valoare dorim să o inversăm (găsiți parola corespunzătoare acesteia), calculăm secvența R(…R(H(R(h)))…). Dacă oricare dintre valorile intermediare coincide cu orice capăt al oricărui lanț, luăm începutul acestui lanț și îl restabilim complet. Cu o probabilitate mare, lanțul complet va conține valoarea hash h , iar parola care o precede va fi cea dorită.

Pentru exemplul de mai sus, dacă inițial avem un hash de 920ECF10, va genera următoarea secvență:

Deoarece kiebgteste sfârșitul lanțului din tabelul nostru, luăm parola inițială corespunzătoare aaaaaași calculăm lanțul până când găsim hash-ul 920ECF10:

Astfel, parola dorită este sgfnyd.

Este de remarcat faptul că lanțul restaurat nu conține întotdeauna valoarea hash necesară h . Acest lucru este posibil atunci când există o coliziune a funcției H sau R. De exemplu, lăsați hash-ul FB107E70 să fie dat, care la un anumit stadiu generează parola kiebgt:

Dar FB107E70 nu apare în lanțul generat de parolă aaaaaa. Acest lucru se numește fals pozitiv . În acest caz, ignorăm potrivirea și continuăm să evaluăm secvența generată de h . Dacă secvența generată atinge lungimea k fără potriviri bune, aceasta înseamnă că parola căutată nu a fost niciodată găsită în lanțurile precalculate.

Conținutul tabelului nu depinde de valoarea hash-ului inversat, acesta este calculat în avans și este folosit doar pentru căutare rapidă. Mărirea lungimii lanțului reduce dimensiunea mesei, dar crește timpul necesar pentru a găsi elementul dorit în lanț.

Lanțurile hash simple au mai multe dezavantaje. Cea mai serioasă este posibilitatea de a uni două lanțuri într-unul singur (generând aceeași valoare în lanțuri diferite). Toate valorile generate după îmbinare vor fi aceleași în ambele lanțuri, ceea ce restrânge numărul de parole acoperite. Deoarece lanțurile pregenerate nu sunt salvate în întregime, este imposibil să se compare în mod eficient toate valorile generate între ele. De regulă, funcția hash H este îngrijită de partea care furnizează criptarea parolei, astfel încât principala problemă constă în funcția de reducere R.

O altă problemă serioasă este selectarea unei astfel de funcție R care va genera parole cu acoperirea și distribuția necesară. Constrângerea alfabetului de ieșire este o constrângere severă în alegerea unei astfel de funcții.

Mese curcubeu

Mesele Rainbow sunt o extensie a ideii de masă cu lanț hash. Ele rezolvă eficient problema coliziunilor prin introducerea unei secvențe de funcții de reducere R 1 , R 2 , …, R k . Funcțiile de reducere sunt aplicate pe rând, intercalate cu funcția de hashing: H, R 1 , H, R 2 , …, H, R k . Cu această abordare, două lanțuri pot fuziona numai dacă valorile de pe aceeași iterație se potrivesc . Prin urmare, este suficient să verificați pentru coliziuni numai valorile finale ale lanțurilor, care nu necesită memorie suplimentară. În etapa finală de compilare a tabelului, puteți găsi toate lanțurile îmbinate, lăsați doar unul dintre ele și generați altele noi pentru a umple tabelul cu numărul necesar de lanțuri diferite. Lanțurile rezultate nu sunt complet lipsite de ciocniri, cu toate acestea, ele nu se vor îmbina complet.

Utilizarea secvențelor de funcții de reducere schimbă modul în care este căutat tabelul. Deoarece hash-ul poate fi găsit oriunde în lanț, trebuie generate k lanțuri diferite:

Definiția unui fals pozitiv se va schimba și ea: dacă „ghicim” incorect poziția hash-ului dorit, acesta va elimina doar unul dintre k lanțurile generate; în același timp, poate fi încă posibil să găsiți hash-ul corect pentru acest lanț de masă, dar într-o poziție diferită.

Deși tabelele curcubeu necesită mai multe lanțuri pentru a ține evidența, ele au o densitate mai mare de parole pentru fiecare intrare în tabel. Spre deosebire de un tabel de lanț hash, utilizarea mai multor funcții de reducere reduce numărul de potențiale coliziuni din tabel, ceea ce îi permite să crească fără pericolul unui număr mare de fuziuni în lanț.

Exemplu

Există un hash ( re3xes) de inversat (recuperarea parolei corespunzătoare) și un tabel curcubeu obținut folosind trei funcții de reducere.

  1. Calculați un lanț de lungime 1 din hash inițial: R 3 ("re3xes")="rambo". Această parolă nu este sfârșitul niciunui lanț de tabele.
  2. Calculați un lanț de lungime 2: R 3 (H(R 2 ("re3xes")))="linux23".
  3. Această parolă se găsește în tabel. Luăm începutul lanțului găsit (parola passwd).
  4. Restabilim lanțul de masă până când obținem hash-ul original re3xes.
  5. Hașul dorit se găsește în lanț, atacul are succes. Parola care precede această valoare hash este parola culturecare trebuie căutată.

Timpul și memoria

Un tabel curcubeu este creat prin construirea de lanțuri de parole posibile. Crearea unor astfel de tabele necesită mai mult timp decât este necesar pentru a crea tabele de căutare obișnuite, dar mult mai puțină memorie (până la sute de gigaocteți, cu volumul pentru tabelele obișnuite de N cuvinte, tabelele curcubeu au nevoie doar de aproximativ N 2/3 ). În același timp, deși necesită mai mult timp (comparativ cu metodele simple precum un atac de dicționar ) pentru a recupera parola inițială, sunt mai fezabile în practică (pentru a construi un tabel obișnuit pentru o parolă de 6 caractere cu caractere octeți, trebuie 256 6 = 281 474 976 710 656 blocuri de memorie, în timp ce pentru curcubeu - doar 256 6 ⅔ = 4 294 967 296 blocuri).

Tabelele pot sparge doar funcția hash pentru care au fost create, adică tabelele MD5 pot sparge doar hash-ul MD5. Teoria acestei tehnologii a fost dezvoltată de Philippe Oechslin [2] ca o variantă rapidă a compromisului timp-memorie [3] . Tehnologia a fost folosită pentru prima dată în programul Ophcrack pentru a sparge hashurile LanMan ( LM-hash ) utilizate în Microsoft Windows . Mai târziu a fost dezvoltat un program mai avansat RainbowCrack , care poate funcționa cu un număr mare de hashe-uri, de exemplu, LanMan, MD5, SHA1 și altele.

Următorul pas a fost crearea programului The UDC , care vă permite să construiți tabele Hybrid Rainbow nu printr-un set de caractere, ci printr-un set de dicționare, care vă permite să recuperați parole mai lungi (de fapt, lungime nelimitată).

Aplicație

Când se generează tabele, este important să se găsească cel mai bun raport al parametrilor interrelaționați:

Parametrii de mai sus depind de setările specificate în timpul generării tabelului:

În acest caz, timpul de generare depinde aproape exclusiv de probabilitatea dorită de selecție, de setul de caractere utilizat și de lungimea parolei. Spațiul ocupat de tabele depinde de viteza dorită de selectare a unei parole din tabelele gata făcute.

Deși utilizarea tabelelor curcubeu facilitează utilizarea forței brute (adică a forței brute ) pentru ghicirea parolelor, în unele cazuri puterea de procesare necesară pentru a le genera/utiliza nu permite unui singur utilizator să obțină rezultatele dorite într-un timp acceptabil. . De exemplu, pentru parolele de cel mult 8 caractere, formate din litere, cifre și caractere speciale !@#$%^&*()-_+=indexate cu algoritmul MD5, pot fi generate tabele cu următorii parametri:

În același timp, probabilitatea de a găsi o parolă folosind aceste tabele va fi de 0,7542 (75,42%), tabelele în sine vor lua 596 GiB , generarea lor pe un computer Pentium-3 1 GHz va dura 3 ani, iar căutarea unei parole. utilizarea meselor gata făcute nu va dura mai mult de 22 de minute.

Cu toate acestea, procesul de generare a tabelului poate fi paralelizat, de exemplu, calculul unui tabel cu parametrii de mai sus durează aproximativ 33 de ore. În acest caz, dacă avem la dispoziție 100 de calculatoare, toate tabelele pot fi generate în 11 zile.

Protecție împotriva meselor curcubeu

Una dintre metodele obișnuite de protecție împotriva hackingului folosind tabelele curcubeu este utilizarea funcțiilor hash ireversibile, care includ sare („ sare ”, „modificator”). Există multe scheme posibile pentru amestecarea semințelor și a parolei. De exemplu, luați în considerare următoarea funcție pentru a crea un hash al unei parole:

hash = MD5 (parolă + sare)

Pentru a recupera o astfel de parolă, un atacator are nevoie de tabele pentru toate valorile posibile de sare. Când utilizați o astfel de schemă, sarea trebuie să fie suficient de lungă (6-8 caractere), altfel un atacator poate calcula tabele pentru fiecare valoare de sare, aleatoare și diferite pentru fiecare parolă. Astfel, două parole identice vor avea valori hash diferite, cu excepția cazului în care se folosește aceeași sare.

În esență, sarea crește lungimea și, eventual, complexitatea parolei. Dacă tabelul este proiectat pentru o anumită lungime sau pentru un set limitat de caractere, atunci sarea poate împiedica recuperarea parolei. De exemplu, parolele vechi Unix foloseau o sare care avea doar 12 biți lungime. Pentru a sparge astfel de parole, un atacator trebuia să numere doar 4096 de tabele, care pot fi stocate liber pe hard disk-uri terabyte. Prin urmare, în aplicațiile moderne, au tendința de a folosi o sare mai lungă. De exemplu, algoritmul de hashing bcrypt folosește o sare de 128 de biți [4] . Această lungime a sării face ca precalculul să fie pur și simplu lipsit de sens. O altă modalitate posibilă de a combate atacurile precalculate este întinderea cheii .  De exemplu:

cheie = hash (parolă + sare) pentru 1 până la 65536 do cheie = hash (cheie + parolă + sare)

Această metodă reduce eficiența precalculării, deoarece utilizarea valorilor intermediare crește timpul necesar pentru calcularea unei parole și, prin urmare, reduce numărul de calcule pe care un atacator le poate efectua într-un interval de timp dat [5] Această metodă este utilizată în următorii algoritmi de hashing: MD5 , care utilizează 1000 de repetări și bcrypt . [6] . O alternativă este folosirea întăririi cheii , care este adesea confundată cu întinderea cheii .  Folosind această metodă, creștem dimensiunea cheii adăugând o sare aleatorie, care este apoi îndepărtată în liniște, spre deosebire de întinderea cheii, unde sarea este păstrată și utilizată în iterațiile ulterioare [7] .

Utilizare

Practic, toate distribuțiile de sisteme de operare Unix , GNU/Linux și BSD folosesc hash-uri cu o sare pentru a stoca parolele de sistem, deși multe aplicații, cum ar fi scripting-ul Internet, folosesc un hash simplu (de obicei MD5 ) fără o „sare”. Sistemele de operare Microsoft Windows și Windows NT folosesc hash-uri LM-hash și NTLM , care, de asemenea, nu folosesc „sare”, ceea ce le face cele mai populare pentru crearea tabelelor curcubeu.

Note

  1. ↑ Hellman M. A criptanalytic time-memory trade-off  // IEEE Transactions on Information Theory. - 1980. - iulie ( vol. 26 , nr. 4 ). - S. 401-406 . — ISSN 0018-9448 . - doi : 10.1109/TIT.1980.1056220 .
  2. ↑ Philippe Oechslin . Preluat la 28 august 2006. Arhivat din original la 23 noiembrie 2005.
  3. ↑ Prezentarea lui Philippe Oechslin la conferința CRYPTO'03 Arhivată 26 septembrie 2007 la Wayback Machine (PDF)
  4. ↑ Alexander, Steven. Protecție prin parolă pentru sistemele de operare moderne  //  ;login:. - Asociația USENIX , 2004. - Iunie ( vol. 29 , nr. 3 ).
  5. ↑ Ferguson, Neils; Bruce Schneier. Criptografie  practică . - Indianapolis: John Wiley & Sons , 2003. - ISBN 0-471-22357-3 .
  6. ↑ Provos, Niels; Mazieres, David O schemă de parole adaptabile în viitor  (nedefinită)  // Proceedings of the FREENIX Track: 1999 USENIX Annual Technical Conference. - Monterey, CA, SUA: Asociația USENIX, 1999. - 6 iunie.
  7. ↑ U. Manber , „A Simple Scheme to Make Passwords Based on One-way Functions Much Harder to Crack”, Computers & Security, v.15, n.2, 1996, pp.171-176. (Engleză)

Link -uri