it-swarm-eu.dev

Confuso sull'entropia (password)

Sembra che ci siano molti 'tipi' diversi di entropia. Mi sono imbattuto in due concetti diversi:

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

B) L'entropia di Shannon della stringa attuale, ovvero l'entropia viene calcolata in base alle frequenze delle lettere/dei 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 alla mia confusione:

È importante comprendere la differenza tra l'entropia di una serie di possibili risultati e l'entropia di un risultato particolare. Un singolo lancio di una moneta giusta ha un'entropia di un bit, ma un risultato particolare (ad esempio "teste") ha un'entropia zero, poiché è del tutto "prevedibile".
- Wikipedia: Entropia (teoria dell'informazione)

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

  1. Quando viene usato B e per quale scopo?
  2. Quale concetto riflette accuratamente l'entropia della password?
  3. Esiste una terminologia per distinguere tra i due?
  4. La vera casualità potrebbe darci correctcorrectcorrectcorrect. Usando A abbiamo ancora 44 bit. Usando B l'entropia sarebbe la stessa di correct. Quando è importante la differenza tra i due?
  5. Se un requisito specifica che una stringa deve avere 20 bit di entropia, devo usare A o B per determinare l'entropia?
39
mds

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

A e B non sono concetti diversi di entropia della password, stanno solo usando ipotesi diverse su come viene costruita una password.

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

B considera correcthorsebatterystaple come una stringa di caratteri e presuppone che la probabilità che un personaggio appaia sia la stessa di quella in lingua inglese. Sulla base di questi presupposti correcthorsebatterystaple ha 84 bit di entropia.

Quindi quale definizione usi dipende davvero da quali ipotesi fai sulla password. Se si assume che la password sia una password in stile XKCD (e che ogni Parola abbia effettivamente una possibilità nel 2048 di apparire nella password), A è il modo corretto di calcolare l'entropia. Se non supponi che la password sia costruita come una raccolta di parole ma supponi che la probabilità che un personaggio appaia uguale alla probabilità del suo aspetto in lingua inglese, allora B è il modo corretto di calcolare l'entropia.

Nel mondo reale nessuna di queste ipotesi è corretta. Quindi se hai 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, vedere Calcolo dell'entropia della password? .

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

23

Cosa significa

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

L'entropia di Shannon presuppone che il valore della lettera successiva sia sia in effetti parzialmente determinato dal valore della lettera precedente (e forse altri). Fatti come "h" spesso seguono "t" e "e" spesso seguono "h" sono presi in considerazione, quindi ai modelli comuni viene 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.

Cosa significa tu

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

In quale dizionario è la tua password?

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

Ad esempio:

  • La tua password è tra le prime 500 password più utilizzate
  • La tua password è nel dizionario di parole inglesi minuscole
  • La tua password è nell'elenco delle parole inglesi minuscole o minuscole con un suffisso di una o due cifre
  • La tua password è nella lista di parole inglesi a caso casuale con haxor sostituzioni numeriche (cioè A => 4, L => 1, S => 5 )
  • La tua password è 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 usati per crackare le password nel mondo reale.

In altre parole

Lo scopo della complessità della password è di opporsi a un attacco di forza bruta. La dimensione del dizionario più piccolo disponibile che contiene la password determina il tempo necessario per decifrare la password. Possiamo indovinare quali dizionari saranno disponibili per l'attaccante, ma non possiamo saperlo con certezza. Pertanto, come proxy per le dimensioni del dizionario, utilizziamo invece entropia . È un sostituto scadente perché non riflette la meccanica dell'attacco reale, ma è potenzialmente migliore di niente.

Il confronto delle password basato sui calcoli dell'entropia può essere potenzialmente fruttuoso, ma si dovrebbe fare attenzione a non attribuire troppo valore a un numero che, alla fine, è solo indirettamente correlato alla capacità della password.

20
tylerl

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

Supponiamo di avere un generatore di numeri casuali con un'entropia di output dimostrabile di 3 bit per cifra di output. L'entropia di "lancio" di quel generatore è di 3 bit. Ora, supponiamo che tu lo esegua per 20 cifre, e nonostante la probabilità ridicolmente piccola, ogni numero nel flusso esce come 6. L'entropia "lancio" è ancora 3 bit per cifra, quindi 60 bit. L'entropia effettiva del "risultato" della password è minuscola - si potrebbe sostenere che è basso come 3 o 4 bit.

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

6
Polynomial

Un singolo byte può contenere fino a 8 bit di entropia. Questo è il limite superiore. Man mano che apprendi di più sui tuoi dati, la quantità di entropia in quel blocco di 8 byte diminuisce. Oh, tutti i tuoi byte sono tutti ASCII caratteri? Ciò significa che il bit più alto deve essere uno 0; sei giù a 7 bit di entropia. Nessun carattere di controllo? Dei ASCII set, 0-31 sono caratteri di controllo: tab, enter, bell, end-of-file. Questo riduce ulteriormente il carattere alfabetico, solo lettere minuscole? Ora stai riducendo enormemente le opzioni disponibili. Parola inglese ? Non molti di questi - un'intera parola inglese, selezionata casualmente, 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é alcuni sono scelti più frequentemente di altri. Se alcune password sono comuni, è più facile indovinare; che influenza l'entropia. Se il 10% dei tuoi utenti ha "password", ciò ridurrà l'entropia nel tuo elenco di password, ovvero è più facile indovinarlo.

Quindi più informazioni hai su una password, più in basso puoi calcolare l'entropia. Nel caso della formula di Shannon, assume i pregiudizi 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 stesse hackerando questa password, sapendo solo che era un linguaggio naturale, e poi improvvisamente scoprendo che c'erano 4 parole da un elenco del 2048 (e conoscendo l'elenco), avrebbero improvvisamente trovato il loro lavoro un MOLTO più facile.

3
AMADANON Inc.

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

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

Ma poi quando lo fai:

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

... stai scegliendo una distribuzione di probabilità diversa da quella usata da Munroe, quindi otterrai una stima diversa, una che assegna alla stringa circa 84 bit di entropia (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 scelgono le password. Se riesci a formarti un'idea ragionevole di come appare questa distribuzione, l'entropia di una password è la lunghezza del messaggio in un codice ottimale per quella distribuzione. Questo è, approssimativamente, l'approccio nei migliori misuratori di forza della password come zxcvbn (sebbene lo formulino in termini di numero medio di ipotesi per colpire la password).

Quando guardi le stime a 44-84 bit mostrate nella tua domanda da questa prospettiva, quello che sta succedendo è questo: Munroe ottiene una stima dell'entropia molto più bassa per la password perché presume che l'attaccante abbia una precisione del 100% ipotesi su come è stata generata la passphrase, in modo che possano escludere un numero enorme di stringhe a priori che non sono semplicemente concatenazioni di quattro parole nel dizionario. Considerando che il calcolo dell'entropia di Shannon che illustrate ottiene una stima dell'entropia molto più elevata perché non è così "intelligente" di una strategia per indovinare passphrase in stile XKCD. zxcvbn è più intelligente, tuttavia, e stima che un cracker di password creerebbe correcthorsebatterystaple in circa 10 ^ 14.43696 ipotesi che sono circa (14,4 × 3,3) + 1 ≈ 48,6 bit di entropia. (Il calcolo è una conversione da logaritmo da base 10 a base 2, più un bit per convertire dal numero di ipotesi all'entropia). Questo è un po 'più della stima di Munroe, ma zxcvbn è codificato per attaccare altre password oltre alle passphrase in stile XCKD .

1
Luis Casillas