Exemplele persoanei pe care le-am dat în întrebarea mea de mai sus sunt corecte în afirmația lor - acel exemplu 2 va face ca ciocnirile, vorbind probabilitatea, să se întâmple mai rar?
Se fac mai multe afirmații Acolo:
O afirmație este că funcția 1 de parola + sare cedând hash definit de
hash = sha512(parola + sare);
pentru (i = 0; i < 1000; i++) {
hash = sha512(hash); // <-- NU faceți asta!
}
este mai probabil să se ciocnească decât funcția 2 de parola + sare cedând hash definit de
hash = sha512(parola + sare);
pentru (i = 0; i < 1000; i++) {
hash = sha512(hash + parola + sare);
}
Acest lucru este corect în teorie și ar fi observabil în practică pentru un hash îngust, de ex. 80 de biți.
O modalitate de a vedea este că
- setul de ieșire al unei funcții aleatoare fixe $H$ repetat $n$ timpii tinde să se îngusteze ca $n$ crește (argument: nu poate crește niciodată când $n$ face și unele rezultate de îngustare din coliziuni ale hash-ului iterat, aici SHA-512);
- probabilitatea de coliziune a unei funcții aleatoare pentru două intrări aleatorii distincte este inversa mărimii setului de ieșire.
Este astfel de înțeles (chiar dacă repetarea unei funcții aleatoare $n$ ori s-ar putea să nu producă o funcție aleatorie peste ceea ce rămâne din setul de ieșire) că probabilitatea de coliziune a $H^n(x)$ pentru două distincte aleatorii $x$ creste cu $n$.
Aceasta limitează rezistența la coliziune a funcției 1 care pentru bucla se repetă $H: h\mapsto\operatorname{SHA-512}(h)$. În timp ce în 2, funcția iterată se schimbă atunci când este introdusă parola + sare se modifică, astfel încât seturile de ieșire se micșorează cu $n$ depinde de acea intrare. Conform unui model de hash ca funcție aleatoare, 2 este, de asemenea, o funcție aleatoare care poate atinge setul complet și probabilitatea de coliziuni pentru diferite intrări parola + sare nu creste ca $n$ face.
Se afirmă, de asemenea, că, din acest motiv, ar trebui să folosim în practică 2 în loc de 1, iar acest lucru este incorect din mai multe motive:
- Cel puțin pentru orice hash care este rezistent la coliziuni, așa cum este SHA-512, nu trebuie să ne facem deloc griji cu privire la coliziuni sau cicluri.
- În context (aplicația de hashing a parolei), rezistență la coliziune a funcției iterate generale nu este o problemă. Rezistenta preimagine este. Și chiar și pentru SHA-1, care nu este rezistent la coliziuni și nu este realist $n$, nu trebuie să ne îngrijorăm că ruperea 1 ar necesita evaluări considerabil mai puține ale hash-ului decât ruperea 2, inclusiv cu precalcul realist.
Un avantaj al lui 2 este: este puțin mai dificil de implementat în hardware deoarece hardware-ul trebuie să folosească parola și sare la fiecare iterație, care astfel trebuie să fie stocate. ASIC-urile pentru a accelera 2 vor fi astfel mai complexe decât pentru 1. Acesta este singurul motiv pentru care văd că 2 este mai puțin rău decât 1 în practică. Încă este rău, pentru că $n=1000$ iterațiile nu sunt suficient de lente pentru ASIC-uri sau GPU-uri care efectuează căutarea prin parolă; și pentru că totul nu folosește memoria, pierzând astfel protecția suplimentară împotriva căutării prin forță brută a parolelor pe care le-a folosit parolele moderne (cum ar fi cripta sau Argon2) da.
Hashingul de mai multe ori va fi mai sigur decât hashingul o dată
Acest lucru depinde în primul rând de obiectiv, care dictează hash-ul de utilizat
- Dacă facem hashing în scopul întinderea cheii, adică de obicei atunci când se trimit o parolă sau o expresie de acces, da: securitatea împotriva căutării cu forță brută crește aproximativ liniar odată cu numărul de runde. Dar, din nou, ar trebui să folosim un hash de parolă dur de memorie.Pentru timpul petrecut egal, chiar și pentru cei învechiți bcrypt va oferi mai multă siguranță decât construcțiile care repetă pur și simplu un hash, cum ar fi PBKDF2 sau funcțiile 1 și 2, care nu sunt recomandate în era ASIC-urilor, FPGA-urilor și GPU-urilor pentru spargerea parolei.
- Dacă facem hash de mai multe ori pentru a consolida o funcție hash criptografică cu un defect (de exemplu, rezistența la coliziune este ruptă), probabil că da. De exemplu. funcția 2 (cu
parola + sare înlocuit cu mesajul la hash) ar remedia toate defectele de securitate cunoscute ale MD5 sau SHA-1 pe lângă lățimea lor de ieșire, chiar dacă facem o singură rundă suplimentară în loc de 1000. Cu toate acestea, acesta este la un preț uriaș în performanță și utilizare, deoarece trebuie să hașăm mesajul de două ori, astfel încât, în unele cazuri, îl stocăm.
- Pentru alte scopuri criptografice, inclusiv semnătura și derivarea cheii dintr-o cheie largă folosind un hash modern, nr. Putem folosi SHA-2 sau SHA-3 (pentru a-i numi pe cei din întrebare) în aceste scopuri. Hashingul repetat nu este necesar și poate chiar reduce ușor rezistența la coliziune (dacă este efectuată ca în 1), cu o singură excepție: dacă hash-ul are proprietate lungime-extensie (așa cum are SHA-2, dar nu SHA-3), și dacă acest lucru nu este de dorit, este rezonabil să re-hash odată ce ieșirea hash-ului (care nu necesită stocarea mesajului de două ori).
