¿Cómo puedo estimar la entropía de una contraseña?

Question

¿Cómo puedo estimar la entropía de una contraseña?

#1 de akton (8 votos)
#2 de Jesse C. Slicer (4 votos)
#3 de Peter Taylor (1 votos)
#4 de Daniel B (1 votos)

14

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.

algorithms passwords

pregunta Wug 02.10.2012 - 21:47

4 respuestas

Lea otras preguntas en las etiquetas algorithms passwords

Micro-servicios y replicación de datos En general, ¿cómo funcionan los controladores de eventos?

Comentarios Recientes

Esto también fue una mejora. Reescribimos los cálculos para que el hash sea un poco más rápido y para que el código sea compatible con versiones anteriores para sistemas operativos como XP y VISUS. Estos cambios condujeron a una ligera disminución en este resultado. Para volver a convertir a una solución presentada por Bakken et al. simplemente volvimos a superar la ecuación 4 de la pregunta 1 y volvimos a ejecutar la prueba de cifrado. Si bien esta mejora no produce mejores resultados que las pruebas anteriores... Lee mas

score 8 · Answer 1

El

Apéndice A en la p46 de NIST SP 800-63 habla sobre el trabajo de Claude Shannon , que estima la entropía de contraseñas utilizando varios bits. De hecho, este es el documento que utiliza la caricatura XKCD para calcular los bits de entropía. Específicamente:

la entropía del primer carácter se toma como 4 bits;

la entropía de los siguientes 7 caracteres es de 2 bits por carácter; esto es más o menos coherente con la estimación de Shannon de que "cuando la estadística   Los efectos que se extienden sobre no más de 8 letras se consideran   la entropía es de aproximadamente 2.3 bits por carácter; "

para los caracteres del 9 al 20, se considera que la entropía es de 1.5 bits por carácter;

para los caracteres 21 y superiores, la entropía se toma como 1 bit por carácter;

Se asigna una "bonificación" de 6 bits de entropía para una regla de composición que requiere tanto   Mayúsculas y caracteres no alfabéticos. Esta   fuerza el uso de estos personajes, pero en muchos casos los personajes   ocurrirá solo al principio o al final de la contraseña, y   reduce el espacio total de búsqueda, por lo que el beneficio es probablemente   Modesto y casi independiente de la longitud de la contraseña;

Se agrega una bonificación de hasta 6 bits de entropía para una revisión exhaustiva del diccionario. Si el   El atacante conoce el diccionario, puede evitarlo.   probar esas contraseñas, y en cualquier caso, será capaz de adivinar mucho   del diccionario, que será, sin embargo, el más probablemente seleccionado   Contraseñas en ausencia de una regla de diccionario. El supuesto es que   La mayoría de los beneficios de adivinación de adivinación para una prueba de diccionario se acumulan para   contraseñas relativamente cortas, porque cualquier contraseña larga que pueda ser   recordado debe ser necesariamente una "frase de contraseña" compuesta de diccionario   palabras, por lo que la bonificación se reduce a cero en 20 caracteres.

La idea es que un sistema de autenticación seleccione ciertos niveles de entropía como umbrales. Por ejemplo, 10 bits pueden ser débiles, 20 medios y 30 fuertes (números seleccionados arbitrariamente como ejemplo, no como recomendación). Desafortunadamente, el documento no recomienda dichos umbrales, probablemente porque la potencia de cálculo disponible para forzar o adivinar contraseñas aumenta con el tiempo:

Como alternativa a la imposición de un conjunto específico de reglas arbitrarias, un El sistema de autenticación puede calificar las contraseñas de los usuarios, usando las reglas indicado anteriormente, y aceptar cualquiera que cumpla con algún estándar mínimo de entropía. Por ejemplo, supongamos que las contraseñas con al menos 24 bits de entropía fueran necesario. Podemos calcular la estimación de entropía de "IamtheCapitanofthePina4" observando que la cadena tiene 23 Caracteres y satisfaría una regla de composición que requiera mayúsculas. y caracteres no alfabéticos.

Esto puede o no ser lo que está buscando, pero no es un mal punto de referencia, por lo menos.

[Editar: Agregó lo siguiente.]

El documento Métricas de prueba para políticas de creación de contraseñas al atacar 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 preciso de entropía para contraseñas generadas por humanos. Recomendaría consultar "Sección 5 Generación de nuevas políticas de creación de contraseñas" para obtener propuestas más precisas.

score 4 · Answer 2

Consulte el código fuente de KeePass al final de esta página . La clase QualityEstimation implementa un algoritmo bastante bueno que parece estar en línea con lo que estás buscando tener en su lugar. Mis resultados se ven como tales:

aaa                              8
aaaaaaaaa                        9
abcdefghi                       18
H0ley$Mol3y_                    73
s^fU¬5ü;y34G<                   99
[a^36]*                         10
[a^20]A[a^15]*                  18
Tr0ub4dor&3                     66
correct horse battery staple    98

score 1 · Answer 3

1

Usted pregunta

Específicamente, ¿alguien puede pensar en situaciones en las que introducir una contraseña al algoritmo SOBRETIRIGA su fuerza?

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.

respondido por el Peter Taylor 03.10.2012 - 14:53

score 1 · Answer 4

¿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 introducir una contraseña en el algoritmo ANTIGUTIRÁ su fuerza?

Has insinuado algo en el preámbulo (ataques de diccionario, etc.). Esencialmente, hay una serie de prácticas comunes que pueden ser adivinadas por el atacante, lo que reduce considerablemente el espacio de búsqueda. Estoy bastante seguro de que su algoritmo "sobreestimará" lo siguiente:

en todas partes
En todas partes
Everywhere1

La contraseña es bastante larga, pero es fácil de descifrar 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 de diccionario decente. Letra típica - > las conversiones de números (es decir, 3v3rywh3r3) también deben considerarse bastante débiles, y debe penalizarse por éstas.

En mucho menor grado, otras contraseñas de problemas pueden ser las que tienen patrones obvios, como:

abcdefghijklmnop
abcde12345

Aunque es probable que estos sean los objetivos de ataques de diccionario reales, tienen 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 no hay duda de que a medida que ganen popularidad, serán cada vez más específicas. 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 estos tipos de contraseñas.

Entonces, para resumir, el algoritmo hace un trabajo bastante bueno de la estimación, pero en realidad debería tener en cuenta la estructura de la contraseña y los patrones comunes conocidos.