In che modo è necessario modificare la sicurezza se siamo in grado di rompere gli hash delle password in un tempo quasi polinomiale?

Penso che il modo migliore per rispondere alla tua domanda sia: la premessa è altamente non plausibile, quindi il problema semplicemente non si pone.

Potrei anche chiedere: se supponiamo di scoprire il viaggio nel tempo, c'è motivo di allarme per la sicurezza delle password? Certo, se scopriamo il viaggio nel tempo, qualcuno potrebbe viaggiare indietro nel tempo, apparire poof appena prima di inserire la mia password, guardare dietro le spalle quando ho digitato la mia password e poof scomparire prima che me ne accorga.

Oppure, se il mio computer può viaggiare su richiesta, posso impostarlo per iterare il seguente ciclo: scegliere una password casuale, provare a vedere se è corretta, se è corretta, stampare la password e fermarsi; se non è corretto, torna indietro nel tempo all'inizio del ciclo e ricomincia. Se è possibile l'algoritmo del time-travel, questo è un algoritmo O (1) -time per decifrare qualsiasi password, dato il suo hash della password!

Ma ovviamente queste risposte sono sciocche, perché per il futuro prevedibile non c'è alcuna probabilità realistica che qualcuno scoprisca come viaggiare indietro nel tempo. Allo stesso modo, per il prossimo futuro non c'è alcuna prospettiva realistica che qualcuno scopra un algoritmo per risolvere efficientemente tutte le istanze SAT. Certo, se qualcuno riuscisse a trovare un algoritmo di risoluzione SAT in grado di risolvere ogni istanza SAT in 15 secondi, potrebbe craccare ogni password (dato il suo hash della password) in 15 secondi. Ma non penso che sia terribilmente probabile che accada nella mia vita.

P.S. Vedo che cliccando sul tuo link probabilmente preferiresti una risposta più tecnica. Il mio suggerimento è di leggere sul compromesso spazio-tempo di Hellman e sui tavoli arcobaleno; ciò ti darà una migliore comprensione dei metodi più avanzati applicabili al cracking delle password. Si potrebbe anche voler leggere perché le tabelle arcobaleno non sono applicabili alle password salate; È probabile che ragioni simili si applichino ai tuoi metodi.

Osservando la complessità del metodo nel tuo link, vedo che il tuo metodo richiede un precomputazione 2 ^v , dove v è il numero di variabili nell'istanza SAT. Al contrario, il compromesso spazio-tempo di Hellman e le tabelle arcobaleno richiedono un precomputazione 2 ⁿ , dove n è il numero di bit della password (il numero di bit immessi nella funzione hash). Nell'impostazione della password, n sarà molto più piccolo di v , quindi le tabelle arcobaleno e il compromesso spazio-tempo di Hellman sembrano funzionare meglio del tuo metodo. In altre parole, non mi sembra probabile che il tuo metodo, anche se valido, supererà lo stato dell'arte del crack delle password o avrà molta rilevanza per il crack delle password nella pratica. Naturalmente, puoi sempre provarlo in un piccolo esperimento e confrontare il tuo metodo con i cracker delle password esistenti; quello sarebbe il vero test. Ma al momento, non vedo alcun motivo per aspettarci progressi nella risoluzione SAT che sarebbero rilevanti per il cracking delle password.

Lasciatemi solo citare le tue due domande reali e metti le cose di SAT al lato ...

If we suppose that we have access to some form of generalized password hacking/cracking that can somehow find an $n$-bit password in time $O(n^{\log n})$, is there need for alarm?

Se supponiamo che sia vero per un esperimento mentale, allora sì, siamo chiaramente nei guai, dal momento che tutte le password del mondo saranno semplicemente irrilevanti. Rispetto al cracking di un hash per le password, è relativamente facile mettere le mani sul detto hash. Non è che tutti conoscessero immediatamente la password di tutti gli altri, ma sarebbe male.

I am really wondering if we know some sort of threshhold (in terms of speed) where password hacking begins to get dangerous?

Vuoi dire che un hacker "morale" (non cracker) dovrebbe smettere di hackerare ad un certo punto? È vero il contrario, per quanto mi riguarda. Se la gente smette di hackerare questa roba perché teme di avvicinarsi troppo a una soluzione, allora sarà più cracker inclini alla moralità che non si fermeranno. Gli hacker "benigni" sono gli unici a poter indicare potenziali pericoli e almeno a cercare di ottenere qualsiasi tipo di avvertimento in anticipo.

Questo ha ottenuto un voto di domande molto alto.

Ad ogni modo, se è vero, che memorizzare gli hash delle password ~ = memorizzare le password in chiaro. Ora considera quali sarebbero le esigenze di sicurezza in atto per la memorizzazione di password in chiaro.

Nel caso in cui non sia evidentemente ovvio, ora è richiesto l'uso di password completamente diverse per ogni sito, e questo significa usare un gestore di password o scrivere le password in basso. E questo presuppone che la crittografia sottostante che protegge SSL sopravviva (non dovrebbe).

Sì, il time cracking quasi-polinomiale o le password potrebbero portare a un numero notevolmente maggiore di intrusioni sulla sicurezza. Il crack delle password con la forza bruta è già stato fatto, quando gli hacker sono abbastanza disperati da aspettare un algoritmo esponenziale. Se gli hacker potessero violare le password in un tempo quasi polinomiale, creerebbero ancora più password. Ovviamente, devono avere accesso al dizionario delle password in modo che non vengano arrestati dal numero di tentativi di password. Il numero di tentativi di password consentiti è in genere costante, quindi anche il cracking quasi polinomiale può essere eseguito in blocchi a meno che gli hacker non abbiano il dizionario.

Perdonami, non ci sono riduzioni standard dal SAT alle applicazioni di crittografia? Sembra una riduzione che dovrebbe esistere in letteratura. Poiché la crittografia stessa è ridotta a SAT tramite NP-completezza, anche gli algoritmi di cracking utilizzano la stessa riduzione. Si prega di consultare il manuale di teoria CS per riduzioni polivalenti utilizzate per dimostrare la completezza di NP. Una riduzione polivalente può essere certamente utilizzata per trasformare un algoritmo SAT tempo psuedo-poly in un algoritmo di password cracking per password crittografate, poiché il tempo poligonale è più veloce del tempo pseudo-poli.