Después de leer varios recursos sobre la seguridad de la contraseña, estoy tratando de crear un algoritmo que proporcione una estimación aproximada de la cantidad de entropía que tiene una contraseña.
Estoy tratando de crear un algoritmo que sea lo más completo posible. En este punto solo tengo pseudocódigo, pero el algoritmo cubre lo siguiente:
- longitud de la contraseña
- personajes repetidos
- patrones (lógicos)
- diferentes espacios de caracteres (LC, UC, numérico, especial, extendido)
- ataques de diccionario
NO cubre lo siguiente, y DEBE cubrirlo BIEN (aunque no perfectamente):
- pedidos (las contraseñas se pueden ordenar estrictamente por salida de este algoritmo)
- patrones (espaciales)
¿Alguien puede dar una idea de lo que este algoritmo podría ser débil? Específicamente, ¿alguien puede pensar en situaciones en las que la introducción de una contraseña para el algoritmo sobreestime su fuerza? Las subestimaciones son menos problemáticas.
El algoritmo:
// the password to test
password = ?
length = length(password)
// unique character counts from password (duplicates discarded)
uqlca = number of unique lowercase alphabetic characters in password
uquca = number of uppercase alphabetic characters
uqd = number of unique digits
uqsp = number of unique special characters (anything with a key on the keyboard)
uqxc = number of unique special special characters (alt codes, extended-ascii stuff)
// algorithm parameters, total sizes of alphabet spaces
Nlca = total possible number of lowercase letters (26)
Nuca = total uppercase letters (26)
Nd = total digits (10)
Nsp = total special characters (32 or something)
Nxc = total extended ascii characters that dont fit into other categorys (idk, 50?)
// algorithm parameters, pw strength growth rates as percentages (per character)
flca = entropy growth factor for lowercase letters (.25 is probably a good value)
fuca = EGF for uppercase letters (.4 is probably good)
fd = EGF for digits (.4 is probably good)
fsp = EGF for special chars (.5 is probably good)
fxc = EGF for extended ascii chars (.75 is probably good)
// repetition factors. few unique letters == low factor, many unique == high
rflca = (1 - (1 - flca) ^ uqlca)
rfuca = (1 - (1 - fuca) ^ uquca)
rfd = (1 - (1 - fd ) ^ uqd )
rfsp = (1 - (1 - fsp ) ^ uqsp )
rfxc = (1 - (1 - fxc ) ^ uqxc )
// digit strengths
strength =
( rflca * Nlca +
rfuca * Nuca +
rfd * Nd +
rfsp * Nsp +
rfxc * Nxc ) ^ length
entropybits = log_base_2(strength)
Algunas entradas y sus salidas entropy_bits deseadas y reales:
INPUT DESIRED ACTUAL
aaa very pathetic 8.1
aaaaaaaaa pathetic 24.7
abcdefghi weak 31.2
H0ley$Mol3y_ strong 72.2
s^fU¬5ü;y34G< wtf 88.9
[a^36]* pathetic 97.2
[a^20]A[a^15]* strong 146.8
xkcd1** medium 79.3
xkcd2** wtf 160.5
* these 2 passwords use shortened notation, where [a^N] expands to N a's.
** xkcd1 = "Tr0ub4dor&3", xkcd2 = "correct horse battery staple"
El algoritmo se da cuenta (correctamente) de que aumentar el tamaño del alfabeto (incluso en un dígito) fortalece enormemente las contraseñas largas, como lo demuestra la diferencia en entropy_bits para las contraseñas sexta y séptima, que consisten en 36 a, pero la 21 a es la segunda. capitalizado Sin embargo, no tienen en cuenta el hecho de que tener una contraseña de 36 a no es una buena idea, se rompe fácilmente con un cracker de contraseña débil (y cualquiera que lo vea escribir lo verá) y el algoritmo no refleja eso .
Sin embargo, refleja el hecho de que xkcd1 es una contraseña débil en comparación con xkcd2, a pesar de tener una mayor densidad de complejidad (¿es esto incluso una cosa?).
¿Cómo puedo mejorar este algoritmo?
Anexo 1
Los ataques de diccionario y los ataques basados en patrones parecen ser la gran cosa, así que intentaré abordarlos.
Podría realizar una búsqueda exhaustiva a través de la contraseña de palabras de una lista de palabras y reemplazar palabras con tokens únicos para las palabras que representan. Los tokens de palabras se tratarían como caracteres y tendrían su propio sistema de peso, y agregarían sus propios pesos a la contraseña. Necesitaría algunos nuevos parámetros de algoritmo (los llamaré lw, Nw ~ = 2 ^ 11, fw ~ = .5 y rfw) y factorizaría el peso en la contraseña como lo haría con cualquiera de los otros pesas
Esta búsqueda de palabras podría modificarse especialmente para que coincida con letras minúsculas y mayúsculas, así como con sustituciones de caracteres comunes, como la de E con 3. Si no agrego un peso extra a esas palabras coincidentes, el algoritmo subestimaría un poco su fuerza. o dos por palabra, lo cual está bien. De lo contrario, una regla general sería, para cada coincidencia de caracteres no perfectos, dar a la palabra un poco de bonificación.
Luego podría realizar comprobaciones de patrones simples, como búsquedas de corridas de caracteres repetidos y pruebas derivadas (tomar la diferencia entre cada carácter), que identificarían patrones como 'aaaaa' y '12345', y reemplazar cada patrón detectado con un patrón ficha, única para el patrón y la longitud. Los parámetros algorítmicos (específicamente, entropía por patrón) podrían generarse sobre la marcha en función del patrón.
En este punto, tomaría la longitud de la contraseña. Cada ficha de palabra y ficha de patrón contaría como un carácter; cada ficha reemplazaría a los personajes que representaban simbólicamente.
Creé algún tipo de notación de patrón, pero incluye la longitud del patrón l, el orden del patrón o y el elemento base b. Esta información podría usarse para calcular un peso arbitrario para cada patrón. Haría algo mejor en el código real.
Ejemplo modificado:
Password: 1234kitty$$$$$herpderp
Tokenized: 1 2 3 4 k i t t y $ $ $ $ $ h e r p d e r p
Words Filtered: 1 2 3 4 @W5783 $ $ $ $ $ @W9001 @W9002
Patterns Filtered: @P[l=4,o=1,b='1'] @W5783 @P[l=5,o=0,b='$'] @W9001 @W9002
Breakdown: 3 small, unique words and 2 patterns
Entropy: about 45 bits, as per modified algorithm
Password: correcthorsebatterystaple
Tokenized: c o r r e c t h o r s e b a t t e r y s t a p l e
Words Filtered: @W6783 @W7923 @W1535 @W2285
Breakdown: 4 small, unique words and no patterns
Entropy: 43 bits, as per modified algorithm
La semántica exacta de cómo se calcula la entropía a partir de patrones está en discusión. Estaba pensando algo como:
entropy(b) * l * (o + 1) // o will be either zero or one
El algoritmo modificado encontraría fallas y reduciría la fuerza de cada contraseña en la tabla original, con la excepción de s^fU¬5ü;y34G<que no contiene palabras o patrones.
Respuestas:
El Apéndice A en la p46 del NIST SP 800-63 habla sobre el trabajo de Claude Shannon , quien estima la entropía de la contraseña utilizando varios bits. De hecho, este es el documento que la caricatura XKCD usa para calcular los bits de entropía. Específicamente:
La idea es que un sistema de autenticación seleccionaría ciertos niveles de entropía como umbrales. Por ejemplo, 10 bits pueden ser débiles, 20 medios y 30 fuertes (números elegidos arbitrariamente como ejemplo, no como una recomendación). Desafortunadamente, el documento no recomienda tales umbrales, probablemente porque la potencia computacional disponible para la fuerza bruta o adivinar contraseñas aumenta con el tiempo:
Esto puede o no ser lo que está buscando, pero no es un mal punto de referencia, por lo menos.
[Editar: se agregó lo siguiente.]
El ensayo Pruebas de métricas para las políticas de creación de contraseñas atacando grandes conjuntos de contraseñas reveladas (por Matt Weir, Sudhir Aggarwal, Michael Collins y Henry Stern) demostró que el modelo de Shannon, descrito anteriormente, no es un modelo exacto de entropía para contraseñas generadas por humanos. Recomendaría consultar "Sección 5 Generar nuevas políticas de creación de contraseñas" para obtener propuestas más precisas.
fuente
Consulte el código fuente de KeePass en la parte inferior de esta página . La
QualityEstimationclase implementa un algoritmo bastante agradable que parece estar en línea con lo que está buscando tener en su lugar. Mis resultados se ven así:fuente
Usted pregunta
Pero tienes un ejemplo en la pregunta. Por diseño, xkcd2 tiene ~ 44 bits de entropía, pero su estimación es de 160.5 bits.
fuente
Has insinuado algunos en el preámbulo (ataques de diccionario, etc.). Esencialmente, hay una serie de prácticas comunes que el atacante puede adivinar, lo que reduce en gran medida el espacio de búsqueda. Estoy bastante seguro de que su algoritmo "sobreestimará" lo siguiente:
La contraseña es bastante larga, pero es trivialmente descifrable ya que la palabra original aparece en un diccionario básico, y las modificaciones se consideran lo suficientemente comunes como para formar parte de cualquier ataque decente al diccionario. Las conversiones típicas de letras -> números (es decir, 3v3rywh3r3) también deben considerarse bastante débiles, y debe penalizarlas.
En un grado mucho menor, otras contraseñas problemáticas pueden ser las que tienen patrones obvios, como:
Aunque es probable que estos sean menos propensos a ser atacados en ataques de diccionario reales, sufren problemas similares a los de su ejemplo "aaaaa ...".
No estoy seguro de si las frases de contraseña están dirigidas actualmente en la mayoría de los ataques de diccionario, pero sin duda a medida que ganen popularidad, serán atacadas cada vez más. Creo que el famoso ejemplo de xkcd tiene esto en cuenta, ya que solo se asignan 11 bits para cada "palabra común". Su algoritmo también sobreestima este tipo de contraseñas.
Entonces, para resumir, el algoritmo hace un trabajo bastante bueno de la estimación, pero realmente debería tener en cuenta la estructura de la contraseña y los patrones comunes conocidos.
fuente