¿Qué son las funciones hash? – Adrian Rodriguez

¿Qué son las funciones hash? – Adrian Rodriguez

Vamos a estudiar uno de los conceptos fundamentales en blockchain, las funciones hash.

Una definición…

Son algoritmos que reciben un conjunto de datos de longitud indeterminada y nos devuelven una cadena de longitud fija. Esta cadena recibe el nombre de hash value, hash codes, hash sums, checksums o hashes.

Cuando nos referimos a un conjunto de datos, puede ser de cualquier tipo digital. Textos, ficheros de música, de vídeo, imágenes, etc. Incluso para estas funciones la extensión del archivo puede alterar el resultado.

No existe una sola y única función de hash, por el contrario, hay una variedad de ellas. Entre las más conocidas: SHA-2, la cual se compone de SHA-224, SHA-256, SHA-384 y SHA_512.

Aquí puedes tener una primera intuición, ya que si la entrada no tiene límite de tamaño y la salida sí, algunas de las entradas de las infinitas posibilidades pueden dar la misma salida. Lo cual es cierto, tienes razón, pero para conseguirlo los métodos no son ni sencillos ni rápidos. Si recorriéramos todas las posibilidades existentes para conseguirlo, necesitaríamos ²¹²⁸ iteraciones, lo cual puede ocupar gran parte de tu tiempo y el de tu descendencia.

Vamos a ver algunas de las características de estas funciones:

Determinista

Dada una entrada (input), la función de hash siempre devolverá la misma salida (output). No importa cuantas veces hagas pasar el input por la función, siempre obtendrás lo mismo. Parafraseando a Einstein: “Locura es esperar algo diferente haciendo pasar siempre lo mismo por una función de hash”.

Esta característica es fundamental para ciertos usos de estas funciones, por ejemplo, para comprobar la autenticidad de un fichero o si ha sido manipulado o no. Necesitamos que ante el mismo fichero siempre devuelva el mismo hash y ante ficheros diferentes hashes diferentes.

Simplemente puntualizar que también existen funciones hash no deterministas, que dependen de algún otro parámetro como fechas, direcciones de memoria, etc.

Eficiencia

El proceso de creación de un hash debe ser rápido y no debe exigir mucho poder de cómputo.

Resistente a colisiones

Tiene que ser extremadamente difícil encontrar entradas diferentes que produzcan el mismo hash. Esta característica suele incluir resistencia a la primera preimagen y segunda preimagen. Lo que supone el primero es que dado un hash sea computacionalmente intratable encontrar el valor de entrada que lo produjo. La resistencia a la segunda preimagen quiere decir que dado un valor de entrada es computacionalmente intratable encontrar otro valor que produzca el mismo hash.

Aquí hablamos de intratable o extremadamente difícil, ya que no es imposible. Para entenderlo debemos hablar de la paradoja del cumpleaños:

Si nos encontramos a una persona aleatoria, las probabilidades de que los dos tengamos la misma fecha de cumpleaños son realmente bajas. Concretamente, partiendo de la asunción de que todos los días tienen la misma probabilidad, sería 1/365.

Sin embargo, si juntamos a un grupo de 20 a 30 personas, las probabilidades de que dos personas tengan la misma fecha de cumpleaños aumentan considerablemente pudiendo superar el 50%.

En consecuencia, dado un número diferentes de posibilidades, necesitas una cantidad de ítems aleatorios que sea la raíz cuadrada de la cantidad de posibilidades para tener un 50% de probabilidad de colisión.

Ocultamiento

No se debe poder deducir o calcular el input a partir del hash, no tiene que ser posible revertir la función. La única forma sería a través de la fuerza bruta, es decir, ir probando todas y cada una de las posibilidades.

Continuidad y Efecto avalancha

Se considera que una función hash es continua si una modificación pequeña en la entrada ocasiona cambios pequeños en el hash.

El efecto avalancha se da cuando cualquier cambio en el input, sin importar si es pequeño (un bit) o grande (todo el texto) produzca que el hash varíe totalmente.

Las primeras son utilizadas, por ejemplo, en algoritmos de búsqueda, ya que pequeñas diferencias producirían hashes similares o iguales. Las segundas son usadas, por ejemplo, por algoritmos de verificación o criptográficos.

Puzzle Friendly

Esta es una de las propiedades que han tenido gran importancia en las criptodivisas en aspectos tales como la minería. Empecemos con una definición técnica:

Para cada salida “Y”, si “k” es elegido de una distribución con una alta entropía mínima es prácticamente imposible encontrar una entrada “x” tal que H(k|x) = Y.

Pasemos a analizar ciertas partes de esta definición para entenderla correctamente,

alta entropía mínima

Tener una alta entropía mínima quiere decir que la distribución donde se eligen los valores es tan grande o con mucha variablidad que la probabilidad de seleccionar aleatoriamente valores repetidos es mínima.

Por tanto, podemos decir que si nos hacen elegir un número de 1 al 10, tenemos una distribución con una baja entropía mínima. Si la distribución es entre 1 y un trillón tenemos una distribución con una alta entropía mínima.

“k|x”

El símbolo “|” hace referencia a concatenación, que significa juntar dos cosas. Por ejemplo, tenemos “ADRI” y “AN”, si los concatenamos resultaría “ADRIAN”.

Volviendo a la definición. Tenemos nuestro valor “Y”. Si elegimos de forma aleatoria un valor “k” de una gran distribución, es casi imposible que encontremos otro valor, llamémoslo “x”, tal que el hash que obtengamos de concatenar “k” y “x” sea “Y”.

¿Por qué decimos que encontrar “x” es casi imposible y no imposible?

Porque se puede conseguir, pero el único método posible es recorrer toda la distribución de forma aleatoria (debido al tamaño de la misma) hasta dar con la solución. Si lo vemos con un caso real, para la función SHA-256 tenemos ²²⁵⁶ valores posibles.

Entendida la definición vamos a ver por qué es puzzle friendly. Para ello vamos a poner nombres a nuestras letras:

“k” es el PUZZLE-ID, es decir es un valor dado.

“Y”: sería un rango de valores, es decir, son los posibles resultados correctos que habría.

Por tanto, para resolver el puzzle se debe encontrar una “x” que genere una salida que esté dentro del rango definido por “Y”. En consecuencia, juntando la definición antes vista y esta versión podemos ver que la dificultad del puzzle depende directamente del tamaño del rango definido por “Y”. Si “Y” define un rango que coincida con todos los valores posibles, el puzzle es fácil, ya que cualquier “x” producirá un valor dentro del mismo. Si, por el contrario, “Y” define un rango con una única solución, estamos ante un puzzle de dificultad máxima, ya que tenemos que recorrer todos los posibles valores hasta encontrar la “x” que genere la salida correcta.

Esto no quiere decir que haya colisiones, ya que cada “x” producirá una salida diferente, solo que el puzzle la admite como válida por estar dentro de la distribución que ha definido.

Las aplicaciones de estas funciones son variadas, vamos a revisar algunas de ellas:

Gestión de identificadores y contraseñas: son ampliamente utilizadas, los proveedores de servicios en la nube o plataformas donde necesitemos datos de accesos como usuario y contraseña. Estos servicios deben comprobar si los datos introducidos son correctos, pero no almacenan estos datos, sino hashes de los mismos. Por ello, las plataformas te piden reiniciar la contraseña cuando solicitas recuperarla.

Prueba de la integridad de contenidos: basándonos en el efecto avalancha de ciertas funciones hash, podemos comprobar si un fichero ha sido manipulado, ya sea en su contenido, nombre, extensión o cualquier otro aspecto que se nos ocurra. A esto se le suele llamar checksum criptográfico.

Identificación de contenido: en algunas aplicaciones se usa el valor hash de un fichero para identificar su contenido, independientemente de otros parámetros.

Dropbox utiliza funciones hash en este sentido, un ejemplo de ellos podemos verlo en el informe revista TechCrunch. En él se nos cuenta que Dropbox bloqueó una cuenta a un usuario por compartir contenido protegido por las leyes de EEUU de derechos de autor. ¿Cómo sabía Dropbox del contenido del fichero? Sencillo, los autores legítimos del contenido habrían generado un hash del mismo, lo habrían agregado a un listado de contenidos protegidos. Por tanto, en cuanto el usuario intentó compartir el fichero, Dropbox comparó el hash del fichero con el listado, al ver que estaba incluido en dicha lista bloqueó la operación.

Detección de virus: Muchos antivirus definen funciones hash que capturan la esencia del virus generando lo que se llama la firma del virus. Esto permite detectarlos y distinguirlos de otros programas o virus.

Las funciones hash son ampliamente utilizadas dentro de blockchain, vamos a ver alguno de estos usos:

Creación de la dirección: por ejemplo, en Bitcoin se utiliza la función SHA-256 hasta 3 veces en el proceso de generación de la dirección.

Minería: es uno de los procesos claves a la hora de generar bloques. Las funciones hash son utilizados en varias partes del proceso como asociar las transacciones al bloque.

Una vez asociados los datos se obtiene un hash del total y se le concatena un valor, nonce, el cual el minero puede manipular para poder conseguir un determinado hash que cumpla con el nivel de dificultad establecido (puzzle friendly)

Base de la seguridad en blockchain: la seguridad de blockchain descansa sobre el efecto avalancha de las funciones hash. Es decir, si intentamos modificar cualquier registro pasado, tendríamos que modificar todos los hashes hasta el presente para mantener la cadena. Lo cual se vuelve imposible si tenemos en cuenta el carácter transparente de blockchain.

Estructura de datos:

Listas ligadas: Son secuencias de bloques donde cada uno tiene el enlace hacía el anterior gracias a un puntero (son variables que almacenan la dirección de otra). Blockchain aplica una variación de esto, sigue siendo una lista ligada, pero los punteros son hashes del contenido del anterior bloque (hash pointers). Es esta variación lo que permite la trazabilidad en blockchain y la seguridad de que su contenido no fue manipulado

Árbol de Merkle: es una estructura de datos en árbol, en el que cada nodo que no es final está etiquetado con el hash de la concatenación de las etiquetas o valores (para nodos finales) de sus nodos hijo.

Fuentes:

Wikipediaorg. 2019. Wikipediaorg. [Online]. [31 July 2019]. Available from: https://es.wikipedia.org/wiki/Funcin_hash

Wikipediaorg. 2019. Wikipediaorg. [Online]. [31 July 2019]. Available from: https://es.wikipedia.org/wiki/Funcin_hash_criptogrfica

Bitcoinwikiorg. 2019. Bitcoin (BTC)wikiorg. [Online]. [31 July 2019]. Available from: https://en.bitcoinwiki.org/wiki/Hash

Blogchainers. 2017. Medium. [Online]. [31 July 2019]. Available from: https://medium.com/@_Blockchainers_/las-3-propiedades-primordiales-de-las-funciones-hash-f007e8568f71

Blockgeekscom. 2017. Blockgeeks. [Online]. [31 July 2019]. Available from: https://blockgeeks.com/guides/what-is-hashing/

Published at Mon, 05 Aug 2019 20:18:51 +0000

Bitcoin Pic Of The Moment
From Bitcoin (BTC) and beyond we look at where it all began from its inception to its current day notoriety helping shape the way in which we pay. We also look at what it means for consumers and merchants and how it can be easily integrated into new and existing platforms.
By devsteve on 2014-10-29 18:22:36