¿Existe un algoritmo de hash que pueda calcular de manera eficiente los hashes de datos concatenados?
Digamos que tenemos una función hash H y dos cadenas de bytes a y b (pueden ser largas, por ejemplo, de varios MiB, por lo que queremos evitar volver a calcular su hash). Ya conocemos el valor de H(a) y H(b), y queremos calcular H(a ++ b) (el hash de las dos cadenas concatenadas).
Nos gustaría tener una función F que pueda calcular H(a ++ b) a partir de H(a), H(b) y cualquier otra propiedad de a y b que podamos calcular de antemano (por ejemplo, longitudes), y que tome menos tiempo que simplemente calcular el hash de la cadena completa.
La función hash H no necesita ser criptográfica, pero debería ser lo suficientemente buena para HashMaps u usos similares.
¿Existen funciones H y F así? ¿O qué debería buscar/investigar si quisiera saber eso?
Actualización 2022.01
Después de investigar un poco más, parece que lo que estoy buscando es una función hash que pueda ser atacada utilizando una variante de un ataque de extensión de longitud que ni siquiera necesita conocer el valor completo del valor inyectado.
davy.ai
Hay funciones hash que admiten la propiedad de poder calcular el hash de cadenas concatenadas sin volver a calcular el hash de toda la cadena. Un ejemplo de ello es la construcción de Merkle-Damgård que se utiliza en funciones hash populares como MD5 y SHA-1.
En esta construcción, la cadena de entrada se divide en bloques y cada bloque se hash por separado. La función hash toma la salida del hash del bloque anterior como entrada junto con los datos del bloque actual. La salida final es el hash de toda la cadena concatenada.
Para calcular
H(a ++ b)utilizando esta construcción y los valores conocidosH(a)yH(b), podemos seguir los siguientes pasos:ayben bloques de tamaño fijo (determinado por la función hash).abloque por bloque utilizando el valor conocidoH(a)como entrada para el primer bloque.bbloque por bloque utilizando el valor conocidoH(b)como entrada para el primer bloque.ayb.Este método evita recalcular el hash de toda la cadena y en su lugar calcula el hash de cada bloque por separado, lo que lo hace más rápido que recalcular el hash de toda la cadena concatenada.
Es importante tener en cuenta que las funciones hash utilizadas con fines criptográficos no deberían ser vulnerables a ataques de extensión de longitud. Sin embargo, para fines no criptográficos como los HashMaps, las funciones hash basadas en la construcción de Merkle-Damgård se utilizan comúnmente.
En resumen, para encontrar una función hash que admita la concatenación de valores hash sin recalcular el hash de toda la cadena, se pueden buscar funciones hash que utilicen la construcción de Merkle-Damgård o métodos similares.