Cum funcționează hashingul?

Rapid, factor 1081.

Sau, dacă preferați, răspundeți la acest lucru: ce este de 23 de ori 47?

Care este mai ușor? Este mai ușor să efectuați o înmulțire (urmați doar regulile mecanic) decât pentru a recupera operanzii dat doar produsul. Multiplicare. (Apropo, acesta este fundamentul unor algoritmi criptografici precum RSA .)

Funcțiile de hash criptografice au fundații matematice diferite, dar au aceeași proprietate: sunt „re ușor de calculat înainte (calculați H (x) dat x), dar practic imposibil de calculat mergând înapoi (dat y, calculați x astfel încât H (x) = y). De fapt, unul dintre semnele unui hash criptografic bun funcția este că nu există o modalitate mai bună de a găsi x decât să le încerci pe toate și să calculezi H (x) până când găsești o potrivire.

O altă proprietate importantă a funcțiilor hash este că două intrări diferite au hashuri diferite. dacă H (x ₁ ) = H (x ₂ ), putem concluziona că x ₁ = x ₂ Matematic vorbind, acest lucru este imposibil – dacă intrările sunt mai mari decât lungimea hashului, trebuie să existe coliziuni.Dar, cu o funcție hash criptografică bună, nu există o modalitate cunoscută de a găsi o coliziune cu toate resursele de calcul din lume.

Dacă doriți să înțelegeți mai multe despre funcții hash criptografice , citiți acest răspuns de Thomas Pornin . Continuați, voi aștepta.

Rețineți că o funcție hash nu este o funcție de criptare. Criptarea implică faptul că puteți decripta (dacă știți cheia). Cu un hash, nu există un număr magic care vă permite să vă întoarceți.

Principalele funcții hash criptografice recomandate sunt SHA-1 și Familia SHA-2 (care vine în mai multe dimensiuni de ieșire, în principal SHA-256 și SHA-512). MD5 este unul mai vechi, acum învechit deoarece a cunoscut coliziuni. În cele din urmă, nu există nicio dovadă matematică că sunt într-adevăr funcții hash criptografice bune, ci doar o credință larg răspândită, deoarece mulți criptografi profesioniști și-au petrecut ani din viață încercând și eșuând să le rupă.

Ok, că ” Este o parte a poveștii. Acum un hash parolă nu este direct o funcție hash criptografică. O funcție hash parolă (PHF) ia două intrări: parola și o sare. sare este generată aleatoriu atunci când utilizatorul își alege parola și este stocate împreună cu parola hash PHF (parolă, sare). (Ceea ce contează este că două conturi diferite au întotdeauna săruri diferite și generarea aleatorie de sare suficient de mare este o modalitate bună de a avea această proprietate cu o probabilitate copleșitoare.) Când utilizatorul se înregistrează din nou, sistemul de verificare citește sarea din baza de date a parolelor, calculează PHF (parolă, sare) și verifică dacă rezultatul este ceea ce este stocat în baza de date.

Scopul sării este că, dacă cineva vrea să spargă o parolă, va trebui să știe hash înainte de a putea începe și trebuie să atace fiecare cont separat. Sarea face imposibilă efectuarea în prealabil a multor lucrări de crăpare, de ex. prin generarea unui tabel curcubeu .

Acest lucru răspunde (2) și (3) – verificatorul legitim și atacatorul află în același lucru modul în care parola (introdusă de utilizator sau ghicită de atacator) este corectă. Un ultim punct al poveștii: o funcție bună de hash de parolă are o proprietate suplimentară, trebuie să fie lentă. Serverul legitim trebuie să îl calculeze o singură dată pe fiecare încercare de conectare, în timp ce un atacator trebuie să îl calculeze o dată pe fiecare presupunere, astfel încât încetineala îl rănește mai mult pe atacator (ceea ce este necesar, deoarece atacatorul are de obicei mai mult hardware specializat).

Dacă vreți să folosiți parole hash, nu vă inventați propria metodă . Utilizați una a metodelor standard : scrypt , bcrypt sau PBKDF2 .  

Comentarii

• La naiba I veniți pe site-ul de securitate de la toți ceilalți și singurul lucru care este foarte clar este că voi băgați o muncă nebună în a răspunde. Nu numai corect, ci extrem de minuțios. Mi-aș dori să pot selecta două răspunsuri, dar al vostru seamănă mult mai mult cu ceea ce Căutam.
• @Griffin – Cu toate acestea, poți să votezi în sus. Sau într-adevăr – atunci când există ‘ mai mult de t wo răspunsuri – votează în sus tot ceea ce crezi că au fost de ajutor, chiar dacă poți accepta doar unul. Multe întrebări de aici au mai mult de un răspuns bun și, uneori, ‘ este chiar recomandat să citiți majoritatea răspunsurilor pentru a înțelege mai bine subiectul aflat la îndemână. Da, uneori chiar și cele votate în jos. Prin vot (în ambele sensuri), îi ajutați pe viitorii cititori să decidă cu privire la validitatea răspunsurilor, în special acei cititori care încă învață despre un anumit subiect. 😉
• Am votat amândoi! Au fost extrem de utile.
• +1: toate răspunsurile sunt bune, dar acesta este cam la fel de aproape de un răspuns perfect ca I ‘ am văzut vreodată pe Stack Exchange. Aș face +10 dacă aș putea.
• @IlmariKaronen Acesta este ‘ motivul pentru care îmi place să vin aici.

Funcțiile hash criptografice sunt obiecte matematice care pot fi descrise ca „o mare amestecare și amestecare a unor biți „. Aceștia iau ca intrare o secvență de biți (posibil unul foarte lung) și oferă o ieșire de dimensiune fixă. Aproximativ vorbind, ele sunt atât de încurcate încât, deși nu există nimic secret în legătură cu acestea (că este doar un cod determinist), nimeni nu își poate da seama cum să le „inverseze” (să găsească o intrare potrivită pentru o ieșire dată) decât prin metoda de bază numită „noroc”: încercați intrări aleatorii până când se găsește o potrivire.

Cum se poate întâmpla, din punct de vedere științific, că funcțiile hash pot exista, este o întrebare bună .

Hashing-ul nu este criptare . Nu există niciun secret, nici o cheie în hashing.

Funcțiile Hash au multe utilizări; una dintre ele este „stocarea parolei”. O funcție hash arată ca un lucru bun pentru stocarea parolei. Nu vrem să stocăm parolele direct (altfel, o privire ocazională în bazele noastre de date de către atacator i-ar oferi prea multe informații; consultați această postare de blog pentru o discuție) ; vrem să stocăm jetoane de verificare a parolei : ceva care permite verificarea unei parole (pe care o prezintă utilizatorul), dar nu dezvăluie parola în sine. Deci ideea este: să stocăm hash-ul parolei. Când o parolă urmează să fie verificată, calculăm hash-ul și vedem dacă se potrivește cu valoarea stocată. Dar ghicirea parolei numai din valoarea hash este dificilă, deoarece funcția hash este rezistentă la „inversare” (vezi mai sus).

Deoarece parolele sunt un tip special de date (datele acelea pe care oamenii le pot aminti), pentru o securitate adecvată, avem nevoie de o „întărire” funcție hash:

• Vrem o funcție hash foarte lentă.
• Nu dorim funcția hash unul , dar multe funcții hash distincte, astfel încât fiecare parolă să fie hash cu propria sa funcție hash; este vorba despre descurajarea atacurilor paralele. Acest proces de transformare a unei singure funcții hash în mai multe variante se numește sărare .

A se vedea acest răspuns pentru un tratament amănunțit al subiectului parolelor hashing.

Comentarii

• Ne pare rău, dar în timp ce răspunsul dvs. a fost extrem de amănunțit și bine pus la punct, am găsit celălalt răspuns să semene mai mult cu ceea ce căutam.

Hashing este o funcție din unele șir de biți (de obicei, lungime variabilă) la un alt șir de biți (de obicei mai mic și cu lungime fixă).

Hashing-ul este utilizat în bazele de date pentru recuperarea datelor și în structurile de date din memorie numite tabele hash. Ne permite să reducem datele arbitrare, cum ar fi un șir de caractere sau un obiect complicat cu multe câmpuri, la un număr binar care poate fi apoi utilizat direct ca index într-o matrice rară pentru a prelua datele asociate (cu unele detalii pentru manipularea hashului) coliziuni).

Funcțiile de hash utilizate în modul de mai sus sunt „veri” ai funcțiilor de hash criptografice. Acestea sunt concepute în funcție de cerințe diferite. Acestea trebuie să fie rapide de calculat și să obțină o distribuție bună.

În calculul securizat, hashurile criptografice sunt folosite pentru a digera datele într-o serie de șiruri de biți reprezentative. Funcțiile criptografice au cerințe diferite. Acestea sunt concepute pentru a fi dificil de inversat (pentru a fi „capcană” sau funcții „unidirecționale”). Nu numai asta, ci o cerință importantă este că trebuie să fie dificil de găsit, pentru un anumit text clar și o valoare hash, un alt text clar care produce același hash.

Hashing-ul poate fi folosit nu numai pentru parole, ci ca sumă de verificare pentru verificarea integrității datelor și ca parte a implementării semnăturilor digitale. Pentru a semna digital un document mare, trebuie pur și simplu să hashem documentul pentru a produce un „rezumat” (un nume folosit pentru ieșirea unei funcții de hash, când ceva hash foarte lung este hash). Apoi, doar acest rezumat este introdus prin cripto-sistem cu cheie publică pentru a produce o semnătură. Puteți vedea slăbiciunea acolo: ce se întâmplă dacă un atacator reușește să producă un document care are același rezumat? Apoi, se pare că semnătura originală produsă peste documentul original este de fapt o semnătură a unui document contrafăcut: a fost efectuată în mod efectiv o falsificare de transplant de semnături.

Hashing-ul parolei permite sistemelor să nu stocheze versiunea în text simplu o parolă, însă le permite să verifice dacă utilizatorul care încearcă să obțină intrarea știe acea parolă. Nu numai că hashing-ul permite sistemelor să nu stocheze parolele text simplu (care ar trebui să fie foarte atent păzite), dar permite posibilitatea ca, chiar dacă hash-urile sunt expuse public, parolele să fie în continuare sigure (în mod similar cu modul în care criptele cu cheie publică sistemele sunt capabile să dezvăluie cheile publice). Deși, în practică, hashurile sunt totuși protejate de accesul publicului: de exemplu, fișierele /etc/shadow pe sisteme de tip Unix, completând fișierele /etc/passwd lizibile în întreaga lume. .

Funcția de hash este orice altceva decât aleatorie. Cu toate acestea, randomizarea este utilizată pentru a contracara atacatorii care construiesc dicționare mari de parole și hashuri, care le permit să caute un cod hash și să recupereze parola corespunzătoare.

Pentru a hash o parolă mai sigur, putem adăuga pur și simplu niște biți întâmplători numiți „sare”. Săruri diferite adăugate la aceeași parolă, desigur, duc la hash-uri diferite (sperăm, cu puține sau deloc coliziuni).

Dacă sarea aleatorie are, să zicem, 32 de biți lățime, înseamnă că, în teorie, o parolă poate hash în peste patru miliarde de moduri diferite, ceea ce face foarte imposibil să existe un dicționar precomputat cu toate hashurile posibile dintr-un număr mare de parole.

Desigur, atunci când utilizatorul este autentificat, nu știe nimic despre această sare. Acest lucru este în regulă, deoarece sarea este stocată împreună cu hash-ul în profilul utilizatorului (adesea, combinat cu hash-ul într-o singură șir de biți compact). Când este validată introducerea parolei utilizatorului, sarea este adăugată la orice parolă a intrat ea, astfel încât hashingul să se efectueze cu sarea corectă. Dacă parola este corectă, hash-ul se va potrivi, deoarece sarea utilizată este și cea potrivită, fiind extrasă din profilul utilizatorului.

Deci, așa este aleatoritatea încorporată în hash-ul parolei, în timp ce încă îi permite să funcționeze.

Ceea ce face ca hashurile să fie greu de spart este că sunt construite din funcții „trap door” sau „one way”. În matematică, există multe exemple de astfel de lucruri. De exemplu, , adăugarea simplă este o ușă capcană. Dacă adăugăm câteva numere întregi pentru a produce o sumă, este imposibil să recuperăm numerele originale, știind doar suma.

Hash-urile parolelor nu sunt parole criptate. Dacă un atacator are hashul și sarea unei parole și se întâmplă să ghicească parola, atunci ea poate confirma cu ușurință acest lucru, exact în același mod în care îl face software-ul de autentificare a autentificării: ea rulează parola plus sarea prin funcția de hash și vede că este corect apare hash.

Comentarii

• Abilități excelente de scriere și o ușurință y pentru a înțelege răspunsul care este corect de fapt, dar abordează toate punctele și păstrează un flux natural care îl face mult mai cuprinzător. ‘ nu este o ispravă ușoară, mulțumesc mult pentru răspunsul dvs.!
• foarte informativ. Ați acoperit toate aspectele.

Una dintre cheile pentru hashing este că aruncă informații. Nu puteți inversa un hash, deoarece cunoștințele necesare au dispărut. Iată câteva exemple de funcții hash viabile (dar destul de inutile). Dacă îmi dai o parolă, aș putea face ceva de genul:

• Numărați numărul de vocale
• Luați codul ASCII pentru fiecare literă și XOR-le pe toate împreună
• Luați suma de control CRC32 a reprezentării binare a parolei (aceasta este de fapt un hash real, doar nu unul criptografic)

În fiecare dintre aceste cazuri, nu pot inversa procesul. În schimb, trebuie să reexecut procesul când îmi dai parola din nou mai târziu pentru a vedea dacă calculul pe care l-am executat se potrivește.

Pentru exemplu: Dacă inițial îmi dai parola „maimuță”, aș putea stoca numărul 3 (3 vocale). Apoi, mai târziu, când încerc să autentific parola „dragon”, execut din nou aceeași verificare și vin cu 2, care nu se potrivește cu 3. Deci știu că mi-ai dat parola greșită. Dar dacă îmi dai parola „melissa”, aș presupune incorect că ai introdus parola corectă. Acesta este un hash coliziune .

Setul de reguli pe care îl aplicați pentru a veni cu numărul care reprezintă o parolă dată este funcția hash . Acestea sunt considerate funcții „unidirecționale”, deoarece nu ar trebui să le puteți inversa. Funcțiile hash de înaltă calitate sunt concepute pentru a limita numărul de coliziuni potențiale, astfel încât să nu vă faceți griji cu privire la această problemă. Un pas mai departe, funcțiile hash criptografice sunt concepute pentru a face dificilă apariția unui șir care s-ar putea potrivi cu o ieșire dată ( și poate crea intenționat coliziuni). De asemenea, acestea sunt concepute pentru a limita cantitatea de informații pe care o puteți obține despre o intrare dată doar din ieșirea hash.

Prin urmare, singurul mod de a spune ce parolă se potrivește cu un hash criptografic dat este să încercați toate posibilitățile până când vă dați peste una care funcționează. Alte măsuri contrare (sare, BPKDF2 etc.) fac acest proces de ghicire și mai dificil, făcând persoana care ghicește parola să sară prin mai multe cercuri pentru fiecare încercare.

Rețineți că am analizat complet modul în care o funcție hash criptografică o face dificil de găsit o parolă de lucru (chiar dacă nu este cea originală). Aceasta se numește „ atac preimagine „. În exemplul banal de mai sus, venirea cu” melissa „ca parolă candidată care conține 3 vocale este un exemplu de astfel de atac.

Funcțiile de hash criptografice fac de obicei acest lucru executând intrarea deși mai multe” runde „ale unui proces dat, unde ieșirea fiecărei runde devine parte a intrării în următoarea.Pentru a afla intrarea primei runde, ar trebui să vă dați seama de intrarea celei de-a doua runde, ceea ce, la rândul său, vă cere să aflați intrarea celei de-a treia runde etc., ceea ce înseamnă că fiecare estimare a fiecărei componente trebuie verificat printr-un set lung și complex de calcule. Thomas Pornin are o explicație destul de exhaustivă a modului în care funcționează această rezistență; lectură destul de utilă, dacă doriți cu adevărat înțelegeți-l.

1. Determinați valoarea constantă a z care îndeplinește această ecuație: xy ^ 7 + yz ^ 5 + x ^ 3z = 0. Aveți nevoie de ajutor? OK, x = 32. Încă nu îl puteți rezolva? Atunci nu ar trebui să știți răspunsul în primul rând.

   Valoarea lui y, care va reduce aceasta la o singură ecuație variabilă, făcând rezolvarea acesteia pentru acea singură variabilă banală pentru orice elev de clasa a VI-a (posibil nevoie de un calculator), este un secret pe care l-am împărtășit doar cu oamenii în care am încredere. Fără acesta, z ar putea fi orice; valoarea sa este dependentă de y și, prin urmare, nu poate fi rezolvată în mod satisfăcător fără un y constant, cunoscut. Dacă nu ” Nu știu valoarea ta, este pentru că nu am avut suficientă încredere în tine pentru a ți-o da în privat.

   Acesta este principiul de bază al criptografiei; formula matematică sau alt proces determinist este bine -documentate, și una sau mai multe dintre variabilele posibile ale formulei sunt, de asemenea, permise să fie cunoscute public, permițând celor două părți să cadă de acord asupra unei modalități de configurare a cifrelor lor, astfel încât fiecare să poată decripta ceea ce criptează celelalte. Cu toate acestea, două variabile rămâneți secret; dacă îl cunoașteți, îl puteți descoperi pe celălalt. Cel pe care ar trebui să-l cunoașteți este cheia și cel pe care îl aveți mesajul poate fi descoperit cu cheia.

   Pentru un hash, este puțin diferit. Un hash nu necesită păstrarea unui secret pentru a păstra altul. În schimb, hash-urile funcționează pe baza unei transformări matematice ireversibile; pentru orice H (x) = y, nu se cunoaște H ^-1 (y) = x, cu excepția faptului că încercați H (x) pentru tot posibilul x până când obțineți y. De obicei, acest lucru se datorează faptului că mai multe rezultate intermediare ale ecuației sunt ambigue; de exemplu, calcularea rădăcinii pătrate a unui număr pozitiv produce tehnic atât un rezultat pozitiv și negativ, deoarece oricare număr ar putea fi înmulțit cu el însuși pentru a produce rezultatul. Inversul unui modul este în mod similar ambiguu; numărul 1, produs de x mod 3, ar fi putut fi produs de orice x = 3k + 1. Aceste tipuri de transformări „unidirecționale” sunt combinate în așa fel încât încercarea de a calcula funcția hash inversă generează posibilități infinite; modul mai ușor (cel mai ușor) de a le rezolva este, prin urmare, să încercați pur și simplu fiecare intrare posibilă până când o ieșire se potrivește. durează încă mult timp.

2. Hash-urile nu sunt întâmplătoare. După cum am afirmat anterior, hashurile sunt rezultatul unei operații matematice ireversibile. Această operațiune trebuie să fie în continuare deterministă; având o intrare constantă, ieșirea este constantă indiferent de câte ori efectuați operația. Nu există o componentă aleatorie.

   Unde ați fi fost confuz este în termenul pentru ceea ce simulează un hash, care este un oracol aleatoriu . Imaginați-vă o cutie neagră, în interiorul căreia se află un omuleț cu memorie fotografică și o metodă mistică de a genera numere perfect aleatorii. Scrii ceva pe o bucată de hârtie și o împingi printr-un slot unde omul îl obține. El îl citește și se întâmplă unul din cele două lucruri. Fie nu l-a citit înainte, caz în care va genera un nou număr aleatoriu și ți-l va da, trimitând atât mesajul tău, cât și numărul în memoria sa. Sau, a citit exact acest lucru mesaj anterior, caz în care își amintește numărul pe care l-a generat prima dată când l-a citit și îți dă numărul. Generatorul de numere aleatorii nu va genera niciodată un număr pe care l-a generat deja, are o magnitudine posibilă infinită, iar omul mic memoria este nelimitată și infailibilă. Prin urmare, omulețul nu va crede niciodată că a citit un mesaj înainte dacă nu a „uitat niciodată că a citit un mesaj înainte și așa nu va produce niciodată, niciodată, două numere diferite pentru același mesaj și nici același numărul pentru două mesaje diferite.

   Acesta este ceea ce încearcă să simuleze funcțiile hash. Ei nu pot modela acest omuleț cu memoria fotografică, deoarece ar necesita spațiu de stocare infinit și disponibilitate universală nelimitată, chiar și pentru dispozitive care nu sunt conectate la orice alt dispozitiv în niciun alt mod. În schimb, se bazează pe un calcul determinist, dar cu aspect aleatoriu care „digeră” mesajul în valoarea lui hash. Aceeași funcție hash, dat același mesaj, va produce același rezumat; cu toate acestea, aceste funcții sunt limitate în numărul de valori hash pe care li se permite să le returneze. Acest lucru creează posibilitatea a ceea ce numim coliziuni hash; există mai multe mesaje posibile decât valori hash, deci mai devreme sau mai târziu (să sperăm că mai târziu), două mă diferă ssages vor produce același hash.

3. Hash-urile pot fi sparte din trei motive de bază.În primul rând, deoarece sunt o derivare deterministă, matematică a mesajului lor, matematicienii (și, astfel, atacatorii) găsesc în cele din urmă o relație matematică între un mesaj și hash-ul acestuia, sau între două mesaje și hash-urile rezultate. Ceea ce a fost odată aleatoriu nu mai este așa. Acest lucru ar permite o serie de atacuri bazate pe natura slăbiciunii constatate; dacă există un mod algoritmic, dat un mesaj și hash-ul acestuia, de a genera un mesaj în coliziune, aceasta este o problemă. Dacă există o modalitate de a manipula un mesaj și de a prezice hash-ul rezultat, aceasta este o problemă diferită. Dacă există, de fapt, o modalitate de a inversa hash-ul, producând un mesaj din hash care, atunci când este re-hash, produce același hash, acea problemă „sa serioasă .

   În al doilea rând, deoarece hashurile au o dimensiune limitată a rezumatului, mai devreme sau mai târziu, două mesaje vor produce același hash. Asta înseamnă că un atacator nu trebuie să găsească mesajul pe care îl utilizați pentru a produce un anumit hash. ; tot ce trebuie să facă este să găsească un mesaj a care să producă același hash. Șansele sunt slabe, teoretic, există o șansă din oricât de multe hash-uri posibile există, dar mai bune decât una în infinit.

   În cele din urmă, deși există o mulțime de mesaje posibile, există o mult mai mică numărul de mesaje probabile . Mesajele pe care le oferim în mod obișnuit funcțiilor hash au de obicei o anumită structură (bazată pe limbă, subiect, formatare electronică și scop), ceea ce înseamnă că, având în vedere o parte a mesajului, putem ghici mai precis alte părți ale mesajului. Aceasta înseamnă, în termeni științei informației, că mesajele care sunt convertite în hashuri au adesea entropie mai mică decât funcția hash în sine; clar spus, o funcție hash care produce rezoluții pe 256 de biți poate produce teoretic orice permutare a acestor biți, 2 ^ 256. Cu toate acestea, dacă există, să zicem, doar 10.000 de mesaje posibile care ar putea fi introduse vreodată în această funcție hash de către un sistem care este studiat pentru atac, atunci doar 10.000 din cele 2 ^ 256 valori hash posibile vor fi văzute vreodată și, mai important, o În cel mai rău caz, atacatorul ar trebui să încerce toate cele 10.000 de intrări posibile pentru a-l găsi pe cel care produce valoarea hash pe care o caută.

Comentarii

• Și acesta este motivul pentru care îmi place securitatea IT ‘ chestiunea site-ului de schimb de stive.
• De asemenea, explicația ta din # 1 este exact ceea ce aveam nevoie. Cu toate acestea, am o întrebare. Se pare că ” hashes ” sunt ca versiunile numerice pentru un anumit lucru (parole în acest caz). Deci, dacă am un site web și mă înscriu 100000 de persoane. Apoi, 50% folosesc parola ” parola ” Sunt capabil să economisesc o tonă de spațiu stocând doar valoarea hash a ” parolă ” în loc de parolă de o grămadă de ori?
• Ei bine dacă ‘ re folosind un hash securizat (> = dimensiune de rezoluție de 256 de biți) apoi stocând valoarea hash a ” parolă va crește dimensiunea stocării. În plus, dacă un atacator ar vedea vreodată că 50% din conturile de utilizator au același hash de parolă, el ‘ ar ști că tot ceea ce ‘ să spargeți o parolă și are acces la 50% din conturile de utilizator. Ar trebui să ” sări ” hash-ul parolei; există o varietate de metode, dar rezultatul final este că aceeași parolă marcată de același algoritm produce un rezumat diferit, din cauza unei valori de sare suplimentare unice pentru fiecare cont.