Come posso stimare l'entropia di una password?

Question

Come posso stimare l'entropia di una password?

#1 da (8 voti)
#2 da (4 voti)
#3 da (1 voti)
#4 da (1 voti)

14

Avendo letto varie risorse sulla forza della password sto provando a creare un algoritmo che fornisca una stima approssimativa di quanto entropia sia la password è.

Sto cercando di creare un algoritmo il più completo possibile. A questo punto ho solo uno pseudocodice, ma l'algoritmo copre quanto segue:

lunghezza della password
caratteri ripetuti
modelli (logici)
spazi di caratteri diversi (LC, UC, Numerico, Speciale, Esteso)
attacchi di dizionario

NON copre quanto segue, e DOVREBBE coprirlo BENE (anche se non perfettamente):

l'ordine (le password possono essere rigorosamente ordinate per output di questo algoritmo)
pattern (spaziali)

Qualcuno può fornire alcune informazioni su ciò a cui questo algoritmo potrebbe essere debole? In particolare, qualcuno può pensare a situazioni in cui inserire una password nell'algoritmo potrebbe OVERESTIMATE la sua forza? Le sottostime sono meno di un problema.

L'algoritmo:

// the password to test
password = ?
length = length(password)

// unique character counts from password (duplicates discarded)
uqlca = number of unique lowercase alphabetic characters in password
uquca = number of uppercase alphabetic characters
uqd   = number of unique digits
uqsp  = number of unique special characters (anything with a key on the keyboard)
uqxc  = number of unique special special characters (alt codes, extended-ascii stuff)

// algorithm parameters, total sizes of alphabet spaces
Nlca = total possible number of lowercase letters (26)
Nuca = total uppercase letters (26)
Nd   = total digits (10)
Nsp  = total special characters (32 or something)
Nxc  = total extended ascii characters that dont fit into other categorys (idk, 50?)

// algorithm parameters, pw strength growth rates as percentages (per character)
flca = entropy growth factor for lowercase letters (.25 is probably a good value)
fuca = EGF for uppercase letters (.4 is probably good)
fd   = EGF for digits (.4 is probably good)
fsp  = EGF for special chars (.5 is probably good)
fxc  = EGF for extended ascii chars (.75 is probably good)

// repetition factors.  few unique letters == low factor, many unique == high
rflca = (1 - (1 - flca) ^ uqlca)
rfuca = (1 - (1 - fuca) ^ uquca)
rfd   = (1 - (1 - fd  ) ^ uqd  )
rfsp  = (1 - (1 - fsp ) ^ uqsp )
rfxc  = (1 - (1 - fxc ) ^ uqxc )

// digit strengths
strength =
( rflca * Nlca + 
  rfuca * Nuca +
  rfd   * Nd   +
  rfsp  * Nsp  +
  rfxc  * Nxc    ) ^ length

entropybits = log_base_2(strength)

Alcuni input e i loro output entropy_bits desiderati ed effettivi:

INPUT           DESIRED        ACTUAL
aaa             very pathetic  8.1
aaaaaaaaa       pathetic       24.7
abcdefghi       weak           31.2
H0ley$Mol3y_    strong         72.2
s^fU¬5ü;y34G<   wtf            88.9
[a^36]*         pathetic       97.2
[a^20]A[a^15]*  strong         146.8
xkcd1**         medium         79.3
xkcd2**         wtf            160.5

* these 2 passwords use shortened notation, where [a^N] expands to N a's.
** xkcd1 = "Tr0ub4dor&3", xkcd2 = "correct horse battery staple"

L'algoritmo realizza (correttamente) che l'aumento della dimensione dell'alfabeto (anche di una sola cifra) rafforza notevolmente le password lunghe, come mostrato dalla differenza di entropy_bits per la sesta e settima password, che consistono entrambe di 36 a, ma la seconda Il 21 a è in maiuscolo. Tuttavia, non tengono conto del fatto che avere una password di 36 a non è una buona idea, è facilmente infranto con un password cracker debole (e chiunque lo guardi digitarlo lo vedrà) e l'algoritmo non riflette quello .

Tuttavia, riflette il fatto che xkcd1 è una password debole rispetto a xkcd2, nonostante abbia una maggiore densità di complessità (è anche una cosa?).

Come posso migliorare questo algoritmo?

Addendum 1

Gli attacchi del dizionario e gli attacchi basati su pattern sembrano essere la cosa più importante, quindi mi proverò a risolverli.

Potrei eseguire una ricerca completa attraverso la password per le parole da un elenco di parole e sostituire le parole con i token univoci alle parole che rappresentano. I token di parole sarebbero quindi trattati come caratteri e avrebbero il loro sistema di pesi, e aggiungerebbero i loro pesi alla password. Avrei bisogno di alcuni nuovi parametri dell'algoritmo (li chiamerò lw, Nw ~ = 2 ^ 11, fw ~ = .5 e rfw) e modificherei il peso nella password come farei con qualsiasi altro pesi.

Questa ricerca di parole potrebbe essere appositamente modificata per corrispondere sia a lettere minuscole e maiuscole, sia a sostituzioni di caratteri comuni, come quella di E con 3. Se non aggiungo peso extra a tali parole abbinate, l'algoritmo sottovaluterebbe la loro forza di un bit o due per parola, che è OK. Altrimenti, una regola generale sarebbe, per ogni corrispondenza di caratteri non perfetta, dare alla parola un bit bonus.

Potrei quindi eseguire semplici controlli di pattern, come ricerche di esecuzioni di caratteri ripetuti e test derivati (prendere la differenza tra ogni carattere), che identificherebbe pattern come 'aaaaa' e '12345', e sostituire ogni pattern rilevato con un gettone modello, unico per il modello e la lunghezza. I parametri algoritmici (in particolare, entropia per modello) potrebbero essere generati al volo in base al modello.

A questo punto, prenderei la lunghezza della password. Ogni token di parola e token di pattern conterebbe come un carattere; ogni token sostituisce i caratteri che rappresentano simbolicamente.

Ho inventato una sorta di notazione di pattern, ma include la lunghezza del pattern l, l'ordine di pattern o e l'elemento base b. Questa informazione potrebbe essere utilizzata per calcolare un peso arbitrario per ogni modello. Farei qualcosa di meglio nel codice reale.

Esempio modificato:

Password:          1234kitty$$$$$herpderp
Tokenized:         1 2 3 4 k i t t y $ $ $ $ $ h e r p d e r p
Words Filtered:    1 2 3 4 @W5783 $ $ $ $ $ @W9001 @W9002
Patterns Filtered: @P[l=4,o=1,b='1'] @W5783 @P[l=5,o=0,b='$'] @W9001 @W9002

Breakdown:         3 small, unique words and 2 patterns
Entropy:           about 45 bits, as per modified algorithm

Password:          correcthorsebatterystaple
Tokenized:         c o r r e c t h o r s e b a t t e r y s t a p l e
Words Filtered:    @W6783 @W7923 @W1535 @W2285

Breakdown:         4 small, unique words and no patterns
Entropy:           43 bits, as per modified algorithm

La semantica esatta di come viene calcolata l'entropia dai pattern è pronta per essere discussa. Stavo pensando qualcosa del tipo:

entropy(b) * l * (o + 1) // o will be either zero or one

L'algoritmo modificato potrebbe trovare difetti e ridurre la forza di ciascuna password nella tabella originale, ad eccezione di s^fU¬5ü;y34G< , che non contiene parole o pattern.

algorithms passwords

posta Wug 02.10.2012 - 21:47

fonte

4 risposte

Leggi altre domande sui tag algorithms passwords

Posso richiedere i lavori di "Software Engineer" senza essere un ingegnere? [chiuso] Come mantieni efficacemente i tuoi test mentre ridisegni?

score 8 · Answer 1

L'Appendice A sulla p46 di NIST SP 800-63 parla della lavoro di Claude Shannon , che stima l'entropia della password usando un numero di bit. In effetti, questo è il documento che il fumetto XKCD usa per calcolare i bit di entropia. In particolare:

the entropy of the first character is taken to be 4 bits;

the entropy of the next 7 characters are 2 bits per character; this is roughly consistent with Shannon’s estimate that “when statistical effects extending over not more than 8 letters are considered the entropy is roughly 2.3 bits per character;”

for the 9th through the 20th character the entropy is taken to be 1.5 bits per character;

for characters 21 and above the entropy is taken to be 1 bit per character;

A “bonus” of 6 bits of entropy is assigned for a composition rule that requires both upper case and non-alphabetic characters. This forces the use of these characters, but in many cases thee characters will occur only at the beginning or the end of the password, and it reduces the total search space somewhat, so the benefit is probably modest and nearly independent of the length of the password;

A bonus of up to 6 bits of entropy is added for an extensive dictionary check. If the attacker knows the dictionary, he can avoid testing those passwords, and will in any event, be able to guess much of the dictionary, which will, however, be the most likely selected passwords in the absence of a dictionary rule. The assumption is that most of the guessing entropy benefits for a dictionary test accrue to relatively short passwords, because any long password that can be remembered must necessarily be a “pass-phrase” composed of dictionary words, so the bonus declines to zero at 20 characters.

L'idea è che un sistema di autenticazione selezionerebbe determinati livelli di entropia come soglie. Ad esempio, 10 bit possono essere deboli, 20 medi e 30 forti (i numeri selezionati arbitrariamente come un esempio, non una raccomandazione). Sfortunatamente, il documento non consiglia tali soglie, probabilmente perché la potenza di calcolo disponibile per la forza bruta o le password di congettura aumentano nel tempo:

As an alternative to imposing some arbitrary specific set of rules, an authentication system might grade user passwords, using the rules stated above, and accept any that meet some minimum entropy standard. For example, suppose passwords with at least 24-bits of entropy were required. We can calculate the entropy estimate of “IamtheCapitanofthePina4” by observing that the string has 23 characters and would satisfy a composition rule requiring upper case and non-alphabetic characters.

Questo può o non può essere quello che stai cercando, ma non è un brutto punto di riferimento, se non altro.

[Modifica: aggiunto il seguente.]

Il documento Verifica delle metriche per i criteri di creazione della password Attaccando i grandi insiemi di password rivelate (di Matt Weir, Sudhir Aggarwal, Michael Collins e Henry Stern) hanno dimostrato che il modello di Shannon, descritto sopra, non è un modello accurato di entropia per le password generate dall'uomo. Ti consiglio di consultare "Sezione 5 Generazione di nuove regole per la creazione di password" per proposte più accurate.

score 4 · Answer 2

Controlla il codice sorgente per KeePass nella parte inferiore di questa pagina . La classe QualityEstimation implementa un algoritmo piuttosto carino che sembra essere in linea con quello che stai cercando di avere. I miei risultati sembrano così:

aaa                              8
aaaaaaaaa                        9
abcdefghi                       18
H0ley$Mol3y_                    73
s^fU¬5ü;y34G<                   99
[a^36]*                         10
[a^20]A[a^15]*                  18
Tr0ub4dor&3                     66
correct horse battery staple    98

score 1 · Answer 3

Chiedi

Specifically, can anyone think of situations where feeding a password to the algorithm would OVERESTIMATE its strength?

Ma hai un esempio nella domanda. In base alla progettazione, xkcd2 ha ~ 44 bit di entropia, ma la tua stima è di 160,5 bit.

score 1 · Answer 4

Can anyone provide some insight on what this algorithm might be weak to? Specifically, can anyone think of situations where feeding a password to the algorithm would OVERESTIMATE its strength?

Ne hai accennato ad alcuni nel preambolo (attacchi di dizionario, ecc.). Essenzialmente, ci sono un certo numero di pratiche comuni che possono essere indovinate dall'attaccante che abbassa notevolmente lo spazio di ricerca. Sono abbastanza sicuro che il tuo algoritmo "sovrastimerà" quanto segue:

ovunque
Ovunque
Everywhere1

La password è piuttosto lunga, ma è banalmente crackabile poiché la parola originale appare in un dizionario di base e le modifiche sono considerate abbastanza comuni da formare parte di qualsiasi attacco decente del dizionario. Lettera tipica - > le conversioni di numeri (ad esempio 3v3rywh3r3) dovrebbero essere considerate piuttosto deboli e dovresti penalizzarle per queste.

In misura molto minore, altre password di problemi potrebbero essere quelle con schemi evidenti, come ad esempio:

ABCDEFGHIJKLMNOP
abcde12345

Anche se probabilmente hanno meno probabilità di essere presi di mira dagli attacchi dei dizionari, soffrono di problemi simili al tuo esempio di "aaaaa ...".

Non sono sicuro che le frasi di password siano attualmente indirizzate alla maggior parte degli attacchi di dizionario, ma senza dubbio mentre guadagnano popolarità, saranno sempre più mirate. Penso che il famoso esempio xkcd tenga conto di questo, dato che sono assegnati solo 11 bit per ogni "parola comune". Il tuo algoritmo sovrastima anche questi tipi di password.

Quindi, per riassumere, l'algoritmo fa un buon lavoro di stima, ma in realtà dovrebbe prendere in considerazione la struttura della password e modelli comuni e noti.