Come è stato sviluppato il concetto di entropia della password?

29

Capisco come calcolare l'entropia della password e cosa rappresentano i valori Length e Character. Ho anche una ragionevole comprensione degli altri tipi di entropia (ad esempio Shannon). Tuttavia, l'entropia della password sembra essere notevolmente diversa (nella forma) rispetto ad altri tipi di entropia; un semplice log₂ (D) dove D è una metrica di difficoltà o complessità. Mi piacerebbe capire come il concetto di entropia della password sia stato sviluppato per comprendere altre applicazioni di questa forma di entropia.

L'entropia della password soddisfa i requisiti di altri tipi di entropia: additiva, lineare, ecc. Per un esempio stupidamente semplice, se il mio sistema richiede due password, posso semplicemente aggiungere l'entropia di ciascuna password?

EDIT: chiaramente non ho formulato questa domanda molto bene. Mie scuse. Lasciatemi riprovare da una prospettiva di sicurezza più cibernetica: possiamo definire la dimensione dell'informazione H₀ (A) in un insieme A come il numero di bit necessario per codificare ciascun elemento di A separatamente, cioè H₀ (A) = log₂ | A |. Ora lascia che A sia l'informazione necessaria per sconfiggere un sistema di protezione sul dispositivo. Per una password, la dimensione impostata A (e quindi la dimensione dell'informazione H₀ (A)) può essere quantificata in modo semplice, N L . Sto cercando di ottenere alcune informazioni su situazioni in cui la dimensione di A non è così facilmente quantificabile, ma ho una metrica che cattura l'insieme di informazioni, diciamo 'B'. Quali sono gli argomenti contro l'uso di H₀ (B) = log₂ (B) per quantificare la dimensione delle informazioni necessarie per sconfiggere il sistema di protezione? Ancora una volta, mi scuso per una domanda formulata male.

    
posta Aengus 01.12.2017 - 18:33
fonte

7 risposte

37

L'entropia nella fisica e nella scienza dell'informazione è solo il logaritmo (tipicamente logico naturale in fisica; log-in base 2 in informatica) del numero di possibilità altrettanto probabili, perché è generalmente più facile trattare e pensare con il logaritmo di questo numero eccezionalmente elevato di possibilità rispetto alle possibilità direttamente.

Se ho generato a caso 128 bit come AES-128 casuale (che memorizzo da qualche parte), è facile vedere che ci sono 2 128 = 340,282,366,920,938,463,463,374,607,431,768,211,456 chiavi possibili che avrei potuto usare (2 uguali -possibile scelte per ogni bit e le probabilità si moltiplicano). Quando si parla di complessità informativa, è più semplice parlare della chiave che ha 128 bit di entropia piuttosto che dire di 340 x 10 36 o 340 undecillion (scala breve) , specialmente se vuoi confrontarlo con una chiave a 256 bit con 2 256 = 115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,639,936 possibilità.

Ora se ti do la password di un utente casuale, tecnicamente non è possibile assegnargli un'entropia in modo univoco.

È possibile assegnare un'entropia solo a un modello di generazione di password. Quindi, se ti viene chiesto di stimare un'entropia per una password, il tuo compito è quello di assumere il modello che potrebbe aver generato quella password.

Se ti avessi dato una password come P[rmDrds,r potresti presumere che ho scelto a caso 10 caratteri da un set di 95 caratteri ASCII stampabili e alla forza bruta dovresti passare per 95 10 ~ 2 65.7 possibilità e avrebbe un'entropia di 65.7 bit. Tuttavia, è solo una password molto debole OpenSesame in cui ho spostato le mie mani sulla tastiera verso la lettera a destra (che è probabilmente uno dei modi 2 ^ 6 ~ 64 per alterare la digitazione di una password a bassa entropia facile da ricordare ). Se potessi trovare OpenSesame in una lista di dire le password più comuni di 1.000 (1000 ~ 2 10 ), in realtà l'entropia di P[rmDrds,r è più vicina a 16 bit (possibilità di 2 < sup> 10 x 2 6 ), quando la generazione della password è scegliere uno dei 64 modi comuni per oscurare una password e quindi scegliere una password da un elenco di 1000 password comuni. Quindi, dopo circa 64.000 tentativi, un esperto forger sofisticato che ha provato questa via d'attacco potrebbe arrivare a P[rmDrds,r , quindi è più accurato stimare la sua entropia come circa 16 bit di 65.7 bit, che è 2 65.7-16 ~ 2 49.7 ~ 914 miliardi di volte più facili da forzare rispetto alla password da 65.7 bit.

Ora, ovviamente, un aggressore di forza bruta meno sofisticato potrebbe aver ignorato la possibilità di spostare i caratteri sulla tastiera di uno spazio a sinistra mentre si passava attraverso gli elenchi di password comuni. Ma per essere sicuri, ignori gli stupidi aggressori e presumi che un attaccante molto sofisticato abbia preso in considerazione tutti i tuoi metodi di generazione di password ( principio di Kerckhoffs dice evita la sicurezza per oscurità, supponi che il nemico abbia considerato la tua tecnica segreta tra molti altri metodi). Quindi, quando qualcuno dice che hai bisogno di una password ad alta entropia, il tuo obiettivo non è una password che sembra essere altamente casuale (e qualche password semplice tester lo etichetta come alta entropia). Vuoi una password casuale che è stata costruita con un sacco di scelte casuali che vengono inserite nella procedura di generazione della password. Non dovresti scegliere parole significative e creare una password per questo con trucchi oscuri come spostare le lettere in giro o sostituzioni di leeclip. Per una password sicura, dovresti fare affidamento su 80+ bit di casualità non umana inseriti nella tua procedura. Dovresti notare che un bit di entropia in una procedura di generazione di password equivale a una decisione di due opzioni (ad es. Qualcosa che potrebbe essere determinato da un lancio della moneta).

E ancora, con una probabilità molto piccola, puoi generare casualmente una password con molte scelte casuali e finisce con una password molto debole; ad esempio, è tecnicamente possibile scegliere casualmente 12 caratteri e ottenere password1234 o dddddddddddd . In pratica, è una possibilità anche se è improbabile che accada (ad esempio, se si utilizza una procedura che genera una password di 90 bit, la probabilità che abbia generato una password che potrebbe anche essere stata generata con una procedura più semplice con solo 34 bit è 2 34 / 2 90 = 1 in 2 56 che è approssimativamente la probabilità di acquistare esattamente due biglietti Mega Millions di fila e vincere il jackpot entrambe le volte).

    
risposta data 01.12.2017 - 20:50
fonte
19

In realtà, dalla tua descrizione, non sono sicuro che tu capisca come calcolare l'entropia della password. L'entropia di una password sarebbe più correttamente descritta come log (R) dove R è una metrica casualità , non una complessità .

Ad esempio, questo non ha nulla a che fare con l'utilizzo di caratteri speciali. La password Tr0ub4dor&3 ha 0 entropia perché l'ho presa da da qualche parte . D'altra parte, la password 1101111110101000001011001110101110011111010100101111001110101011 ha un'entropia di 64 bit, perché l'ho appena generata prendendo 8 byte casuali e stampandoli in binario.

L'entropia di una password è l'entropia della teoria dell'informazione. Misura la quantità di informazioni che qualcuno che sta cercando di infrangere la password non sa. Se non diversamente specificato, le persone di sicurezza presumono che il sistema debba difendersi da persone con intelligenza almeno normale. Per principio di Kerckhoffs , assumiamo che l'attaccante conosca il metodo con cui è stata scelta la password. Quindi il contenuto informativo a cui l'hacker manca del metodo è 0. Ciò che l'attaccante non può sapere, tuttavia, è l'output del mio generatore casuale. Quindi l'entropia di una password è il contenuto informativo fornito dal generatore casuale. Supponendo un generatore di numeri casuali perfetto e un metodo di generazione della password che trasforma output RNG distinti in password distinte, questo contenuto di informazioni è uguale alla quantità di dati letti dal RNG.

L'entropia della password è additiva. Se un sistema ha due password in modo tale che è necessario fornire entrambi per accedere, l'entropia della coppia di password è la somma dell'entropia delle due password. Nota che qui c'è un'ipotesi di indipendenza! Se riesci a scoprire se una password è corretta senza conoscere l'altra, allora l'entropia del sistema a due password è inferiore alla somma dell'entropia. (Come caso estremo, considera una password di N bit di lunghezza fissa: potresti considerare ogni bit della password come una mini-password separata, se puoi testare ciascun bit in modo indipendente, sono necessari solo 2N tentativi per spezzarlo invece di 2 ^ N). Ancora una volta, questa proprietà deriva dalla teoria dell'informazione: è possibile aggiungere l'entropia di due fonti di informazioni separate, ma non ha senso aggiungere l'entropia di due fonti che si sovrappongono.

    
risposta data 01.12.2017 - 19:46
fonte
5

Il motivo per cui l'entropia della password di solito è come log₂ (D) è che questa è l'entropia di Shannon per una fonte di informazioni che ha una distribuzione di probabilità uniforme per tutti i potenziali risultati quando il numero di potenziali risultati è D. In questo contesto, Risultati significa risultati da un processo stocastico di generazione di password.

E come altri hanno sottolineato, l'entropia non è una proprietà di nessuna password individuale. Entropia è una proprietà di un insieme di password definito da un particolare insieme di regole. Tuttavia, se non ti preoccupi di essere rigoroso, a volte puoi vagamente dedurre quali sono quelle regole controllando una password individuale, ad es. la presenza di cifre e lettere maiuscole implica vagamente regole che specificano un insieme più grande (con una distribuzione di probabilità uniforme) rispetto a quando sono presenti solo lettere minuscole.

Per una singola password c'è una misura diversa chiamata complessità di Kolmogorov che misura quanti bit di informazione sono necessari per produrre quella particolare password da un algoritmo predeterminato. Questa è ovviamente una misura relativa poiché dipende dall'algoritmo, ma in senso lato è possibile utilizzare la lunghezza compressa della password come proxy per la complessità di Kolmogorov.

    
risposta data 02.12.2017 - 18:55
fonte
4

Un modo migliore per pensare all'entropia di una password è la quantità minima di bit richiesta per trasmettere le informazioni contenute nella password. Alcuni esempi:

Se la mia password è 'aaaaaaaa', allora un modo valido per visualizzare l'entropia della password sarà di 5,9 bit (entropia per il carattere alfanumerico con maiuscole e minuscole) più 3 bit (per indicare che è ripetuta 3 volte).

Se un servizio richiede due password e io l'ho impostato per corrispondere l'un l'altro, non ho aumentato in modo significativo la quantità di informazioni per comunicare le password su una singola password, dal momento che "Password123" e "Password123 1" non sono " Questo è diverso in termini di entropia.

Se un servizio richiede due password ed entrambe sono (separatamente) generate casualmente, allora I ha raddoppiato l'entropia nelle password (anche se avrebbe più senso avere una sola password con più requisiti minimi rigorosi).

    
risposta data 01.12.2017 - 19:17
fonte
1

L'entropia della password è come l'entropia di ogni fonte di informazione: è -log_2 della probabilità bayesiana di quella esatta password per l'attaccante. In quanto tale, l'entropia di una password è, in senso stretto, dipendente dall'attaccante, perché è la probabilità bayesiana per lui, comprese tutte le informazioni che già possiede.

L'entropia della password per te è zero, perché la probabilità bayesiana della password corretta è 1 per te: il suo universo è costituito da una sola password, perché tu lo sai.

Se hai deciso di estrarre una parola selezionata in modo casuale da un dizionario di 4096 parole e l'hacker lo sa, l'entropia della password è di 12 bit. Se, tuttavia, l'attaccante non sa quale dei 256 dizionari possibili (con parole diverse, diciamo, perché lingue diverse) hai scelto, e se assegna a ognuna di esse probabilità uguali, la tua password avrà 20 bit di entropia per lui.

Se, d'altra parte, gli dà il 50% di probabilità di averlo preso dal dizionario giusto, e assegna l'altro 50% / 255 agli altri 255 dizionari (in altre parole, ha indovinato il dizionario giusto con 50%), quindi la password avrà solo 13 bit di entropia per lui. Nota che se ha indovinato il dizionario principale sbagliato, allora la tua password ha in realtà 21 bit di entropia per lui, perché ha assegnato solo il 50% / 255 al dizionario giusto! In altre parole, l'entropia di una password dipende da ciò che l'utente malintenzionato stima di sapere sulla tua password.

L'unico modo assolutamente sicuro per avere una password ad alta entropia è usare un vero generatore di numeri casuali (basato, per esempio, sulla seconda legge della termodinamica o sulla fisica quantistica), dove l'entropia fisica viene utilizzata per generare entropia di informazioni. Il punto è che nessuno ha uno stimatore bayesiano migliore dell'entropia fisica (o altrimenti, la seconda legge della termodinamica verrebbe violata: questo è esattamente ciò che la seconda legge sta dicendo in realtà).

Le funzioni di trapdoor a senso unico crittografiche non aggiungono entropia: nel migliore dei casi, conservano l'entropia. Se scegli un numero da 1 a 32, e poi calcoli SHA-256 o SHA-1 o qualsiasi combinazione di funzioni hash, avrai una cosa che sembra una password molto casuale, ma avrà solo 5 bit di entropia se il tuo picking di 1-32 era uniformemente casuale: ci sono solo 32 possibili risultati, non importa quanti bit hai nella tua password finale.

Anche i generatori pseudo casuali non aggiungono entropia: offuscano l'entropia che è nel seme. Non sono altro che una complicata sequenza di funzioni di hash applicate al seme.

    
risposta data 02.12.2017 - 17:03
fonte
1

Come altri hanno già detto, non è l'entropia della password, è l'entropia della generazione di password : quanto è difficile duplicare una determinata password data la piena conoscenza di come è stata creata.

Per calcolare l'entropia, annota il processo, passo dopo passo. Quindi determinare quanti tentativi ci vorrebbe per trovare una password generata da questi passaggi.

Password: 01012006

Processo: il compleanno di mio figlio nel formato mmddyyyy. 365,25 all'anno, l'età massima attuale delle persone e l'età minima per la nascita di un bambino di successo non superano i 115 anni. 115 x 365.25 = 42.004 tentativi prima che tu sia sicuro di aver trovato la password.

Processo: scegli 8 numeri casuali usando un dado a 10 facce. 10 ^ 8 tentativi prima di aver trovato la password.

La stessa password esatta, una è molto più facile da ottenere e soggetta a un'ottimizzazione fuori banda (informazioni non direttamente parte del processo, ma che limitano le opzioni). Se conosco la data di nascita dei tuoi figli, il numero massimo di tentativi attuali è probabilmente inferiore a 1000 e inferiore a 1.

Per quanto riguarda l'additivo: non esattamente. Hai solo un algoritmo di generazione password, include solo un passaggio che è stato utilizzato altrove come processo completo per la generazione di una password.

    
risposta data 02.12.2017 - 17:56
fonte
0

L'entropia della password è data da quanto tempo impiegherebbe tipicamente un utente malintenzionato, che conosceva il tuo schema di generazione della password, a scorrere tutte le possibili password che poteva generare.

Per esempio io uso un generatore di password che è fondamentalmente dicewords. Uso un metodo crittograficamente strong per generare una parola casuale, quindi uso gruppi di 6 bit da quello per scegliere da un dizionario di 64 parole inglesi di 3 lettere (ratto, mucca, uomini ...), per rendere la password più leggibile / utilizzabile / memorabile.

Sebbene l'entropia apparente (l'autore dell'attacco non conosca il metodo) di un personaggio dalla password risultante sia di circa 5 o 6 bit (un carattere da 26 alfa o più alfanumerico), la vera entropia (l'attaccante ha il mio programma) è solo 2, grazie alla conoscenza di come è stato generato.

Una password sicura è arrivata semplicemente avendo un numero sufficiente di caratteri. Una stringa di 39 caratteri avrà 78 bit di vera entropia.

    
risposta data 04.12.2017 - 08:19
fonte

Leggi altre domande sui tag