¿Cómo afecta la repetición de caracteres a la entropía de las contraseñas?

La entropía de la contraseña se basa en el número de combinaciones posibles. Para que un patrón reduzca la entropía, el atacante debe conocer el patrón.

Si el patrón no es fijo y conocido, la reducción en la complejidad será específica del algoritmo del atacante . Será diferente para los diferentes atacantes. Por ejemplo, con un ataque de diccionario, la complejidad efectiva para las palabras del diccionario es el tamaño del diccionario, para las palabras fuera de la complejidad de la fuerza bruta del diccionario.

No sé si existe o puede haber un algoritmo matemáticamente óptimo para las repeticiones de letras. La solución más sencilla que se me ocurre es tratar las repeticiones de símbolos, hasta las repeticiones N, como grafemas adicionales. En ese caso, la fuerza de la contraseña será el número de grafemas que contiene.

Contra tal algoritmo, la fuerza agregada de cada símbolo consecutivo de los símbolos del 2 al N es 0, y es equivalente a otro grafema de hasta 2N. Pero tal algoritmo será más lento contra contraseñas aleatorias debido a un conjunto de caracteres efectivo más grande. Por ejemplo, la comprobación de repeticiones de 2 largos para cada símbolo disminuirá su velocidad en un factor de 2 ^ (longitud-1). Pero contra una contraseña que contiene todos los símbolos dobles, su velocidad mejorará hasta una raíz cuadrada de la complejidad anterior.

Si es imperativo que la eficiencia de la fuerza bruta no se vea comprometida, un ajuste gratuito siempre comienza a elegir el último grafema como igual al anterior. En ese caso, la resistencia agregada desde el primero (para longitud variable) o todos los símbolos de repetición al final (para longitud fija) es 0. Hacerlo en el medio ya no es un pellizco gratis. Tampoco se intentan repeticiones adicionales en una contraseña de longitud variable, aunque es tan barato como para ser casi gratis.

En resumen, contra un algoritmo optimizado para seleccionar contraseñas con caracteres repetidos, la fuerza de una contraseña puede estimarse al eliminar todos los dígitos consecutivos después del primero para obtener la longitud efectiva L '. La fortaleza teórica sería aproximadamente (conjunto de caracteres * N) ^ L ', donde N es el número máximo de repeticiones que el atacante está probando.

Contra un algoritmo optimizado para la eficiencia de fuerza bruta, solo se deben eliminar los dígitos consecutivos al final. La fuerza teórica con un algoritmo ingenuo sería charset ^ (L'-1) * (charset + N). Sin embargo, cualquier algoritmo práctico probará muchos sufijos (las contraseñas a menudo terminan en "1" o "1!" Para omitir las reglas de complejidad).

Todo depende de qué algoritmo utilice el atacante. Los diccionarios, incluidas las listas de contraseñas filtradas, generalmente se intentarán primero.

A un amigo cuyo doctorado en estadística le gusta decir, "A menudo, el único significado de una improbabilidad estadística es que ha ocurrido lo improbable".

La fórmula que le das tiene solo si cada personaje se selecciona al azar, lo que implica una selección independiente de los otros caracteres. Por lo tanto, es improbable, pero no imposible, que una contraseña completamente aleatoria sea 3333333333.

Dicho esto, los atacantes usan heurísticas. Uno de ellos podría ser buscar repeticiones y, al encontrarlo, probar que el siguiente personaje es otra repetición antes de intentar combinaciones más difíciles. Por lo tanto, estaría tentado a rechazar las sugerencias de contraseña con tres o más caracteres repetidos.

H = L * log (N) es la entropía matemática del conjunto de las posibles contraseñas de L caracteres al azar elegidos entre un conjunto de tamaño N. Es solo el registro de ese número: H = log (N ^L ).

Pero tan pronto como agregue reglas adicionales como:

• no permitir la repetición del mismo símbolo
• requiere la presencia de caracteres de subconjuntos desunidos

reduce el número de patrones posibles y reduce la fuerza (entropía). Si un atacante sabe que una contraseña no puede contener repeticiones de un personaje, puede optimizar su algoritmo con eso. Pero, de hecho, H mide la fuerza de la contraseña contra los ataques de fuerza bruta, donde el atacante asume que cualquier combinación tiene la misma probabilidad y navega constantemente por todo el conjunto posible.

Tales restricciones son de todos modos comunes, porque la mayoría de los usuarios no usan el verdadero azar para elegir una contraseña, y algunos malditos patrones simples ( 00000000 o 12345678 para ocho caracteres numéricos) tienen una probabilidad mucho mayor de ser elegidos que otros (*). Así que esas restricciones intentan evitar esas contraseñas simples que podrían ser atacadas por dictionary o más precisamente heurísticas ataques.

Ahí es donde entramos en el juego psicológico. Si asumo que el atacante usará heurísticas para probar primero patrones específicos, debería rechazarlos. Incluso si sé que esto reduce el número de contraseñas posibles, de ahí la fuerza teórica de la contraseña.

TL / DR: Cuantas más restricciones agregue a la contraseña, más resistente será a los ataques de corta duración utilizando heurísticas, más vulnerable será a los ataques de fuerza bruta

Como es difícil dar probabilidades precisas para las contraseñas elegidas por los humanos, es difícil determinar con precisión la entropía real. La fórmula anterior solo es válida cuando cada combinación tiene exactamente la misma probabilidad. Pero tan pronto como las probabilidades varíen de manera importante, la fórmula de entropía teórica dará un valor mucho menor. Extracto de wikipedia :

  

la entropía Η de una variable aleatoria discreta X con valores posibles {x1, ..., xn} y la función de masa de probabilidad P (X) es:

H ( X ) = E [ I ( X ) ] = E [ − ln ⁡ ( P ( X ) ) ]

donde E representa la expectativa de una variable