Cómo probar una teoría de adivinación de contraseñas del libro "Introducción a la seguridad informática" de Matt Bishop

Con matemáticas:

Supongamos que hay n contraseñas posibles. El número de contraseña i tiene la probabilidad p_i de ser seleccionado. Se asume que el atacante conoce los valores exactos de p_i y los prueba en el debido orden. Sin pérdida de generalidad, asumo que p₁ es la contraseña más probable, y así sucesivamente (es decir, p _i > = p _j siempre que i < j ).

Deje q_j la suma de todos los valores de p_i para i desde 1 hasta j . q_j es la probabilidad de que la contraseña sea parte de las contraseñas más probables de j (necesariamente, q _n = 1 : la contraseña es parte del espacio de posibles contraseñas). Lo siguiente es cierto:

  

Para todos j , q _j > = j / n

Porque si q _j < j / n (para algún valor j ), entonces debe haber un valor i más bajo que j tal que p _i < 1 / n . La condición en p_i (valores que no aumentan) implica que todos p_k para k > i son inferiores a 1 / n , y esto implica que q _n < 1 , que no es posible.

q_j es la probabilidad de que el atacante tenga éxito al hacer como máximo j conjeturas. Los valores más altos implican un éxito más rápido, es decir, si hay dos probabilidades de distribución P y P ', de manera que q' _j > = q _j para todos j , entonces el ataque para P ' tiene éxito al menos tan rápido como el ataque para P . Tenga en cuenta que dos probabilidades de distribución no pueden compararse necesariamente de esta manera (podría haber algunas , pero no todos valora j de manera que q ' _j > = q _j ), pero, si pueden ser comparados, la conclusión es la siguiente.

La distribución uniforme ( p _i = 1 / n para todos i ) implica q _j = j / n para todos j , que, como se explicó anteriormente, se compara favorablemente (para el defensor) con todas las demás distribuciones. Por lo tanto, esta es la distribución que hace que el ataque sea más lento.

Con física:

La velocidad de éxito del ataque es mayor cuando la entropía de la contraseña es menor. La distribución uniforme maximiza la entropía.

Hagamos algunas definiciones:

1. Equiprobable significa que para un conjunto de contraseñas W , cada elemento en W tiene la misma probabilidad de ocurrencia, es decir, P ( W _a ) = P ( W _b ) para cualquier a y b .
2. Se supone que el conjunto W sí contiene la contraseña que estamos buscando. Como tal, podemos suponer que Σ P ( W _n ) = 1.
3. La probabilidad de que un n -length subconjunto de W contenga la contraseña que estamos buscando es n * P ( W _x ) para cualquier x , o esencialmente n dividido por el número de contraseñas en W .
4. Si todas las contraseñas no son equiprobables, pero la definición # 2 aún se mantiene, nuestra mejor estimación (sin conocer las probabilidades de subconjuntos específicos) es que una selección aleatoria de W se adherirá a la definición # 3 .

El tiempo esperado se define como la cantidad de trabajo necesario para encontrar la contraseña de destino con una probabilidad del 50%. Como tal, descifrar ingenuamente una contraseña contra el conjunto W siempre dará como resultado un tiempo esperado de n / 2, donde n es el número de entradas en W .

Sin embargo, si conoce la probabilidad de cada contraseña, puede organizarlas en grupos equiprobable. Como tal, todas las contraseñas en W se dividen en n subconjuntos W⁰ , W ¹ , W² , ... Wⁿ , cada uno de los cuales Contiene una serie de contraseñas equiprobable. La advertencia de esto es que ya no se garantiza que la contraseña esté en un solo subconjunto, solo tenemos la posibilidad de que la contraseña esté en un subconjunto en particular. Sin embargo, la definición # 2 aún se mantiene cuando considera todos los subconjuntos como un todo, es decir, Σ P ( W ⁿ ) = 1.

Supongamos que tenemos cinco subconjuntos:

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

En este caso, debemos calcular la cantidad de contraseñas que verificamos antes de que la probabilidad total de golpear la contraseña llegue a 0.5. Entonces, para el primer subconjunto ( W ⁰ ) alcanzamos 0.1, para el segundo ( W ¹ ) alcanzamos 0.22, para el tercero ( W ² ) llegamos a 0.436. Cuando miramos el cuarto grupo ( W ³ ) notamos que estamos excediendo 0.5. Por lo tanto, calculamos el número de contraseñas en el depósito W³ que nos llevará de una probabilidad de 0.436 a 0.5. Esto es simple: reste, luego divida: 0.5 - 0.436 = 0.064, 0.064 / 0.00007 = 914. Por lo tanto, nuestro trabajo esperado es 20 + 60 + 540 + 914 = 1534 hashes.