Algoritmos HASH (II): Atacando MD5 y SHA-1

Este artículo es una colaboración enviada por LordHASH

Algunos de los algoritmos de HASH más utilizados, que son sobre los que trabajaremos, son los siguientes:

  • MD5 (Message-Digest Algorithm 5 o Algoritmo de Firma de Mensajes 5): Desarrollado por Ron Rivest, ha sido hasta los últimos años el algoritmo hash más usado. Procesa mensajes de una longitud arbitraria en bloques de 512 bits generando un compendio de 128 bits. Debido a la capacidad de procesamiento actual esos 128 bits son insuficientes, además de que una serie de ataques criptoanalíticos han puesto de manifiesto algunas vulnerabilidades del algoritmo. Puede ser útil para comprobar la integridad de un fichero tras una descarga, por ejemplo, pero ya no es aceptable desde el punto de vista del criptoanálisis.
  • SHA-1 (Secure Hash Algorithm 1 o Algorimo de Hash Seguro 1): El SHA-1 toma como entrada un mensaje de longitud máxima 264 bits (más de dos mil millones de Gigabytes) y produce como salida un resumen de 160 bits. Este número es mayor que el que se utilizaba en el algoritmo SHA original, 128 bits. Ya existen nuevas versiones de SHA que trabajan con resúmenes de 224,256,384 e incluso 512 bits.

En realidad, lo seguros o inseguros que estos algoritmos sean no depende de los conocimientos informáticos o telemáticos que uno tenga, sino de sus conocimientos matemáticos. Nuestra intención es demostrar por dónde cojean los algoritmos de HASH, la dificultad computacional que presentan, y qué soluciones se dan a los posibles ataques que puedan sufrir por parte de individuos malintencionados.

Desde el año 2004 aproximadamente, cuando saltaron las primeras noticias escandalosas sobre la ruptura de MD5, la seguridad que ofrecen los algoritmos de HASH a nuestros esquemas de cifrado ha sido una cuestión que se ha puesto en entredicho. ¿Qué seguridad ofrecen estos algoritmos? ¿Resulta computacionalmente complejo romper uno de estos algoritmos? ¿Qué solución se debe adoptar? Intentaremos resolver estas cuestiones.

Intentemos dar una descripción algo más matemática de lo que es una función HASH. Supongamos que tenemos un mensaje a, al que aplicamos una función resumen a la que llamaremos h. Decimos entonces que el resultado de esta operación, al que llamaremos b es el HASH de a. Es decir:

h(a)=b

Esta función debe ser sencilla de realizar para un computador, pero debe ser computacionalmente imposible realizar la operación inversa, al menos para usuarios normales.

Además, esta función tiene otra característica: el tamaño de la entrada no es de longitud fija, puede ser de longitud variable. Esto tiene la siguiente consecuencia, que no demostraremos matemáticamente, pero que asumiremos por estar razonado en otros artículos publicados en Internet (al final se indican): es posible que dos mensajes de entrada a produzcan el mismo mensaje de salida b. Es decir, es posible encontrar un mensaje c, tal que:

h(c)=b

Sin embargo, encontrar ese mensaje debe ser, al igual que la particularidad antes mencionada, muy complejo desde el punto de vista computacional. Para los algoritmos de HASH esto es lo que se conoce como colisión: que dos mensajes de entrada produzcan el mismo mensaje de salida.

Así, a priori, podemos establecer dos posibles vulnerabilidades de las funciones HASH:

  • Que sea posible realizar la operación:

    h-1(b)=a

    Habitualmente, a la operación de invertir la función HASH comprobando todas las posibilidades para los bits de salida se le llama ataque de fuerza bruta. Esto es lo que debe ser computacionalmente impracticable. Supondría aplicar la función HASH 2n veces hasta encontrar la coincidencia (n es el número de bits de salida de la función).

  • Que se hallen colisiones:

    h(a)=b y h(c)=b, a distinto de c

    Lo que antes hemos denominado colisión.

Estas dos posibles debilidades dan lugar a cuatro tipos de ataques:

  • Ataque Tipo 1: El atacante es capaz de encontrar dos mensajes al azar que colisionan pero es incapaz de hacerlo de forma sistemática. Si es capaz de dar sólo con dos mensajes que provocan colisión, esta no es razón suficiente para tildar el algoritmo de ineficiente. Índice de peligrosidad: *
  • Ataque Tipo 2: El atacante es capaz de generar dos mensajes distintos de forma que sus HASH colisionen, pero sin saber a priori qué hash resultará. Es decir, el atacante no podría generar “queriendo” el HASH que necesite para fines maliciosos. Índice de peligrosidad: **
  • Ataque Tipo 3: El atacante es capaz de construir un mensaje sin sentido de forma que su HASH colisione con el de un mensaje con sentido. Si éste es el caso, el agente malicioso puede atacar algoritmos de encriptación asimétricos con firma digital, haciendo que se firmen mensajes sin sentido, y que el destinatario los acepte como fidedignos. Índice de peligrosidad: ***
  • Ataque Tipo 4: El atacante es capaz de crear un segundo mensaje falso que tiene sentido y cuyo hash colisiona con el del mensaje verdadero. En este caso, el atacante puede actuar con total impunidad, puede falsificar certificados, firmar mensajes…El resultado sería desastroso. Índice de peligrosidad: ****.

El problema entonces es el siguiente: ¿cómo de difícil es encontrar una solución? ¿Qué ataques reales son practicables? ¿Qué se gana incrementando el número de bits de salida del algoritmo?

En primer lugar, responderemos a la última pregunta. Si aumentamos el número de bits de salida del algoritmo, el ataque de fuerza bruta será más impracticable y también lo será encontrar los mensajes que colisionen, pues teóricamente se cumple que para confiar en que podemos encontrar dos mensajes que colisionen no hay que realizar 2n operaciones, si no sólo 2n/2.

Realicemos algunos cálculos para realizar ataques de fuerza bruta:

  • Para una clave de 12 dígitos, escrita con un teclado con 97 caracteres (base 97), habría que realizar (esto no tiene nada que ver con los algoritmos de HASH):

    9712 = 693.842.360.995.438.000.295.041 comprobaciones.

  • Para MD5, la salida es de 128 bits, sería necesario realizar:

    2128=3’402823669 * 1038 operaciones.

Trabajemos ahora con los ataques basados en búsqueda de colisiones:

  • Para MD5, la salida es de 128 bits, luego hay que operar sobre la mitad de bits, y sería necesario realizar:

    264=18.446.744.073.709.551.616 operaciones.

  • Para el algoritmo SHA 1, cuya salida es de 160 bits:

    280=1.208.925.819.614.629.174.706.176 operaciones.

    Curiosidad: 1.000.000 de ordenadores capaces de procesar en 1 µs cada operación tardarían más de 38.000 años en las 280 operaciones.

Y para los más desconfiados e incluso paranoicos: ¿qué hay de las supercomputadoras y de la gente que sí dispone de los medios necesarios? Cuando saltaron las primeras alarmas sobre estos algoritmos, hace unos dos años, las cifras eran las siguientes:

  • Para romper el SHA-0 completo se ha requerido un supercomputador de BULL de 256 procesadores durante unos 9 años de proceso, pero al supercomputador que está instalando IBM en la UPC (Barcelona) sólo le costaría del orden de 1 año.
  • Otro grupo de investigadores, Wang, Feng, Lai, y Yu han reportado haberlo conseguido con una complejidad aproximadamente 2000 veces menor (240 en vez de 251). Esta reducción equivaldría a una necesidad de cálculo de algo menos de 1 día, si la relación fuese lineal, pero los mismos investigadores han reportado necesitar sólo 1 día con un IBM P690 en cluster, para romper el MD5, que tiene una complejidad equivalente.

Por tanto, lo habitual no es que nos ataque desde uno de estos grandes usuarios (tienen cosas más interesantes que hacer, diría yo…) si no que nos ataque un cracker o similares (ACLARACIÓN: No incluyamos a los señores programadores en esto, los hackers. Gracias a Richard Stallman).

Lo habitual es que este tipo de usuarios realicen ataques basados en diccionarios, como la aplicación para Ñu/Linux John the Ripper. Este tipo de aplicaciones tiene una base de datos con claves comunes, que prueban sobre los sistemas a los que queremos acceder (por ejemplo Sistemas basados en UNIX donde se almacenan los resúmenes HASH de el nombre de usuario y su clave para autenticar). Ante esto sólo hay una solución: EVITAR LAS PASSWORDS ABSURDAS. No sirve (marta -tkm ni maria-secreto) ok??

Concluyendo, dependiendo de su nivel de paranoia críptica y de la aplicación que estén utilizando…escojan su algoritmo de HASH, pero no acepten menos de SHA-1. Cuando un algoritmo empieza a presentar vulnerabilidades no tarda mucho en ser aniquilado, así que a algunos de estos les queda poco tiempo de vida.

Fuentes:

Ir a Algoritmos HASH (I): Introducción

Sigue leyendo

Algoritmos HASH (I): Introducción

Este artículo es una colaboración enviada por LordHASH

En primer lugar, trataremos de abordar de forma sencilla este concepto para aquellos que no lo conozcan. Podemos decir que un HASH no es más que un número resumen. De hecho, en muchos sitios web podéis encontrar expresiones como “checksum MD5”, lo que literalmente se traduce por “suma de comprobación”. Así, el concepto no es complicado, pero sí su implementación. Pongamos un ejemplo: supongamos que tenemos un fichero cualquiera. Pues bien, si consideramos dicho fichero como un flujo de bits y le aplicamos un algoritmo de HASH lo que obtenemos es otro conjunto de bits (de longitud fija y que depende del número de bits de salida del algoritmo o función que utilicemos) que depende bit a bit del contenido del flujo original de bits que sirvió como entrada al algoritmo.
Además, cumplen las siguientes propiedades:

• Todos los HASHes generados con una función de hash tienen el mismo tamaño, sea cual sea el mensaje utilizado como entrada.
• Dado un mensaje, es fácil y rápido mediante un ordenador calcular su HASH.
• Es imposible reconstruir el mensaje original a partir de su HASH.
• Es imposible generar un mensaje con un HASH determinado.

Es decir, un algoritmo de HASH no es un algoritmo de encriptación, aunque sí se utiliza en esquemas de cifrado, como algoritmos de cifrado asimétrico (por ejemplo en el RSA).

Ahora bien, tener una función de estas características puede tener muchas aplicaciones. Algunas de ellas pueden ser las siguientes:

  • Comprobación de integridad de ficheros: Supongamos que queremos transmitir un fichero a un amigo. Si antes de realizar este envío calculamos la función HASH del fichero, para nuestro amigo del otro extremo es posible verificar la integridad del fichero aplicando el mismo algoritmo al archivo que recibe. Si ambos coinciden, podemos asegurar que el envío ha sido satisfactorio. Ésta es una aplicación real que se utiliza, por ejemplo, para comprobar la integridad de muchos paquetes que se descargan en distribuciones del sistema operativo GNU/Linux.
  • Seguridad en procesos de identificación en sistemas: Los procesos de identificación (Login+Password) se ven reforzados por estos algoritmos. Se utilizan de la siguiente forma: cuando un usuario accede a su computadora debe introducir su nombre de usuario y su password. Pues bien, si el sistema operativo no registra estos datos como “texto claro”, si no que registra el resultado de aplicarles una función HASH, en el caso de que un usuario malicioso logre acceder a nuestro archivo de registros no conseguirá (a menos que el algoritmo utilizado sea malo o disponga de una supercomputadora) revertir el contenido de dicho registro, y por tanto no puede acceder a nuestro sistema. Esta misma idea se aplica en identificación de usuarios en muchas webs, con la diferencia de que para que este esquema sea seguro debe incluir información adicional y “aleatoria”, como marcas de tiempo y redundancias.
  • Firma digital: Estos algoritmos se utilizan en esquemas de firma digital para verificar la integridad de la información enviada por el canal de comunicaciones. Algoritmos de cifrado asimétrico, como RSA por ejemplo, realizan lo siguiente: calculan la función HASH del contenido del mensaje que se va a enviar y luego se firma dicho checksum con la clave privada del emisor. Así se asegura la integridad de la información y el “no repudio”.
  • En el próximo post veremos algo más sobre ataques a dos algoritmos HASH: MD5 ySHA-1.

    Ir a Algoritmos HASH (II): Atacando MD5 y SHA-1

Sigue leyendo
Sigue leyendo

Criptografía: Protocolo de distribución de clave BB84

El cifrado de Vernam

El protocolo de cifrado que se usa en criptografía cuántica es posiblemente el más sencillo de todos y hasta ahora, el único que se ha demostrado que es irrompible, el cifrado de Vernam, o One Time Pad. Como ya se ha explicado anteriormente, no me extenderé demasiado, solamente diré que consiste en una clave 100% aleatoria (no vale pseudoaleatoria) de igual longitud que el mensaje y que lo único que hay que hacer para cifrar es un XOR con el mensaje y la clave. ¿Cuál es el problema? Que solo se puede usar una vez, porque si usáramos dos veces la misma clave, el problema de encontrar el texto en claro sería trivial para cualquier criptoanalista. Entonces, si no podemos usar la misma clave dos veces, tendremos que hacer llegar la clave al receptor de alguna manera, o bien quedando con él antes o a través de un canal seguro. La idea del canal seguro es inútil, porque si de verdad exisitiera no tendríamos ni que cifrar el mensaje, respecto a lo de quedar antes en persona, es lo que se solía hacer para usar este cifrado, como los cuadernos con claves de un solo uso que se usaban en la Segunda Guerra Mundial y que Stephenson narra perfectamente en su Criptonomicón. Pero hoy día, la opción de los cuadernos de un solo uso queda totalmente fuera de uso y es poco útil en comunicaciones industriales y operaciones que se realizan a diario.

En definitiva, tenemos el sistema ideal de cifrado, sencillo y eficaz, pero no podemos usarlo por un pequeño problema técnico a la hora de distribuir la clave. La mecánica cuántica viene a solucionar este problema proponiendo un método para distribuir una clave binaria, tan larga como se quiera, totalmente aleatoria y asegurándose de que solo el emisor y el receptor la poseen, justo lo que necesitamos.

Sigue leyendo

Criptografía: Introducción a los cifrados cuánticos

Vuelve la saga de la criptografía, esta vez con dos posts que intentarán explicar algo de la tan desconocida (incluso por mí) criptografía cuántica. Estos dos posts han sido escritos para nosotros por Sergio, al que le damos las gracias por su colaboración y por su gran explicación de este tema.

Este post no contiene mucho acerca de la criptografía cuántica en sí, sino más bien es un post de conceptos y términos que se usarán en el siguiente post. Esperemos que todos aprendamos cosas interesantes de estos posts, y por cierto decir que yo no tengo ni la más remota idea de estos temas así que las dudas serán difíciles de solucionar por mí.

Sobre la polarización de la luz.

El problema de la criptografía cuántica es que, aunque su protocolo sea sencillo, necesita unos conocimientos de mecánica cuántica para entenderlo. Intentaré en este primer punto explicar por encima como se comportan los fotones y que interés tiene esto para nosotros.

Pasando por alto la polémica que iniciaron Newton y Huygens sobre la naturaleza de la luz, vamos a empezar suponiendo que la luz se propaga en forma de ondas. Todos hemos visto una onda dibujada como una función seno o coseno, y realmente no necesitamos más, solo hay que darse cuenta que estas ondas están dibujadas sobre un papel y por tanto son planas, y aunque esto no tiene por que ser siempre así, ya que la dirección de oscilación puede variar de un punto a otro, ese tipo de ondas no nos interesan. Pues bien, tenemos ondas planas, pero ahora tenemos que tener en cuenta la orientación del papel, podemos ponerlo perpendicular al suelo, de manera que tendremos una onda verticalmente polarizada, o paralelo al suelo, en cuyo caso será horizontalmente polarizada. Pero también lo podemos ponerlo de manera oblicua, digamos 45º o -45º o incluso cualquier otra orientación, sin embargo son estas las que nos interesan.

Si estudiamos ahora los polarizadores, podemos suponerlos como un filtro formado por rendijas muy pequeñas. Estos filtros solo dejan pasar la luz polarizada en la misma dirección que las rendijas, por ejemplo, si tenemos un polarizados horizontal, con las rendijas paralelas al suelo, el papel (siguiendo con el simil de una función seno dibujada) podría pasar por ellas si estuviera horizontal, es decir, si la honda fuera horizontalmente polarizada, pero no si fuera vertical. Ahora bien, si la onda fuera oblicua a 45º, y recordando un poco de suma de vectores, podemos descomponerla en una componente horizontal y otra vertical, y solo pasaría una de las dos componentes, de manera que tendríamos la mitad de la luz al final y además, estaría horizontalmente polarizada, por lo que habríamos cambiado su polarización. Ojo a este punto porque es importante.

Además, existen otro tipo de polarizadores un poco más complicado que lo que hacen es actuar como si fueran dos juntos, dejan pasar toda la luz tanto si es horizontal como vertical, y además no la modifican, pero si es oblicua, la convierten en horizontal o vertical al azar, y además es un azar puro, nada de procesos caóticos deterministas, azar puro y duro. Así, si mando una onda a +45º por este polarizador tendré un 50% de probabilidades de obtener una onda horizontal y las mismas de tener una onda vertical. Por supuesto, lo mismo ocurre al revés, tomando un polarizador a ±45º y ondas horizontales y verticales. Y si hasta ahora hemos estado trabajando con ondas, la parte más sorprendente es que la luz también se comporta como partículas, y además estas partículas heredan todas las propiedades de las ondas. Parece que no tiene mucho sentido hablar de la polarización de una partícula, entendida como una pequeña bolita, pero resulta que efectivamente, los fotones individuales, como partículas, tienen polarización, y es con fotones con lo que vamos a trabajar.

Post anterior: Cifrado de clave pública II

Sigue leyendo

Criptografía: Cifrado de clave pública II

Cifrado RSA

El algoritmo fue descrito en 1977 por Ron Rivest, Adi Shamir y Len Adleman (la sigla RSA es Rivest Shamir Adleman) en el MIT.

El cifrado RSA es un algoritmo de cifrado de clave pública (o asimétrico) por bloques, que como todos los cifrados de clave pública tiene dos claves: una pública, que se distribuye a los usuarios que quiera el propietario de ella, y otra privada, la cual es guardada en secreto por su propietario. Así cuando se envía un mensaje, el emisor usa la clave pública de cifrado del receptor para cifrar el mensaje y una vez que dicho mensaje llega al receptor, éste se ocupa de descifrarlo usando su clave oculta.

El algoritmo sigue los siguientes pasos:

  1. Se construye un número “N”, que resulta del producto de dos primos “p” y “q” (normalmente son números muy grandes). Teniendo N = p · q y Φ(N) = (p-1) · (q-1)
  2. Se selecciona un número “e”,1 < e < Φ(N), tal que MCD (e, Φ(N)) = 1 (“e” y Φ(N) son primos relativos).
  3. Se calcula el inverso de “e”, denotado por “d”, tal que e · d = 1 (mod Φ(N))
  4. Con esto se consiguen las claves (e, d), siendo la clave pública (e, N) y la clave privada (d, N).

Una vez tenemos las claves podemos pasar a cifrar/descfirar los mensajes:

  • Cifrado: C = Me (mod N) con MCD (M, N) = 1 y M < N
  • Descifrado: M = Cd (mod N)

La seguridad de este algoritmo radica en que no hay maneras rápidas conocidas de factorizar un número grande en sus factores primos utilizando computadoras tradicionales.

(Más información en Wikipedia)

Sigue leyendo