Funciones Hash

Una función hash h = hash(M) es una función que toma como entrada cualquier mensaje M, de cualquier longitud y da una salida h de una longitud fija que tiene las siguientes propiedades:

  • Parece aleatoria pero es determinista: es decir para el mismo mensaje M, hash(M) es siempre el mismo.
  • Un mínimo cambio en el mensaje M, da un resultado completamente diferente.
  • Es “one way“: esto quiere decir que es facilmente computable en un sentido y muy difícil en sentido contrario. Es decir dado un hash h, es computacionalmente inviable hallar M tal que h = hash(M)
  • Es resistente a colisiones. Como el espacio de datos de entrada (el número de mensajes posibles) es mucho mayor que el de salida (el número de hashes posibles), es evidente que tiene que haber M1 y M2 tales que hash(M1) = hash(M2). A esto se le llama una colisión. Pues bien, que una función hash sea resistente a colisiones significa que es computacionalmente inviable encontrar dos mensajes diferentes tales que su hash sea el mismo.

Veamos algunos ejemplos:

aaldave@~ $ echo -n Mensaje1 sobre el que calcular el sha-1 | shasum
029acc47c63e06a8140c0cadac44d4ea65024158
aaldave@~ $ echo -n Mensaje2 sobre el que calcular el sha-1 | shasum
9b0381804b870754f050ee663669f724c7124fba
aaldave@~ $ echo -n 1 | shasum
356a192b7913b04c54574d18c28d46e6395428ab
aaldave@~ $ echo -n Satoshi Nakamoto | shasum
ea8ffd7dd95cc12d42f5b240730618d57b4f1dc0

En este caso he usado la función hash sha-1. (SHA es el acrónimo de Secure Hash Algorithm)

Observad como dos mensajes prácticamente iguales (los dos primeros), dan un hash completamente diferente. Parece aleatorio, pero no lo es. Es completamente determinista. Si hacemos el hash de un mismo mensaje hoy o dentro de cien años en otro ordenador, o calculado en papel, el resultado es el mismo.

También podemos notar que no importa la longitud del mensaje de entrada, la longitud de la salida (el hash) es simpre la misma.

Un error común es pensar en una función hash como una “encriptación, o compresión” del mensaje. No es ni una encriptación ni una compresión, ya que el proceso no es reversible. No sólo porque es computacionalmente inviable encontrar un M cuyo hash sea h, sino que además, para cualquier h hay muchísimos M cuyo hash es h, con lo cual incluso aunque encontráramos uno de ellos, no sabríamos si es el que buscamos. Pensad que, por ejemplo, podríamos hacer el sha-1 del Quijote, la novela completa. Obviamente en 20 bytes no está “ni comprimida ni encriptada” la novela completa.

El hash de un mensaje es como una “huella digital” del mensaje

Las funciones hash son muy útiles y en Bitcoin se usan también mucho. Por ejemplo para el minado. “Minar” un bloque es esencialmente probar a ver si el hash de la cabecera de un bloque de transacciones es un valor suficientemente pequeño (que empiece por un número determinado de ceros). Si no da, se modifica la cabecera (existe un campo especialmente para ello) y se prueba otra vez. Y así hasta que se encuentre una cabecera cuyo hash esté por debajo de dicho valor. Cuando un minero encuentra un hash suficientemente pequeño, ha encontrado un bloque válido y lo difunde al resto de la red. El resto de nodos verifican que efectivamente el hash de esa cabecera cumple el requisito y añaden ese bloque a la cadena de bloques (blockchain).

También se usan funciones hash en las direcciones de Bitcoin. Una dirección es una codificación especial de un hash de la clave pública. En realidad, el hash de un hash. Primero se hace un sha256 de la clave pública y al resultado se le aplica un ripemd160. Es decir: btcaddress = base58check(ripemd160(sha256(PubKey)))

También se usan hashes en las propias firmas digitales. En vez de firmar un mensaje completo (la transacción puede ser un mensaje grande), en realidad se firma un hash de la transacción. Con esto el proceso de firma es mucho más eficiente computacionalmente.

Para coger mejor la “sensación” de qué es una función hash, en el siguiente enlace podéis hacer pruebas.

https://emn178.github.io/online-tools/sha1.html

Y para emepezar a entender qué es el “proof of work“, intentad hallar una cadena de texto cuyo hash comience por 0. (Por supuesto, probando… ¡no hay otra forma!)

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s