Perché i sali possono essere pubblici? [duplicare]

Il punto di un sale unico è questo: il lavoro che l'attaccante esegue per decifrare la password salata di un utente non può essere riutilizzato contro un altro utente. Quindi affronta questo punto della tua domanda:

Even if you had to recalculate the hash for every user, that is still only one calculation for each user. And if applying a salt is O(1), shouldn't undoing every user cost O(n)?

Pensaci in questo modo. Supponiamo che tu abbia n utenti e che l'autore dell'attacco esegua tentativi di password m . Se non si dispone di sali, l'utente malintenzionato può verificare ciascuna delle sue m parole d'ordine per tutti gli utenti n , il che significa che possono eseguire m × n ipotesi utente / password.

Con i sali unici, d'altra parte, ognuna delle ipotesi della password m dell'attaccante è applicabile solo a un utente. In questo modo possono solo eseguire tentativi di coppie di utenti / password m . Questa è una grande vittoria per il difensore.

E questa analisi presuppone che l'attaccante conosca tutti i sali. Quindi la risposta alla tua domanda, in senso stretto, è che i sali possono essere pubblici perché offrono un grande miglioramento della sicurezza anche se l'hacker li conosce. (In contrasto con le chiavi, ad esempio, le crittografie offrono la sicurezza no contro un utente malintenzionato che conosce la chiave.)

Possiamo modificare un po 'la tua domanda e chiedere: perché non mantenere segreti i sali? Bene, questo è in realtà una cosa; il nome popolare di "sali segreti" è pepe , e ci sono persone che li usano, offrono ulteriore sicurezza oltre a ciò che fanno i sali pubblici. Ma molte persone semplicemente non pensano che la sicurezza extra valga il tempo e il fastidio di mantenere segreti aggiuntivi. Altri sono effettivamente scettici sul fatto che aggiungano maggiore sicurezza nella pratica:

• link
• link

Tuttavia, altri sono più positivi riguardo ai peperoni. In particolare, la richiesta del concorso per l'hash delle password ha permesso specificamente agli algoritmi di accettare una "chiave segreta" (pepe) oltre a un sale

Ma una cosa è certa: l'uso dei peperoni è molto più complesso rispetto all'utilizzo di sali pubblici, a causa delle ulteriori misure necessarie per garantire che un compromesso del database delle password non comprometta anche i peperoni.

From what I understand, salts are called "salts" rather than "keys" because they are allowed to be public.

Questa è solo una parte della storia. Le chiavi vengono utilizzate in un'operazione di crittografia reversibile. Un hash è progettato per essere irreversibile . Un Salt in a Hash è più simile a quello che le routine di crittografia chiamano un vettore di inizializzazione. L'intento è renderlo unico.

However, isn't going from salted password to hashed password trivial if the salt is public?

Il sale non è pubblico. È memorizzato accanto all'hash. Un database di hash rubati è più difficile da decifrare se ognuno ha un sale unico, anche se tutti i sali sono noti.

da mia altra risposta a un domanda correlata:

Dovresti utilizzare un hash di password lenta. (per esempio bcrypt) Per "lento" intendo computazionalmente costoso, prendendo più di 100 ms (sul tuo hardware) ^{con la protezione DoS *} per testare una singola password. Ciò serve ad aumentare la potenza di elaborazione necessaria (sull'hardware dell'attaccante) per trovare la password con la forza bruta, nel caso in cui l'hash venga rubato.

Per utente sale unico altamente raccomandato. (nel caso di bcrypt viene generato automaticamente) Salt dovrebbe essere altamente unique (cioè lungo e casuale). Usando sale unico significa che un utente malintenzionato dovrebbe eseguire un lavoro di forza bruta separato per ciascun utente .

Se non c'erano "sale", l'attaccante poteva usare immediatamente un Tavolo Arcobaleno e nessuna forza bruta.

Se si utilizza solo un "sale condiviso", un utente malintenzionato potrebbe crackare le password per tutti gli utenti con un job forza bruta singolo . (non veloce come una tabella arcobaleno ma ancora molto più facile di una forza bruta separata Job per ognuno)

_{* Come commentato @Navin , questo sarebbe un potenziale vettore di attacco DoS. Una soluzione è limitare il numero di tentativi orari per IP e per nome utente. È anche possibile che tu debba ridurre la "lentezza" del tuo hash a solo 10ms. Questo non è buono come 100ms da una prospettiva di "hash rubato", ma comunque migliore di "microsecondi".}

Risolviamo un problema più semplice. Fai finta che l'attaccante abbia un elenco di tutte le password univoche usate nel database, ma non sa a chi appartiene. Questo elenco contiene le password p . Ci sono utenti n . p non può essere maggiore di n ma in pratica sarà sempre rigorosamente inferiore a n .

Con un non univoco sale, l'utente malintenzionato deve calcolare ogni hash della password con il sale applicato. Sono calcoli hash O (p) .

Senza sale, se esiste già una tabella arcobaleno per l'algoritmo hash, l'attaccante cerca solo i valori hash per ogni password dalla tabella di ricerca, richiedendo esattamente calcoli hash zero.

Con un unique salt, l'attacker deve calcolare circa la metà di tutti gli hash delle password per ciascun utente , quindi richiede O (n × p) calcoli hash.

In questo esempio molto semplificato, con p≅n , è la differenza tra O (1) , O (n) e O (n²) . In realtà, l'utente malintenzionato NON deve avere un elenco di tutte le password univoche nel database e deve sprecare un sacco di calcoli hash che provano password che non sono nemmeno nel database; in altre parole p <> . Quindi negli scenari della vita reale l'impatto è ancora più estremo, specialmente per il caso di hash univoco.

Sto parlando del numero di calcoli hash per la dimensione del calcolo qui, perché se il tuo sistema è ben progettato con un hash lento, allora quella sarà la parte più costosa dell'attacco. Se la tua parte più costosa è l'enumerazione e il confronto di un hash calcolato per ciascun utente, allora hai un problema più grave.

Ricorda che una tabella arcobaleno è essenzialmente una tabella pre-calcolata che può essere applicata a qualsiasi set di password non salato. Ciò significa non solo la TUA tabella delle password, ma anche quella di tutti gli altri. La creazione della tabella arcobaleno è difficile e richiede molto tempo. Ma una volta creato, può essere riutilizzato contro e di nuovo e distribuito ad altri come qualsiasi altro strumento.

Immagina lo scenario in cui non hai saltato le password. Qualcuno può ( e ha ) creato set di tabelle precalcolate che possono in sostanza fendere istantaneamente le password da 1-7 o 1-9 o anche 1-10 caratteri se hai usato diversi hash comuni.

Applicare una quantità sufficiente di sale alle password rende impossibile questo attacco di pre-computazione poiché il pre-calcolo è generalmente molto, molto più difficile del semplice calcolo solo dei sali nel file delle password.

Mi sentivo come se non capissi bene come funzionava il tavolo arcobaleno o come veniva usato, ma non riuscivo a posizionare cosa ne fosse fuori, così sono andato a scavare un po 'di più e rileggere l'articolo di wikipedia e penso Ho chiarito le cose per conto mio e posso rispondere alla tua domanda.

La risposta breve è che la tabella arcobaleno funziona perché capita di trovare una corrispondenza per la tua password in qualche punto della catena e la password sale molto più lunga, il che significa che per ottenere ancora le corrispondenze la tua tabella arcobaleno cresce al punto di essere non pratico / impossibile o le tue probabilità di generare una corrispondenza per la password vanno verso il basso.

Una catena di hash di base utilizza una funzione di riduzione per trasformare un hash in una possibile password e poi lo blocca e ripete il processo. La tabella hash memorizza quindi la password iniziale che ha generato il primo hash e l'ultima password "possibile" generata dalla funzione di riduzione. Per decifrare una password, eseguila attraverso la funzione di riduzione e controlla la tabella per vedere se hai uno dei tuoi risultati registrati. Se non lo fai, lo fai e lo riduci di nuovo e ricontrolla. Ripeti la procedura fino a quando non hai trovato una corrispondenza o se hai perso tutta la lunghezza delle tue catene. Se trovi una corrispondenza, segui sostanzialmente la catena all'indietro finché non trovi il risultato originale della funzione di riduzione e l'aspetto della precedente "possibile" password che era stata cancellata e ridotta per darti la tua corrispondenza e hai la tua password. Se non hai trovato una corrispondenza, la tua tabella arcobaleno non copriva la password.

Questo processo ha problemi di collisione ma non può rilevarli se non si trovano nello stesso passo della catena, quindi la tabella arcobaleno utilizza una funzione di riduzione unica per ogni passo di riduzione fatto nella catena, quindi è solo una collisione se accade sullo stesso passo e possono rilevarlo perché entrambe le catene avranno lo stesso risultato finale e costruiscono una nuova catena che non è una collisione. Le password che la tabella dell'arcobaleno può incrinare sono determinate dalle possibili password generate nella catena in modo che il numero totale di password coperte sia il numero di passaggi nella catena moltiplicato per il numero di catene memorizzate. Facendo in modo che le tue funzioni di riduzione generino password molto più lunghe in modo che copra password + sale o il risultato hash della password + sale rende la tabella arcobaleno meno efficace. Finisci per coprire molto meno delle possibili password o le tue catene impiegano più tempo a calcolare più a lungo per creare il tuo tavolo e controllare la password e il tuo tavolo diventa sempre più difficile da archiviare / cercare.

link