Pourquoi std :: hash n'est-il pas garanti d'être déterministe?

28

Ci-après, nous utilisons N4140 (C ++ 14 Standard).

Conformément au § 17.6.3.4 Exigences de hachage ,

La valeur renvoyée ne dépendra que de l'argument k de la durée du programme .

[Remarque: Ainsi, toutes les évaluations de l'expression h(k)avec la même valeur pour kdonnent le même résultat pour une exécution donnée du programme . - note de fin]

et le § 20.9.12 Hachage du modèle de classe dit

...

l'instanciation hash<Key>doit:

(1.1) - satisfaire aux exigences de hachage (17.6.3.4) ...

(1.2) - ...

Cela signifie qu'une valeur de hachage value(c.-à-d. hash<decltype(value)>(value)) Peut prendre une valeur différente si vous redémarrez le programme.

Mais pourquoi? Cette limitation ne se trouvait pas dans la norme C ++ 11, mais dans la norme C ++ 14, C ++ 17 et C ++ 20. En tant qu'utilisateur (pas un développeur STL), il serait très utile s'il std::hashétait déterministe. Y a-t-il des difficultés mathématiques à implémenter une fonction de hachage déterministe? Mais les fonctions de hachage que nous utilisons quotidiennement (par exemple obsolètes md5sumou plus sûres sha256) sont toutes déterministes. Y a-t-il un problème d'efficacité?

c++ hash language-lawyer std ynn
la source
7
"... Les fonctions de hachage ne sont nécessaires que pour produire le même résultat pour la même entrée dans une seule exécution d'un programme; cela permet des hachages salés qui empêchent les attaques par déni de service par collision ." source: en.cppreference.com/w/cpp/utility/hash
Richard Critten
5
Il permet à un algorithme déterministe de prendre des entrées non déterministes. Les valeurs du pointeur, par exemple. Une structure de données immuable pourrait hacher les adresses de ses données internes, ce qui pourrait être beaucoup plus rapide que le hachage du contenu.
John Kugelman
4
Cette réponse contient de bons liens pour savoir pourquoi vous ne voudriez pas du déterminisme.
NathanOliver
3
Ne menacez pas cela comme une limitation, mais en rendant les contraintes standard un peu moins strictes.
Marek R
4
Voici une explication complète pour laquelle les contraintes ont été assouplies.
Marek R

Réponses:

17

Il n'est pas nécessaire que la fonction de hachage soit déterministe entre les exécutions, mais vous pouvez toujours fournir votre propre hachage, par exemple pour les conteneurs non ordonnés si c'est un comportement sur lequel vous comptez.

Quant à savoir pourquoi, cppreference dit:

Les fonctions de hachage ne sont nécessaires que pour produire le même résultat pour la même entrée dans une seule exécution d'un programme; cela permet des hachages salés qui empêchent les attaques par déni de service par collision.

Si les Hashexigences indiquent qu'il est déterministe, vous ne pourrez pas fournir un hachage salé sans casser l'exigence.

Voici l' explication réelle pourquoi

Geoffroy
la source
7

Cette réponse (et les liens qu'elle contient ) suggérée par @NathanOliver est finalement utile. Permettez-moi de citer des parties importantes.

Pour une fonction de hachage non cryptographique, il est possible de pré-calculer des entrées massives avec la même valeur de hachage pour ralentir algorithmiquement les conteneurs non ordonnés, et entraîne une attaque par déni de service.

(à partir du numéro 2291. std :: hash est vulnérable aux attaques par collision DoS )

Pour cette raison, les concepteurs de langage migrent vers le hachage aléatoire. Dans le hachage aléatoire, la valeur de hachage de la chaîne «a» peut changer à chaque fois que vous exécutez votre programme. Le hachage aléatoire est désormais la valeur par défaut en Python (à partir de la version 3.3), Ruby (à partir de la version 1.9) et Perl (à partir de la version 5.18).

(de Réalisez-vous que vous utilisez le hachage aléatoire? )

Passez à Prêt, plutôt qu'immédiat, car même l'autorisation a été controversée dans la discussion du réflecteur

(à partir du numéro 2291. std :: hash est vulnérable aux attaques par collision DoS )

En pratique, pour autant que je sache, aucune std::hashimplémentation n'implémente le hachage aléatoire mais vous pouvez écrire le vôtre my::secure_hash.

(à partir de cette réponse )

PS

Je viens de googler "table de hachage dos" et trouvé une page informative: Le moment où vous réalisez que chaque serveur dans le monde est vulnérable .

ynn
la source