Ce sunt mesele curcubeu și cum se folosesc?

Tabelele curcubeu sunt de obicei confundate cu o altă tehnică mai simplă care utilizează un timp de calcul torage tradeoff in password recovery: hash tables.

Tabelele Hash sunt construite prin hashing fiecare cuvânt într-un dicționar de parole. Perechile parola-hash sunt stocate într-un tabel, sortate după valoarea hash. Pentru a utiliza un tabel hash, luați simplu hash și efectuați o căutare binară în tabel pentru a găsi parola originală, dacă este prezentă.

Tabelele Rainbow sunt mai complexe. Construirea unei tabele curcubeu necesită două lucruri : o funcție de hash și o funcție de reducere. Funcția de hash pentru un set dat de tabele Rainbow trebuie să se potrivească cu parola hash pe care doriți să o recuperați. Funcția de reducere trebuie să transforme un hash în ceva utilizabil ca parolă. O funcție simplă de reducere este în Base64 codificați hash-ul, apoi trunchiați-l cu un anumit număr de caractere.

Tabelele curcubeu sunt construite din „lanțuri” cu o anumită lungime: 100.000 de exemplu. Pentru a construi lanțul, alegeți o valoare de semințe aleatorii. Apoi aplicați funcțiile de hash și reducere la această semință și la rezultatul acesteia și continuați să iterați de 100.000 de ori. Sunt stocate doar semințele și valoarea finală. Repetați acest proces pentru a crea cât mai multe lanțuri dorite.

Pentru a recupera o parola folosind Rainbow Tables, este supus hashul parolei procesul de mai sus pentru aceeași lungime: în acest caz 100.000, dar fiecare verigă din lanț este reținută. Fiecare verigă din lanț este comparată cu valoarea finală a fiecărui lanț. Dacă există o potrivire, lanțul poate fi reconstruit, păstrând atât ieșirea fiecărei funcții de hash, cât și ieșirea fiecărei funcții de reducere. Acest lanț reconstruit va conține hash-ul parolei în cauză, precum și parola care a produs-o.

Punctele tari ale unui tabel hash sunt că recuperarea unei parole este rapidă (căutare binară) și construirea persoanei tabelul hash poate alege ce intră în el, cum ar fi primele 10.000 de parole. Punctul slab comparativ cu Rainbow Tables este că tabelele hash trebuie să stocheze fiecare pereche hash-parolă.

Rainbow Tables are avantajul că persoana care construiește acele tabele poate alege cât spațiu de stocare este necesar selectând numărul de linkuri din fiecare lanț. Cu cât sunt mai multe legături între semință și valoarea finală, cu atât mai multe parole sunt capturate. Un punct slab este că persoana care construiește lanțurile nu alege parolele pe care le captează, astfel încât Tabelele Rainbow nu pot fi optimizate pentru parole obișnuite. De asemenea, recuperarea parolei implică calcularea unor lanțuri lungi de hashuri, ceea ce face ca recuperarea să devină o operațiune costisitoare. Cu cât lanțurile sunt mai lungi, cu atât sunt capturate mai multe parole, dar este nevoie de mai mult timp pentru a găsi o parolă în interior.

Tabelele Hash sunt bune pentru parolele obișnuite, Tabelele Rainbow sunt bune pentru parolele dificile. Cea mai bună abordare ar fi să recupereze cât mai multe parole posibil folosind tabele hash și / sau cracking convențional cu un dicționar al celor mai bune N parole. Pentru cei care rămân, utilizați Tabelele Rainbow.

Comentarii

• Oh, Doamne, recunosc că sunt șocat – discut și explic tabelele Rainbow toate timp și în tot acest timp se pare că am fost unul dintre ” confuz în mod obișnuit „! Aș face în total +1000 de ori, am învățat ceva nou aici (și am crezut că știu răspunsul). Mă bucur că am pus întrebarea până la urmă … Mulțumesc!
• Deși pentru a fi specifici (acum că mi-ai deschis ochii, am făcut mai multe cercetări :)), Rainbow Tables se diferențiază de lanțurile Hellman Hash folosind mai multe funcții de reducere diferite. Mai complex, într-adevăr … dar într-adevăr o idee destul de frumoasă (Ah! Este de aceea de ce au ‘ numit ” Rainbow ” tabele?)
• Sunt de acord că aceasta este o explicație foarte bună. În răspunsul meu l-am explicat simplu și, de asemenea, l-am explicat greșit, fiind simplu.Frumusețea meselor Rainbow este faptul că nu ‘ nu stochează fiecare valoare hash. Mă voi edita pe a mea, dar voi vota și asta pentru că este cu siguranță o explicație mai bună.
• Hmm … Deși cu cât mă gândesc mai mult la asta, în sistemele din viața reală, mesele Rainbow nu sunt nici pe departe la fel de utile ca mese de hash. După cum ați menționat, pentru parolele comune tabelele hash sunt mult mai bune (deoarece acestea sunt de ordinul mărimii mai rapide, iar cerințele de dimensiune pentru un dicționar de parole sunt, desigur, mult mai mici decât întreaga gamă posibilă de parole). Și cine ‘ ne glumim? Majoritatea parolelor se încadrează în această categorie, este foarte rar (și va fi de ceva timp) să trebuiască să apelați în RT.
• Din păcate, m-ați pierdut aici: ” Pentru a recupera o parolă folosind Rainbow Tables, parola este supusă procesului de mai sus pentru aceeași lungime. ” Cum poate parola să treacă procesul atunci când ‘ nici măcar nu se știe? V-ați referit la hash-ul parolei? De asemenea, există ‘: ” Fiecare verigă din lanț este comparată cu valoarea finală a fiecărui lanț. ” Nu pot vedea o situație în care o verigă din lanț să se potrivească cu valoarea finală a lanțului, deoarece valoarea verigii ar fi continuu hașată și redusă.

Există multe explicații bune despre ce sunt mesele curcubeu, acesta Cum funcționează mesele Rainbow este deosebit de bun. De asemenea, articolul Wikipedia are și o explicație foarte bună. Pentru o lectură puțin mai aprofundată, lucrarea definitivă cu privire la subiect este Efectuarea unui compromis mai rapid al criptanaliticii în timp-memorie .

O explicație simplă a Rainbow Tables este că acestea folosesc o tehnică de schimb de memorie în timp. Înțeles, în loc să ia o valoare hash țintă și un dicționar de cuvinte, apoi să hashing fiecare cuvânt și să facă comparația din mers (abordarea forței brute folosind ceva de genul John ), în schimb, aveți în avans toate valorile din dicționar (acest lucru poate dura foarte mult, în funcție de dimensiunea dicționarului). Dar, odată ce ați terminat, puteți compara câte hash-uri doriți cu valorile pre-hash din tabelele curcubeu, acest lucru este semnificativ mai rapid decât calcularea hash-urilor din nou.

Explicația pe care am scris-o aici anterior în un efort de a fi scurt a fost înșelător, deoarece nu a explicat utilizarea reducerilor pe care le folosesc mesele curcubeu. Pentru o explicație mai bună până când rescriu acest bit, consultați @Crunge answer .

Puteți genera tabelele curcubeu singur utilizând o aplicație precum RainbowCrack sau le puteți descărca din surse precum Grupul Shmoo , Free Rainbow Tables , proiectul Ophcrack și multe alte locuri, în funcție de tipul de hash-uri pentru care aveți nevoie de tabele.

Pentru a vă proteja împotriva unui atac bazat pe Tabelul Curcubeu, cea mai eficientă metodă de combatere este să vă asigurați că fiecare hash dintr-un sistem este sărat . Acest lucru face ca mesele curcubeu pre-generate să fie inutile și ar însemna că un atacator ar trebui să genereze un set personalizat de tabele pe care să le folosească împotriva hashurilor vizate, ceea ce ar fi posibil doar dacă ar cunoaște sarea.

Comentarii

• Mai mult (luați în considerare modificarea acestui lucru), dacă utilizați o sare diferită pentru fiecare parolă, înregistrând-o necriptată în baza de date, atunci atacat ar trebui să genereze un set personalizat de tabele pentru fiecare hash, care ar învinge obiectul exercițiului – întregul punct al mesei curcubeu este de a forța brută întreg spațiul de parolă și apoi de a obține toate parolele pentru o forță brută efort; dacă ‘ primești doar o parolă pe fiecare tabel curcubeu, atunci ai putea, de asemenea, să forțezi direct hashul.

Scop și relevanță

Tabelele curcubeu ajută la spargerea parolelor dificile, adică a celor care nici măcar nu pot fi găsite într-un dicționar mare. Parolele au fost stocate în mod istoric ca hashuri simple în bazele de date și acest lucru este eficient împotriva tabelelor curcubeu: creați o singură tabel curcubeu (lent) și rulați orice număr de baze de date pline de hashuri împotriva acestuia (rapid).

În zilele noastre, din ce în ce mai multe sisteme utilizează algoritmi de stocare a parolelor corespunzători, cum ar fi Bcrypt, Scrypt sau Argon2. Vezi: Cum să [stochezi] parolele în siguranță? Acești algoritmi sunt nu mai este „vulnerabil” la tabelele curcubeu: deoarece fiecare hash este unic, chiar dacă parolele sunt egale, tabelele curcubeu nu mai funcționează.

De aceea, tabelele curcubeu sunt nepopulare astăzi.Chiar dacă nu se folosește ceva modern precum Argon2, dezvoltatorii din zilele noastre știu de obicei că ar trebui să folosească cel puțin o sare. Acest lucru este deja suficient pentru a face inutilă o masă curcubeu.

Cum funcționează

Crearea unui tabel

Imaginați-vă că creăm o masă curcubeu cu doar două lanțuri, fiecare având lungimea 5. Tabelul curcubeu este pentru funcția fictivă hash MD48, care generează 48 de biți (doar 12 caractere hexazecimale). Când construim lanțul, vedem acest lucru:

Chain 0: 0=cfcd208495d5 => z=fbade9e36a3f => renjaj820=7668b2810262 => aL=8289e8a805d7 => ieioB=2958b80e4a3a => WLgOSj Chain 1: 1=c4ca4238a0b9 => ykI4oLkj=140eda4296ac => Dtp=1b59a00b7dbe => W=61e9c06ea9a8 => 6cBuqaha=d4d2e5280034 => 0uUoAD 

Începem cu 0 deoarece este primul lanț (avem nevoie doar de o valoare pentru a începe). Când hashem acest lucru cu MD48, acesta se transformă în cfcd208495d5. Acum aplicăm o funcție de „reducere” care formează practic acest hash înapoi într-un parola și vom termina cu „z”. Când vom hash din nou, obținem fbade9e36a3f, apoi o reducem din nou și obținem renjaj820 . Există încă câteva cicluri, iar rezultatul final este WLgOSj.

La fel pentru al doilea lanț. Începem doar cu o altă valoare și facem același lucru. Aceasta se termină cu 0uUoAD.

Tabelul nostru complet curcubeu este acum:

WLgOSj => 0 0uUoAD => 1 

Asta este tot ce trebuie să stocați.

Căutarea unui hash

Să spunem că am găsit un hash online, 7668b2810262. Să-l spargem folosind tabelul nostru!

Looking for hash "7668b2810262", reduced to "aL". hashed=>reduced "aL" to ieioB hashed=>reduced "ieioB" to WLgOSj Found a match, "WLgOSj" is in our rainbow table: WLgOSj => 0 The chain starts with "0". Let"s walk that chain and look for the hash. hashed "0" to cfcd208495d5 hashed "z" to fbade9e36a3f hashed "renjaj820" to 7668b2810262 That hash matches! Found the password: renjaj820 

Pentru a vă juca singur, exemplele de mai sus au fost create folosind acest script Python: https://gist.github.com/lgommans/83cbb74a077742be3b31d33658f65adb

Proprietăți de scalare

Pe scurt:

• Căutări rapide înseamnă tabele mai mari, presupunând că acoperirea rămâne aceeași.
• O acoperire mai bună înseamnă căutări mai lente sau tabele mai mari.
• Tabelele mai mici înseamnă căutări mai lente sau o acoperire mai slabă.

Următoarele secțiuni presupun că timpul per reducere hash + este de 1µs și nu ține cont de coliziuni. Acestea sunt toate numere de bază, menite ca exemple și nu valori exacte.

Timp de căutare

Dacă o operațiune de reducere hash + durează o microsecundă, atunci generarea unui tabel cu un milion de lanțuri și 10 000 de reduceri pe lanț ar dura aproximativ 3 ore:
chain_length × chain_count / reductions_per_second / seconds_per_hour
= 10 000 × 1 000 000 / 1 000 000 / 3600 = 2,8 ore.

Efectuarea unei căutări în acel tabel durează în medie 10 milisecunde. Acest lucru se datorează faptului că, de obicei, va trebui să trecem prin chain_length/2 reduceri înainte de a găsi care lanț conține hash. De exemplu, s-ar putea să trebuiască să facem 3000 de reduceri pe un hash înainte de a găsi o valoare care este în tabel. Apoi, trebuie să refacem acel lanț de la început până când găsim valoarea potrivită. Dacă ar fi trebuit doar să facem 3000 pentru a o găsi în tabelul nostru, atunci trebuie să facem 7000 de reduceri de la început pentru a ajunge la punctul potrivit din lanț. Practic, facem la fel de multe operații atunci când privim în sus ca atunci când generăm un singur lanț. Prin urmare, timpul de căutare este de 10 000 de ori mai microsecundă, adică zece milisecunde (sau o centisecundă, dacă doriți).

Cerințe de stocare

Când doriți să creați un tabel complet și rapid de căutare pentru o funcție hash, chiar și MD5, ați avea în continuare nevoie de o sută de miliarde de miliarde de terabyți de stocare. Asta ” Nu este foarte util. Dar ce se întâmplă dacă vrem să acoperim doar parole cu litere mici până la 10 caractere?

Dacă vrem să petrecem cel mult 30 de secunde căutând un hash și presupunând că avem nevoie de 1 microsecundă (o milionime de secundă) per hash + reduce ciclul, atunci putem avea o lungime a lanțului de: 1 million × 30 = 30 de milioane. Există 26 ¹⁰ (sau 10 ¹⁴ ) parole cu litere mici de 10 caractere posibile, iar pe lanț acoperim 30 de milioane de valori. Asta ne lasă cu 4 milioane de lanțuri. Știm că fiecare lanț are doar o valoare inițială și finală stocată și că valorile sunt de 10 caractere fiecare. Deci, 2 × 10 × 4 million = 76 de date MiB.

Generarea tabelului prin iterarea tuturor parolelor cu 10 caractere durează mult: 30 de secunde pe lanț, ori de 4 milioane de lanțuri este aproximativ 91 de ani. O mulțime de oameni ar fi interesați de un astfel de tabel, totuși, așadar, prin reunirea a 1092 de procesoare (= 91 × 12), durează doar 1 lună. Acest lucru arată cât de mic poate fi comparat un astfel de tabel cu spațiul de parolă pe care îl acoperă: căutările durează doar 30 de secunde și trebuie să stocați doar date de 76MiB.

Concluzie

Tabelele Rainbow pot fi considerat un schimb de timp-memorie : se stochează doar o mică parte a tabelului și se recuperează printr-un calcul suplimentar în timpul căutării. Acesta face parte din motivul pentru care sărurile, sau mai bine zis, un algoritm bun de stocare a parolelor precum Scrypt sau Argon2 sunt importante pentru a menține parolele în siguranță.O masă curcubeu poate recupera o parolă sărată numai dacă tabelul conține o intrare suficient de mare pentru a conține atât sarea, cât și parola, ceea ce ar fi extrem ineficient și va învinge întregul scop.

Rețineți că un lucru similar se aplică cu criptarea: atunci când oamenii criptează fișierele cu o parolă, se poate construi o masă curcubeu pentru a sparge fișierele. Să spunem că software-ul folosește AES, iar primul bloc al fișierului ar trebui să decripteze la „parola corectă” folosind parola furnizată de utilizator, apoi o masă curcubeu ar folosi AES în loc de o funcție hash.

Ori de câte ori gestionați o parolă (un secret care este de o forță necunoscută și, mai ales, dacă utilizatorul ar putea să o reutilizeze), rulați-o întotdeauna printr-un algoritm adecvat (lent) de stocare a parolelor pentru ao face lent și unic pentru a sparge. >

Comentarii

• Bună explicație. Dacă am înțeles asta corect, puterea meselor curcubeu constă în a avea o funcție de reducere bună, nu? Cum pot veni cu unul bun? Și cum pot evita coliziunile pentru toți candidații din lanțuri?
• @ Kyu96 Întrebări bune! Nu ‘ nu știu răspunsul, dar aș fi interesat dacă găsiți unul. Această pagină se referă doar la întrebarea generală a ceea ce este o masă curcubeu, nu la detalii precum cum să proiectăm un algoritm. Ar trebui să deschideți o nouă întrebare , dar acest site web este despre ” protejarea activelor împotriva amenințărilor digitale ” (iirc ). Cred că ar fi subiect pentru site-ul nostru suror, crypto.stackexchange.com , care este despre ” matematica și proprietățile sistemelor criptografice, analiza acestora (” cryptanalysis „) și subiecte subsidiare care alcătuiesc în general criptologia, cum ar fi numărul aleator generație. ”