Función hash no criptográfica

Las funciones hash no criptográficas ( NCHF ^[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 la 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 , Murmur3 . ^[3]

Aplicaciones y requisitos

Entre los usos típicos de las funciones hash no criptográficas se encuentran los filtros de floración , las tablas hash y los bocetos de conteo . Estas aplicaciones requieren, además de velocidad, 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 ; Los NCHF simples, como la verificación de redundancia cíclica (CRC), esencialmente no tienen resistencia a la colisión ^[4] y, por lo tanto, no pueden usarse 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 sea necesario encontrar la información muy rápidamente (preferiblemente en el tiempo O(1) , lo que también conseguir una escalabilidad perfecta ). ^[5]

Estébanez et al. enumere los FNC "más importantes": ^[6]

• 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 utilizado en software que abarca desde sistemas operativos Linux y FreeBSD , servidores DNS, NFS hasta Twitter , PlayStation2 y consola Xbox ;
• lookup3 fue creado por Robert Jenkins . Hash también se usa ampliamente y se puede encontrar en PostgreSQL , Linux, Perl , Ruby e Infoseek ;
• SuperFastHash fue creado por Paul Hsieh utilizando ideas de FNV y lookup3, siendo uno de los objetivos el alto grado de efecto de avalancha. El 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, Times 33 con adición"). Esta función de multiplicación y suma muy simple fue propuesta por Daniel J. Bernstein . Es rápido y eficiente durante la inicialización. Muchos entornos de programación basados ​​en PHP 5 , Python , 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 un hash multiplicativo temprano basado en la propuesta de Donald E. Knuth , siendo uno de los hash más antiguos que todavía se utilizan.

Diseño

Las funciones hash no criptográficas optimizadas para software frecuentemente implican la operación de multiplicación. Dado que en el hardware la multiplicación consume muchos recursos y limita la frecuencia, se propusieron diseños más amigables con ASIC , incluido 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 se puede utilizar para las mismas aplicaciones, la latencia de sus algoritmos suele ser demasiado alta debido a la gran cantidad de rondas . ^[3] Sateesan et al. proponemos utilizar las versiones de ronda reducida de los cifrados y hashes 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, pero ralentiza el cálculo, ya que es necesario generar más bits. ^[7]

Ver 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. Sello 2011.
5. Estébanez et al. 2013, pág. 1.
6. Estébanez et al. 2013, págs. 3–4.
7. 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 no criptográficas rápidas en hardware". Microprocesadores y Microsistemas . 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.
• Sello, Mark (8 de noviembre de 2011). "Hashes no criptográficos". Seguridad de la información: principios y práctica (2 ed.). John Wiley e hijos. ISBN 978-1-118-02796-7. OCLC  1039294381.
• Patgiri, Ripón; Nayak, Sabuzima; Muppalaneni, Naresh Babu (25 de abril de 2023). Filtro Bloom: una estructura de datos para redes de computadoras, big data, computación en la nube, Internet de las cosas, bioinformática y más. Prensa académica. págs. 37–38. ISBN 978-0-12-823646-8. OCLC  1377693258.