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

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

10 Comentarios

  1. Interesante, desde luego. Aunque me ha costado entenderlo la primera vez que lo he leido. Supongo que por lego en la materia.

    Publica una respuesta
  2. Es muy interesante, y vi algo en la carrera sobre este tema.

    El problema principal -pero que en contextos es muy conveniente- es que la función de HASH es una función “inyectiva”. Por eso, es simplemente un camino de ida. Puedo asegurar que:

    HASH(mensaje1) = codigoA

    Pero no puedo asegurar que:

    mensaje1 = MENSAJE(codigoA)

    O sea, no existe función inversa que me permita realizar el camino inverso. En otras palabras, esto se debe a que pueden existir dos mensajes distintos pero que:

    HASH(mensaje1) = codigoA
    HASH(mensaje123) = codigoA

    Entonces, teniendo solo “codigoA” no puedo saber realmente a quien pertenece.
    Esto es práctico ya que al no existir mecanismo inverso, se ofrece mayor seguridad -como bien indicaste en los usos que tiene-.

    En algunos sistemas se utiliza este tipo de métodos para encriptar passwords y, como es un camino de ida, para habilitar el ingreso de un usuario. El problema es que si el hash de ambos passwords es el mismo, el usuario puede entrar con más de un password, o peor, pueden conseguir el archivo que guarda los hashes, y verificar si dos usuarios tienen el mismo hash: esto indicaría que si conozco la contraseña de uno, puedo utilizarla para entrar como el otro usuario también. La solución es simple, y se mezcla, como bien indicaste, con información “aleatoria” como el tiempo del último ingreso al sistema.

    Igualmente, no deja de ser interesante las cualidades que tiene. Personalmente, espero ver este tipo de algoritmos en este cuatrimestre, así que veré si aprendo algo aún más interesante.

    Saludos!

    Publica una respuesta
  3. Has escrito “Si ambos coinciden, podemos asegurar que el envío ha sido satisfactorio.”
    Siendo un poco tiquis miquis, lo correcto no sería “es altamente probable que el envío sea satisfactorio”. Según tengo entendido las funciones hash no son inyectivas, porque si lo fueran enviar un fichero o enviar el código hash sería lo mismo. Y como tu ya comentas es imposible reconstruir el mensaje original a partir del hash.

    Publica una respuesta
  4. Pablo_cg ¿no seria que la función no tiene que ser inyectiva?, porque si mal no recuerdo inyectiva era cuando cada elemento del conjunto de partida tiene una imagen distinta en el de llegada, por lo que si que seria posible una función inversa.
    Lo que si podría ser es suprayectiva ya que todo hash posible sería resultado de aplicar la función a algún archivo. Y tampoco seria biyectiva.

    Publica una respuesta
  5. pablo_cg parte de lo que comentas saldrá en el próximo post. Paciencia :).

    cojin una función inyectiva tiene inversa restringiéndose al conjunto imagen, pero para calcularla hay que conocer ese conjunto. De todas formas al parecer esta función no sería inyectiva por lo que comenta pablo_cg:

    HASH(mensaje1) = codigoA
    HASH(mensaje123) = codigoA

    A ver si con el siguiente post se aclaran las cosas.

    Publica una respuesta
  6. Uff…no esperaba tanta respuesta ante este post…sólo indicaros que algunas de estas cuestiones se resolverán en el próximo post, como bien indica ^DiAmOnD^. Las funciones hash se explicarán de forma algo más exahustiva en el próximo, así como algunos ataques que se han practicado sobre estas cuestiones. Paciencia, y muchas gracias.

    Gracias, sobre todo, a Gaussianos y a ^DiAmOnD^, que me han brindado una gran oportunidad. Espero que el contenido esté a la altura que se merece.

    Publica una respuesta
  7. Bien expuesto, i un tema interesante.
    Ya que se presentan bastantes usos al Hash, explicare el unico que conocia yo.
    Esta bien saber que sirven para mas cosas.

    Las tablas de dispersion: son un formato de almacenamiento de datos. Tiene varias variantes, pero no entrare en detalles.

    Pero bueno, pongamos que queremos almacenar datos de manera efectiva. Tenemos que tener una funcion hash (h) , que efectivamente no tiene que ser inyectiva.
    Pongamos que la funcion Hash da valores (enteros) entre 0 y n.

    Entonces podemos almacenar todos los datos en una tabla de 30 casillas. Cada elemento lo pondremos en la casilla h(elemento).
    Si la funcion es suficientemente buena, podemos suponer que los elementos quedaran suficientemente bien repartidos. Por lo tanto, si tenemos que buscar un elemento entre m elementos, le aplicamos la funcion h y sabremos en que casilla deberia estar.

    Entonces podremos buscar (de la manera habitual), pero en lugar de entre m elementos, lo haremos en un conjunto de (en el caso medio) m/n elementos, lo que sera bastante mas efectivo.

    (en el caso peor buscaremos entre m elementos, pero seria con una funcion hash desastrosa… :P)

    Bueno, espero que se haya entendido, aunque se que me explico considerablemente mal.
    Preguntar cualquier duda, aunque no es que yo sea muy conocedor del tema.

    Publica una respuesta
  8. perdon, me confundi al escribir… 😛 quise decir que la funcion NO es INYECTIVA, justamente despues trate de justificarlo xD

    Publica una respuesta
  9. y ademas (continuo… deberian agregar la opcion de “modificar” a los mensajes, soy demasiado friki como para estar conforme con el primer envio :P), una forma de entenderlo mejor es:

    La función puede recibir, prácticamente, cualquier cantidad de valores de entrada -lógicamente no, pero son tantos, que es imposible darse una idea-, mientras que el resultado devuelto debe ser una cantidad finita.
    Supongamos que el hash se utiliza para cadenas de caracteres. Cada caracter puede tomar comunmente entre 256 valores distintos -sin considerar si es imprimible o no-. Supongamos que la función recibirá, como mucho, cadenas de hasta 100 caracteres.

    La cantidad de valores posibles que recibirá será, para hacerse una idea, de:

    256 (1 car) + 256^2 (2 cars) + 256^3… + 256^100

    100 î
    ∑ 256
    î=1

    Que da como resultado 6.694163509·10^240 (es decir, un número de 240 posiciones).

    Por otro lado, consideremos que el hash será un número hexadecimal de 20 caracteres, para cualquier cadena. Habrá entonces 16^20 posibles resultados de la función (es lógico que sean mucho menos, porque se utilizan para control y demás, no tendría sentido que ocupara demasiado). En total, serían 16^20 = 1208925819614629174706176 > 1.2 x 10^24. Es decir, un número de 25 dígitos.

    Ahora, evidentemente el resultado para varios mensajes será el mismo. Pero qué tan común será eso?

    6.7 x 10^240
    ————
    1.2 x 10^24

    Aprox. = 5 x 10^216

    Es decir, existirán más de 5 x 10^216 cadenas posibles que puedan generar el mismo código de HASH. Esto aparenta ser mucho -bueno, lo es…- pero dentro de un universo de más de 6.7 x 10^240, se produce una coincidencia cada 10^24 cadenas utilizadas, apróximadamente. Esta cantidad no deja de ser exorbitante, por lo cual, la función de hash de esta manera se puede considerar segura para tests de integridad o contraseñas. Y lo importante también es que ocupa mucho menos que la cadena original: mientras que la cadena puede ocupar hasta 100 bytes aprox, una cadena de 20 dígitos hexa ocupara solamente 10 bytes. Es decir, por un 10% más de espacio ocupado estamos ante un simple pero eficiente método para verificar la integridad de la información en un mensaje, por ejemplo. Lógicamente, podrían utilizarse bastante menos dígitos hexa y la seguridad se mantendría aun muy alta.

    Bueno, sólo quería contarlo ^^. Saludos desde Argentina!

    Publica una respuesta

Trackbacks/Pingbacks

  1. meneame.net - Algoritmos Hash... [c&p] Podemos decir que un HASH no es más que un número resumen. De hecho, en muchos…
  2. Gaussianos » Algoritmos HASH (II): Atacando MD5 y SHA-1 - [...] Ir a Algoritmos HASH (I): Introducción Escrito por ^DiAmOnD^, 18 de Abril de 2007 en Informática, Criptografía, Colaboraciones [...]
  3. Yo, programador » Blog Archive » Seguridad en algoritmos HASH - [...] Algoritmos Hash (I): Introducción [...]
  4. TalSoft TS » Blog Archive » Algoritmos HASH: Atacando MD5 y SHA-1 - [...] Ir a Algoritmos HASH (I): Introducción [...]
  5. Algoritmos de hashing | PROG III News - […] https://gaussianos.com/algoritmos-hash-i-introduccion/ […]
  6. Introducción a la criptografía (I) | dovahnet - […] 1º Parte […]

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *