Distanza tra due password

15

È risaputo che le persone riutilizzano le loro password su siti diversi. Il riutilizzo può essere fatto in due modi:

  1. utilizzando esattamente la stessa password per due siti diversi,
  2. lieve modifica della password di un sito e utilizzo su altro. Li chiamiamo password simili.

Per il caso 1. il confronto delle password rivela direttamente il riutilizzo della password.

Per il caso 2. non esiste una misura chiara su come misurare la distanza tra due stringhe. La metrica più popolare è Levenshtein o modifica la distanza. Ad esempio la distanza di modifica tra "password" e "password1" è solo 1 corrispondente all'inserimento della lettera "1"

Tuttavia, la distanza di Levenshtein non sempre funziona bene. Ad esempio, se la password di qualche sito dice che x.com è "lunedi" e la password del sito y.com è "mercoledì", la distanza di modifica sarà 5. Supponendo che l'utente malintenzionato conosca la password di x.com ie "lunedi" e le posizioni in cui sono state apportate modifiche per il sito y.com , almeno 26 ^ 5 varianti di password il lunedì dovrebbero essere tentate.

Ma concettualmente "lunedi" viene sostituito da un altro giorno della settimana. Ci sono altri 6 giorni della settimana diversi da "lunedi". Quindi, in questo caso, l'attaccante intelligente deve provare solo 6 giorni della settimana diversi rispetto alle varianti 26 ^ 5 di "lunedì".

Quale dovrebbe essere il modo migliore per misurare la distanza tra due password?

    
posta Curious 15.12.2014 - 06:21
fonte

2 risposte

13

Non esiste un modo valido. Quello che dici, è praticamente la misurazione della distanza della password in la nostra mente . È chiaramente impossibile avere un metodo diretto per farlo.

La seconda cosa, quello che vuoi misurare, dipende pesantemente dalla persona, e spesso contiene solo per lui informazioni conosciute. Ad esempio, uno dei tuoi colleghi potrebbe usare il nome di suo figlio sui diversi server aziendali. Non è possibile creare una soluzione software per trovare questo, ma alcuni hacker / colleghi possono avere queste informazioni e usarle per craccare il suo account.

Ciò che puoi fare, è stato un passo in avanti verso la NSA: sebbene tu non possa spiare direttamente la mente della gente, puoi usare i Big Data per emularne alcuni molto simili.

Cosa ti serve: informazioni disponibili pubblicamente in rete. Ad esempio:

  1. Thesaurus
  2. Wikipedia (anche se non esiste un modo semplice per misurare la distanza di collegamento tra due parole chiave, il suo database è semplicemente scaricabile e puoi creare uno script per analizzare la sua connettività di collegamento).
  3. O semplicemente potresti fare ricerche google automatizzate con google search api , e ottenere il rapporto di hit tra il primo, tra la seconda password e tra una doppia query (ad esempio, se la prima password è "apple" e la seconda è "orange", quindi Hits("apple")*Hits("orange")/Hits("apple", "orange")^2 deve essere inferiore a un limite sperimentale impostato dall'utente).

Ma attenzione: non eseguire query contenenti le password in un cloud pubblico non affidabile, si trattava di una violazione della sicurezza molto seria! Naturalmente, dipende solo dai vostri punti di vista / considerazioni / responsabilità, che il cloud pubblico è affidabile per te. Per me, nessuno era.

Al posto tuo ho fatto quanto segue:

  1. Ricevo un mirror wikipedia (hanno un semplice database mysql che è pubblicamente scaricabile)
  2. Crea una mappa delle distanze dei collegamenti (era molto semplice, anche se forse era grande)
  3. Ho creato per le due password il confronto con il titolo dell'articolo wikipedia più vicino (era necessario un notevole confronto con levenshtein, quindi avrai bisogno di molta CPU)
  4. Finalmente ho usato la seguente formula: D ("pwd1", "pwd2") = Levensheiten ("pwd1", Lev_nearest ("pwd1")) + Wiki_Link_Distance (Lev_nearest ("pwd1"), Lev_nearest (" pwd2 ")) + Levensheiten (" pwd2 ", Lev_nearest (" pwd2 "))

Estensione: la wiki contiene circa un milione di voci di testo, il che rende quasi impossibile la ricerca del percorso più breve. Avresti sicuramente implementato questo come un C ++ e userai algoritmi ottimizzati molto bene. Quindi, sarà difficile. In alternativa, puoi farlo usando wikipedia solo le parole più comuni (che possono essere trovate ottenendo le loro statistiche di utilizzo). Sebbene il wiki inglese abbia circa un milione di articoli, un madrelingua inglese ne conosce solo una decina di migliaia.

Qualcuno dovrebbe davvero scrivere questo, è stato un meraviglioso demone opensource da qualche parte nel github: -)

    
risposta data 15.12.2014 - 11:10
fonte
10

Sei fortunato, c'è un buon modo per normalizzare questo per le informazioni pubblicamente disponibili : WolframAlpha può essere utilizzato per ridurre le stringhe in componenti logici che possono essere confrontati e portare a un confronto Levenshtein più accurato.

Esempio di "lunedì"

Una volta che "fattore" la stringa in tutti i suoi possibili significati (giorno della settimana, valore scrabble, ecc.) puoi usare gli elementi come un nuovo valore comparativo.

Per informazioni private , come ad esempio il nome di pari livello, dovrai seguire un metodo simile per ricostruire la struttura di Wolfram per il tuo negozio proprietario. Wolfram ha un'API disponibile che esporta i risultati dei risultati in JSON e può aiutare ad allineare le tue opinioni con ciò che è necessario per creare un repository privato di questo tipo.

    
risposta data 15.12.2014 - 16:35
fonte

Leggi altre domande sui tag