Cálculo del tiempo requerido para aplicar la fuerza bruta a un código aleatorio

3

Supongamos que tenemos amount códigos de entrada aleatorios de length caracteres de un alfabeto de tamaño alphabet . El número de códigos posibles se calcula fácilmente como keyspace = alphabet ^ length .

Ahora tome a un atacante que esté tratando de ingresar usando la adivinación aleatoria de códigos de fuerza bruta. A la tasa de adivinaje rate , el tiempo en el que se pueden verificar todos (y por lo tanto la entrada está garantizada) se calcula fácilmente como keyspace / rate .

Sin embargo, lo que realmente me gustaría saber es cómo calcular el tiempo requerido para que el atacante tenga una posibilidad determinada de encontrar un código de entrada válido. Este es un sistema donde todo lo que necesita es un código válido, no hay un requisito secundario como un nombre de usuario (piense en cupones). Una vez más, hay amount en keyspace .

Por ejemplo, ¿cuánto tiempo le tomará al atacante tener un 1% de probabilidad de encontrar un código válido? ¿Y el 10%? ¿Y el 25%? Etc. O lo inverso, dada una cantidad específica de tiempo, ¿cuáles son las posibilidades?

    
pregunta Bart van Heukelom 13.07.2015 - 14:18
fuente

2 respuestas

2

Para el caso esperado (promedio), el número de intentos tiene una relación lineal con la probabilidad de éxito que se está considerando.

expected_time = probability * keyspace / ( rate * 2)

Por lo tanto, si el espacio clave estuviera compuesto por mil millones de códigos y el atacante pudiera forzar la fuerza de 1 millón de códigos por segundo para tener un 10% de probabilidad de éxito, el atacante necesitaría 50 segundos.

expected_time = 10% * 1000000000/(1000000 * 2)

Ahora, en su caso, usted indica que hay varios códigos válidos ( amount ). ¿Pueden estos códigos ser atacados en paralelo? Generalmente tratamos de evitar escenarios donde eso sea posible. Esta es una de las razones por las que agregamos sal a las contraseñas. Evita que un atacante ataque todas las posibles contraseñas de hash en paralelo. Otro ejemplo sería vincular un código a un ID de usuario determinado. Incluso si se conoce userid, esto limita al atacante a buscar un código específico, no un código válido. Si no es posible un ataque paralelo, la fórmula anterior es verdadera, pero si el atacante puede realizar un ataque contra todos los códigos válidos posibles con un solo intento, el tiempo esperado se reduce en la cantidad de códigos válidos ( amount ).

expected_time = probability * keyspace / (rate * amount * 2)

Otra forma de verlo es la cantidad de códigos válidos reduce el tamaño del espacio de teclas (suponiendo que los ataques se pueden realizar en paralelo y cualquier código válido es aceptable). Tenga en cuenta que en ninguno de los dos casos se aplica el problema de cumpleaños, por lo que solo hay una reducción lineal en el tiempo esperado cuando el atacante puede realizar un ataque paralelo. En términos de hash, esto sería un ataque de preimagen no un ataque de colisión. Aún así, generalmente intentamos escenarios donde los ataques paralelos son posibles porque no queremos aumentar la eficiencia del ataque (incluso de manera lineal).

    
respondido por el Gerald Davis 13.07.2015 - 14:26
fuente
0

Volviendo a las matemáticas probabilísticas de la escuela secundaria, lo siguiente debería estar cerca.

Dadas las claves válidas de amount en un espacio de tamaño space , la probabilidad de que cualquier suposición aleatoria sea correcta es winChance = amount / space .

Dado un número de conjeturas (que se calcula fácilmente a partir de rate y time ), la posibilidad de encontrar 0 claves válidas es (1-winChance) ^ guesses . Eso hace que la posibilidad de encontrar al menos 1 clave válida:

1 - ((1-winChance) ^ guesses)

Lo que no he tenido en cuenta es que después de cada intento fallido, la probabilidad de que el siguiente valor sea correcto aumenta ligeramente. Supongo que con un espacio suficientemente grande / suficientemente pequeño, este aumento es insignificante.

    
respondido por el Bart van Heukelom 13.07.2015 - 16:27
fuente

Lea otras preguntas en las etiquetas