In che modo la ripetizione dei caratteri influenza l'entropia delle password?

L'entropia della password è basata sul numero di combinazioni possibili. Per un pattern che riduce l'entropia, il pattern deve essere noto all'attaccante.

Se il modello non è fisso e noto, la riduzione della complessità sarà specifica dell'algoritmo dell'attaccante . Sarà diverso per i diversi attaccanti. Ad esempio, con un attacco dizionario, la complessità effettiva delle parole del dizionario è la dimensione del dizionario, per le parole al di fuori della complessità della forza bruta del dizionario.

Non so se esiste o può essere un algoritmo matematicamente ottimale per le ripetizioni di lettere. La soluzione più semplice a cui riesco a pensare è quella di trattare le ripetizioni dei simboli, fino a una ripetizione N, come grafemi extra. In tal caso, la forza della password sarà il numero di grafemi che contiene.

Contro tale algoritmo, la forza aggiunta di ciascun simbolo consecutivo dal 2 ° all'N ° simbolo è 0, e equivalente ad un altro grafema fino a 2N. Ma questo stesso algoritmo sarà più lento rispetto alle password casuali a causa di un set di caratteri più efficace. Ad esempio, il controllo di ripetizioni di 2 lunghezze per ogni simbolo diminuirà della sua velocità di un fattore di 2 ^ (lunghezza-1). Ma contro una password che è tutti simboli doppi, la sua velocità migliorerà solo a una radice quadrata di complessità superiore.

Se è imperativo che l'efficienza della forza bruta non sia compromessa, un tweak libero inizia sempre a selezionare l'ultimo grafo come uguale a quello precedente. In questo caso la forza aggiunta dalla prima (per lunghezza variabile) o tutti i simboli di ripetizione alla fine (per lunghezza fissa) è 0. Farlo nel mezzo non è più un aggiornamento gratuito. Nessuno dei due sta cercando ripetizioni extra con una password di lunghezza variabile, sebbene sia così economico da essere quasi gratuito.

In breve, contro un algoritmo ottimizzato per selezionare le password con caratteri ripetuti, la forza di una password può essere stimata facendo cadere tutte le cifre consecutive oltre la prima per ottenere la lunghezza effettiva L '. La forza teorica sarebbe approssimativamente (charset * N) ^ L ', dove N è il numero massimo di ripetizioni che l'attaccante sta testando.

Contro un algoritmo ottimizzato per l'efficienza della forza bruta, dovrebbero essere eliminate solo le cifre consecutive alla fine. La forza teorica con un algoritmo ingenuo sarebbe charset ^ (L'-1) * (set di caratteri + N). Comunque, qualsiasi algoritmo pratico testerà già molti suffissi (le password spesso finiscono con "1" o "1!" Per aggirare le regole di complessità).

È tutta una questione di quale algoritmo utilizza l'utente malintenzionato. I dizionari, inclusi gli elenchi di password persi, verranno generalmente provati per primi.

Un amico il cui dottorato è in statistica ama dire, "Spesso l'unico significato di un'improbabilità statistica è che l'improbabile è successo."

La formula che si ottiene mantiene solo se ogni carattere è selezionato casualmente, il che implica una selezione indipendente dagli altri caratteri. Quindi, è improbabile, ma non impossibile che una password completamente casuale possa essere 3333333333.

Detto ciò, gli hacker usano l'euristica. Uno di questi potrebbe essere quello di cercare le ripetizioni e, trovando tale, verificare che il prossimo carattere sia un'altra ripetizione prima di provare combinazioni più difficili. Quindi, sarei tentato di rifiutare i suggerimenti di password con tre o più caratteri ripetuti.

H = L * log (N) è l'entropia matematica dell'insieme delle possibili password di L caratteri casualmente scelti tra un insieme di dimensioni N. È solo il log di quel numero: H = log (N ^L ).

Ma non appena aggiungi regole aggiuntive come:

• disattiva la ripetizione dello stesso simbolo
• richiede la presenza di caratteri provenienti dal disinserimento di sottoinsiemi

riduci il numero di possibili pattern e riduci la forza (entropia). Se un utente malintenzionato sa che una password non può contenere ripetizioni di un personaggio, può ottimizzare il suo algoritmo con quello. In realtà, H misura la forza della password contro gli attacchi di forza bruta, laddove l'attaccante presume che qualsiasi combinazione abbia la stessa probabilità e naviga in modo coerente l'intero set possibile.

Tali restrizioni sono comunque comuni, perché la maggior parte degli utenti non usa il true random per scegliere una password, e alcuni pattern dannatamente semplici ( 00000000 o 12345678 per otto caratteri numerici) hanno una probabilità molto più alta di essere scelti rispetto ad altri (*). Quindi quelle restrizioni cercano di evitare quelle semplici password che potrebbero essere attaccate da dizionario o più esattamente euristiche attacchi.

Ecco dove entriamo nel gioco psicologico. Se presumo che l'attaccante userà l'euristica per testare prima determinati modelli, io dovrei escluderli. Anche se so che questo riduce il numero di password possibili, da qui la forza teorica della password.

TL / DR: più vincoli aggiungi alla password, maggiore sarà la resistenza agli attacchi a breve termine utilizzando l'euristica, più vulnerabile sarà agli attacchi di forza bruta

Poiché è difficile dare precise probabilità per le password scelte dall'uomo, è difficile determinare con precisione l'effettiva entropia. Sopra il formule è valido solo quando ogni combinazione ha esattamente la stessa probabilità. Ma non appena le probabilità variano in modo sostanziale, la formula di entropia teorica darà un valore molto più basso. Estratto da wikipedia :

the entropy Η of a discrete random variable X with possible values {x1, ..., xn} and probability mass function P(X) is:

H ( X ) = E [ I ( X ) ] = E [ − ln ⁡ ( P ( X ) ) ]

dove E rappresenta l'aspettativa di una variabile