thumb|330px|Una función de hash en funcionamientu.
A les funciones resumen tamién se-yos llama funciones hash o funciones digest.H. Tiwari, K. Asawa "Cryptographic Hash Function: An Elevated View", European Journal of Scientific Research, 2010D. Henrici,"Concepts, Protocols, And Architectures". Lectures Notes in Electrical Engineering. Springer-Verlag 2008. Una función hash H ye una función computable por aciu un algoritmu tal que:
Tien como entrada un conxuntu d'elementos, que suelen ser cadenes, y convertir nun rangu de salida finito, de normal cadenes de llargor fixu. Esto ye, la función actúa como una proyeición del conxuntu O sobre'l conxuntu M.
Reparar que M pue ser un conxuntu definíu d'enteros. Nesti casu podemos considerar que'l llargor ye fixa si'l conxuntu ye un rangu de númberos d'enteros yá que podemos considerar que'l llargor fixu ye la del númberu con mayor númberu de cifres. Tolos númberos pueden convertise al númberu especificáu de cifres a cencielles anteponiendo ceros.
De normal el conxuntu O tien un númberu eleváu d'elementos y M ye un conxuntu de cadenes con un númberu más o menos pequeñu de símbolos. La idea básica d'un valor hash ye que sirva como una representación compacta de la cadena d'entrada.
Por esta razón dizse qu'estes funciones resumen datos del conxuntu dominiu.
Oríxenes del términu
El términu hash provién, aparentemente, de l'analoxía col significáu estándar (n'inglés) de dicha pallabra nel mundu real: picar y entemecer. Donald Knuth cree que H. P. Luhn, emplegáu d'IBM, foi'l primeru n'utilizar el conceutu nun memorándum fecháu en xineru de 1953. El so usu masivu nun foi hasta dempués de 10 años.
Terminoloxía acomuñada
Al conxuntu O llámase-y dominiu de la función resumen. A un elementu d'O llámase-y preimagen o dependiendo del contestu clave o mensaxe.
Al conxuntu M llámase-y imaxe de la función hash. A un elementu de M llámase-y valor resumen, códigu hash o a cencielles hash.
Dizse que se produz un choque cuando dos entraes distintes de la función resumen producen la mesma salida. De la definición de función resumen podemos dicir qu'O, el dominiu de la función, puede tener infinitos elementos. Sicasí M, el rangu de la función, tien un númberu finito d'elementos por cuenta de que'l tamañu de les sos cadenes ye fixu. Por tanto la posibilidá d'esistencia de choques ye intrínseca a la definición de función hash. Una bona función resumen ye una que tien pocos choques nel conxuntu esperáu d'entrada. Esto ye, deseyar que la probabilidá de choque seya bien baxa.
Parámetros adicionales
La definición formal dada, dacuando xeneralízase pa poder aprovechar les funciones hash n'otros ámbitos. Pa ello a la función resumen añader nuevos parámetros de forma que'l valor hash nun ye solo función del conteníu en sí, sinón amás d'otros nuevos factores.
Pa topar valores resumen de ficheros dacuando úsense, amás del conteníu en sí, diversos parámetros como'l nome del archivu, el so llargor, hora de creación, etc.
Otres vegaes añaden parámetros que dexen configurar el comportamientu de la función. Por casu, la función resumen puede recibir como parámetru una función de xeneración de valores pseudoaleatorios que ye usada dientro del algoritmu de la función hash.
Otros exemplos de parámetros son l'usu de valores sal, l'usu de claves secretes, l'usu de parámetros qu'especifiquen el rangu de la función (funciones hash de rangu variable), l'usu de parámetros qu'especifiquen el nivel de seguridá que se quier nel valor resumen de salida (funciones hash dinámiques), etc.
Funciones resumen con clave
Una función resumen con clave HK (n'inglés keyed hash function) ye una función resumen H que tien un parámetru secretu K que pertenez al conxuntu posible de claves y na que pa una entrada x, hK(x) ye'l valor resumen de x. Al restu de funciones resumen dizse que son ensin clave (n'inglés unkeyed hash function).
Propiedaes
La calidá d'una función resumen vien definida con base nel prestu de ciertes propiedaes deseables nel contestu nel que se va a usar.
So costu
Calcular el valor hash precisa pocu costu (computacional, de memoria, etc.).
Compresión
Una función hash estrúi dato si puede mapear un dominiu con datos de llargor bien grande a datos con llargor más pequeñu
Uniforme Dizse qu'una función resumen ye uniforme cuando pa una clave escoyida aleatoriamente ye igualmente probable tener un valor resumen determináu, independientemente de cualesquier otru elementu.
Pa una función hash H uniforme del tipu H:{0,1}m→{0,1}n, esto ye: Les cadenes tán construyíes sobre un alfabetu de 2 símbolos (Alfabetu binariu) El dominiu ye'l conxuntu de les cadenes de llargor m El rangu ye'l conxuntu de les cadenes de llargor n podemos dicir qu'a cada resume correspuénde-y 2m-n mensaxes y que la probabilidá de que dos mensaxes dean como resultáu la mesma salida ye 2-n
P'algoritmos de busca, si toles entraes son igualmente probables, búscase esta propiedá pa embrivir el númberu de choques yá que cuantos más choques haya, va ser mayor el tiempu d'execución de les busques.
De rangu variable En delles funciones resumen el rangu de valores resumen pue ser distintu a lo llargo del tiempu. Exemplu: funciones hash usaes pa tables resumen que precisen espandise. Nestos casos a la función hash tien de pasáse-y un parámetru que-y dexe saber en qué rangu mueve la execución pa topar el valor resumen.
Inyectividad y función hash perfecta
Dizse que la función resumen ye inyectiva cuando cada datu d'entrada se mapea a un valor resumen distintu. Nesti casu dizse que la función resumen ye perfecta. Por que se dea, ye necesariu que la cardinalidad del conxuntu dominiu seya inferior o igual a la cardinalidad del conxuntu imaxe. De normal, namái se dan funciones hash perfectes cuando les entraes tán preestablecidas. Exemplu: mapear los díes del añu en númberos del 1 al 366 según l'orde d'apaición.
Formalización:
implica
Cuando nun se cumple la propiedá de inyectividad dizse qu'hai choques. Hai un choque cuando y .
Determinista
Una función hash dizse que ye determinista cuando dada una cadena d'entrada siempres devuelve'l mesmu valor hash. Esto ye, el valor hash ye la resultancia d'aplicar un algoritmu qu'opera solu sobre la cadena d'entrada. Exemplos de funciones hash non deterministes son aquelles funciones hash que dependen de parámetros esternos, tales como xeneradores de númberos pseudoaleatorios o la fecha. Tampoco son deterministes aquelles funciones hash que dependen de la direición de memoria na que ta almacenada la cadena d'entrada. Esa direición ye accidental y nun se considera un cambéu de la cadena entrada en sí. De fechu puede camudar dinámicamente mientres la mesma execución del algoritmu de la función hash.
Propiedaes p'analizar la resistencia frente a choques L'estudiu d'esti tipu de propiedaes ye bien útil nel campu de la criptografía pa los llamaos 'código de detección de cambeos'.
Resistencia a la primera preimagen
Dizse qu'una función resumen tien resistencia a la primera preimagen o a cencielles que tien resistencia a preimagen (del inglés preimage-resistant) si, dau un valor hash y, ye computacionalmente intratable atopar x tal que h(x)=y.
Resistencia a la segunda preimagen
A. J. Menezes et all, "Handbook of Applied Cryptography", CRC Press 2011Dizse qu'una función resumen tien resistencia a la segunda preimagen (n'inglés second preimage-resistant) si dau un mensaxe x, ye computacionalmente intratable atopar un x', , tal que h(x)=h(x').
Resistencia a choques (CRHF)
Dizse qu'una función hash tien resistencia a choques o que ye resistente a choques o CRHF (del inglés Collision Resistant Hash Function) si atopar un par con tal que ye computacionalmente intratable. Esto ye, ye difícil atopar dos entraes que tengan el mesmu valor resumen.
Como atopar una segunda preimagen nun puede ser más fácil qu'atopar un choque, entós la resistencia a choques inclúi la propiedá de resistencia a la segunda preimagen.Bart Preneel,"The State of Cryptographic Hash functions.I. B. Damgard, "Collision free hash functions and public key signatures schemes". Advances in Cryptology- Crypto'89. LNCS 304 pages 203-216. Springer 1987 Per otru llau puede dicise que la mayoría de les funciones resumen CRHF son resistentes a preimagen. La resistencia a choques implica resistencia a preimagen pa funciones hash con salida aleatoria uniforme.Kazumaro Aoki, Yu Sasaki, "Meet in the midle preimage attacks against reduced SHA-0 and SHA-1"
En dellos trabayos a estes funciones llámase-yos funciones resumen d'un solu sentíu fuertes (del inglés strong one way hash function) pa resaltar que ye fuerte por cuenta de qu'hai llibre eleición de los dos valores x y y.
Función resumen d'un solu sentíu (OWHF) H. Tiwari et all, "Cryptographic Hash Function:An elevated View", European Jorunal of Scientific Research, Vol 43 páxs.452-465. 2010Una función hash dizse que ye una función resumen d'un solu sentíu o que ye OWHF (del inglés One-Way Hash Function) si tien les propiedaes de resistencia a preimagen y de resistencia a segunda preimagen. Esto ye, ye difícil atopar una entrada que la so hash seya un valor resumen preespecificado.
Reparar que ye distintu a la definición xeneral que se fai de funciones d'un solu sentíu:
Una función dizse que ye una función d'un solu sentíu o que ye OWF si pa cada x del dominiu de la función, ye fácil computar f(x), pero pa tou y del rangu de f, ye computacionalmente intratable atopar cualesquier x tal que y=f(x).
La diferencia ente OWHF y OWF ye que OWF nun riquir que seya función resumen nin que seya resistente a segunda preimagen.
En dellos trabayos a estes funciones llámase-yos funciones hash d'un solu sentíu débiles (del inglés weak one way hash function) pa resaltar que ye débil en contraste con CRHF (que ye fuerte) por cuenta de que a los cumplir la propiedá de resistencia a segunda preimagen nun hai llibre eleición na selección del valor x, y por tanto del valor h(x), nel que se tien que producir el choque.
Resistencia al cuasi choque W. R. Speirs,"Dynamic cryptographic hash functions", Thesis. Purdue University School.2007H ye resistente al cuasi choque (n'inglés near-colission resistance) si ye difícil atopar dos mensaxes y con pa les cualos les sos imáxenes y difieran solamente nunos pocos bits.
Peter Stavroulakis et all,"Handbook of Information and Communication Security", Spring 2010Por casu podemos tener una función resistente a choques de 256 bits que nun ye resistente al cuasi choque porque pueden atopase cuasi-choques pa los 224 bits de más a la izquierda.
Funciones con choques de hash parciales Son funciones nes qu'invirtiendo ciertu costu en procesamientu de CPU y memoria ye posible atopar en tiempos razonables dos entraes que produzan resultaos nos que los sos bits paecer en ciertu grau. Por casu que se paezan nun porcentaxe de bits, o más comúnmente que sían iguales ye los n-bits más significativos.
Por casu con SHA1 pa consiguir un choque total con fuercia bruto precisaríamos comprobaciones o siquier usando la paradoxa del cumpleaños. Sicasí si vamos amenorgando'l númberu de bits más significativos que tienen que coincidir, el númberu de comprobaciones va baxando pasu ente pasu.
Funciones resumen con esta propiedá usar en sistemes de prueba de trabayu, como Hashcash o Bitcoin pa consiguir les pruebes de trabayu.
Resistencia a les preimágenes parciales
Dirk Henric,"RFID security and privacy: concepts, protocols, and architectures", Springer 2008Una función resumen tien resistencia a preimágenes parciales (n'inglés Partial-preimage resistance) si ye difícil atopar una parte de la preimagen d'un valor hash inclusive conociendo'l restu de la preimagen. Esto ye, débese recurrir a encomalo bruta: si desconócense t bits de la preimagen, tienen de realizase en permediu 2n-t operaciones de hash atopalo.