Python utilise cette solution et décide de changer sa fonction de hachage pour Murmur.
Peut-être que Murmur a été discuté, mais Python ne l'utilise pas. La modification apportée à Python est d'ajouter un secret qui est utilisé dans la fonction de hashage (DJBX31A modifié pour utiliser ce secret). Le secret est un nombre de 64 ou 128 bits (2 long en C). Il a été montré qu'en pratique, on obtient seulement 256 fonctions de hashage différentes (au lieu de 264 ou 2128 ). Dans Python 3.3, le secret est généré aléatoirement à chaque exécution. Dans les versions précédentes, il faut utiliser une option en ligne de commande ou une variable d'environement pour rendre la fonction de hachage aléatoire (que le secret soit généré et utilisé).
Pour améliorer la sécurité, Python 3.4 utilise désormais SipHash qui est plus difficile à casser (clé plus grande, construction cryptographique, etc.). Je n'ai pas entendu d'attaque sur SipHash pour le moment.
Changer complètement l'implémentation du type dict de Python a également été discuté. Martin von Loewis a par exemple proposé le type "AVL tree" (avec une implémentation "presque fonctionnelle") : http://bugs.python.org/issue13703#msg152030
Il faut relire la discussion complète (ce ticket, mais également la liste de discussion python-dev). Il me semble que cette option a été rejeté pour plusieurs raisons. Dave Malcolm a par exemple noté que l' "AVL tree" ne permet pas d'utiliser des types arbitraires comme clés (ou plutôt que l'AVL tree s'y prête mal). Antoine Pitrou souligne un problème de consommation mémoire.
Pour comprendre la discussion, il faut se rappeler qu'en 2012, la fonction hash() de Python était déterministe et les développeurs s'attendaient à ce que les types dict et set aient toujours la même représentation (repr(data)). La première question était d'estimer le nombre d'applications cassées par une nouvelle fonction de hash.
Au sujet de la PEP 456, il était prévu au départ de pouvoir charger une fonction de hash via une bibliothèque externe. Finalement, la PEP a été simplifiée pour utiliser plutôt des options de compilation, et la PEP se concentre essentiellement sur SipHash. L'implémentation permet quand même de changer plus facilement de fonction de hash.
De l'autre côté beaucoup de plateformes ont changé de fonction de hachage pour éviter le pire cas mais n'ont pas cherché à l'améliorer et sont restés aux listes chainées.
Il faut aussi savoir que le type dict de Python est un type "fondamental" dans le langage. Quand on écrit "x = 1", "x" devient la clé d'un dictionnaire. Ensuite, "print(x)" va chercher la valeur de x dans un dictionaire. Il existe un dictionnaire des variables globales, un dictionnaire des variables locales (note : souvent optimisé en utilisant une liste en interne), le passage de paramètres à une fonction peut aussi nécessiter une dictionnaire, etc. Les performances du type dict impactent donc fortement les performances globales du langage Python.
Perso, je garde un goût amer de toutes ces discussions sur les fonctions de hash. Pour moi, c'est bidon. Je trouve les attaques algorithmes très compliquées, comparativement à la facilité d'un DoS classique (en attaquant le réseau plutôt que l'application). Du genre, Spamhaus où un bug DNS a été exploité (flood UDP). Pour attaquer un site web, suffit de trouver une page de prendre longtemps à être calculée et demander au serveur de calculer plein de fois cette page.
# Python
Posté par Victor STINNER (site web personnel) . En réponse à la dépêche OpenJDK JEP 180: HashMap, collisions & attaques par la complexité. Évalué à 10.
Quelques détails sur le cas de Python.
Python utilise cette solution et décide de changer sa fonction de hachage pour Murmur.
Peut-être que Murmur a été discuté, mais Python ne l'utilise pas. La modification apportée à Python est d'ajouter un secret qui est utilisé dans la fonction de hashage (DJBX31A modifié pour utiliser ce secret). Le secret est un nombre de 64 ou 128 bits (2
longen C). Il a été montré qu'en pratique, on obtient seulement 256 fonctions de hashage différentes (au lieu de 264 ou 2128 ). Dans Python 3.3, le secret est généré aléatoirement à chaque exécution. Dans les versions précédentes, il faut utiliser une option en ligne de commande ou une variable d'environement pour rendre la fonction de hachage aléatoire (que le secret soit généré et utilisé).Pour améliorer la sécurité, Python 3.4 utilise désormais SipHash qui est plus difficile à casser (clé plus grande, construction cryptographique, etc.). Je n'ai pas entendu d'attaque sur SipHash pour le moment.
D'ailleurs, le type
dictde Python n'utilise pas de liste chaînée mais l'adressage ouvert :http://fr.wikipedia.org/wiki/Table_de_hachage#Adressage_ouvert
Changer complètement l'implémentation du type dict de Python a également été discuté. Martin von Loewis a par exemple proposé le type "AVL tree" (avec une implémentation "presque fonctionnelle") :
http://bugs.python.org/issue13703#msg152030
Il faut relire la discussion complète (ce ticket, mais également la liste de discussion python-dev). Il me semble que cette option a été rejeté pour plusieurs raisons. Dave Malcolm a par exemple noté que l' "AVL tree" ne permet pas d'utiliser des types arbitraires comme clés (ou plutôt que l'AVL tree s'y prête mal). Antoine Pitrou souligne un problème de consommation mémoire.
Pour comprendre la discussion, il faut se rappeler qu'en 2012, la fonction hash() de Python était déterministe et les développeurs s'attendaient à ce que les types dict et set aient toujours la même représentation (
repr(data)). La première question était d'estimer le nombre d'applications cassées par une nouvelle fonction de hash.Au sujet de la PEP 456, il était prévu au départ de pouvoir charger une fonction de hash via une bibliothèque externe. Finalement, la PEP a été simplifiée pour utiliser plutôt des options de compilation, et la PEP se concentre essentiellement sur SipHash. L'implémentation permet quand même de changer plus facilement de fonction de hash.
De l'autre côté beaucoup de plateformes ont changé de fonction de hachage pour éviter le pire cas mais n'ont pas cherché à l'améliorer et sont restés aux listes chainées.
Il faut aussi savoir que le type dict de Python est un type "fondamental" dans le langage. Quand on écrit "x = 1", "x" devient la clé d'un dictionnaire. Ensuite, "print(x)" va chercher la valeur de x dans un dictionaire. Il existe un dictionnaire des variables globales, un dictionnaire des variables locales (note : souvent optimisé en utilisant une liste en interne), le passage de paramètres à une fonction peut aussi nécessiter une dictionnaire, etc. Les performances du type dict impactent donc fortement les performances globales du langage Python.
Perso, je garde un goût amer de toutes ces discussions sur les fonctions de hash. Pour moi, c'est bidon. Je trouve les attaques algorithmes très compliquées, comparativement à la facilité d'un DoS classique (en attaquant le réseau plutôt que l'application). Du genre, Spamhaus où un bug DNS a été exploité (flood UDP). Pour attaquer un site web, suffit de trouver une page de prendre longtemps à être calculée et demander au serveur de calculer plein de fois cette page.