Algoritmul lui Grover (sau orice alt algoritm cuantic aplicabil) se aplică doar pentru slăbirea funcției hash în sine sau poate căuta și numai intrări plauzibile (a-z, A-Z, 0-9 <=14 caractere) pentru a reduce spațiul de căutare?
Grover este o metodă de căutare generală - nu știe sau nu îi pasă cum este dată funcția interpretează intrarea. Dacă îi oferiți o funcție care interpretează intrările ca „(a-z, A-Z, 0-9 <=14 caractere)”, va funcționa cu ea, cu complexitatea așteptată.
Pe de altă parte, întrebarea relevantă poate fi „este folosirea unui computer cuantic are sens economic, spre deosebire de o fermă de GPU sau de unele ASIC?” Sugerez că pentru următoarele decenii (adică până când tehnologia Quantum Computer va trece printr-un număr de generații), metodele clasice vor fi mai rapide în acest caz.
Unele dintre motivele pentru aceasta:
Costul unei operațiuni de calcul cuantic poate fi de așteptat să fie mult mai mare decât costul celui clasic corespunzător. Acesta este un factor constant atunci când se compară cele două - totuși, dacă acest factor constant este poate de un miliard sau de un trilion, chiar nu ar trebui ignorat.
Paralelizare - căutările clasice pe computer (ca aceasta) sunt perfect paralelizabile (de care ar profita din plin o fermă de GPU sau un set de ASIC-uri). În schimb, algoritmul lui Grover (sau orice căutare similară Quantum Oracle) nu este - înțelegi că $n^2$ accelerați dacă puteți efectua $O(n)$ operațiuni succesive. Cu toate acestea, dacă nu puteți aștepta atât de mult și trebuie să implementați mai multe calculatoare cuantice pentru a efectua căutarea, ei bine, nu obțineți asta. $n^2$ accelera între ei. De exemplu, pentru a efectua căutarea de 100 de ori mai rapid, aveți nevoie de 10.000 de ori mai multe calculatoare cuantice.
Reutilizarea cheii de căutare. Cu calculul clasic, putem genera un tabel Rainbow - generarea acelui tabel durează cam atât timp cât căutarea completă; cu toate acestea, odată ce este finalizat, efectuarea de căutări repetate pe diverse parole cu hash este ieftină. În schimb, rularea algoritmului lui Grover va face o căutare pe o singură parolă - dacă vrem să verificăm un alt hash, trebuie să plătim din nou pentru căutarea completă. Ai putea construi o masă Rainbow pe un computer cuantic, desigur; cu toate acestea, nu cred că veți obține o accelerație cuantică și nu am auzit de o alternativă în care să obțineți o viteză cuantică.
Acum, de-a lungul timpului, ne putem aștepta în mod rezonabil ca costul calculatoarelor cuantice să scadă (și să scadă mai repede decât costul comparativ al calculatoarelor clasice) și ne putem aștepta ca calculatoarele cuantice să devină mai rapide în timp (deci necesită mai puțină paralelizare); Pur și simplu nu mă aștept ca niciuna dintre tendințe să se întâmple peste noapte...
Pentru a fi clar, am înțeles că orice funcție de hashing (chiar și cu ieșiri inutil de lungi, cum ar fi SHA-512) este o modalitate groaznică de a stoca parolele utilizatorilor și ar trebui folosit Argon2 sau similar, dar m-am gândit că duritatea memoriei și alte aspecte ar putea face întrebarea prea largă sau un răspuns mai puțin aplicabil.
Cu înțelegerea noastră actuală a compromisurilor inerente într-un computer cuantic (care ar putea fi considerabil în afara bazei), o funcție de memorie hard ar fi destul de dureros să se ocupe de un computer cuantic. Evaluarea unei astfel de funcții hash pare să necesite o memorie cuantică mare și (din câte știm noi) aceasta pare a fi îngrozitor de costisitoare [1].
Algoritmul lui Grover ar fi aplicabil (din nou, nu-i pasă care este funcția hash); cu toate acestea ar părea a fi destul de scump.
Deci, presupunând că presupunerile noastre sunt corecte, o funcție de memorie hard hash (Argon2) ar fi și mai rezistentă la calculul cuantic decât funcțiile hash simple.
[1]: Cred că cel puțin o parte din motiv este că dacă aveți o memorie cuantică mare și o accesați pentru o adresă încurcată, ajungeți să efectuați operațiuni pe fiecare celulă de memorie (sau cel puțin, fiecare celulă care ar putea fi adresată de adresa încâlcită). În schimb, cu o memorie clasică, trebuie doar să accesați celula care este adresată. Dacă vorbim de o memorie cu 1.000.000 de locații adresabile, aceasta înseamnă că memoria cuantică ar putea avea nevoie să efectueze de 1.000.000 de ori mai multe operații în comparație cu cazul clasic.
