Confundido acerca de la entropía (contraseña)

Navega tus respuestas
38

Parece que hay muchos "tipos" diferentes de entropía. Me he encontrado con dos conceptos diferentes:

A) El ejemplo XKCD de correcthorsebatterystaple . Tiene 44 bits de entropía porque cuatro palabras elegidas al azar de una lista de 2048 palabras es 4 * log2 (2048) = 44 bits de entropía. Esto lo entiendo.

B) La entropía de Shannon de la cadena real, es decir, la entropía se calcula en función de las frecuencias de las letras / símbolos. Aplicando la fórmula de Shannon en correcthorsebatterystaple , el resultado es 3.36 bits de entropía por carácter. 

# from http://stackoverflow.com/a/2979208
import math
def entropy(string):
        "Calculates the Shannon entropy of a string"

        # get probability of chars in string
        prob = [ float(string.count(c)) / len(string) for c in dict.fromkeys(list(string)) ]

        # calculate the entropy
        entropy = - sum([ p * math.log(p) / math.log(2.0) for p in prob ])

        return entropy

print entropy('correcthorsebatterystaple')
# => 3.36385618977

Wikipedia solo aumenta mi confusión:

  

Es importante darse cuenta de la diferencia entre la entropía de un conjunto de resultados posibles y la entropía de un resultado particular. Un solo lanzamiento de una moneda justa tiene una entropía de un bit, pero un resultado particular (por ejemplo, "cara") tiene cero entropía, ya que es completamente "predecible".   - Wikipedia: Entropy (teoría de la información)

No entiendo muy bien la distinción entre la entropía del lanzamiento (generación) y la entropía del resultado (la cadena).

  1. ¿Cuándo se usa B y con qué propósito?
  2. ¿Qué concepto refleja con precisión la entropía de la contraseña?
  3. ¿Hay terminología para diferenciar entre los dos?
  4. La verdadera aleatoriedad podría darnos correctcorrectcorrectcorrect . Utilizando A todavía tenemos 44 bits. Usando B la entropía sería lo mismo que la de correct . ¿Cuándo es importante la diferencia entre los dos?
  5. Si un requisito especifica que una cadena debe tener 20 bits de entropía: ¿uso A o B para determinar la entropía?
pregunta mds 05.10.2012 - 06:56
fuente

5 respuestas

20

El artículo de Wikipedia explica la entropía matemática, que no es idéntica a lo que la gente quiere decir cuando habla de entropía de contraseña. La entropía de la contraseña es más acerca de lo difícil que es adivinar una contraseña bajo ciertas suposiciones que es diferente del concepto matemático de la entropía.

A y B no son conceptos diferentes de la entropía de las contraseñas, solo están utilizando diferentes supuestos como la forma en que se construye una contraseña.

A trata a correcthorsebatterystaple como una cadena de palabras en inglés y supone que las palabras se seleccionan al azar de una colección de 2048 palabras. Según estos supuestos, cada palabra proporciona exactamente 11 bits de entropía y 44 bits de entropía para correcthorsebatterystaple .

B trata a correcthorsebatterystaple como una cadena de caracteres y asume que la probabilidad de que aparezca cualquier carácter es la misma que en el idioma inglés. Según estos supuestos, correcthorsebatterystaple tiene 84 bits de entropía.

Por lo tanto, la definición que use realmente depende de las suposiciones que haga sobre la contraseña. Si asume que la contraseña es una contraseña de estilo XKCD (y que cada palabra tiene una posibilidad de que una en 2048 aparezca en la contraseña), entonces A es la forma correcta de calcular la entropía. Si no asume que la contraseña se construye como una colección de palabras, pero asuma que la probabilidad de que cualquier carácter parezca ser igual a la probabilidad de que aparezca en el idioma inglés, entonces B es la forma correcta de calcular la entropía.

En el mundo real, ninguna de estas suposiciones es correcta. Entonces, si tiene un "requisito que especifica que una cadena necesita tener 20 bits de entropía" y esto es para las contraseñas generadas por el usuario, es muy difícil dar una definición precisa de la entropía. Para obtener más información sobre esto, consulte ¿Cómo calcular la entropía de la contraseña? .

Si, por otro lado, puede usar cadenas generadas por computadora (y está usando un buen PRNG), entonces cada carácter alfanumérico (a-z, A-Z, 0-9) dará casi 6 bits de entropía.

    
respondido por el David Wachtfogel 05.10.2012 - 08:23
fuente
16

Qué significa

La entropía de

lanzamiento de moneda asume que de un lanzamiento a otro, el resultado del lanzamiento anterior no afectará el resultado del siguiente lanzamiento. Por lo tanto, cada lanzamiento agrega un poco de entropía.

La entropía de

Shannon supone que el valor de la siguiente letra está de hecho, parcialmente determinado por el valor de la letra anterior (y quizás otras). Los hechos como "h" a menudo siguen a "t" y "e" a menudo siguen a "h" se toman en consideración para que a los patrones comunes se les asigne un valor de entropía más bajo. Entonces, con un diccionario en inglés, la cadena the tendría un valor de entropía de Shannon mucho más bajo que la cadena exu .

Lo que significa you

La implicación directa de esto con respecto a las contraseñas es bastante insignificante. La pregunta real (y única) importante con respecto a las contraseñas es la siguiente:

  

¿En qué diccionario está tu contraseña?

Es decir, si tuviera que construir una lista de contraseñas potenciales para realizar un ataque de fuerza bruta, ¿qué tan grande tendría que ser el diccionario para contener su contraseña?

Por ejemplo:

  • Su contraseña se encuentra entre las 500 contraseñas más utilizadas más comúnmente
  • Su contraseña está en el diccionario de palabras en inglés en minúsculas
  • Su contraseña está en la lista de palabras en inglés en minúsculas o en mayúsculas y minúsculas con un sufijo de uno o dos dígitos
  • Su contraseña está en la lista de palabras en inglés de casos aleatorios con sustituciones numéricas de haxor (es decir, A = > 4, L = > 1, S = > 5)
  • Su contraseña está en la lista de todas las cadenas de 8 caracteres o menos usando números y letras mayúsculas y minúsculas.

Todo lo anterior son ejemplos de diccionarios de uso frecuente de descifrado de contraseñas en el mundo real.

En otras palabras

El propósito de la complejidad de la contraseña es enfrentarse a un ataque de fuerza bruta. El tamaño del diccionario disponible más pequeño que contiene su contraseña determina la cantidad de tiempo requerido para descifrar su contraseña. Podemos adivinar qué diccionarios estarán disponibles para el atacante, pero no podemos saberlo con certeza. Por lo tanto, como proxy del tamaño del diccionario, en su lugar usamos entropía . Es un sustituto deficiente porque no refleja la mecánica de ataque real, pero es potencialmente mejor que nada.

Las comparaciones de contraseñas basadas en cálculos de entropía pueden ser potencialmente fructíferas, pero debe tener cuidado de evitar atribuir demasiado valor a un número que, al final, solo se relaciona de manera indirecta con el rendimiento de la contraseña.

    
respondido por el tylerl 05.10.2012 - 09:38
fuente
6

Supongo que la forma más sencilla de ilustrarlo es con un ejemplo.

Digamos que tenemos un generador de números aleatorios que tiene una entropía de salida demostrable de 3 bits por dígito de salida. La entropía de "lanzamiento" de ese generador es de 3 bits. Ahora, digamos que ejecutas eso para 20 dígitos, y a pesar de la probabilidad ridículamente pequeña, cada número en el flujo sale como 6. La entropía de "tirar" sigue siendo de 3 bits por dígito, por lo tanto de 60 bits. El verdadero "resultado" de la entropía de la contraseña es minúsculo, se podría argumentar que es tan bajo como 3 o 4 bits.

La diferencia es que la entropía de "lanzamiento" representa la entropía esperada de la salida, basada en el modelado probabilístico del generador, mientras que la entropía de "resultado" representa la entropía de información real de los datos que produjo en un caso real. / p>     

respondido por el Polynomial 05.10.2012 - 09:38
fuente
3

Un solo byte puede contener hasta 8 bits de entropía. Este es el límite superior. A medida que aprende más sobre tus datos, la cantidad de entropía en esos bloques de 8 bytes disminuye. Oh, todos tus bytes son todos los caracteres ASCII? Eso significa que el bit más alto debe ser un 0; Usted está a 7 bits de entropía. No hay personajes de control? Del conjunto ASCII, 0-31 son caracteres de control: tabulador, intro, campana, final de archivo. Eso reduce aún más el carácter. Alfabético, solo minúsculas? Ahora estás reduciendo enormemente las opciones disponibles. ¿Palabra inglesa? No muchos de ellos: una palabra inglesa completa, seleccionada ALEATORIAMENTE, solo puede tener alrededor de 12 bits, por ejemplo, aunque las palabras tengan 5 caracteres.

Las contraseñas elegidas por los humanos son aún peores; no porque las posibilidades sean menores, sino porque algunas son elegidas con más frecuencia que otras. Si ciertas contraseñas son comunes, es más fácil de adivinar; Eso efectúa la entropía. Si el 10% de sus usuarios tienen una "contraseña", se reducirá la entropía en su lista de contraseñas, es decir, es más fácil de adivinar.

Entonces, cuanto más información tenga sobre una contraseña, menor será la posibilidad de calcular la entropía. En el caso de la fórmula de Shannon, asume los sesgos en los lenguajes naturales y calcula la entropía en 3.6 bits * 25 caracteres = aproximadamente 90 bits. Cuando obtiene la información adicional (4 palabras, cada una de una lista de 2048), se reduce a 44 bits.

Míralo de esta manera: si alguien estuviera pirateando esta contraseña, sabiendo solo que era un lenguaje natural, y luego de repente descubriera que eran 4 palabras de una lista de 2048 (y que conocía la lista), de repente encontrarían su trabajo es mucho más fácil.

    
respondido por el AMADANON Inc. 05.03.2014 - 22:56
fuente
0

Lo que te falta aquí es el hecho de que una medición de entropía está vinculada a alguna distribución de probabilidad específica . No puede hablar sobre la entropía de una contraseña sin hacer una suposición, explícita o implícita, acerca de qué distribución de probabilidad es la contraseña extraída aleatoriamente de . Lo que se basa en la naturaleza del proceso mediante el cual se genera la contraseña.

En el cómic XKCD, Munroe le está diciendo que generó la frase de contraseña al seleccionar sucesivamente e independientemente cuatro palabras al azar de un diccionario de aproximadamente 2 ^ 11 palabras. Esto le indica con precisión la distribución de probabilidad de la que se extrae la contraseña: la distribución uniforme discreta en un conjunto de 2 ^ 44 frases de contraseña distintas.

Pero entonces cuando haces esto:

  

B) La entropía de Shannon de la cadena real, es decir, la entropía se calcula en función de las frecuencias de las letras / símbolos. Aplicando la fórmula de Shannon en correcthorsebatterystaple , el resultado es 3.36 bits de entropía por carácter.

... estás eligiendo una distribución de probabilidad diferente a la que usó Munroe, por lo que obtendrás una estimación diferente, una que asigna aproximadamente 84 bits de entropía a la cadena (25 × 3.36).

Si está evaluando la entropía de las contraseñas para las que no sabe cómo se generaron, una perspectiva fructífera e intuitiva es adoptar la idea de que la distribución de probabilidad en juego es el conocimiento e hipótesis de los atacantes sobre cómo los usuarios seleccionar contraseñas Si puede formarse una idea razonable de cómo se ve esta distribución, entonces la entropía de una contraseña es la longitud del mensaje en un código óptimo para esa distribución. Esto es, muy aproximado, el enfoque en los mejores medidores de fortaleza de contraseña como zxcvbn (aunque lo formulan en términos de número promedio de adivina para golpear la contraseña).

Cuando observa las estimaciones de 44 vs. 84 bits que muestra en su pregunta desde esta perspectiva, lo que sucede es lo siguiente: Munroe obtiene una estimación de entropía mucho más baja para la contraseña porque asume que el atacante tiene una Hipótesis precisa al 100% sobre cómo se generó la frase de contraseña, para que puedan descartar un gran número de cadenas a priori que no son concatenaciones de cuatro palabras en el diccionario. Mientras que el cálculo de entropía de Shannon que usted ilustra, obtiene una estimación de entropía mucho más alta porque no es tan "inteligente" de una estrategia para adivinar frases de contraseña de estilo XKCD. Sin embargo, zxcvbn es más inteligente y estima que un cracker de contraseñas crackearía correcthorsebatterystaple en aproximadamente 10 ^ 14.43696 conjeturas que son aproximadamente (14.4 × 3.3) + 1 ≈ 48.6 bits de entropía. (El cálculo es una conversión de logaritmo de base 10 a base 2, más un bit para convertir del número de conjeturas a entropía). Eso es un poco más que la estimación de Munroe, pero zxcvbn está codificado para atacar otras contraseñas que solo frases de estilo XCKD .

    
respondido por el Luis Casillas 30.01.2018 - 00:30
fuente

Lea otras preguntas en las etiquetas

¿Es seguro cargar y escanear archivos personales en VirusTotal? ¿Por qué la autenticación HTTP básica codifica el nombre de usuario y la contraseña con base64?