Confuso su entropia (password)

38

Sembra che ci siano molti "tipi" di entropia. Ho trovato due concetti diversi:

A) L'esempio XKCD di correcthorsebatterystaple . Ha 44 bit di entropia perché quattro parole scelte a caso da un elenco di 2048 parole sono 4 * log2 (2048) = 44 bit di entropia. Questo capisco.

B) L'entropia di Shannon della stringa attuale, vale a dire che l'entropia viene calcolata in base alle frequenze delle lettere / simboli. Applicando la formula di Shannon su correcthorsebatterystaple il risultato è 3,36 bit di entropia per carattere.

# from http://stackoverflow.com/a/2979208
import math
def entropy(string):
        "Calculates the Shannon entropy of a string"

        # get probability of chars in string
        prob = [ float(string.count(c)) / len(string) for c in dict.fromkeys(list(string)) ]

        # calculate the entropy
        entropy = - sum([ p * math.log(p) / math.log(2.0) for p in prob ])

        return entropy

print entropy('correcthorsebatterystaple')
# => 3.36385618977

Wikipedia aggiunge solo confusione:

It is important to realize the difference between the entropy of a set of possible outcomes, and the entropy of a particular outcome. A single toss of a fair coin has an entropy of one bit, but a particular result (e.g. "heads") has zero entropy, since it is entirely "predictable".
-- Wikipedia: Entropy (information theory)

Non capisco perfettamente la distinzione tra l'entropia del lancio (generazione) e l'entropia del risultato (la stringa).

  1. Quando viene utilizzato B e per quale scopo?
  2. Quale concetto riflette con precisione l'entropia della password?
  3. Esiste una terminologia per distinguere tra i due?
  4. La vera casualità potrebbe darci correctcorrectcorrectcorrect . utilizzando A abbiamo ancora 44 bit. Usando B l'entropia sarebbe la stessa di quello di correct . Quando è la differenza tra i due importanti?
  5. Se un requisito specifica che una stringa deve avere 20 bit di entropy-do io uso A o B per determinare l'entropia?
posta mds 05.10.2012 - 06:56
fonte

5 risposte

20

L'articolo di Wikipedia spiega l'entropia matematica, che non è identica a ciò che le persone intendono quando parlano di entropia della password. L'entropia della password è più importante di quanto sia difficile indovinare una password in base a determinati presupposti, diversi dal concetto matematico di entropia.

A e B non sono concetti diversi di entropia della password, ma usano solo presupposti diversi su come viene costruita una password.

A tratta correcthorsebatterystaple come una stringa di parole inglesi e presuppone che le parole siano selezionate casualmente da una raccolta di 2048 parole. Sulla base di queste ipotesi ogni parola fornisce esattamente 11 bit di entropia e 44 bit di entropia per correcthorsebatterystaple .

B considera correcthorsebatterystaple come una stringa di caratteri e assume che la probabilità che un personaggio appaia è la stessa che è nella lingua inglese. Sulla base di queste ipotesi, correcthorsebatterystaple ha 84 bit di entropia.

Quindi la definizione che utilizzi dipende in realtà dalle supposizioni che fai riguardo alla password. Se si presuppone che la password sia una password in stile XKCD (e che ogni parola abbia effettivamente la possibilità che uno in 2048 appaia nella password), allora A è il modo corretto per calcolare l'entropia. Se non si assume che la password sia costruita come una raccolta di parole, ma si supponga che la probabilità che un personaggio appaia uguale alla probabilità che appaia nella lingua inglese, B è il modo corretto per calcolare l'entropia.

Nel mondo reale nessuna di queste ipotesi è corretta. Quindi, se si dispone di un "requisito che specifica che una stringa deve avere 20 bit di entropia" e questo è per le password generate dall'utente, è molto difficile dare una definizione precisa di entropia. Per ulteriori informazioni, consultare Calcolo dell'entropia delle password? .

Se, d'altra parte, puoi usare stringhe generate dal computer (e stai utilizzando un buon PRNG), ogni carattere alfanumerico (a-z, A-Z, 0-9) darà quasi 6 bit di entropia.

    
risposta data 05.10.2012 - 08:23
fonte
16

Che cosa significa

L'entropia

lancio della moneta presuppone che da un lancio all'altro, il risultato del lancio precedente non influenzi il risultato del lancio successivo. Quindi, ogni lancio aggiunge un po 'di entropia.

L'entropia

Shannon presuppone che il valore della lettera successiva sia in realtà parzialmente determinato dal valore della lettera precedente (e forse da altri). Fatti come "h" spesso seguono "t" e "e" spesso seguono "h" sono presi in considerazione in modo che ai modelli comuni sia assegnato un valore di entropia inferiore. Quindi con un dizionario inglese, la stringa the avrebbe un valore di entropia di Shannon molto più basso della stringa exu .

Che cosa significa tu

L'implicazione diretta di questo rispetto alle password è piuttosto insignificante. La vera (e unica) domanda importante riguardo alle password è questa:

What dictionary is your password in?

Vale a dire, se dovessi costruire un elenco di potenziali password per condurre un attacco di forza bruta, quanto dovrebbe essere grande il dizionario per contenere la tua password?

Ad esempio:

  • La tua password è nella top 500 delle password più utilizzate
  • La tua password è nel dizionario delle parole inglesi minuscole
  • La tua password è nell'elenco delle parole inglesi minuscole o in maiuscolo con un suffisso di una o due cifre
  • La tua password è nella lista di parole inglesi casuali con sostituzioni numeriche haxor (cioè A = > 4, L = > 1, S = > 5)
  • La tua password è presente nell'elenco di tutte le stringhe di 8 caratteri o meno utilizzando numeri e lettere maiuscole e minuscole.

Tutti i precedenti sono esempi di dizionari di cracking delle password reali utilizzati di frequente.

In altre parole

Lo scopo della complessità della password è di fronteggiare un attacco di forza bruta. La dimensione del dizionario più piccolo disponibile che contiene la tua password determina la quantità di tempo necessaria per decifrare la tua password. Possiamo indovinare su quali dizionari saranno disponibili per l'aggressore, ma non possiamo saperlo con certezza. Pertanto, come proxy per le dimensioni del dizionario, utilizziamo invece entropy . È un sostituto scadente perché non riflette le reali meccaniche di attacco, ma è potenzialmente meglio di niente.

I confronti delle password basate sui calcoli di entropia potrebbero essere fruttuosi, ma dovresti fare attenzione a non attribuire troppo valore a un numero che, alla fine, è solo indirettamente correlato a quanto bene la password reggerà.

    
risposta data 05.10.2012 - 09:38
fonte
6

Suppongo che il modo più semplice per illustrarlo sia con un esempio.

Diciamo che un generatore di numeri casuali ha un'entità di uscita dimostrabile di 3 bit per cifra di output. L'entropia di "lancio" di quel generatore è di 3 bit. Ora, diciamo che lo gestisci per 20 cifre, e nonostante la probabilità ridicolmente piccola, ogni numero nel flusso esce come 6. L'entropia di "lancio" è ancora 3 bit per cifra, quindi 60 bit. L'effettiva entropia "risultato" della password è minima - si potrebbe obiettare che è bassa come 3 o 4 bit.

La differenza è che l'entropia "lancio" rappresenta l'entropia attesa dell'output, basata sulla modellazione probabilistica del generatore, mentre l'entropia "risultato" rappresenta l'effettiva entropia dell'informazione dei dati che ha prodotto in un caso reale.

    
risposta data 05.10.2012 - 09:38
fonte
3

Un singolo byte può contenere fino a 8 bit di entropia. Questo è il limite superiore. Man mano che si impara di più sui dati, la quantità di entropia in questi blocchi da 8 byte diminuisce. Oh, tutti i tuoi byte sono tutti caratteri ASCII? Ciò significa che il bit più alto deve essere uno 0; sei giù fino a 7 bit di entropia. Nessun personaggio di controllo? Del set ASCII, 0-31 sono i caratteri di controllo - tab, enter, bell, end-of-file. Ciò riduce ulteriormente il carattere. alfabetico, minuscolo solo? Ora stai riducendo notevolmente le opzioni disponibili. Parola inglese? Non molti di questi - un'intera parola inglese, RANDOMLY selected, può avere solo circa 12 bit, anche se le parole possono avere 5 caratteri.

Le password scelte dagli umani sono anche peggiori; non perché le possibilità siano più piccole, ma perché alcune sono scelte più frequentemente di altre. Se certe password sono comuni, è più facile da indovinare; ciò influenza l'entropia. Se il 10% dei tuoi utenti ha una "password", ciò ridurrà l'entropia nella tua lista di password - cioè è più facile da indovinare.

Quindi più informazioni hai su una password, più in basso puoi calcolare l'entropia. Nel caso della formula di Shannon, assume i bias nei linguaggi naturali e calcola l'entropia a 3,6 bit * 25 caratteri = circa 90 bit. Quando ottieni le informazioni aggiuntive (4 parole, ciascuna da un elenco di 2048), che scende a 44 bit.

Guarda in questo modo - se qualcuno stava hackerando questa password, sapendo solo che era un linguaggio naturale, e poi improvvisamente scoprendo che c'erano 4 parole da un elenco di 2048 (e conoscendo l'elenco), avrebbero trovato improvvisamente il loro lavoro è MOLTO più facile.

    
risposta data 05.03.2014 - 22:56
fonte
0

La cosa che ti manca qui è il fatto che una misura di entropia è legata ad una specifica distribuzione di probabilità . Non puoi parlare dell'entropia di una password senza fare alcune ipotesi, esplicite o implicite, su quale distribuzione di probabilità è la password estratta casualmente da . Quale parte inferiore alla natura del processo in cui viene generata la password.

Nel fumetto XKCD, Munroe ti sta dicendo che ha generato la passphrase selezionando in successione e in modo indipendente quattro parole a caso da un dizionario di circa 2 ^ 11 parole. Questo ti dice esattamente la distribuzione di probabilità dalla quale viene disegnata la password: la distribuzione discreta uniforme su un insieme di 2 ^ 44 passphrase distinte.

Ma poi quando lo fai:

B) The Shannon entropy of the actual string i.e. the entropy is calculated based on frequencies of the letters/symbols. Applying the Shannon formula on correcthorsebatterystaple the result is 3.36 bits of entropy per character.

... stai scegliendo una distribuzione di probabilità diversa da quella utilizzata da Munroe, quindi otterrai una stima diversa, una che assegna circa 84 bit di entropia alla stringa (25 × 3.36).

Se stai valutando l'entropia delle password per le quali non sai come sono state generate, una prospettiva fruttuosa e intuitiva è quella di adottare l'idea che la distribuzione di probabilità in gioco sia la conoscenza e le ipotesi degli aggressori su come gli utenti selezionare le password. Se riesci a formarti un'idea ragionevole di come sia questa distribuzione, l'entropia di una password è la lunghezza del suo messaggio in un codice ottimale per quella distribuzione. Questo è, molto approssimativamente, l'approccio nei metri di forza password migliori come zxcvbn (anche se lo formulano in termini di numero medio di indovina per colpire la password).

Quando guardi le stime da 44 a 84 bit mostrate nella tua domanda da questo punto di vista, ciò che sta succedendo è questo: Munroe ottiene una stima di entropia molto inferiore per la password perché presume che l'attaccante abbia una Un'ipotesi precisa al 100% su come è stata generata la passphrase, in modo che possano escludere un numero enorme di stringhe a priori che non sono solo concatenazioni di quattro parole nel dizionario. Considerando che il calcolo dell'entropia di Shannon che si illustra ottiene una stima di entropia molto più alta perché non è così "intelligente" di una strategia per indovinare passphrase in stile XKCD. zxcvbn è più furbo, tuttavia, e stima che un cracker delle password creerebbe correcthorsebatterystaple in circa 10 ^ 14.43696 ipotesi di circa (14.4 × 3.3) + 1 ≈ 48.6 bit di entropia. (Il calcolo è una conversione da logaritmo in base 10 a base 2, più un bit da convertire da numero di ipotesi a entropia.) Questo è un po 'più di stima di Munroe, ma zxcvbn è codificato per attaccare altre password rispetto alle passphrase in stile XCKD .

    
risposta data 30.01.2018 - 00:30
fonte

Leggi altre domande sui tag