È una certezza matematica che qualsiasi funzione di hash con una dimensione di output fissa avrà collisioni. Tuttavia, la possibilità di una collisione può essere ridotta utilizzando una funzione di hash con una dimensione di output di grandi dimensioni. Usando SHA-2 con la dimensione di output predefinita di 256 bit, ad esempio, significa che avrete bisogno di 2 ^ 128 utenti prima che ci sia il 50% di possibilità che alcuni di essi abbiano lo stesso hash della password [*].

Idealmente, dovresti applicare una funzione di hash a SALT+PASSWORD , dove SALT è un valore univoco specifico per l'account utente. Se i valori di sale vengono scelti in modo univoco sugli account, ciò garantisce che sia il nome utente sia la password devono corrispondere a un account specifico per consentire l'accesso.

Si prega di notare che quanto sopra è inteso solo per spiegare il concetto. In pratica, dovresti delegare quasi sempre questa attività a un'implementazione di qualità di una funzione di hashing della password standard, come PBKDF2 o bcrypt, anziché eseguire il rollover.

[*] - supponendo che nessuna coppia abbia effettivamente la stessa password, il che può accadere con sorprendentemente pochi utenti diversi.

Nel caso in cui Alice e Bob abbiano la stessa identica password e Alice acceda come Bob accidentalmente, non c'è nulla che ci si possa ragionevolmente aspettare da questo.

In termini di sforzi irragionevoli, è possibile memorizzare l'hash di PEPPER+PASSWORD per ogni utente (dove PEPPER è una costante a livello di sito), eseguire uno script per rilevare casi con password uguale, inserire l'hash su un " lista errata ", e invia automaticamente e-mail chiedendo agli utenti di cambiare la loro password se il loro hash della password è nella" lista cattiva ". Si noti tuttavia che questo apre il sito fino a un nuovo tipo di attacco in cui un utente malintenzionato cambia ripetutamente la propria password in una password comune e attende di vedere se viene generata un'e-mail. Se lo è, sanno che un altro utente ha quella password e possono provare i nomi utente comuni con esso (o, il risultato di raschiare qualsiasi dato pubblico disponibile per i nomi utente, tale forum del sito). Pertanto, dovresti limitare la frequenza dello script che invia messaggi di posta elettronica (ad esempio, a una volta al giorno) per ridurre l'efficacia di un simile attacco.

Se si consente l'uso di password deboli, c'è sempre la possibilità che un utente possa digitare un altro nome utente, digitare qualcosa come "qweasd" o "P @ ssw0rd" ed effettuare il login; più utenti hai, più è probabile che ciò sia possibile. Dai un'occhiata a Analisi di dump delle password di LinkedIn : 1.13M persone hanno utilizzato la password "123456"! Non c'è nulla che puoi fare per proteggerti, oltre a richiedere una password sicura.

Ma se questa è una preoccupazione per te, puoi usare un salt casuale per ogni password (memorizzata nella stessa tabella con la password). Ad esempio, per un utente che immette la password "abcdef" si genera un salt casuale "9D @!" E si memorizza l'hash di "9D @! Abcdef" e il sale. In questo caso, anche se due utenti hanno esattamente la stessa password, ad esempio 123456, non sarà evidente dal dump del database.

Un'altra soluzione, come proposto sopra, potrebbe essere l'hash username e password insieme. In questo caso potrebbe essere meglio usare anche un separatore - un simbolo che non può essere parte del nome utente, come i due punti, e hash la combinazione "username: password". Ciò impedirebbe casi simili in cui l'utente abc1 ha la password 123456 e l'utente abc ha una password 1123456 - i loro hash corrisponderanno se non viene utilizzata alcuna separazione.

When hashing passwords, two passwords can produce the same hash, so if a user inputs someone else's username but his own password, there is a possibility that he will be able to login to that other account. How to prevent this?

Questo scenario, esattamente come hai descritto, non è possibile. L'altro utente avrebbe un sale diverso, quindi anche se avessi una password che avrebbe un hash in collisione, il valore effettivo inserito nell'algoritmo di hashing sarebbe diverso.

Detto questo, è possibile (anche se estremamente improbabile) che la password dell'utente combinata con il sale dell'altro utente generi l'hash dell'altro utente. Nessun sito web a cui abbia mai lavorato si è mai preoccupato di questo, dal momento che è così improbabile.

Ma ... se lo volessi, potresti evitare le collisioni usando il seguente tipo di logica quando salvi la password dell'utente (supponendo che venga salvata come hash salato):

var userName = GetUsernameFromUser();
var password = GetPasswordFromUser();
bool isSaved = false;
while (!isSaved)
{
    var salt = GetRandomSalt();
    var hash = ComputeHash(password + salt);
    if (!ExistsInDatabase(hash))
    {
        SaveHashedPassword(userName, salt, hash);
        isSaved = true;
    }
}

Quanto sopra continuerà a provare diversi valori di sale finché l'hash non entrerà in collisione con qualcosa.

Non consiglio di farlo, ma questo risponde alla domanda.

Questo non è in realtà un problema a tutti in un sistema di autenticazione di login e password correttamente implementato.

L'autenticazione di accesso funziona su coppie di nome utente e password

Quando un utente effettua il login, fornisce un nome utente (o un altro identificativo, come l'email) insieme alla sua password. Verifica di accesso significa verificare che la coppia (username, password) sia autentica. Il nome utente viene utilizzato per cercare la voce della password corrispondente e l'hash della voce viene utilizzato per verificare che la password fornita sia quella corretta per tale nome utente.

Se qualcuno sta tentando di accedere all'account di Alice, confrontiamo la password che presentano all'hash memorizzato per l'account di Alice; se fallisce, non andiamo a controllare se corrisponde alla password di Bob.

Potrebbe sembrare ovvio, ma è importante, come vedremo in seguito, perché ogni tentativo di accesso per un determinato nome utente viene testato utilizzando quel nome utente salato e nessun altro.

Gli hash salati hanno una probabilità di collisione molto bassa

Dovresti utilizzare una funzione di hashing della password specializzata per memorizzare le password. (Vedi: risposta di Thomas Pornin a "Come fare in modo sicuro le password di hash?" ) Queste funzioni richiedono un sale come argomento aggiuntivo. Questi sali dovrebbero essere univoci per ogni inserimento di password (idealmente dovrebbero essere scelti a caso) e conservati insieme alla password hash; in effetti, ha più senso trattare l'intera coppia salina + hash come un'unità, come un codice di verifica della password (come Formato stringa PHC ). In queste condizioni:

1. La probabilità che due utenti con la stessa password ottengano identici hash è trascurabile;
2. La probabilità che due utenti con password diverse ottengano sali che producono risultati hash identici è anche trascurabile.

Quindi, se la memorizzazione della password è implementata correttamente, non dovresti osservare le collisioni. È astronomicamente improbabile.

Le collisioni non contano comunque

Ma supponiamo che Alice e Bob, in qualche modo, pur avendo password e sali diversi, in qualche modo improbabilmente le loro password + hash delle coppie salate abbiano lo stesso risultato. Cosa succederebbe? In effetti, niente di male:

1. Se Alice immette il nome utente e la password, viene autenticata correttamente.
2. Se Bob inserisce il nome utente e la password, viene autenticato con successo.
3. Se Alice immette nome utente Bob e la sua password, l'autenticazione quasi certamente fallisce. Perché? Perché viene sottoposto a hash con sale di Mario , che è diverso da quello di Alice.
4. Allo stesso modo, se Bob inserisce il nome utente di Alice e la sua password, l'autenticazione fallisce, perché è sottoposta a hash
5. Se Alice immette il nome utente e la password di Bob, l'autenticazione ha esito positivo falso, ma è perché conosce il nome utente e la password.
6. Se Bob immette il nome utente e la password di Alice, l'autenticazione ha esito errato, ma è perché conosce il nome utente e la password.

Affinché lo scenario si verifichi, ciò di cui avremmo effettivamente bisogno è una situazione in cui pwhash(alice_pw, bob_salt) = pwhash(alice_pw, alice_salt) . Ma:

• Se si selezionano sali abbastanza grandi a caso, ciò è astronomicamente improbabile;
• Anche se tale situazione si fosse verificata improbabilmente, non saresti in grado di distinguere dagli hash nel tuo database;
• Anche se un utente malintenzionato conosce i sali, trovare un (fake_password, true_salt) che collide è tanto difficile quanto indovinare la vera password.

Conclusione

Questo non è in realtà un problema a tutti in un sistema di autenticazione di login e password correttamente implementato.

A causa del principio pigeonhole , qualsiasi algoritmo hash di lunghezza fissa avrà collisioni. L'unico modo per evitare collisioni consiste nell'utilizzare l'algoritmo per l'hashing perfetto a lunghezza variabile

Si noti che con un buon algoritmo di hashing, a partire da hash a 128 bit, la possibilità di collisione è statisticamente impossibile. Si esaurirà l'energia nell'universo conosciuto prima che si possa generare collisione con un buon hash a 256 bit con la forza bruta. In questi hash, gli attacchi generalmente ruotano attorno alla ricerca della debolezza matematica, piuttosto che della forza bruta.

Sempre quando esegui l'hashing di informazioni sensibili come password, dovresti usare un algoritmo strong e una cosa chiamata sale. Quando un server esegue un hash dalla tua password, utilizza un determinato metodo per farlo in base all'algoritmo in uso. Non importa quanto sia strong l'algoritmo, quando non è salato, produrrà sempre lo stesso risultato con la stessa stringa. Quindi, la soluzione qui è che è necessario utilizzare un sale con il tuo algoritmo. È meglio se tu possa usare un metodo creato da professionisti che genera un hash con un sale.

Inoltre, potresti piantarne uno solo se la frase dice:

se l'utente è questo e il sale è questo, quindi accedi. Allora sei sicuro che solo questo utente con questo nome utente sta effettuando l'accesso.

Ma, se vuoi davvero che l'hash sia casuale, hai bisogno di un po 'di sale.

Quindi, cos'è un salt?

Bene, Wikipedia lo spiega in modo positivo:

In cryptography, a salt is random data that is used as an additional input to a one-way function that "hashes" a password or passphrase. Salts are closely related to the concept of nonce. The primary function of salts is to defend against dictionary attacks or against its hashed equivalent, a pre-computed rainbow table attack.[1] Salts are used to safeguard passwords in storage. Historically a password was stored in plaintext on a system, but over time additional safeguards developed to protect a user's password against being read from the system. A salt is one of those methods. A new salt is randomly generated for each password. In a typical setting, the salt and the password (or its version after Key stretching) are concatenated and processed with a cryptographic hash function, and the resulting output (but not the original password) is stored with the salt in a database. Hashing allows for later authentication without keeping and therefore risking the plaintext password in the event that the authentication data store is compromised. Since salts do not have to be memorized by humans they can make the size of the rainbow table required for a successful attack prohibitively large without placing a burden on the users. Since salts are different in each case, they also protect commonly used passwords, or those who use the same password on several sites, by making all salted hash instances for the same password different from each other. Cryptographic salts are broadly used in many modern computer systems, from Unix system credentials to Internet security. - Wikipedia https://en.wikipedia.org/wiki/Salt_(cryptography)

Quindi, quando usiamo un sale, evitiamo i cosiddetti attacchi arcobaleni e gli attacchi dictonary e non otteniamo la stessa stringa hash.

Come aggiungeremo un salt?

Ci sono almeno due modi per aggiungere un sale.

1. Aggiungi il sale alla stringa prima del suo hash che è, stringa + sale

2. Utilizza metodi incorporati o buoni metodi progettati da professionisti

Okay, prima di tutto, un sale deve essere davvero, davvero casuale per ogni singola password. Questo è un alto rischio se si ha un sale che è sempre lo stesso perché quando sarà esposto (Sì, quando, perché tutti saranno hackerati in qualche punto), è molto più facile per l'hacker infrangere tutte le password nel database. Con questo in mente, continuiamo.

Il primo metodo, aggiungere un sale direttamente alla stringa non è male, ma poi la domanda è: dove conservare il sale? E come hai intenzione di renderlo il più casuale possibile? Bene, è consigliabile che se stai andando a memorizzare sali che sono memorizzati in modo sperato dalle password, anche in un altro database perché forse qualcuno ha hackerato la tabella delle password o il database in cui sono le password e non i sali, quindi non sa il sale e quindi non le password. Quindi dobbiamo pensare al randomnes del nostro sale, quale metodo è il migliore per generare la cosa più casuale che puoi ottenere? Dipende ovviamente dalla lingua e non hai menzionato alcuna lingua nella tua domanda, quindi temo di non poterti aiutare con quello.

Il secondo è quello di utilizzare funzioni integrate progettate per hash una password con un salt. Questi sono spesso migliori di un semplice aggiunta di sale e hash, perché puoi essere sicuro di ottenere il sale più casuale possibile e diverso su ciascuna password. Il mal di testa con dove conservare il sale e come posso lasciare che sia casuale e ogni password e cosa usare in modo che diventi molto, molto casuale, scompare. Una linea e tu sei bravo. Anche questo è spesso mantenuto e ci sono alcuni metodi che forniscono l'algoritmo più potente che la lingua può offrire + salt. Quindi, questo è ancora più sicuro, perché non devi preoccuparti di quale algoritmo è meglio usare o quando l'algoritmo che stai usando si interrompe, non hai bisogno di andare oltre l'intero codice e cambiare. Ma non tutte le lingue supportano questo tipo di metodi, quindi il primo è quindi meglio di niente.

Il secondo metodo è abbastanza buono, credo, perché non è nemmeno necessario memorizzare il sale, almeno non nel database e quindi è impossibile sapere quale password appartiene a ogni sale, quindi è abbastanza sicuro. Inoltre, mi raccomando durante l'hashing, se possibile, che usi un metodo che usa sempre l'algoritmo più potente disponibile e un sale molto casuale. Perché, allora accade automaticamente e non devi preoccuparti.

Quindi, penso che il secondo metodo sia migliore perché è un sovraccarico e, se possibile, più sicuro perché si utilizzano funzioni integrate. Ma non tutti i linguaggi di programmazione hanno queste funzioni integrate, quindi il primo metodo è meglio di niente. Ma, se ciò non è possibile, usa il primo.

Lì, ce l'hai, la risposta breve è fondamentalmente mettere un po 'di sale sulla tua password, quindi l'hash non sarà lo stesso per ogni password.

Spero che questa informazione aiuti te e alcuni altri.

Una funzione di hash è una funzione tale che riceve un input in {0,1}^n e il suo output è nello spazio {0,1}^t

Poiché n può teoricamente crescere all'infinito, allora ci sono infiniti valori che si associano allo stesso valore x nello spazio {0,1}^t . Questo è noto, e quindi come hai detto ci sono almeno due valori che producono lo stesso valore di hash

Ma le funzioni di hash crittograficamente sicure hanno una proprietà speciale, sono resistenti alle collisioni. Ciò significa essenzialmente che un utente malintenzionato che vuole trovare una collisione per un determinato valore hash non ha un approccio migliore rispetto all'utilizzo di una ricerca esaustiva

Nel caso particolare di bcrypt (le funzioni di hash più comuni considerate sicure per l'hashing delle password, poiché è una tua preoccupazione) ha un output di 184 bit (senza il prefisso, il sale e il workflow). Ciò significa che un utente malintenzionato che desidera trovare una collisione per una determinata password bcrypt ed ha bisogno di provare almeno% parole chiave% di password in media. Anche se potessi calcolare 1 milione% di hash di hash al secondo, avresti bisogno di più di 3,76 quadrilioni di anni per trovare una collisione per un determinato hash

Le probabilità che un utente mispella il suo nome utente e inserisca la sua password e ottenga l'accesso a un account di un'altra persona è intorno a 2^92 , assumendo che inserisca un nome utente valido

Parlando statisticamente, è più facile che qualcuno di noi muoia causi un impatto con una meteora piuttosto che trovare una collisione per una% hash della password con hash in un'ipotesi casuale

PS: tutto ciò avviene se l'applicazione utilizza correttamente i sali. Se non due utenti con la stessa password (come bcrypt ) potrebbero essere catastrofici

Salare ogni password potrebbe essere troppa sicurezza qui. Inoltre è necessario un meccanismo per memorizzare ogni sale con le password. Altrimenti non puoi generare l'hash.

Sulla domanda attuale, penso che una combinazione username + password vada bene.

È possibile aggiungere un totale di sale per tutte le password per impedire se dal reverse engineering. Quindi in pratica i tuoi hash saranno:

Global Salt + username + password

È molto improbabile che si verifichi una collisione nell'algoritmo SHA-256. Dai un'occhiata al problema del compleanno :

Un modo semplice sarebbe concatenare nome utente e password per formare una stringa e cancellare l'intero processo. L'idea è La combinazione di nome utente e password con un separatore deve essere unica in quanto il nome utente sarebbe unico. Se si utilizza il nome utente duplicato, utilizzare il codice utente ecc. Qualcosa che è univoco per l'utente.