Función hash no criptográfica

Las funciones hash no criptográficas ( NCHFs ^[1] ) son funciones hash destinadas a aplicaciones que no necesitan los rigurosos requisitos de seguridad de las funciones hash criptográficas (por ejemplo, resistencia a preimagen ) y, por lo tanto, pueden ser más rápidas y consumir menos recursos. ^[2] Los ejemplos típicos de hashes no criptográficos optimizados 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]

Solicitudes y requisitos

Entre los usos típicos de las funciones hash no criptográficas se encuentran los filtros bloom , las tablas hash y los bosquejos de recuento . Estas aplicaciones requieren, además de velocidad, propiedades de distribución uniforme y 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), esencialmente no tienen resistencia a colisiones ^[5] y, por lo tanto, no se pueden usar con una entrada abierta a la 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 lugar de la informática donde exista la necesidad de encontrar la información muy rápidamente (preferiblemente en el tiempo O(1) , lo que también permitirá lograr 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, es muy utilizada en Linux , sistemas operativos FreeBSD , servidores DNS, NFS , Twitter , PlayStation2 y consola Xbox , entre otros.
• lookup3 fue creado por Robert Jenkins . Este hash también se usa ampliamente y se puede encontrar en PostgreSQL , Linux, Perl , Ruby e Infoseek .
• SuperFastHash fue creado por Paul Hsieh usando ideas de FNV y lookup3, con uno de los objetivos de lograr un alto grado de efecto avalancha. El hash se usa 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, Multiplicar 33 veces con adición"). Esta función de multiplicación y adición muy simple 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 inundar , 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 sesgadas en la entrada.
• DEK es uno de los primeros hashes multiplicativos basados ​​en una propuesta de Donald E. Knuth y es uno de los hashes más antiguos que todavía se utiliza.

Diseño

Las funciones hash no criptográficas optimizadas para software con frecuencia 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 , incluidos SipHash (que tiene el beneficio adicional de poder usar una clave secreta para la autenticación de mensajes ), NSGAhash y XORhash. Aunque técnicamente se puede utilizar criptografía ligera para las mismas aplicaciones, la latencia de sus algoritmos suele ser demasiado alta debido a una gran cantidad de rondas . ^[3] Sateesan et al. proponen utilizar las versiones de ronda reducida 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 es necesario generar más bits. ^[8]

Véase también

• Una lista de funciones hash no criptográficas

Referencias

1. Estébanez et al. 2013.
2. Sateesan et al. 2023, pág. 1.
3. Sateesan et al. 2023, pág. 2.
4. Mittelbach & Fischlin 2021, pág. 303.
5. Sello 2011.
6. Estébanez et al. 2013, pág. 1.
7. Estébanez et al. 2013, págs. 3–4.
8. Patgiri, Nayak y Muppalaneni 2023, págs.

Fuentes

• Sateesan, Arish; Biesmans, Jelle; Claesen, Thomas; Vliegen, Jo; Mentens, Nele (abril de 2023). "Algoritmos y arquitecturas optimizados para funciones hash rápidas no criptográficas en hardware". Microprocesadores y microsistemas . 98 : 104782. doi :10.1016/j.micpro.2023.104782. ISSN  0141-9331.
• Estébanez, César; Saez, Yago; Recio, Gustavo; Isasi, Pedro (28 enero 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.ª edición). John Wiley & Sons. ISBN 978-1-118-02796-7.OCLC 1039294381  .
• Patgiri, Ripon; Nayak, Sabuzima; Muppalaneni, Naresh Babu (25 de abril de 2023). Filtro Bloom: una estructura de datos para redes informáticas, big data, computación en la nube, Internet de las cosas, bioinformática y más. Academic Press. págs. 37–38. ISBN 978-0-12-823646-8.OCLC 1377693258  .
• Mittelbach, Arno; Fischlin, Marc (2021). "Hash no criptográfico". La teoría de las funciones hash y los oráculos aleatorios . Cham: Springer International Publishing. págs. 303–334. doi :10.1007/978-3-030-63287-8_7. ISBN 978-3-030-63286-1.