thumb|330px|Una función de hash en funcionamiento. Una función resumen, en inglés , también conocida con los híbridos función hash o función de hash, convierte uno o varios elementos de entrada a una función en otro elemento. También se las conoce como función extracto, del inglés , función de extractado y por el híbrido función digest.

Una función hash H es una función computable mediante un algoritmo tal que:

La función hash tiene como entrada un conjunto de elementos, que suelen ser cadenas, y los convierte en un rango de salida finito, normalmente cadenas de longitud fija. Es decir, la función actúa como una proyección del conjunto U sobre el conjunto M.

Hay que tener en cuenta que M puede ser un conjunto definido de enteros. En este caso, podemos considerar que la longitud es fija si el conjunto es un rango de números de enteros, ya que podemos considerar que la longitud fija es la del número con mayor cantidad de cifras. Cabe destacar que es posible convertir todos los números a una cantidad específica de cifras simplemente anteponiendo ceros.

Normalmente el conjunto U tiene un número elevado de elementos y M es un conjunto de cadenas con un número acotado de símbolos. La idea básica de un valor hash es que sirva como una representación compacta de la cadena de la entrada. Por esta razón, se dice que estas funciones permiten resumir datos del conjunto dominio.

Orígenes del término El término hash proviene, aparentemente, de la analogía con el significado estándar (en inglés) de dicha palabra en el mundo real: «picar y mezclar». Donald Knuth cree que H. P. Luhn, empleado de IBM, fue el primero en utilizar el concepto en un memorándum fechado en enero de 1953, aunque su utilización masiva no se produjo hasta después de 10 años.

Terminología asociada Al conjunto U se le llama dominio de la función hash. A un elemento de U se le llama preimagen o, dependiendo del contexto, clave o mensaje. Al conjunto M se le llama imagen de la función hash. A un elemento de M se le llama valor resumen, código hash o simplemente hash.

Se dice que se produce una colisión cuando dos entradas distintas de la función resumen producen la misma salida. De la definición de función resumen podemos decir que U, el dominio de la función, puede tener infinitos elementos. Sin embargo M, el rango de la función, tiene un número finito de elementos debido a que el tamaño de sus cadenas es fijo. Por tanto la posibilidad de existencia de colisiones es intrínseca a la definición de función hash. Una buena función resumen es una que tiene pocas colisiones en el conjunto esperado de entrada. Es decir, se desea que la probabilidad de colisión sea muy baja.

Parámetros adicionales La definición formal dada, a veces se generaliza para poder aprovechar las funciones hash en otros ámbitos. Para ello a la función resumen se le añaden nuevos parámetros de forma que el valor hash no es solo función del contenido en sí, sino además de otros nuevos factores.

Para hallar valores resumen de ficheros a veces se usan, además del contenido en sí, diversos parámetros como el nombre del archivo, su longitud, hora de creación, etc.

Otras veces se añaden parámetros que permiten configurar el comportamiento de la función. Por ejemplo, la función resumen puede recibir como parámetro una función de generación de valores pseudoaleatorios que es usada dentro del algoritmo de la función hash.

Otros ejemplos de parámetros son el uso de valores sal, el uso de claves secretas, el uso de parámetros que especifican el rango de la función (funciones hash de rango variable), el uso de parámetros que especifican el nivel de seguridad que se quiere en el valor resumen de salida (funciones hash dinámicas), etc.

Funciones resumen con clave Una función resumen con clave HK () es una función resumen H que tiene un parámetro secreto K que pertenece al conjunto posible de claves y en la que para una entrada x, hK(x) es el valor resumen de x. Al resto de funciones resumen se dice que son sin clave ().

Propiedades La calidad de una función resumen viene definida con base en la satisfacción de ciertas propiedades deseables en el contexto en el que se va a usar.

Bajo costo Calcular el valor hash necesita poco costo (computacional, de memoria, etc.).

Compresión Una función hash comprime datos si puede mapear un dominio con datos de longitud muy grande a datos con longitud más pequeña

Uniforme Se dice que una función resumen es uniforme cuando para una clave elegida aleatoriamente es igualmente probable tener un valor resumen determinado, independientemente de cualquier otro elemento.

Para una función hash H uniforme del tipo H:{0,1}m→{0,1}n, es decir: Las cadenas están construidas sobre un alfabeto de 2 símbolos (Alfabeto binario) El dominio es el conjunto de las cadenas de longitud m El rango es el conjunto de las cadenas de longitud n podemos decir que a cada resumen le corresponden 2m-n mensajes y que la probabilidad de que dos mensajes den como resultado la misma salida es 2-n

Para algoritmos de búsqueda, si todas las entradas son equiprobables, se busca esta propiedad para minimizar el número de colisiones, ya que, cuantas más colisiones haya, mayor será el tiempo de ejecución de las búsquedas.

De rango variable En algunas funciones resumen el rango de valores resumen puede ser diferente a lo largo del tiempo. Ejemplo: funciones hash usadas para tablas resumen que necesitan expandirse. En estos casos a la función hash se le debe pasar un parámetro que le permita saber en qué rango se mueve la ejecución para hallar el valor resumen.

Inyectividad y función hash perfecta

Se dice que la función resumen es inyectiva cuando cada dato de entrada se mapea a un valor resumen diferente. En este caso se dice que la función resumen es perfecta. Para que se dé, es necesario que la cardinalidad del conjunto dominio sea inferior o igual a la cardinalidad del conjunto imagen. Normalmente, sólo se dan funciones hash perfectas cuando las entradas están preestablecidas. Ejemplo: mapear los días del año en números del 1 al 366 según el orden de aparición.

Formalización:

implica

Cuando no se cumple la propiedad de inyectividad, se dice que hay colisiones. Hay una colisión cuando y .

Determinista

Una función hash se dice que es determinista cuando dada una cadena de entrada siempre devuelve el mismo valor hash. Es decir, el valor hash es el resultado de aplicar un algoritmo que opera solo sobre la cadena de entrada. Ejemplos de funciones hash no deterministas son aquellas funciones hash que dependen de parámetros externos, tales como generadores de números pseudoaleatorios o la fecha. Tampoco son deterministas aquellas funciones hash que dependen de la dirección de memoria en la que está almacenada la cadena de entrada. Esa dirección es accidental y no se considera un cambio de la cadena entrada en sí. De hecho puede cambiar dinámicamente durante la propia ejecución del algoritmo de la función hash.

Propiedades para analizar la resistencia frente a colisiones El estudio de este tipo de propiedades es muy útil en el campo de la criptografía para los llamados 'códigos de detección de modificaciones'.

Resistencia a la primera preimagen

Se dice que una función resumen tiene resistencia a la primera preimagen o simplemente que tiene resistencia a preimagen () si, dado un valor hash y, es computacionalmente inviable encontrar x tal que h(x)=y.

Resistencia a la segunda preimagen

Se dice que una función resumen tiene resistencia a la segunda preimagen () si dado un mensaje x, es computacionalmente inviable encontrar un x', , tal que h(x)=h(x').

Resistencia a colisiones (CRHF) Se dice que una función hash tiene resistencia a colisiones o que es resistente a colisiones (, CRHF) si encontrar un par con tal que es computacionalmente inviable. Es decir, es difícil encontrar dos entradas que tengan el mismo valor resumen.

Como encontrar una segunda preimagen no puede ser más fácil que encontrar una colisión, entonces la resistencia a colisiones incluye la propiedad de resistencia a la segunda preimagen. Por otro lado, se puede decir que la mayoría de las funciones resumen CRHF son resistentes a preimagen. La resistencia a colisiones implica resistencia a preimagen para funciones hash con salida aleatoria uniforme.

En algunos trabajos a estas funciones se les llama funciones resumen de un solo sentido fuertes () para resaltar que es fuerte debido a que hay libre elección de los dos valores x e y.

Función resumen de un solo sentido (OWHF) Una función hash se dice que es una función resumen de un solo sentido (, OWHF) si tiene las propiedades de resistencia a preimagen y de resistencia a segunda preimagen. Es decir, es difícil encontrar una entrada cuya hash sea un valor resumen preespecificado.

Nótese que es diferente a la definición general que se hace de funciones de un solo sentido.

Una función se dice que es una función de un solo sentido (OWF) si para cada x del dominio de la función, es fácil computar f(x), pero para todo y del rango de f, es computacionalmente inviable encontrar cualquier x tal que f(x)=y.

La diferencia entre OWHF y OWF es que OWF no requiere que sea función resumen ni que sea resistente a segunda preimagen.

En algunos trabajos a estas funciones se les llama funciones hash de un solo sentido débiles () para resaltar que es débil en contraste con CRHF (que es fuerte) debido a que al cumplir la propiedad de resistencia a segunda preimagen no hay libre elección en la selección del valor x, y por tanto del valor h(x), en el que se tiene que producir la colisión.

Resistencia a la casi colisión H es resistente a la casi colisión () si es difícil encontrar dos mensajes y con para las cuales sus imágenes y difieran solamente en unos pocos bits.

Por ejemplo, podemos tener una función resistente a colisiones de 256 bits que no es resistente a la casi colisión porque se pueden encontrar casi-colisiones para los 224 bits de más a la izquierda.

Funciones con colisiones de hash parciales Son funciones en las que invirtiendo cierto coste en procesamiento de CPU y memoria es posible encontrar en tiempo razonable dos entradas que produzcan resultados en los que sus bits se parezcan en cierto grado. Por ejemplo, que se parezcan en un porcentaje de bits, o más comúnmente que sean iguales en los n bits más significativos.

Por ejemplo, con SHA1, para conseguir una colisión total con fuerza bruta, necesitaríamos comprobaciones o al menos usando la paradoja del cumpleaños. Sin embargo, si vamos reduciendo el número de bits más significativos que tienen que coincidir, el número de comprobaciones va bajando paulatinamente.

Resistencia a las preimágenes parciales

Una función resumen tiene resistencia a preimágenes parciales () si es difícil encontrar una parte de la preimagen de un valor hash incluso conociendo el resto de la preimagen. Es decir, se debe recurrir a la fuerza bruta: si se desconocen t bits de la preimagen, se deben realizar en promedio 2n-t operaciones de hash para encontrarlo.

A una función resumen resistente a preimágenes parciales también se le dice que es localmente de un solo sentido ().

Con normalización de datos

En algunas aplicaciones, las cadenas de entrada pueden contener características que son irrelevantes cuando comparamos las cadenas. Por ejemplo en algunas aplicaciones las mayúsculas pueden ser irrelevantes. Por tanto para hallar el valor hash es interesante ignorar las distinciones no relevantes entre las cadenas de entrada. De esta forma, cadenas distintas con diferencias no relevantes tienen asociados valores hash iguales.

Continuidad y efecto avalancha

Se dice que una función resumen es continua cuando una modificación minúscula (ej un bit) en la cadena de entrada ocasiona pequeños cambios en el valor hash.