¿Qué es exactamente (y precisamente) "hash"?

38

He escuchado que la palabra "hash" se usa en diferentes contextos (todos dentro del mundo de la informática) con diferentes significados. Por ejemplo, en el libro Learn Python the Hard Way, en el capítulo sobre diccionarios se dice "Python los llama" dictos ". Otros idiomas los llaman" hashes "." Entonces, ¿son los diccionarios hash?

El otro uso común de la palabra está relacionado con el cifrado. También he escuchado (y leído) personas que usan la palabra "hash" como una función específica dentro de la programación de alto nivel.

¿Entonces, qué es esto exactamente?

¿Alguien (con tiempo y con conocimiento) puede explicar amablemente los detalles de "hash (o hashes)"?

gracedlamb
fuente
8
Wikipedia tiene artículos detallados sobre tablas hash y funciones criptográficas hash . ¿Qué estás buscando que no esté en esos?
David Richerby
1
Ya enumeras múltiples usos del término "hash", y hay más. Entonces, ¿cómo exactamente espera obtener una respuesta a "qué es exactamente?"
Rafael
44
En este sentido, "hashes" es un acortamiento de las "tablas hash", por ejemplo, tablas que usan hashes para la organización de claves. Es como llamar a la gasolina "gas": no se espera que el "gas" sea gaseoso o que los gases tengan propiedades similares a la gasolina, ¿verdad? Esto sucede todo el tiempo con el lenguaje: el acortamiento en particular son fuentes muy comunes de superposición de palabras.
Luaan
1
"No hay una definición para esta palabra: nadie sabe qué es el hash". - The Devil's Dictionary
jpmc26
Con respecto a los diferentes trenes de pensamiento, qué es una función hash: una función hash es solo una función con un montón de propiedades, pero no es cómo se define lo que es relevante, es qué propiedades queremos que tenga, lo que derivamos de cómo queremos usar la función, eso es relevante. Debido a que queremos usarlo para acceder a cosas rápidamente, queremos que sea eficientemente computable. Debido a que no tenemos espacio infinito disponible, queremos que el codominio sea finito. Debido a que queremos evitar colisiones lo mejor posible, queremos que la función hash distribuya los hash de manera uniforme.
G. Bach

Respuestas:

44

El artículo de Wikipedia sobre funciones hash es muy bueno, pero aquí daré mi opinión.


¿Qué es un hash?

"Hash" es realmente un término amplio con diferentes significados formales en diferentes contextos. No hay una sola respuesta perfecta a su pregunta. Explicaré el concepto subyacente general y mencionaré algunos de los usos más comunes del término.

Un "hash" es una función denominada función hashh que toma como objetos de entrada y da salida a una cadena o un número. Los objetos de entrada suelen ser miembros de tipos de datos básicos como cadenas, enteros o más grandes compuestos de otros objetos como estructuras definidas por el usuario. La salida es típicamente un número o una cadena. El sustantivo "hash" a menudo se refiere a esta salida. El verbo "hash" a menudo significa "aplicar una función hash". Las principales propiedades que debe tener una función hash son:

  1. Debería ser fácil de calcular y
  2. Los resultados deben ser relativamente pequeños.

Ejemplo:

Digamos que queremos numerar hash en el rango de 0 a 999,999,999 para numerar entre 0 y 99. Una función hash simple puede ser h(X)=Xmod100 .

Propiedades adicionales comunes:

Dependiendo del caso de uso, podríamos querer que la función hash satisfaga propiedades adicionales. Aquí hay algunas propiedades adicionales comunes:

  1. Uniformidad : a menudo queremos que los hashes de los objetos sean distintos. Además, podemos querer que los hashes se "extiendan". Si quiero dividir algunos objetos en 100 cubos (por lo que la salida de mi función hash es un número de 0 a 99), entonces generalmente espero que aproximadamente 1/100 de los objetos caigan en el cubo 0, aproximadamente 1/100 en cubo 1, y así sucesivamente.

  2. Resistencia de colisión criptográfica : a veces esto se lleva aún más lejos, por ejemplo, en criptografía, es posible que desee una función hash de tal manera que sea computacionalmente difícil para un adversario encontrar dos entradas diferentes que se asignen a la misma salida.

  3. Compresión : a menudo quiero dividir entradas arbitrariamente grandes en una salida de tamaño constante o un número fijo de cubos.

  4. Determinismo : es posible que desee una función hash cuya salida no cambie entre ejecuciones, es decir, la salida de la función hash en el mismo objeto siempre será la misma. Puede parecer que esto entra en conflicto con la uniformidad anterior, pero una solución es elegir la función hash aleatoriamente una vez, y no cambiarla entre ejecuciones.


Algunas aplicaciones

Una aplicación común está en las estructuras de datos, como una tabla hash, que son una forma de implementar diccionarios. Aquí, asigna algo de memoria, por ejemplo, 100 "cubos"; luego, cuando se le pide que almacene un par (clave, valor) en el diccionario, inserta la clave en un número 0-99 y almacena el par en el depósito correspondiente en la memoria. Luego, cuando se le pide que busque una clave, la convierte en un número 0-99 con la misma función de hash y comprueba ese depósito para ver si esa clave está allí. Si es así, devuelve su valor.

Tenga en cuenta que también podría implementar diccionarios de otras maneras, como con un árbol de búsqueda binario (si sus objetos son comparables).

Otra aplicación práctica son las sumas de verificación, que son formas de verificar que dos archivos son iguales (por ejemplo, el archivo no estaba dañado desde su versión anterior). Debido a que es poco probable que las funciones hash asignen dos entradas a la misma salida, usted calcula y almacena un hash del primer archivo, generalmente representado como una cadena. Este hash es muy pequeño, quizás solo unas pocas docenas de caracteres ASCII. Luego, cuando obtienes el segundo archivo, lo hash y compruebas que la salida es la misma. Si es así, casi con certeza es exactamente el mismo archivo byte por byte.

Otra aplicación está en la criptografía, donde estos hashes deberían ser difíciles de "invertir", es decir, dada la salida y la función hash, debería ser computacionalmente difícil averiguar las entradas que condujeron a esa salida. Un uso de esto es para las contraseñas: en lugar de almacenar la contraseña en sí, almacena un hash criptográfico de la contraseña (tal vez con algunos otros ingredientes). Luego, cuando un usuario ingresa una contraseña, usted calcula su hash y verifica que coincida con el hash correcto; Si es así, usted dice que la contraseña es correcta. (Ahora, incluso alguien que puede mirar y descubrir el hash guardado en el servidor no tiene tan fácil fingir ser el usuario). Esta aplicación puede ser un caso en el que la salida es tan larga o más larga que la entrada, ya que La entrada es muy corta.

usul
fuente
1
Buena explicación pero no estoy de acuerdo con "muy poco probable". Ver: programmers.stackexchange.com/questions/49550/... : colisión hacer aparecer, ya veces sorprendente frecuencia.
Olivier Dulac
8
También tenga en cuenta que en el contexto de la criptografía, el término "hash" implica muy fuertemente una operación "unidireccional" que no se puede revertir fácilmente en la práctica. Cuando se puede revertir fácilmente, se llama "cifrado". Esta es la razón por la cual la gente de Security.SE le dirá que siempre manipule las contraseñas de sus clientes, que nunca las cifre.
Ixrec
44
Un hash que no se "extiende" sigue siendo un hash, pero quizás no sea muy bueno para su aplicación.
Deja de dañar a Monica el
1
Claro, estos son todos buenos puntos.
usul
10

Una función hash es una función que toma una entrada y produce un valor de tamaño fijo. Por ejemplo, puede tener una función hash stringHashque acepte unstring de cualquier longitud y produzca un número entero de 32 bits.

Por lo general, es correcto decir que la salida de una función hash es un hash (también conocido como un valor hash o una suma hash). Sin embargo, a veces las personas se refieren a la función en sí misma como un hash . Esto es técnicamente incorrecto, pero generalmente se pasa por alto, ya que generalmente se entiende (en contexto) que la persona se refería a la función hash .

El uso típico de una función hash es implementar una tabla hash . Una tabla hash es una estructura de datos que asocia valores con otros valores típicamente conocidos como claves. Lo hace mediante el uso de una función hash en la tecla para producir un valor hash de tamaño fijo que puede usar para una búsqueda rápida de los datos que almacena. No entraré en detalles completos sobre cómo lo hace, pero el hecho clave aquí es que se llama una tabla hash porque se basa en una función hash para producir valores hash (hash).

Aquí es donde entra parte de la confusión, porque algunas personas (de nuevo, algo incorrectamente) se refieren a una tabla hash como un hash. Como se indicó en otras respuestas, a veces la implementación de una tabla hash en un idioma dado se refiere a la tabla hash como un hash (especialmente Perl hace esto, aunque espero que otros idiomas también lo hagan). Otros idiomas eligen referirse a su implementación de una tabla hash como un diccionario. Python es uno de estos lenguajes, pero debido a lo arraigados que están en el lenguaje, muchos usuarios de Python acortan el término diccionario a 'dict'.

Entonces, aunque el uso correcto del término hash es referirse al valor hash producido por una función hash , las personas a veces también usan el término informalmente para referirse a funciones hash y tablas hash , creando así la confusión.

Pharap
fuente
2
No estoy seguro de que sea realmente incorrecto referirse a una tabla hash o función hash como "hash" (no parece peor que, por ejemplo, usar "Washington" para referirse a "Estados Unidos", como en " Washington acogió con cautela la declaración de China "). Pero estoy de acuerdo en que es confuso y es bueno que sea muy claro al respecto en su respuesta.
David Richerby
1
@DavidRicherby Formalmente, diría que el trabajo "hash" no está definido. "Función hash", "valor hash", "tabla hash" y "para hacer hash una cadena" tienen definiciones matemáticas precisas, pero "hash" es ambiguo. Del mismo modo, sé lo que quiere decir con "Washington", pero su oración aún tiene sentido si interpreto que "Washington" significa "George Washington" o "Denzel Washington" en lugar de "La ciudad de Washington", que es una forma muy informal para referirse al gobierno federal. En pocas palabras: tenga cuidado de no confundir "saber lo que quiere decir" para una definición formal rigurosa.
Mike Ounsworth
@DavidRicherby Eso no es realmente una analogía equivalente. La incorrección es discutible pero la informalidad no lo es.
Pharap
2

Una función hash es, en términos generales, cualquier función en la que la imagen es más pequeña que el dominio . La salida de dicha función f(x)se puede denominar "el hash de x".

En informática generalmente encontramos dos aplicaciones de funciones hash.

El primero es para estructuras de datos como tablas hash , donde queremos asignar el dominio clave (por ejemplo, enteros de 32 bits o cadenas de longitud arbitraria) a un índice de matriz (por ejemplo, entero entre 0 y 100). El objetivo aquí es maximizar el rendimiento de la estructura de datos; Las propiedades de la función hash que suelen ser deseables son la simplicidad y la distribución uniforme de salida.

Perl llama a su tipo de matriz asociativa incorporada un "hash" , que parece ser lo que está causando su confusión aquí. No conozco ningún otro idioma que haga esto. En términos generales, la estructura de datos podría verse como una función hash (donde el dominio es el conjunto actual de claves), pero también se implementa como una tabla hash.

El segundo es para la criptografía : autenticación de mensajes, verificación de contraseña / firma, etc. El dominio suele ser cadenas de bytes arbitrarias. Aquí nos preocupa la seguridad, que a veces significa un rendimiento deliberadamente bajo, donde las propiedades útiles son la colisión y la resistencia previa a la imagen.

Deja de dañar a Monica
fuente
Y todavía tengo objeciones a su primera oración porque cuando se combinan contraseñas de 32 caracteres con SHA-512, el espacio de entrada es en realidad más pequeño que el espacio de salida. Al encadenar funciones hash juntas, el dominio y el rango son los mismos; El tamaño del espacio de entrada es irrelevante. La respuesta de Pharap tiene la definición correcta: "Una función hash es cualquier función con una salida de longitud fija". Eso es todo, eso es todo lo que necesitas, todas las demás condiciones de las que estás hablando están implícitas en eso.
Mike Ounsworth el
@MikeOunsworth pero el dominio de SHA-512 es cadenas binarias de longitud arbitraria. Supongo que podría robar la redacción de Pharaps, pero estaba tratando de hacer explícitas las condiciones para el beneficio del OP. No estoy seguro de que sea necesario "de longitud fija", ni esté definido sin ambigüedades.
Deja de dañar a Monica el
@OrangeDog Ok, pero puedo envolver SHA-512 dentro de una función llamada MikesHash()que acepta cadenas de longitud 12 y las pasa a SHA-512, y devuelve la salida. Estoy bastante seguro de que MikesHash()aún cumple con la definición de una función hash. (En la práctica tiene razón, las funciones hash que utilizamos aceptan entradas de longitud arbitraria, pero no creo que algo no sea una función hash si no es así)
Mike Ounsworth,
@MikeOunsworth igualmente puedo envolverlo de modo que la salida se trunca o se rellena si el msb es uno. La salida ya no es de longitud fija, pero ¿sigue siendo una función hash?
Deja de dañar a Monica el
@OrangeDog Yo diría que no. Mi punto desde el principio ha sido que una función hash debe correlacionarse con una salida de tamaño fijo, pero el tamaño de entrada es irrelevante. Nos hemos alejado mucho del tema. Su respuesta tiene algo bueno, solo tenga cuidado con su definición formal ;-)
Mike Ounsworth
0

Gran pregunta Basil Ajith,

Aquí está mi perspectiva de lo que es un hash para algo en lo que estoy trabajando hoy.

* *

Use la suma de verificación para verificar que el tarball sea congruente con la página de descarga

* *

ingrese la descripción de la imagen aquí Se pone el sombrero de auditor, me refiero a la túnica de mago

hash es un valor / cadena / lo que sea / etiqueta, asegúrese de que sea el mismo en su máquina que la fuente de una descarga.

Jesse MacDougall
fuente
3
Este es solo un uso para un hash. Hay muchos otros usos.
Yuval Filmus
Bienvenido al sitio! El uso de hashes criptográficos como sumas de verificación ya está cubierto por la respuesta aceptada, por lo que su respuesta no agrega nada nuevo, mientras ocupa mucho espacio en la pantalla.
David Richerby
-1

Trataré de agregar un breve resumen de lo que otros dicen.

Función hash

Hay un tipo especial de funciones llamadas funciones hash.

"SHA256 es una función hash bien conocida que es criptográficamente segura"

Tres aplicaciones principales son * tablas hash, * sumas de verificación (verificaciones de integridad de datos, por ejemplo, en discos duros o protocolos ADSL), * y criptografía (varias formas de autenticación criptográfica que incluyen, entre otras, firmas digitales y almacenamiento seguro de contraseñas).

Tabla de picadillo

La tabla hash es una estructura de datos para una búsqueda rápida. Utiliza funciones hash internamente, de ahí el nombre.

"Las bases de datos usan tablas hash y árboles de búsqueda internamente para acelerar la ejecución de solicitudes de búsqueda"

Picadillo

  1. un tipo de datos abstractos del diccionario

"Hash" es el nombre oficial de los diccionarios integrados en Perl. Son tablas hash internamente, de ahí el nombre. "Esta subrutina acepta un hash como primer argumento". Estos días se pueden usar para cualquier matriz asociativa, no necesariamente una tabla hash.

  1. resultado de aplicar una función hash a alguna entrada

"Se proporcionan hashes MD5 de las imágenes .iso para verificar su integridad después de la descarga".

nponeccop
fuente