La funzione LSH (Locality Sensitive Hash) corrisponde approssimativamente alle vecchie password

Question

La funzione LSH (Locality Sensitive Hash) corrisponde approssimativamente alle vecchie password

#1 da (1 voti)
#2 da (0 voti)

2

Recentemente, mi sono imbattuto in un sito web che richiede di cambiare la mia password dopo che è trascorso X giorni da quando ne avevo creato l'ultima. Intelligentemente, il servizio ha fatto in modo che la password non corrispondesse (approssimativamente) a qualsiasi altra che avevo usato prima (cosa che chiaramente non usava permutazioni). Tuttavia, ero incuriosito da come avrebbe potuto farlo, dal momento che la mia comprensione ingenua all'epoca era che avrebbero dovuto archiviare testo semplice per calcolare una distanza tra due stringhe.

Cercando di non assumere il peggio del sito web (gestito da un'organizzazione multi-miliardaria, per uso interno dei dipendenti), ho approfondito un po 'di più i metodi che sono stati utilizzati. Il primo che ho pensato è stato il paragone con hash sub-string (l'ho immediatamente buttato fuori a causa del possibile indebolimento del testo in chiaro). Pensavo che potessero fare l'operazione di permutazione-hashing (Ancora una volta, l'ho buttato fuori perché corrispondeva approssimativamente, e anche con alcune modifiche, sembrava fare abbastanza bene).

Ecco quando ho incontrato LSH come concetto. Ho pensato che fosse un'idea carina, che permetteva un confronto dei dati a conoscenza zero. Cioè, costruire un hash che ha un'alta probabilità di abbinare le cose simili a se stesso, ma comprime e non contiene necessariamente le informazioni del testo in chiaro da cui è stato derivato.

Qualcosa sulla falsariga del link

773e2df0a02a319ec34a0b71d54029111da90838cbc20ecd3d2d4e18c25a3025 spam1 47182cf0802a11dec24a3b75d5042d310ca90838c9d20ecc3d610e98560a3645 spam2

The nilsimsa of these two codes is 92 on a scale of -128 to +128. That means that 36 bits are different and 220 bits the same. Any nilsimsa over 24 (which is 3 sigma) indicates that the two messages are probably not independently generated.

È sicuro, e in caso contrario, esiste una versione sicura di detto metodo? Grazie.

storage passwords hash

posta Daymon Schroeder 04.03.2014 - 00:48

fonte

2 risposte

Leggi altre domande sui tag storage passwords hash

Perché Windows sta controllando svchost di default? DNS: inoltro condizionato

score 1 · Answer 1

Una funzione di hash sensibile alla località per definizione non ha l'effetto valanga ( link ), che è una proprietà chiave per una funzione hash crittografica. Le proprietà desiderabili per LSH sono essenzialmente l'opposto di ciò che è desiderabile per una funzione hash crittografica.

In effetti, la memorizzazione dell'hash sensibile alla località di una password non è certo migliore della memorizzazione della password in chiaro.

Un semplice metodo che può essere usato per verificare se una password è simile a una precedente, senza deviare dalla pratica raccomandata di archiviare solo un hash crittografato salato della password, è semplicemente usare un metodo per enumerare un gruppo di password simili a una determinata password (ad esempio, modifica, aggiunta o rimozione di una lettera), e quindi per ogni password precedente, calcolare l'hash di ciascuna password simile con il sale appropriato per vedere se corrisponde. Se si utilizza un hash password estremamente lento, tuttavia, questo metodo potrebbe essere problematico.

score 0 · Answer 2

Questo schema non è sicuro. Lasciami spiegare perché.

Salt

Una condizione importante per la sicurezza di uno schema di hashing delle password è che viene utilizzato un salt casuale unico che viene combinato con la password prima che l'hash sia calcolato. È richiesto un salt per hash password uguali a diversi hash. Questo protegge dagli attacchi in cui viene utilizzata una tabella arcobaleno. Inoltre, un attaccante non può ricavare alcuna informazione dalle frequenze osservate degli stessi hash perché tutti gli hash sono diversi. Se non si utilizza sale, un utente malintenzionato potrebbe tentare di attaccare gli hash più comuni perché in genere si tratta di password molto deboli.

Usando un sale un LSH non ha più senso perché la combinazione di sale + password differisce troppo. Gli hash risultanti sarebbero troppo diversi.

Attacca sugli hash LSH senza sale

Se viene usato un LSH senza sale e questo LSH restituisce hash simili (non uguali) per password simili, posso pensare ad un modo per attaccare quegli hash:

Se un utente malintenzionato desidera craccare una password, potrebbe iniziare con l'hashing di una password arbitraria. Quindi può usare la differenza dell'hash target e l'hash della sua password selezionata per adattare quella password che proverà nel passaggio successivo. Ripete questo finché non ha trovato la password corretta.

Questo è un semplice problema di ottimizzazione. Esistono alcuni metodi ben noti per risolvere i problemi di ottimizzazione. Ad esempio, gli algoritmi genetici potrebbero essere adatti per questo attacco. Definisci la funzione fitness come il numero di bit che non corrispondono e l'obiettivo è di minimizzare quella funzione.

Possibile soluzione

C'è una possibile soluzione a cui riesco a pensare. Mantenere un elenco delle password che un utente ha utilizzato finora e crittografare questo elenco. Per la crittografia / decodifica utilizzare un HSM (modulo di sicurezza hardware). Le chiavi sono memorizzate nell'HSM e non è possibile accedervi (ad esempio leggere) tramite il software. Pertanto, la chiave non può essere esposta. L'unico modo per l'hacker di ottenere le password in chiaro è decrittografare i testi cifrati sull'hardware in cui è installato HSM. Dovresti anche monitorare l'HSM per rilevare anomalie, ad es. per rilevare un aumento del numero di operazioni di decodifica.