Función hash no criptográfica

Las funciones hash no criptográficas ( NCHF ^{[ 1 ]} ) son funciones hash destinadas a aplicaciones que no requieren los rigurosos requisitos de seguridad de las funciones hash criptográficas (por ejemplo, resistencia a la preimagen ) y, por lo tanto, pueden ser más rápidas y consumir menos recursos. ^{[ 2 ]} Ejemplos típicos de funciones hash no criptográficas optimizadas para CPU incluyen FNV-1a y Murmur3 . ^{[ 3 ]} Algunas funciones hash no criptográficas se utilizan en aplicaciones criptográficas (generalmente en combinación con otras primitivas criptográficas); en este caso se describen como funciones hash universales . ^{[ 4 ]}

Entre los usos típicos de las funciones hash no criptográficas se encuentran los filtros bloom , las tablas hash y los bocetos de conteo . Estas aplicaciones requieren, además de velocidad, una distribución uniforme y propiedades de avalancha . ^{[ 3 ]} La resistencia a colisiones es una característica adicional que puede ser útil contra ataques de inundación de hash ; las NCHF simples, como la verificación de redundancia cíclica (CRC), prácticamente no tienen resistencia a colisiones ^{[ 5 ]} y, por lo tanto, no se pueden usar con una entrada susceptible de manipulación por parte de un atacante.

Los NCHF se utilizan en diversos sistemas: analizadores léxicos , compiladores , bases de datos , redes de comunicación , videojuegos, servidores DNS , sistemas de archivos ; en cualquier ámbito de la informática donde sea necesario encontrar la información muy rápidamente (preferiblemente en tiempo O(1) , lo que también permitirá una escalabilidad perfecta ). ^{[ 6 ]}

Estébanez et al. enumere los FCNH "más importantes": ^{[ 7 ]}

• La función hash Fowler-Noll-Vo (FNV) fue creada por Glenn Fowler y Phong Vo en 1991 con contribuciones de Landon Curt Noll . FNV, con sus dos variantes, FNV-1 y FNV-1a, se utiliza ampliamente en Linux , sistemas operativos FreeBSD , servidores DNS, NFS , Twitter , PlayStation 2 y Xbox , entre otros.
• lookup3 fue creado por Robert Jenkins . Este hash también es ampliamente utilizado y se puede encontrar en PostgreSQL , Linux, Perl , Ruby e Infoseek .
• SuperFastHash fue creado por Paul Hsieh utilizando ideas de FNV y lookup3, con el objetivo de lograr un alto grado de efecto avalancha. Este hash se utiliza en WebKit (parte de Safari y Google Chrome ).
• MurmurHash 2 fue creado por Austin Appleby en 2008 y se utiliza en libmemcached , Maatkit y Apache Hadoop .
• DJBX33A ("Daniel J. Bernstein, Multiplicador 33 con Suma"). Esta función de multiplicación y suma, muy sencilla, fue propuesta por Daniel J. Bernstein . Es rápida y eficiente durante la inicialización. Muchos entornos de programación basados ​​en PHP 5 , Python y ASP.NET utilizan variantes de este hash. El hash es fácil de saturar , exponiendo los servidores.
• BuzHash fue creado por Robert Uzgalis en 1992. Está diseñado en torno a una tabla de sustitución y puede tolerar distribuciones extremadamente asimétricas en la entrada.
• DEK es una función hash multiplicativa temprana basada en una propuesta de Donald Knuth y es una de las funciones hash más antiguas que todavía se utiliza.

Las funciones hash no criptográficas optimizadas para software frecuentemente implican la operación de multiplicación. Dado que la multiplicación en hardware consume muchos recursos y limita la frecuencia, se han propuesto diseños más compatibles con ASIC , incluyendo SipHash (que tiene el beneficio adicional de poder usar una clave secreta para la autenticación de mensajes ), NSGAhash y XORhash. Aunque técnicamente la criptografía ligera puede usarse para las mismas aplicaciones, la latencia de sus algoritmos suele ser demasiado alta debido a la gran cantidad de rondas . ^{[ 3 ]} Sateesan et al. proponen usar versiones de rondas reducidas de hashes y cifrados ligeros como funciones hash no criptográficas. ^{[ 2 ]}

Muchos NCHF tienen un tamaño de resultado relativamente pequeño (por ejemplo, 64 bits para SipHash o incluso menos): un tamaño de resultado grande no aumenta el rendimiento de las aplicaciones de destino, sino que ralentiza el cálculo, ya que se necesitan generar más bits. ^{[ 8 ]}

• Sateesan, Arish; Biesmans, Jelle; Claesen, Thomas; Vliegen, Jo; Mentens, Nele (abril de 2023). "Algoritmos y arquitecturas optimizadas para funciones hash rápidas no criptográficas en hardware" (PDF) . Microprocessors and Microsystems . 98 104782. doi : 10.1016/j.micpro.2023.104782 . ISSN 0141-9331 . 
• Estébanez, César; Sáez, Yago; Recio, Gustavo; Isasi, Pedro (28 de enero de 2013). «Rendimiento de las funciones hash no criptográficas más comunes» (PDF) . Software: práctica y experiencia . 44 (6): 681– 698. doi : 10.1002/spe.2179 . ISSN 0038-0644 . 
• Stamp, Mark (8 de noviembre de 2011). «Hashes no criptográficos» . Seguridad de la información: principios y práctica (2.ª  ed.). John Wiley & Sons. ISBN 978-1-118-02796-7OCLC 1039294381​​ 
• Patgiri, Ripon; Nayak, Sabuzima; Muppalaneni, Naresh Babu (25 de abril de 2023). Filtro de Bloom: una estructura de datos para redes informáticas, macrodatos, computación en la nube, Internet de las cosas, bioinformática y más allá . Academic Press. págs. 37–38 . ISBN  978-0-12-823646-8OCLC 1377693258​​ 
• Mittelbach, Arno; Fischlin, Marc (2021). «Hashing no criptográfico». La teoría de las funciones hash y los oráculos aleatorios . Cham: Springer International Publishing. pp. 303–334 . doi : 10.1007/978-3-030-63287-8_7 . ISBN  978-3-030-63286-1.