08 mayo 2014

¿Qué es un HASH?

El día de ayer leía a través de meneame.net una entrada de blog de una compañía que desarrolla un bloqueador de malware intentando explicar ¿Qué es un HASH?(Inglés).

Dentro de la entrada, explicaban escencialmente algunas características del HASH MD5. En lo personal entiendo el motivo de la publicación, sin embargo, no me agradó demasiado que se mezclaran algunos conceptos que a la larga podrían dificultar la comprensión de un concepto que debería ser sencillo, por ejemplo la idea errónea que un "hash puede ser crackeado".

Posiblemente si estás en esta página aún no tengas claro ¿Qué es? y ¿Para qué sirve un HASH?, así que en los próximos párrafos intentaré explicarlo de la manera más sencilla posible y te explicaré también porqué "crackear un hash" no tiene sentido.



¿Qué es un HASH?


Vamos a partir de un concepto muy simple:

Un "HASH" es una función matemática y/o lógica que nos permite transformar un conjunto de datos datos (texto, imágenes, archivos) en un único valor numérico.

La utilidad del HASH viene en el hecho de que podemos utilizar ese número, entre otras cosas, para determinar si los contenidos en dos textos son iguales sin necesidad de comparar elemento por elemento, para realizar búsquedas de manera rápida y para verificar la integridad de los datos transmitidos sobre un medio de comunicación que pueda ser propenso a la pérdida de datos.

Esto es así porque computacionalmente hablando, es muchísimo más rápido comparar dos números entre sí que comparar un archivo que podría tener cientos, miles o millones de valores diferentes dentro de sí.

Un HASH a la medida


Imaginemos una función de HASH a la que llamaremos [TeUbico-HASH]. Por ahora no nos importa que operaciones se realizan dentro de esta función, simplemente sabemos que al entregarle una serie de datos y que esta función nos devolverá un número entre 0 y 9999.

Vamos a limitar (con el afan de simplificar el concepto para facilitar el análisis) el tamaño de las cadenas de texto que se pueden "hashear" a 99 caracteres como máximo y vamos a limitar a que no se puedan utilizar tíldes o espacios.

Con estas restricciones, los textos generarán los siguientes resultados:

(La flecha indica la dirección de los datos)

Texto      -> [Función]      -> Resultado
Hola_Mundo -> [TeUbico-HASH] -> 1024
TeUbi_co   -> [TeUbico-HASH] -> 824
Computador -> [TeUbico-HASH] -> 1014
Era        -> [TeUbico-HASH] -> 312

Otra característica interesante del HASH es que su salida debería ser invariante en tanto la entrada se mantenga constante. Para el ejemplo anterior, "Era" siempre nos dará de manera invariante como resultado 312 sin importar cuantas veces consecutivas apliquemos el HASH sobre la misma cadena.

Adicionalmente una función "HASH" debe de ser de una sola vía. Esto significa que una vez aplicada la función sobre los datos de entrada no debe ser posible (o al menos no con gran certeza) averiguar que cadena fué utilizada para generar el hash específico.

La protección de claves


Los sistemas informáticos normalmente poseen algún sistema de autenticación para sus usuarios. Esto se hace normalmente solicitando un nombre de usuario que identifica a la persona que quiere acceder y una clave secreta que en teoría únicamente el usuario autorizado conoce.

Al final del día, la gran mayoría de sistemas de autenticación funcionan como la "lista de invitados" utilizada por un guardia de seguridad en una fiesta. 

Cada persona interesada en entrar a la fiesta se identifica con su nombre y proporciona su "palabra clave", luego el guardia revisa su lista y verifica que los datos proporcionados por la persona coinciden con los que tiene almacenados.

La lista de invitados se podría almacenar así:

usuario | clave
antonio | carrito
claudia | tolkIEn
carlos  | mI_casa
ana     | millAves
mario   | gatitos

Siguiendo con la analogía y en un mundo ideal: la lista de invitados sería inaccesible por alguien que no tenga autorización para verla y el guardia  tendría una memoria de pez que le permitiría olvidar al instante las palabras clave de los invitados.

La realidad, tristemente, es completamente diferente: En los sistemas de información la lista de acceso se guarda dentro de una base de datos como una tabla de usuarios, aunque es posible diseñar un sistema muy seguro nada garantiza que al final del día un "atacante" logre tener acceso de una u otra manera.

La pregunta se convierte entonces en algo como: ¿De qué manera podemos verificar las claves de nuestros usuarios sin almacenar la palabra clave?

Para solucionar esto lo que haremos es almacenar el HASH en vez de la correspondiente clave en una tabla, de una manera más o menos similar a la siguiente:

usuario | hash
antonio | 703
claudia | 723
carlos  | 713
ana     | 813
mario   | 1104

El sistema entonces tendrá que calcular "al vuelo" el valor del hash para verificar el acceso.

Por ejemplo si me presento como "mario" y  clave "aves":

aves -> [TeUbicoHASH] -> 402

El sistema revisará la lista y encontrará que para el usuario "mario" el hash debería haber sido 1104 en vez de 402 y por tanto me denegará el acceso.

Alguien me dirá: ¿Pero entonces no sería más fácil darle al usuario el hash en vez de su clave? La respuesta es NO, porque el guardia para esta analogía no conoce las claves sino que las calcula al momento de que se las proporcionan. Hemos dotado a nuestro "guardia" con una muy efectiva memoria de pez.

Obviamente nuestro guardia podría tomar nota de las claves en una hoja a parte, esto es conocido como un "ataque del intermediario" (MiM attack), pero de esto no vamos a entrar en detalle por el momento y vamos a "asumir" para fines prácticos que nuestro guardia no tiene lápiz ni papel a la mano a donde realizar apuntes y que es incapaz de acordarse qué fue lo que comió hace cinco minutos.

Las colisiones


Pero ahora viene un problema: regresemos al concepto básico. Un HASH es una operación matemática y/o lógica sobre un conjunto de datos que nos da un número como resultado. Nuestro [TeUbicoHASH] es capaz de tomar cualquier texto (en tanto tenga menos de 99 caracteres) y convertirlo en un número entre 0 y 9999.

El problema es, que nuestro idioma tiene cerca de 283,000 palabras, esto significa que por puros efectos de la probabilidad cada palabra en nuestra función [TeUbicoHASH] muy probablemente tiene otras 28 palabras con las que comparte el mismo hash (diviendo 283000/10000).

Y esto es muy fácil de comprobar en el caso de nuestro [TeUbicoHASH]:

Texto   -> [Función]     -> Resultado
carrito -> [TeUbicoHASH] -> 703
casetas -> [TeUbicoHASH] -> 703
calamar -> [TeUbicoHASH] -> 703

Si son un poco observadores, ya se habrán hecho una idea de cómo funciona nuestro algoritmo HASH de ejemplo y por qué los ejemplos anteriores se corresponden al mismo HASH.

Y aquí es donde quisiera dejar claro algo: Todas las funciones de HASH tienen colisiones. Lo importante, desde el punto de vista del diseño de sistemas, es que el tamaño del hash resultante cubra al el conjunto de posibles combinaciones de datos en la entrada de tal manera que garantice el nivel de seguridad que deseamos.

Por ejemplo si nuestro conjunto de datos de entrada son las palabras en el idioma español, necesitaríamos un hash que fuera capaz de cubrir al menos 283,000 valores diferentes. Si utilizamos un hash que es capaz de generar un número a la salida entre 1 y 999,999 estaríamos muy bien cubiertos.

Normalmente nos encontraremos con el caso contrario, que nuestra función de HASH solo cubre una parte de los posibles datos del sistema. Esto no importa en tanto el sistema esté diseñado para detectar las condiciones y reaccionar acorde y que la probabilidad de encontrar colisiones sea lo suficientemente baja en la práctica como para que no implique un problema de seguridad.

Que tán grande es el número que se genera como resultado es lo que se conoce como el tamaño del HASH y usualmente se mide en bits.

Estos son algunas funciones HASH comunes y su tamaño en bits:

Función HASH | Tamaño | # de hashs
MD5          | 128    | 3.40e^38
SHA-1        | 160    | 1.46e^48
SHA-256      | 256    | 1.16e^77
SHA-512      | 512    | 1.34e^154 

Para que se hagan una idea de que tan grandes son estos números, la ESA publica un artículo donde estima rápidamente que en en el universo podría haber entre 10^22 y 10^24 estrellas, este número es inferior al total de HASHs generables con la función MD5.

Crackeando una tabla de HASH


Sinceramente no me gusta el título de esta sub-sección porque es completamente erróneo, pero lo uso así para poder aclararlo como se debe: Un HASH es un simple número y por tanto NO SE PUEDE CRACKEAR O VULNERAR.

El decir que se va a crackear una tabla de HASH de passwords es como decir que vamos a crackear las tabla del 9 o que vamos a crackear el número 324. Es simplemente absurdo y no tiene el más mínimo sentido.

Lo que si se puede hacer, es intentar averiguar qué textos generan ciertos HASH para una función conocida o buscar debilidades en el algoritmo de HASH que nos den pistas sobre qué formato o datos pudieron haber generado. Esto es a lo que se ha popularizado como "crackear hashes".

Escencialmente hay varias formas de hacer lo anterior. Sin entrar en muchos detalles:

  1. La fuerza bruta: La más común, consiste en probar a través de un diccionario o combinaciones de letras y números hasta que encontremos la palabra que generó el HASH especificado. Este proceso es lento y generalmente poco eficiente. Sin embargo si tomamos en consideración que la mayoría de gente utiliza como clave la palabra "password" o  "123456" puede que no resulte una idea tan descabellada después de todo.
    Las medidas de contingencia para esto se centran en dificultar el tiempo que toma realizar pruebas o desactivar el acceso al usuario si se ingresa un valor erróneo luego de X cantidad de intentos. Es sin embargo es poco útil si el atacante tiene acceso directo a la tabla de usuarios.
  2. Uso de tablas pre-calculadas: En vez de calcular en el aire generamos una serie de tablas de HASH con valores pre-calculados para una serie de datos de entrada. Así en vez de buscar combinaciones al azar de la entrada verificamos primero si el HASH no se encuentra ya en una tabla pre-existente.
    La medida de contingencia más efectiva contra este tipo de ataques es utilizar hash "salteados". Agregar "sal" a un password significa colocar información aleatoria (pero no secreta) a la clave antes de aplicar el HASH, de esta manera para dos palabras iguales el resultado (al ser diferente la entrada) no podrá buscarse en una tabla de valores pre-calculados. Esto es sumamente efectivo en caso de que el atacante tenga acceso a la tabla de datos ya que se verá obligado a utilizar la fuerza bruta. Si el algoritmo de HASH es seguro y se utilizan buenas políticas de claves esto evitará en la mayoría de los casos que el atacante pueda obtener alguna clave de la tabla.
  3. Identificando patrones que nos den pistas sobre qué tipo de información o formato de los datos puede haber generado el HASH a partir de su resultado: Esta es tal vez la forma de ataque más "peligrosa" porque indica que existe una vulnerabilidad en el propio diseño del algoritmo que está "filtrando" información acerca de los datos que fueron utilizados para generarlo.

Y me voy a centrar en 3 porque es muy interesante y me servirá para justificar el siguiente punto.

Tomemos nuevamente [TeUbicoHASH], este algoritmo es súmamente débil. El algoritmo funciona de manera muy simple los primeros dos dígitos corresponden al largo de la cadena, el tercer dígito al número de letras mayúsculas utilizadas y el último dígito al número de vocales en el texto.

Un atacante, sin conocer el algoritmo puede aprender que la palabra "eva" tiene el mismo [TeUbicoHASH] que la palabra "eso". Así que puede preparar cadenas de texto de las cuales ya conoce cual será su resultado. Por lo que utilizar [TeUbicoHASH] para autenticación sería una decisión muy tonta... y por esta razón:

Nunca, pero nunca... Inventes tu propio algoritmo de HASH.

A menos que seas un matemático experto, que estés dispuesto a trabajar en el área de seguridad y cifrado, estés dispuesto a que tus algoritmos sean revisados en pares (peer-reviewed) y a participar en algún concurso donde antes, durante y después del concurso de seguridad muchísimas personas intentarán de una manera u otra encontrar debilidades en tu algoritmo...

Lo mejor será es que utilices algún algoritmo de HASHING existente.

Los algoritmos de HASH seguros o criptográficos tienen algunas características que los hacen muy robustos y difíciles de "romper".

  1. El efecto avalancha o cascada. Esto significa que con un pequeño cambio en los datos de entrada el resultado va a ser completamente diferente.
  2. El resultado de la operación no revela datos o patrones que permitan determinar el formato de los datos utilizados en la entrada de la misma. Se dice que un conjunto de datos generados a partir de una función criptográfica perfecta sería indistinguible de datos generados al azar.
  3. Están sustentados en la complejidad de en la "inversión" de la operación que los generó. Es decir, resulta fácil verificar su respuesta conociendo las entradas pero es sumamente difícil determinar las entradas utilizadas conociendo únicamente la respuesta de la operación.

Otra característica (no exclusiva de los HASH criptográficos pero muy útil) es la siguiente:

Son "simples" de implementar y su costo operacional es bajo. De tal manera que los algoritmos de hash además de cumplir con 1, 2 y 3 tienen que ser lo suficientemente sencillos y eficientes para que puedan ser implementados desde el microcontrolador más sencillo hasta el supercomputador más grande.

Usos comunes de HASH


Hay cientos de diferentes tipos de HASH. La aplicación más conocida es para autenticación de usuarios. Sin embargo sus características los hacen útiles para otras aplicaciones.

Como nota interesante las mismas técnicas utilizadas para "atacar" un hash pueden ser utilizadas para hacer cosas interesantes como las siguientes. Y por ello me gustaría decir que realmente en tecnología no hay cosas "buenas o malas" todo depende del uso que se le de.

Estas son otras aplicaciones útiles de los hash:

Búsqueda de contenidos: Por ejemplo el hash inventado en esta entrada [TeUbicoHASH] no resulte seguro para autenticar un usuario, pero si quiero buscar palabras similares es muy posible que por sus características este si sea de utilidad. Existen diferentes tipos de HASH que nos permitirán buscar archivos similares, secuencias similares o como en este ejemplo palabras similares. Además resulta más "económico" y eficiente guardar una tabla con hash y sus referencias en vez de guardar todo un archivo.

Verificación de integridad de archivos: Si yo transfiero un archivo desde A hasta B a través de los hash puedo verificar de alguna manera que los datos se hayan transferido de manera correcta.

Por ejemplo:

Como transmisor envío "asa" y su checksum:

asa,302

Pero mi receptor recibió en cambio:

ask,302

Al verificar se qué ha habido algún problema con la transmisión de información ya que el dato esperado no coincide con el hash. Hay algunos algoritmos de HASH y sumas de verificación que permiten recuperar hasta cierto punto los datos perdidos, pero de esto no hablaremos en esta entrada.

Formato de representación hexadecimal.


Normalmente cuando hablamos de HASH los más comunmente utilizados son MD5 y SHA-1, para no tener que escribir un número muy largo se utiliza una representación hexadecimal. Aquí está una tabla de ejemplo de "como se ven" los hash de la palabra "TeUbi.co" a través de diferentes funciones de hash:

texto    -> [Funcion HASH] -> HASH (Hexadecimal)
TeUbi.co -> [MD5]          -> e9d1c4743c241a952131ce10d4e5e0e9
TeUbi.co -> [SHA-1]        -> a7a9cfd99a01a91458ef680b2a06d0cf46026c14

Por último un ejemplo de una tabla "salteada", podrán ver como para el mismo texto utilizando diferentes "sales" el HASH es diferente mostrando el funcionamiento del efecto "avalancha".

texto + sal -> [Funcion HASH] -> HASH (Hexadecimal)
TeUbi.co1   -> [MD5]          -> d6ab0b37db9d05f78f02d11d3270f7e9
TeUbi.co2   -> [MD5]          -> 7b91bc41ec8bd0952febd7d475a3c688
TeUbi.co3   -> [MD5]          -> 2512455ebc0aa67ac435b853997f1376

En esta entrada no pienso explicar la teoría de funcionamiento de los HASH MD5 o SHA-1 primero porque no soy un experto en el tema y segundo porque están basados en premisas matemáticas que normalmente no tienen aplicación práctica fuera del contexto de la aplicación del algoritmo.


Normalmente en aplicaciones de seguridad se trabaja en la "desconfianza", no les pido que confíen ciegamente en los algoritmos más utilizados, pero tomen en consideración que muchos de ellos han sido revisados y probados por muchísimos expertos alrededor del mundo, que están en continuo "ataque" y que han demostrado ser lo suficientemente robustos para aplicaciones críticas.

Adicionalmente la comunidad en varias ocasiones se han encargado de publicar vulnerabilidades o "ataques" a los mismos así que si bien no podemos tener una completa certeza de que sean 100% seguros al menos tenemos la seguridad de que han sido probados.

Terminando...


La próxima vez que alguien les diga que un HASH es algo complejo... sabrán decirles que la "función que genera el HASH" es algo complejo, pero un HASH es un número como cualquier otro cuyas características nos facilitan la vida en muchas cosas y garantizan parte de la seguridad de nuestros sistemas informáticos.

Te recomiendo visites los vínculos al final para obtener más información sobre cómo funcionan los HASH, en especial la lista de algoritmos de HASH de la Wikipedia en Inglés.

No habiendo nada más que decir... ¡Hasta la próxima!


Más recursos:

1 comentario:

Pablo dijo...

Para almacenamiento de claves, la velocidad no es una buena característica de un algoritmo de hash. Es mejor usar un algoritmo específico para contraseñas, como bcrypt: http://security.stackexchange.com/questions/211/how-to-securely-hash-passwords