Come dimostrare una teoria che indovina la password dal libro di Matt Bishop "Introduzione alla sicurezza informatica"

Con la matematica:

Supponiamo che ci siano n password possibili. Il numero di password i ha probabilità p _i di essere selezionato. Si presume che l'attaccante conosca i valori esatti di p _i e li provi nell'ordine dovuto. Senza perdita di generalità, suppongo che p ₁ sia la password più probabile, e così via (cioè p _i > = p _j ogni volta i < j ).

Sia q _j la somma di tutti p _i per i che vanno da 1 a j . q _j è la probabilità che la password faccia parte delle j password più probabili (necessariamente, q _n = 1 : la password fa parte dello spazio di possibili password). Quanto segue è vero:

For all j, q_j >= j/n

Perché se q _j < j / n (per alcuni valori j ), allora deve esserci un valore i inferiore a j tale che p _i < 1 / n . La condizione su p _i (valori non crescenti) implica quindi che tutti p _k per k > sono inferiori a 1 / n , e questo implica che q _n < 1 , che non è possibile.

q _j è la probabilità che l'hacker esegua al più tentativi di j . Valori più alti implicano un successo più veloce, cioè se ci sono due probabilità di distribuzione P e P ' tali che q' _j > = q _j per tutti j , quindi l'attacco per P ' riesce almeno altrettanto velocemente dell'attacco per P . Nota che due date probabilità di distribuzione non possono necessariamente essere confrontate come questa (potrebbero esserci alcuni , ma non tutti valori j tali che q ' _j > = q _j ), ma, se può essere confrontato, la conclusione è la seguente.

La distribuzione uniforme ( p _i = 1 / n per tutti i ) implica q _j = j / n per tutti j , che, come spiegato sopra, confronta favorevolmente (per il difensore) con tutte le altre distribuzioni. Pertanto, questa è la distribuzione che rende l'attacco più lento.

Con fisica:

La velocità di successo dell'attacco è maggiore quando l'entropia della password è inferiore. La distribuzione uniforme massimizza l'entropia.

Facciamo alcune definizioni:

1. Equiprobable significa che per un insieme di password W , ogni elemento in W ha un'uguale probabilità di occorrenza, cioè P ( W _a ) = P ( W _b ) per qualsiasi a e b .
2. Si presume che il set W contenga effettivamente la password che stiamo cercando. Come tale, possiamo supporre che Σ P ( W _n ) = 1.
3. La probabilità che un sottoinsieme n di W contenga la password che stiamo cercando è n * P ( W _x ) per qualsiasi x , o essenzialmente n diviso per il numero di password in W .
4. Se tutte le password non sono equiprobabili, ma la definizione # 2 è ancora valida, la nostra migliore stima (senza conoscere le probabilità di sottoinsiemi specifici) è che una selezione casuale di W sarà comunque conforme alla definizione # 3 .

Il tempo previsto è definito come la quantità di lavoro necessaria per trovare la password di destinazione con una probabilità del 50%. In quanto tale, ingenuamente crackare una password contro il set W risulterà sempre in un tempo previsto di n / 2, dove n è il numero di voci in W .

Tuttavia, se conosci la probabilità di ciascuna password, puoi organizzarle in bucket equiprobabili. Come tale, tutte le password in W sono suddivise in n sottoinsiemi W ⁰ , W ¹ , W ² , ... W ⁿ , ognuno dei quali contiene un numero di password equiprobabili. L'avvertenza è che la password non è più garantita per essere in un singolo sottoinsieme - abbiamo solo una probabilità che la password sia in un particolare sottoinsieme. Tuttavia, la definizione n. 2 continua a valere quando si considerano tutti i sottoinsiemi nel loro insieme, cioè Σ P ( W ⁿ ) = 1.

Supponiamo di avere cinque sottoinsiemi:

Subset | Prob. (Password) | Count | Prob. (Subset)
-------+------------------+-------+---------------
W0     | 0.005            | 20    | 0.1
W1     | 0.002            | 60    | 0.12
W2     | 0.0004           | 540   | 0.216
W3     | 0.00007          | 6000  | 0.42
W4     | ~0.0000426       | 3380  | 0.144

In questo caso dobbiamo calcolare il numero di password che controlliamo prima che la probabilità totale di raggiungere la password raggiunga 0,5. Quindi, per il primo sottoinsieme ( W ⁰ ) raggiungiamo 0.1, per il secondo ( W ¹ ) noi raggiungere 0,22, per il terzo ( W ² ) raggiungiamo 0.436. Quando guardiamo al quarto bucket ( W ³ ) ci accorgiamo che stiamo superando lo 0.5. Quindi, calcoliamo il numero di password nel bucket W ³ che ci porterà da una probabilità di 0.436 a 0.5. Questo è semplice: sottrarre, quindi dividere: 0,5 - 0,436 = 0,064, 0,064 / 0,00007 = 914. Quindi, il nostro lavoro previsto è 20 + 60 + 540 + 914 = 1534 hash.