¿Por qué no se garantiza que std :: hash sea determinista?

28

En adelante, usamos N4140 (C ++ 14 Standard).

De acuerdo con los requisitos de Hash § 17.6.3.4 ,

El valor devuelto dependerá solo del argumento k durante la duración del programa .

[Nota: por lo tanto, todas las evaluaciones de la expresión h(k)con el mismo valor para kproducir el mismo resultado para una ejecución dada del programa . - nota final]

y § 20.9.12 El hash de plantilla de clase dice

...

la instanciación hash<Key>deberá:

(1.1) - satisface los requisitos de Hash (17.6.3.4) ...

(1.2) - ...

Esto significa que un valor hash de value(es decir, hash<decltype(value)>(value)) puede tomar un valor diferente si reinicia el programa.

¿Pero por qué? Esta limitación no estaba en el Estándar de C ++ 11, sino en el Estándar de C ++ 14, C ++ 17 y C ++ 20. Como usuario (no desarrollador de STL), sería bastante útil si std::hashfuera determinista. ¿Hay alguna dificultad matemática en la implementación de una función hash determinista? Pero las funciones hash que usamos diariamente (por ejemplo, obsoletas md5sumo más seguras sha256) son todas deterministas. ¿Hay algún problema de eficiencia?

c++ hash language-lawyer std ynn
fuente
77
"... las funciones de hash solo se requieren para producir el mismo resultado para la misma entrada dentro de una sola ejecución de un programa; esto permite hashes salados que evitan ataques de denegación de servicio por colisión ". fuente: en.cppreference.com/w/cpp/utility/hash
Richard Critten
55
Permite que un algoritmo determinista tome entradas no deterministas. Valores de puntero, por ejemplo. Una estructura de datos inmutable podría trocear las direcciones de sus datos internos, lo que podría ser mucho más rápido que trocear los contenidos.
John Kugelman
44
Esta respuesta tiene algunos enlaces agradables sobre por qué no querría el determinismo.
NathanOliver
3
No amenace esto como una limitación, pero hacer que las restricciones estándar sean un poco menos estrictas.
Marek R
44
Aquí hay una explicación completa de por qué se han aflojado las restricciones.
Marek R

Respuestas:

17

No es necesario que la función hash sea determinista entre ejecuciones, pero aún puede proporcionar su propio hash, por ejemplo, para contenedores desordenados si es un comportamiento en el que confía.

En cuanto a por qué, cppreference dice:

Las funciones de hash solo se requieren para producir el mismo resultado para la misma entrada dentro de una sola ejecución de un programa; esto permite hashes salados que evitan los ataques de denegación de servicio por colisión.

Si los Hashrequisitos le dicen que sea determinista, entonces no podría proporcionar un hash salado sin romper el requisito.

Aquí está la explicación real de por qué

Geoffroy
fuente
7

Esta respuesta (y enlaces en ella) sugerida por @NathanOliver es finalmente útil. Déjame citar partes importantes.

Para una función hash no criptográfica, es posible calcular previamente entradas masivas con el mismo valor hash para ralentizar algorítmicamente los contenedores desordenados, y resulta en un ataque de denegación de servicio.

(del número 2291. std :: hash es vulnerable al ataque de colisión DoS )

Por esta razón, los diseñadores de idiomas están migrando a hashing aleatorio. En el hash aleatorio, el valor de hash de la cadena "a" puede cambiar cada vez que ejecuta su programa. El hash aleatorio ahora es el predeterminado en Python (a partir de la versión 3.3), Ruby (a partir de la versión 1.9) y Perl (a partir de la versión 5.18).

(de ¿Te das cuenta de que estás usando hashing aleatorio? )

Mover a Listo, en lugar de Inmediato, ya que incluso el permiso ha sido polémico en la discusión del reflector

(del número 2291. std :: hash es vulnerable al ataque de colisión DoS )

En la práctica, hasta donde yo entiendo, no hay implementación de std::hashhash aleatorio de implementos, pero puede escribir el suyo my::secure_hash.

(de esta respuesta )

PD

Acabo de buscar en Google "hash table dos" y encontré una página informativa: el momento en que te das cuenta de que todos los servidores del mundo son vulnerables .

ynn
fuente