Búsqueda de diccionario

Ataque de diccionario ( ataque de diccionario de inglés ): un ataque al sistema de seguridad que utiliza el método de enumeración completa ( fuerza bruta en inglés ) de las contraseñas previstas utilizadas para la autenticación , que se lleva a cabo mediante la revisión secuencial de todas las palabras ( contraseñas en su forma pura o cifrada ). imágenes) de cierto tipo y longitud del diccionario para posteriormente hackear el sistema y acceder a información clasificada . [1] Este evento, en la mayoría de los casos, es de carácter negativo, contrario a las normas morales y legislativas.

Búsqueda de diccionario y complejidad de la contraseña

Desde el punto de vista de la teoría de la probabilidad , la elección de una contraseña es determinista y lógica. La contraseña puede ser: fecha de nacimiento, nombre, objeto, un conjunto de números, una secuencia de letras estrechamente espaciadas en el teclado. En el caso general, lo anterior se concatena .

El resultado de estas suposiciones es que la predeterminación en la elección de la contraseña juega un papel clave en la elección de los algoritmos en los que se basa el método de búsqueda por diccionario .

Hay dos tipos de ataques:

En línea : Ataques en los que la única forma de que un atacante verifique que una contraseña dada es correcta es interactuando con el servidor.
Fuera de línea : un ataque en el que un atacante puede verificar todas las contraseñas válidas sin necesidad de volver al servidor.

Es posible calcular una puntuación de seguridad de contraseña, en particular, para determinar la proporción de ataques de diccionario exitosos . La puntuación de probabilidad de éxito se puede definir como la relación entre el número de contraseñas descifradas en un ataque de diccionario y el número total de intentos.

Información histórica

El uso de Internet Worm en 1988 proporciona un caso bien documentado de descifrado de contraseñas. [2] El gusano intentó descifrar contraseñas trabajando con una serie de diccionarios. La primera etapa del ataque utilizó un conjunto de palabras que contenían nombres de usuario tomados del archivo de contraseñas del sistema Unix. Si esto no tenía éxito, se utilizó un diccionario interno de 432 palabras de la jerga de Internet de uso común. Si el segundo paso no fue exitoso, se utilizó un diccionario Unix de 24474 palabras. El gusano también buscó una contraseña vacía. Los sitios atacados informaron que alrededor del 50% de las contraseñas se descifraron con éxito utilizando esta estrategia.

El siguiente paso fue obra de Daniel Klein . [3] Para proporcionar sus resultados, recopiló archivos cifrados de contraseñas del sistema Unix . Esta colección contenía aproximadamente 15.000 pares diferentes de nombre de usuario/contraseña ( login/password ) . Klein construyó una serie de diccionarios y un conjunto de mecanismos para permitir las permutaciones. El diccionario que proporcionó constaba de aproximadamente 60.000 elementos. Esta hoja incluía nombres, lugares, referencias ficticias, términos bíblicos, expresiones de los poemas de W. Shakespeare , etc. Luego de aplicar una estrategia de permutación (uso de letras mayúsculas, sustituciones obvias, permutaciones de números), recibió un espacio de contraseña de más de 3.3 millones de posibilidades. El uso de este diccionario ayudó a Klein a descifrar el 24,2% de todas las contraseñas en ciertos servidores.

En 1991-1992. eugenio spafford( ing. Eugene Spafford ) logró construir, basado en estadísticas, un diccionario con el cual el 20% de las contraseñas en servidores seleccionados sucumbieron al cracking. [cuatro]

En el año 2000, un equipo de investigadores de la Universidad de Cambridge realizó un estudio en el que se atacaron 195 contraseñas cifradas , de las cuales el 35 % se descifraron con éxito. [5]

Tabla: Porcentaje de contraseñas encontradas en investigaciones sistemáticas

Investigador(es) / proyecto	Tiempo	Contraseñas verificadas	Porcentaje de hallazgo, [%]
Gusano de Internet [2]	1988	miles	~50
estudio de Klein [3]	1990	15000	24.2
estudio de Spafford[cuatro]	1992	13787	20.0
Investigadores de la Universidad de Cambridge [5]	2000	195	35,0

Principios básicos para construir un diccionario

En la mayoría de las contraseñas, existe una similitud fonética con las palabras del idioma natural (inglés); la razón de esto es la facilidad de recordar este tipo de información sobre una contraseña dada. Esta propiedad se tiene en cuenta en los "filtros de Markov" basados en la cadena de Markov , que es una técnica estándar en el procesamiento del lenguaje natural. La presencia de caracteres no alfabéticos en la contraseña puede interpretarse como la aplicación de una máquina de estado a un conjunto específico de elementos.

Filtros de Markov

Una contraseña alfabética generada por humanos se distribuye de manera desigual en el espacio de las secuencias alfabéticas. Esta condición se puede tener en cuenta con gran precisión en "filtros de Markov" de cero y primer orden: [6]

Modelo de Markov de orden cero : cada símbolo se genera según su propia distribución de probabilidad e independiente de los símbolos anteriores.
Modelo de Markov de primer orden : a cada digrama (par ordenado) de símbolos se le asigna una probabilidad y cada símbolo se genera en dependencia condicional del anterior.

Matemáticamente,

orden cero del modelo de Markov:

P(\alpha )=\prod _{x\in \alpha }\nu (x),

primer orden del modelo de Markov:

P(x_{1}x_{2}\ldots x_{n})=\nu (x_{1})\prod_{i=1}^{n-1}\nu (x_{i+ 1 }\mid x_{i}),

donde es la probabilidad de distribución de una secuencia de caracteres, es el carácter de esta secuencia, es la frecuencia de un carácter o digrama individual en el texto. $P(\cdot)$ $x_{yo}$ $\nu$

Para eliminar cadenas improbables en el diccionario, se utiliza la discretización de probabilidad: se introduce un sistema de dos niveles con un umbral : $\ theta$

orden cero del modelo de Markov:

D_{\nu ,\theta }=\{\alpha :\prod _{x\in \alpha }\nu (x)\geq \theta \},

primer orden del modelo de Markov:

D_{\nu ,\theta }=\{x_{1}x_{2}\ldots x_{n}:\nu (x_{1})\prod _{i=1}^{n-1 }\nu (x_{i+1}\mid x_{i})\geq \theta\}.

Observaciones

el modelo de Markov de primer orden muestra mejores resultados (da un mayor porcentaje de pirateo) en relación con el modelo de Markov de orden cero . La excepción es cuando la estrategia de contraseña usa abreviaturas que consisten en las primeras letras de cada palabra en una oración abstracta;
la distribución de frecuencia de las letras en la contraseña depende del idioma específico para el que se compila el diccionario (una generalización de este método es la combinación de supuestos idiomas para crear una contraseña).

Filtros usando máquinas de estado

Para crear máquinas de estado , se introducen algunas restricciones y suposiciones en relación con la contraseña descifrada:

en una contraseña alfanumérica, todos los números van al final;
es más probable que la primera letra de una contraseña alfabética esté en mayúscula que las demás;
en una contraseña alfabética, el número de letras minúsculas es mayor que el número de mayúsculas.

Los autómatas finitos deterministas son medios ideales para expresiones con las restricciones propuestas. [6]

El primer paso para construir un diccionario basado en autómatas finitos es crear una secuencia de expresiones regulares ( \" minúsculas" , \"mayúsculas antes de minúsculas" , \"todas las mayúsculas van antes de minúsculas" , etc.).

Un diccionario se define como un conjunto de palabras que coinciden con los filtros de Markov y se les aplica un número finito de expresiones regulares .

D_{\nu ,\theta ,\left\langle M_{i}\right\rangle }=\{\alpha :\prod _{x\in \alpha }\nu (x)\geq \theta , \,\existe i:M_{i}\ni \alpha \}.

Algoritmos

Diccionario modificado del modelo de Markov de orden cero

El algoritmo utilizado para crear el diccionario es ligeramente diferente del filtro de Markov de nivel cero (en este caso, se utilizará un umbral diferente para diferentes longitudes de palabra en el diccionario ). [6] $\ theta$

El diccionario modificado se define como

D_{\nu ,\theta ,l}=\{\alpha :|\alpha |=l,\prod _{x\in \alpha }\nu (x)\geq \theta \}.

Reescribir el filtro (diccionario) en forma aditiva

D_{\nu ,\theta ,l}=\{\alpha :|\alpha |=l,\sum _{x\in \alpha }\mu (x)\geq \lambda \},

donde _ $\mu (x)=\log \nu (x),\,\lambda =\log \theta$

deja _ Luego definimos diccionarios parciales . Tenga en cuenta que se define porque , por lo tanto, no depende de la elección de . ${\displaystyle \{\alpha :|\alpha |=l',\prod _{x\in \alpha }\nu (x)=\theta '\))$ ${\displaystyle D_{\nu ,\theta ,l,\theta ',l'}=\{\beta :\alpha \beta \in D_{\nu ,\theta ,l))\))$ ${\displaystyle D_{\nu ,\theta ,l,\theta ',l'))$ $\prod_{x\in \alpha \beta}\nu (x)=\prod_{x\in \alpha}\nu (x)\prod_{x\in \beta}\nu (x )=\theta '\prod _{x\in \beta }\nu (x)$ $\alfa$

Para cualquier prefijo , el diccionario parcial contiene todas las secuencias posibles de caracteres que se pueden adjuntar a ese prefijo , por lo que la cadena resultante satisface todas las propiedades de Markov.

En general, un diccionario parcial se puede escribir

\mid D_{\nu ,\,umbral,\,longitud\,total,\,nivel,\,longitud\,actual}\mid

Algoritmo recursivo para calcular el tamaño de un diccionario parcial [6]

tamaño_parcial1 ( longitud_actual , nivel ) { si nivel >= umbral : devuelve 0 si longitud_total = longitud_actual : devuelve 1 suma = 0 para cada carácter en el alfabeto suma = suma + tamaño_parcial1 ( longitud_actual + 1 , nivel + mu ( carácter ) ) devuelve suma }

Algoritmo recursivo para encontrar una clave de un diccionario (toma un índice en el espacio de claves como entrada y devuelve la clave correspondiente ) [6]

get_key1 ( longitud_actual , índice , nivel ) { si longitud_total = longitud_actual : devuelve "" sum = 0 para cada carácter en el alfabeto new_level = nivel + mu ( char ) // buscado desde el tamaño de matriz precalculado = tamaño_parcial1 [ longitud_actual + 1 ] [ nuevo_nivel ] if suma + tamaño > índice // '|' se refiere a la concatenación de cadenas return char | get_key1 ( longitud_actual + 1 , índice - suma , nuevo_nivel ) suma = suma + tamaño // el control no puede llegar aquí imprime "índice más grande que el tamaño del espacio de teclas" ; salir }

Observaciones

parcial_tamaño1 se evalúa solo una vez (no una vez por clave );
get_key1 se calcula durante el criptoanálisis ;
para ver todo el espacio de claves , debe ejecutar get_key1 con current_length = 0 y level = 0 .

Vocabulario del modelo de Markov de primer orden

Al igual que con el método de orden cero, se definen diccionarios parciales .

Después de buscar una cadena en un diccionario parcial , debe preocuparse por el último carácter (teniendo en cuenta el digrama y su distribución)

tamaño_parcial2 ( longitud_actual , carácter_anterior , nivel ) { si nivel >= umbral : devuelve 0 si longitud_total = longitud_actual : devuelve 1 suma = 0 para cada carácter en el alfabeto si longitud_actual = 0 nivel_nuevo = mu ( caracter ) else nivel_nuevo = nivel + mu ( caracter_anterior , char ) suma = suma + tamaño_parcial2 ( longitud_actual + 1 , char , nuevo_nivel ) } get_key2 ( longitud_actual , índice , carácter_anterior , nivel ) { if longitud_total = longitud_actual : devuelve "" sum = 0 para char en el alfabeto if current_length = 0 new_level = mu ( char ) else nuevo_nivel = nivel + mu ( prev_char , char ) tamaño = tamaño_parcial2 ( longitud_actual + 1 , char , nuevo_nivel ) if sum + size > index return char | get_key2 ( longitud_actual + 1 , índice - suma , carácter , nuevo_nivel ) suma = suma + tamaño // el control no puede llegar aquí imprime "índice más grande que el tamaño del espacio de teclas" ; salir }

Comentario

el uso de algoritmos híbridos da mejores resultados para el criptoanálisis por búsqueda de diccionario . [6]

Contraataques básicos a los ataques de diccionario

Cómo contrarrestar los ataques de diccionarios en línea

Hay varias formas de contrarrestar los ataques de diccionarios en línea :

respuesta retardada : para el par de inicio de sesión/contraseña proporcionado , el servidor utiliza un pequeño retardo de respuesta Sí/no generado especialmente (por ejemplo, no más de una respuesta por segundo;
bloqueo de cuenta : una cuenta se bloquea después de varios (un número predeterminado) intentos fallidos de inicio de sesión/contraseña ( por ejemplo, una cuenta se bloquea durante una hora después de cinco intentos de contraseña incorrectos);
utilizando Prueba de trabajo ;
uso de funciones salt y hash lento en el lado del cliente.

Observaciones

estas medidas, en la mayoría de los casos, evitan un ataque de diccionario y el descifrado de la contraseña que lo acompaña en un tiempo razonable;
Los datos de la implementación de contrarrestar los ataques de diccionarios en línea permiten el bloqueo a largo plazo de las cuentas de usuario con la selección correcta del período de ataque.

Protocolos de autenticación de usuario

Se supone que el usuario de esta cuenta ingresa la combinación correcta de inicio de sesión/contraseña , mientras que el ataque de diccionario lo realiza un programa automático. Se requiere que un intento de ingresar la contraseña correcta sea "computacionalmente simple" para humanos y "computacionalmente difícil" para máquinas.

El protocolo es una prueba que permite al servidor distinguir a un humano de un bot . Fue propuesto por primera vez por M. Naor ( ing. Moni Naor ) y se llama prueba de Turing inverso ( ing. Reverse Turing test (RTT) ), otro nombre para esto es CAPTCHA . El Ensayo de Turing Inverso debe cumplir las siguientes condiciones: [7]

generación automática;
facilidad de implementación para una persona;
complejidad para las máquinas;
baja probabilidad de adivinar la respuesta.

La prueba de imagen cumple todas las condiciones anteriores.

Protocolo 1 (combinación de la prueba inversa de Turing con cualquier sistema de autenticación) [8]

Se le pide al usuario que responda a un mensaje RTT antes de que comience la autenticación (antes de ingresar el nombre de usuario/contraseña ).

Comentario

Este método no es óptimo para sistemas grandes, ya que es bastante irritante y psicológicamente difícil para el usuario ingresar la respuesta a la prueba RTT cada vez antes de la autenticación . [ocho]

Protocolo 2 (protocolo de inicio de sesión del usuario, versión modificada del protocolo 1) [8]

Si el usuario inicia sesión correctamente, el servidor envía una cookie a la computadora del usuario que contiene un registro de la autenticación del usuario y el período de validez de este mensaje (suponiendo que la imposibilidad de cambiar la información en la cookie sin notificar al servidor (esto se puede garantizar agregando un MAC ( mensaje de código de autenticación ), que se calcula usando una clave conocida solo por el servidor).

1. el usuario ingresa el nombre de usuario/contraseña . Si su computadora contiene cookies proporcionadas por este servidor, el servidor recupera la cookie ; 2. autenticación de inicio de sesión/contraseña ; 3. si el nombre de usuario/la contraseña son verdaderos, entonces una. si la cookie se encuentra en un estado válido (verificado por la fecha en que fue modificada por el servidor) y el registro que identifica al usuario (y almacenado en la cookie ) coincide con el inicio de sesión ingresado , entonces se otorga acceso al servidor al usuario; b. de lo contrario, el servidor genera una prueba RTT y la envía al usuario. El usuario obtiene acceso al servidor solo después de una respuesta correcta a la solicitud de RTT ; 4. si el par de inicio de sesión/contraseña es incorrecto, entonces una. con una probabilidad (donde este es un parámetro del sistema, por ejemplo ), se le ofrece al usuario pasar una prueba RTT e independientemente de la respuesta, se bloquea el acceso al servidor;

pags

{\ estilo de visualización 0 \ leq p \ leq 1}

{\ estilo de visualización p = 0,05}

b. con probabilidad , la conexión se bloquea inmediatamente.

1 p

Observaciones

se supone que el usuario utiliza un pequeño número de ordenadores y es poco probable que el ataque se lleve a cabo desde uno de ellos;
el proceso de inicio de sesión utiliza un navegador web y se requieren cookies ;
El algoritmo del protocolo está construido de tal manera que el proceso de generar un mensaje RTT ocurre solo en dos casos: cuando la entrada de la cookie en la computadora del usuario no es válida y cuando el par de inicio de sesión/contraseña es incorrecto. Esto le permite descargar servidores usando este protocolo;
la probabilidad es una función del par usuario/contraseña . Hay casos en los que, para valores fijos de inicio de sesión/contraseña , solo se producirán bloqueos de cuenta o solo se generarán mensajes RTT en caso de errores múltiples. $pags$

Contrarrestar ataques de diccionario fuera de línea

Los ataques de diccionario sin conexión se pueden prevenir o dificultar de las siguientes maneras:

agregando un valor conocido a hashing - salt ( sal inglesa )
usando una función hash lenta, por ejemplo. cripta

Implementación de hardware

Trusted Platform Module (TPM) es un chip de hardware que permite a las computadoras mantener los datos seguros. La posesión de información secreta (en adelante, authData ) es necesaria para acceder y utilizar las claves TPM .

Durante el ataque, el criptoanalista puede aprender: [9]

inicie sesión para authData y la respuesta de TPM a esta solicitud;
secreto compartido( eng. secreto compartido ) asociado con authData y la respuesta TPM .

La compilación de diccionarios basada en la información recibida se usa en un ataque de diccionario fuera de línea para determinar authData .

Métodos de lucha: utilizando un método criptográfico SPEKE modificado( Intercambio de clave exponencial de contraseña simple ), que se basa en el algoritmo de intercambio de clave Diffie-Hellman (permite que dos partes creen un secreto compartido $s$ ( ing. secreto compartido fuerte ), basado en un secreto compartido débil $w$ ( ing. secreto débil ), que comparten).

Protocolo (método criptográfico modificado SPEKE)

1. el usuario ejecuta el comando requerido para la autorización con authData ; 2. El proceso de usuario y TPM están incluidos en el protocolo SPEKE $d$
, usando como un secreto compartido débil $d$ $w$ ;
3. El proceso de usuario selecciona uno aleatorio y lo envía a TPM , donde está la función hash ; 4. TPM elige uno al azar y lo envía al proceso de usuario; 5. cada uno de ellos calcula un secreto ; 6. se reemplaza por como clave HMAC . $X$ ${\ Displaystyle H (d) ^ {x}}$ $H$
$y$ ${\displaystyle H(d)^{y))$
${\displaystyle s=H(d)^{xy))$
$w$ $s$

Observaciones

las restricciones a la elección se describen en el algoritmo de intercambio de claves Diffie-Hellman ; ${\ estilo de visualización d, w, h, x, y}$
la elección de la función hash está determinada por el método de cifrado en el criptoprocesador ( chip TPM ). $H$
el protocolo está sujeto a mejoras. [9]

Véase también

Notas

↑ Shirey R. Solicitud de comentarios : 4949 . — Agosto de 2007.
↑ 1 2 Eugene Spafford. El gusano de Internet: crisis y secuelas (inglés) . - Comunicaciones de la ACM, junio de 1989. - Pág. 678-687 .
↑ 1 2 Daniel V. Klein. Una encuesta y mejoras a la seguridad de contraseñas // Asociación USENIX. — 1990.
↑ 1 2 Eugene Spafford. Observación de opciones de contraseñas reutilizables // Asociación USENIX. - 31 de julio de 1992. Archivado desde el original el 20 de julio de 2011.
↑ 1 2 Yan Jianxin, Blackwell Alan, Anderson Ross, Gran Alasdair. La memorabilidad y la seguridad de las contraseñas: algunos resultados empíricos / Markus Kuhn. — Septiembre de 2000.
↑ 1 2 3 4 5 6 Narayanan Arvind, Shmatikov Vitaly. Ataques rápidos de diccionario a las contraseñas mediante el intercambio espacio -tiempo . — 7 al 11 de noviembre de 2005.
↑ Naor Moni. Verificación de un humano en el circuito o Identificación a través de la Prueba de Turing . — 13 de septiembre de 1996.
↑ 1 2 3 Pinkas Benny, Sander Tomas. Protección de contraseñas contra ataques de diccionario .
↑ 1 2 Chen Liqun, Ryan Mark. Ataque de diccionario de Ofine en datos de autorización débiles de TCG TPM y solución (inglés) .

Enlaces

RFC 2828 - Glosario de seguridad en Internet
RFC 4949 - Glosario de seguridad en Internet, versión 2
El dilema de la contraseña segura . Consultado el 13 de noviembre de 2011. Archivado desde el original el 27 de febrero de 2012.
Diccionarios (inglés) . Consultado el 13 de noviembre de 2011. Archivado desde el original el 27 de febrero de 2012.
CAPTCHA (inglés) (enlace no disponible) . Consultado el 13 de noviembre de 2011. Archivado desde el original el 27 de febrero de 2012.
Philippe Oechslin. Cómo hacer un intercambio criptoanalítico de memoria de tiempo más rápido (inglés) . Consultado el 13 de noviembre de 2011. Archivado desde el original el 27 de febrero de 2012.
John the Ripper cracker de contraseñas (inglés) (enlace descendente) . Consultado el 13 de noviembre de 2011. Archivado desde el original el 27 de febrero de 2012.