Después de leer varios recursos sobre la fortaleza de la contraseña, estoy tratando de crear un algoritmo que proporcione una estimación aproximada de cuánta entropía a la contraseña tiene.
Estoy intentando crear un algoritmo lo más completo posible. En este punto solo tengo pseudocódigo, pero el algoritmo cubre lo siguiente:
- longitud de la contraseña
- caracteres repetidos
- patrones (lógicos)
- espacios de caracteres diferentes (LC, UC, Numeric, Special, Extended)
- ataques de diccionario
NO cubre lo siguiente, y DEBE cubrirse BIEN (aunque no perfectamente):
- orden (las contraseñas se pueden ordenar estrictamente por la salida de este algoritmo)
- patrones (espaciales)
¿Alguien puede proporcionar alguna información sobre lo que este algoritmo podría ser débil? Específicamente, ¿puede alguien pensar en situaciones en las que la introducción de una contraseña al algoritmo ANTES EVALUAR su fuerza? Las subestimaciones son un problema menor.
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 de 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 muestra la diferencia en entropy_bits para las contraseñas 6 y 7, que consisten en 36 a, pero la segunda 21a se capitaliza. 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ñas débil (y cualquiera que vea cómo la escribes la 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?
Addendum 1
Los ataques de diccionario y los ataques basados en patrones parecen ser lo más importante, así que intentaré solucionarlos.
Podría realizar una búsqueda exhaustiva a través de la contraseña para las palabras de una lista de palabras y reemplazar las palabras con tokens únicos a las palabras que representan. Los tokens de palabras serían tratados como caracteres y tendrían su propio sistema de peso, y agregarían sus propios pesos a la contraseña. Necesitaría algunos parámetros nuevos 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 pesos.
Esta búsqueda de palabras podría modificarse especialmente para que coincida con las letras mayúsculas y minúsculas, así como con las sustituciones de caracteres comunes, como la de E con 3. Si no agrego peso extra a esas palabras coincidentes, el algoritmo subestimaría su fuerza. por un poco o dos por palabra, lo que está bien. De lo contrario, una regla general sería que, para cada coincidencia de caracteres no perfecta, asigne un bit de bonificación a la palabra.
Luego podría realizar verificaciones 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 token de patrón, exclusivo del patrón y la longitud. Los parámetros algorítmicos (específicamente, la entropía por patrón) podrían generarse sobre la marcha basándose en el patrón.
En este punto, tomaría la longitud de la contraseña. Cada token de palabra y token de patrón contarán como un carácter; cada token reemplazaría los caracteres que representaban simbólicamente.
Inventé 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 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 en algo como:
entropy(b) * l * (o + 1) // o will be either zero or one
El algoritmo modificado encontraría fallas y reduciría la fortaleza de cada contraseña en la tabla original, con la excepción de s^fU¬5ü;y34G<
, que no contiene palabras ni patrones.