Le colonel Moutarde, sur la table (de hachage), avec un livre de maths

Posté par ɹǝıʌıʃO le 30 décembre 2011 à 20:42. Édité par baud123, claudex, Benoît Sibaud et patrick_g. Modéré par Malicia. Licence CC By‑SA.

Étiquettes :

déc.

2011

Quand des chercheurs en informatique font de la théorie, certains écoutent, comme les développeurs de Perl. D'autres dorment au fond de la classe : cette fois, le bonnet d'âne est pour PHP, Python, V8 (JavaScript par Google, qui sert par exemple dans node.js), Ruby (sauf CRuby), de nombreux serveurs d'applications en Java, mais aussi ASP.NET. Ils ont dû se réveiller brutalement mercredi, lors d'une présentation d'Alexander Klink et Julian Wälde au Chaos Communication Congress montrant comment saturer très simplement un serveur grâce à une attaque basée sur la complexité algorithmique.

Le point commun entre tous ces logiciels : ils sont capables de recevoir par HTTP une requête accompagnée de variables et de leurs valeurs. Par exemple, lorsqu'on remplit un formulaire sur un site web, le navigateur envoie au serveur une variable nommée réponse avec la valeur 42. C'est aussi ce qui sert à naviguer sur un site marchand ou un bouchot à trolls en restant identifié. Quand la requête arrive, il faut donc que chaque variable, accompagnée de sa valeur, soit disponible pour le programme qui va la traiter. Pratiquement tous les langages le font de la même façon : ils les insèrent dans une table de hachage.

Ô ♫ mon ♬ tablo-o-o-oooooo ♩

[avertissement : ceux qui savent ce qu'est une table de hachage perdent leur temps s'ils lisent ce paragraphe. Bon, en même temps, ils sont déjà sur DLFP…]

Soit un langage de programmation dans lequel existent deux types de données : les nombres entiers et les chaînes de caractères. En combinant les deux, il est possible de construire un tableau dans lequel chaque case, numérotée, contient une chaîne de caractères.

1 → « Victorine continua sa lecture en fermant les yeux »
2 → « La vache paît en paix dans ces gras pâturages »
3 → « Ah ! dit don Manoel en portugais »

Un hacheur sachant hacher

C'est pratique, mais malheureusement, les variables que l'on utilise sur des pages web sont nommées, pas numérotées. Le nom d'une variable est lui-même une chaîne de caractères. Il faudrait donc une méthode qui transforme une chaîne en entier, c'est-à-dire une fonction de hachage. Pour une chaîne c donnée, la fonction de hachage h renvoie un entier n : h(c)=n.

Ainsi, on a une façon bien pratique d'enregistrer les variables : on se donne une fonction de hachage et un tableau comme ci-dessus, que l'on nomme table de hachage, et on range les chaines à l'emplacement correspondant à leur image par la fonction de hachage. Par exemple, si on a une variable nommée question et contenant « six fois neuf », on calcule h(« question »)=42, et on enregistre donc la chaîne « six fois neuf » dans l'emplacement numéro 42 du tableau.

Un arrière-gout sucré

À ce stade, le programme n'a pas encore la main. Cette étape préparatoire va servir par la suite, cachée sous une couche de sucre syntaxique. Par exemple, si le programmeur demande la valeur de POST['question'], l'environnement d'exécution va calculer h(« question »)=42 et aller chercher le contenu de la case numéro 42.

What's in a name ?

Il y a tout de même un problème. Oh, un tout petit problème, un de ceux qui ne se posent qu'en théorie, jamais en pratique. Le nombre de seaux (« cases » du tableau) est nécessairement limité, contrairement au nombre de chaînes de caractères qu'il est possible de construire. Il existe donc forcément, pour une fonction h et une chaîne c1 données, une chaîne c2 telle que h(c1) = h(c2) = n. On dit alors que c2 est un deuxième antécédent de n par h, et qu'une collision se produit entre c1 et c2. Dans ce cas, comme une case ne peut accueillir qu'une chaîne, il faut recourir à une astuce : chaque case, en plus d'une chaîne, contient aussi l'adresse d'une nouvelle case. On peut ainsi chaîner les valeurs sans limite autre que la mémoire de la machine.

41 → « foo »
42 → « A noir » → « E blanc » → « I rouge » → « O bleu » → « U vert » → « Voyelles »

Savez-vous compter les trous ?

Insérer dans une case numérotée ou dans une liste chaînée, c'est la même chose. Sans doute… Sauf pour les quelques farfelus qui comptent les opérations nécessaires à l'exécution d'un programme en fonction de la taille de ses données d'entrée. C'est ce qu'on appelle la complexité algorithmique.

Dans le cas de l'insertion d'une valeur c dans une table de hachage, si on tombe toujours sur une case vide, ce nombre d'opérations ne dépend que du nombre d'opérations que va mettre la fonction de hachage pour calculer sa valeur. Pour une fonction de hachage classique, le temps d'une insertion est donc proportionnel à la longueur de c, ce que l'on note O(|c|). Comme les bonnes fonctions de hachage sont très rapides, cela ne pose pas de problème. Pour une application web, en pratique, la longueur des données à hacher sera forcément très faible, et on peut donc considérer (bouchez-vous les oreilles si un puriste est dans les environs : il va hurler) que ce temps est une constante. Pour insérer n éléments, il faut donc O(n) opérations. À la grosse louche, si l'insertion d'un élément prend 0,0000001 seconde, l'insertion de 10000 éléments prend 0,001 seconde et celle de 100000 éléments prend 0,01 seconde. Une paille.

En revanche, si la case choisie est toujours déjà occupée, c'est une toute autre histoire. En effet, il faut alors parcourir la liste des données insérées pour trouver la place de la nouvelle chaine, qui peut très bien être à la fin (si elles sont triées, ce qui est généralement le cas). On tombe alors dans le pire cas : l'insertion de n éléments qui ont la même image par h nécessite O(n²) opérations. Si l'insertion d'un élément prend toujours 0,0000001 seconde, l'insertion de 10 000 éléments prend désormais 10 secondes et celle de 100 000 éléments prend 1000 secondes. Il y a peu de chances que l'utilisateur soit toujours en train d'attendre, un quart d'heure après avoir envoyé ses données.

Heureusement, en pratique, il est très rare de tomber sur une case occupée. Les développeurs des principaux environnements d'exécution sont compétents et ont donc choisi de très bonnes fonctions de hachage, souvent issues des travaux du mathématicien américain Daniel Bernstein, un expert en cryptologie. Grâce à cela, il est extrêmement difficile de trouver plusieurs chaines de caractères qui ont le même antécédent. On peut donc oublier ce scénario pathologique certes, complètement théorique toutefois.

Mais pourquoi est-il aussi méchant ?

Sauf, bien sûr, si on dispose d'une attaque contre ces fonctions de hachage. Une telle attaque est à la base des travaux de Klink et Wälde. En résumé, ils ont trouvé un moyen de fabriquer un grand nombre de chaines de caractères qui ont la même image par les fonctions de hachage utilisées par les bibliothèques des principaux langages. Ils peuvent ainsi construire une requête HTTP contenant un grand nombre de variables nommées exprès pour provoquer le scénario pathologique décrit ci-dessus : occupation à 100% du processeur dédié à cette tâche.

Dromadaire 1 – ânes 0

Ce genre d'attaque ne date pourtant pas d'hier, du moins en théorie. Un article de Crosby et Wallach paru en 2003 décrit le problème et apporte des solutions. Les développeurs de Perl ont réagi dans la foulée en modifiant légèrement leur fonction de hachage, ceux de CRuby également, et… c'est à peu près tout. Pratiquement tous les autres langages largement déployés sur des serveurs sont toujours vulnérables.

Un grain de sel suffit

La solution est évidente : l'attaquant ne doit pas être capable de prévoir le résultat de la fonction de hachage. Comment est-ce possible si le code source des logiciels déployés est public ? Simplement en modifiant la fonction de hachage pour intégrer un élément de hasard, sur le même principe que le salage des mots de passe. En général, la méthode employée pour hacher consiste à prendre un entier valant initialement 0, puis modifier cet entier en fonction des données à hacher, caractère par caractère. Dans les versions actuelles de Perl, cet entier ne vaut plus initialement 0, mais une valeur aléatoire qui ne sort jamais de l'environnement d'exécution. Résultat : les collisions sont pratiquement impossibles à trouver, et paf l'attaque.

En attendant…

Quelques mesures simples protègent efficacement contre ce genre d'attaque, mais il n'est pas toujours facile, voire pas toujours possible, de les mettre en place. On peut limiter la taille maximale d'une requête, mais c'est ballot si l'utilisateur est censé pouvoir envoyer beaucoup de données. Plus fin : on peut limiter le nombre maximum de variables, notamment avec Suhosin pour PHP. En tous cas, maintenant que le 25 décembre est passé, il est temps d'arrêter de croire au père Noël : le choix d'une structure de données et des fonctions associées est toujours important.

Aller plus loin

Présentation d'Alexander Klink et Julian Wälde au Chaos Communication Congress [PDF, 6 Mo] (1071 clics)

# CRuby

Posté par __o le 30 décembre 2011 à 21:14. Évalué à 10. Dernière modification le 30 décembre 2011 à 21:19.

En fait CRuby 1.8 est affecté par ce problème (corrigé il y a deux jours: [1]). Seule la version 1.9 ne l'était pas.

Pour PHP, un correctif a été pushé le 14 décembre (pas de release par contre).

Pour Tomcat la seule façon de contrer le problème est de limiter la taille des requêtes POST.

L'article [2] explique très bien le problème aussi.

Pour l’anecdote, on y vois que parmi PHP, ASP.NET, Tomcat, CRuby; PHP est celui qui résiste le mieux à l'attaque, et CRuby est celui qui résiste le moins bien (il consomme 100 fois plus de CPU que PHP pour la même attaque):

So you can keep about 10.000 Core i7 CPU cores busy processing PHP requests using a gigabit internet connection. Alternatively for ASP.NET, 30,000 Core2 CPU cores, or for Java Tomcat 100,000 Core i7 CPU cores, or for CRuby 1.8 1,000,000 Core i7 CPU cores, can be kept busy with a single gigabit connection.

[1] http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/391607
[2] https://cryptanalysis.eu/blog/2011/12/28/effective-dos-attacks-against-web-application-plattforms-hashdos/
# interessant

Posté par RB le 30 décembre 2011 à 21:29. Évalué à 4.

; Maximum amount of time each script may spend parsing request data. It's a good
; idea to limit this time on productions servers in order to eliminate unexpectedly
; long running scripts.
max_input_time = 60

Ce temps, est à ce que j'ai compris, le temps de parser l'input (donc pas le temps d'upload des données) avant de rendre la main au code PHP proprement dit.

Je ne comprend pas pourquoi cette valeur est par défaut de 60, quand le max_execution_time est généralement de 30. Le temps d'initialiser les valeurs dans le cas courant doit être à mon avis extrêmement rapide et ne devrait jamais dépasser une fraction de seconde. Pourquoi cette valeur est-elle par défaut si haute ?
- [^] # Re: interessant
  
  Posté par __o le 30 décembre 2011 à 21:38. Évalué à 1.
  
  Les uploads de fichiers peuvent durer un certain temps, selon la taille du fichier et la bande passante. Je suppose que c'est pour ça.
- [^] # Re: interessant
  
  Posté par __o le 30 décembre 2011 à 21:46. Évalué à 0.
  
  La doc est ambiguë, mais max_input_time limite le temps de réception + parsage des données POST.
  - [^] # Re: interessant
    
    Posté par RB le 31 décembre 2011 à 03:35. Évalué à 1.
    
    A priori non:
    
    Dernière version de la doc:
    
    "This sets the maximum time in seconds a script is allowed to parse input data, like POST and GET. It is measured from the moment of receiving all data on the server to the start of script execution."
    
    D'autres gens qui se posaient la question:
    
    https://bugs.php.net/bug.php?id=53590&
    
    Plus inquiétant:
    
    "Also, with multipart requests reading and parsing the data are done in one step (in the reading step), so that occurs before the timeout starts counting. The documentation is wrong when it mentions "file uploads"."
    
    Donc il semble que fixer une valeur basse ne suffirait pas à assurer une protection...
    - [^] # Re: interessant
      
      Posté par __o le 31 décembre 2011 à 13:50. Évalué à 1.
      
      En fait ça dépend de plusieurs trucs, mais d'après le code ce timeout est bien installé avant de lire les données POST, puis remplacé par max_execution_time avant d'exécuter le script.
      
      Par contre ça peut dépendre du serveur http (qui peut buffuriser la requête), et de la plateforme (marche pas sous windows à priori).
# N'optimiser que si nécessaire

Posté par Kerro le 30 décembre 2011 à 23:04. Évalué à -5.

Les tables de hachage sont très bien lorsqu'il y a beaucoup de choses à stocker.
Les requêtes HTTP qui comportent plus de 100 valeurs sont rares.

Pour chaque requête il faut se palucher la construction d'une table de hachage. Et pour chaque accès aux valeurs il faut se farcir la recherche dans la table en question (hachage du nom recherché, puis recherche). Ces opérations sont bien plus coûteuses que si s'était "rangé en vrac", à condition de ne pas avoir trop de valeurs. Ce qui est le cas dans 99.9% des cas (valeur issue de mes notes personnelles, là, dans le tiroir).

Tout ça pour ?
Tout ça pour perdre du temps dans 99.9% des cas. Pour les 0.01% restant, le programmeur, sachant qu'il n'y a pas de table de hachage, les fourre dans une qu'il construit pour l'occasion et le tour est joué. Comme on fait d'habitude quoi.

Et ô surprise, ne pas complexifier aurait encore évité des bugs. Dingue.
- [^] # Re: N'optimiser que si nécessaire
  
  Posté par Antoine le 30 décembre 2011 à 23:20. Évalué à 10.
  Et pour chaque accès aux valeurs il faut se farcir la recherche dans la table en question (hachage du nom recherché, puis recherche). Ces opérations sont bien plus coûteuses que si s'était "rangé en vrac", à condition de ne pas avoir trop de valeurs.
  
  Oui, bien sûr. Et comme ça un attaquant peut profiter du fait que les recherches sont en O(n). C'est quoi le sujet de la dépêche déjà ?
  
  Au fait, pour le côté "bien plus coûteux que si c'était rangé en vrac" :
```
$ ./python -m timeit -s "vars=['a', 'b', 'c', 'd']" "vars.index('c')"
10000000 loops, best of 3: 0.155 usec per loop
$ ./python -m timeit -s "vars={'a':1, 'b':2, 'c':3, 'd':4}" "vars.get('c')"
10000000 loops, best of 3: 0.0751 usec per loop
```
  Déjà avec 4 entrées, la table hash est deux fois plus rapide que la table "en vrac".
  
  le programmeur, sachant qu'il n'y a pas de table de hachage, les fourre dans une qu'il construit pour l'occasion et le tour est joué
  
  Oui, tiens, c'est une bonne idée ça, de laisser le programmeur se faire chier à reprogrammer sa propre table hash, correctement optimisée, à chaque occasion. Laisse-moi deviner, tu es aussi contre la gestion automatique de la mémoire parce c'est aussi simple d'appeler free() au bon moment ?
  
  En fait tu voudrais que les langages haut niveau ressemblent au C, mais à ça il y a une solution très simple : programme en C. Problème résolu :-)
  - [^] # Re: N'optimiser que si nécessaire
    
    Posté par claudex le 30 décembre 2011 à 23:36. Évalué à 0.
    
    Oui, bien sûr. Et comme ça un attaquant peut profiter du fait que les recherches sont en O(n). C'est quoi le sujet de la dépêche déjà ?
    
    Le sujet de la dépêche, c'est le temps de construction de la table de hachage, pas la recherche puisqu'on n'ira jamais chercher des paramètres qui sont envoyé mais qu'on n'avait pas prévu de chercher.
    
    « Rappelez-vous toujours que si la Gestapo avait les moyens de vous faire parler, les politiciens ont, eux, les moyens de vous faire taire. » Coluche
    - [^] # Re: N'optimiser que si nécessaire
      
      Posté par Antoine le 31 décembre 2011 à 00:36. Évalué à 1.
      
      Le sujet de la dépêche, c'est le temps de construction de la table de hachage, pas la recherche puisqu'on n'ira jamais chercher des paramètres qui sont envoyé mais qu'on n'avait pas prévu de chercher.
      
      Ben si tu veux détecter les doublons, la construction implique de rechercher une clé avant de l'insérer.
      - [^] # Re: N'optimiser que si nécessaire
        
        Posté par claudex le 31 décembre 2011 à 10:11. Évalué à 1.
        
        Tu peux très bien rechercher les doublons uniquement à la consultation. Cela te permet de voir que la liste contient beaucoup trop d'élément et qu'il vaut mieux abandonner cette requête.
        
        « Rappelez-vous toujours que si la Gestapo avait les moyens de vous faire parler, les politiciens ont, eux, les moyens de vous faire taire. » Coluche
        
        [^] # Re: N'optimiser que si nécessaire
        
        Posté par Antoine le 31 décembre 2011 à 11:06. Évalué à 3.
        
        Certes, une fois que l'attaque est connue, tu peux faire ce qu'il faut pour la contourner. Mais dans ce cas, tu fais pareil avec une table hash en limitant par exemple le nombre d'éléments insérables (solution PHP). Ou bien tu aléatoirises le hachage (solution Perl, et je crois qu'on se dirige vers ça côté Python).
        
        Avec le même genre d'arguments, un tri à bulles est préférable à un tri rapide parce que le tri à bulles, lui, est toujours lent. La bonne solution est plutôt de s'assurer que l'algo de tri ne peut facilement dégénérer, sans être d'emblée non plus en O(n**2).
        
        [^] # Re: N'optimiser que si nécessaire
        
        Posté par claudex le 31 décembre 2011 à 11:47. Évalué à 1.
        
        Je montre juste que la détection de doublon n'est pas nécessaire à la construction de ta liste.
        
        « Rappelez-vous toujours que si la Gestapo avait les moyens de vous faire parler, les politiciens ont, eux, les moyens de vous faire taire. » Coluche
        
        [^] # Re: N'optimiser que si nécessaire
        
        Posté par ɹǝıʌıʃO le 31 décembre 2011 à 13:53. Évalué à 1.
        
        La bonne solution est plutôt de s'assurer que l'algo de tri ne peut facilement dégénérer, sans être d'emblée non plus en O(n**2)
        
        Voir introsort pour ceux que ça intéresse. Au passage, de nombreux environnements d’exécution utilisent « quicksort » pour trier, sans plus de précision dans leur doc (je n’ai pas regardé le code source). Si ce n’est pas une version de quicksort intégrant une astuce pour éviter le cas pathologique, ça peut donner des idées pour la prochaine fois…
        
        [^] # Re: N'optimiser que si nécessaire
        
        Posté par neologix le 31 décembre 2011 à 16:47. Évalué à 4.
        
        Si ce n’est pas une version de quicksort intégrant une astuce pour éviter le cas pathologique
        
        Pour CPython, c'est une variante du bien connu merge sort :
        http://en.wikipedia.org/wiki/Timsort
        
        Donc pas de problème, worst-case en O(n log n).
        
        [^] # Re: N'optimiser que si nécessaire
        
        Posté par Nicolas Boulay (site web personnel) le 02 janvier 2012 à 10:46. Évalué à 2.
        
        c'est possible que cela soit le quicksort de la libc ?
        
        "La première sécurité est la liberté"
        
        [^] # Re: N'optimiser que si nécessaire
        
        Posté par Thierry Thomas (site web personnel, Mastodon) le 03 janvier 2012 à 16:40. Évalué à 4.
        
        Non, ça doit être celui-ci : Küküllőmenti legényes
- [^] # Re: N'optimiser que si nécessaire
  
  Posté par scand1sk (site web personnel) le 30 décembre 2011 à 23:34. Évalué à 3.
  
  "Ranger en vrac", ça veut dire se priver de tableaux associatifs $_GET/$_POST en PHP pour les remplacer par un tableau indexé (ou mieux, une liste chaînée, mais ce n'est pas très courant en PHP) de structures comprenant le nom du paramètre et sa valeur.
  
  Effectivement, d'un point de vue performance, s'il y a peu de paramètres, ça peut concurrencer une table de hachage, mais à quel prix d'un point de vue utilisabilité ! Et pour gagner des cacahuètes (la moindre requête SQL doit exploser violemment le temps nécessaire pour construire la table de hash). Étrangement, pour moi, c'est justement cette approche qui me parait une optimisation peu nécessaire.
  - [^] # Re: N'optimiser que si nécessaire
    
    Posté par Batchyx le 31 décembre 2011 à 11:31. Évalué à 4.
    
    Les tableaux associatifs ne sont pas nécessairement des tables de hachage, surtout pour des chaînes. Ça peut être des variantes d'arbre binaire de recherche, de B-tree, de TRIE ...
    
    Le fait d'utiliser des tables de hachage par défaut dans les langages, c'est bien joli, mais quand on veut des perfs, le mieux est de laisser la possibilité à l'utilisateur de choisir ce qu'il veut. Les tables de hachage avec quelques longues chaînes, c'est pas vraiment idéal.
    - [^] # Re: N'optimiser que si nécessaire
      
      Posté par Nicolas Boulay (site web personnel) le 02 janvier 2012 à 10:47. Évalué à 1.
      
      Ou encore que le logiciel utilise le meilleur contenaire possible selon les opérations faites dessus et sa taille maximum.
      
      "La première sécurité est la liberté"
- [^] # Re: N'optimiser que si nécessaire
  
  Posté par barmic le 30 décembre 2011 à 23:38. Évalué à 2.
  
  Tu voudrais utiliser un ensemble pour ça ? Et comment recherche-tu la valeur d'une variable à partir de son nom ?
  
  Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)
  - [^] # Re: N'optimiser que si nécessaire
    
    Posté par Sufflope (site web personnel) le 01 janvier 2012 à 23:19. Évalué à 2.
    
    Non mais laisse tomber, c'est Kerro. Encore quand il donne de grandes leçons dans son domaine, ça passe encore, on peut presque y croire ; mais depuis qu'il a installé un Apache (monitoré par Nagios hein, 'tention) il s'est autoproclamé expert en HTTP / Web, mais c'est pas encore ça.
# Remarque stupide de théoricien

Posté par DeeTay le 30 décembre 2011 à 23:21. Évalué à 9.

Il y a tout de même un problème. Oh, un tout petit problème, un de ceux qui ne se posent qu'en théorie, jamais en pratique. Le nombre de seaux (« cases » du tableau) est nécessairement limité, contrairement au nombre de chaînes de caractères qu'il est possible de construire. Il existe donc forcément, pour une fonction h et une chaîne c1 données, une chaîne c2 telle que h(c1) = h(c2) = n.

Allez, on joue sur les mots : cette phrase est fausse =D En effet, soit une fonction de hachage h à valeurs dans un ensemble, disons {1,...,k}. Je définis la fonction h' par h'("Bonjour !") = 0, et h'(c) = h(c) si c != "Bonjour !". C'est une fonction de hachage à valeurs dans {0,...,n}, mais pour si on prend c1 = "Bonjour !", alors il n'existe pas de chaîne c2 vérifiant h'(c1) = h'(c2) =)

Bon, après on peut aussi jouer encore plus sur les mots et considérer que la formule "pour toute fonction h, pour toute chaîne c1, il existe une chaîne c2 telle que h(c1) = h(c2)" est toujours vraie, vu qu'il suffit de choisir c2=c1 pour que ça marche.

Voilà, c'était la contribution utile de la soirée.
# Collisions dans une table de hachage

Posté par rogo le 30 décembre 2011 à 23:23. Évalué à 10.
Il y a une erreur, ou tout du moins une maladresse d'expression, dans le passage intitulé "What's in a name ?". Je ne parle pas de l'espace à la française avant le point d'interrogation, mais bien de la description technique.

Si h(k1) = 42 et h(k2) = 42, alors 42 → v1 → v2 ne suffit pas à construire une table de hachage. Comment saurait-on quelle valeur correspond à la clé k1 et quelle valeur à la clé k2 ?
Il faut donc stocker, non pas une liste chaînée des valeurs, mais une liste chaînée des couples (clé, valeur) : 42 → [k1,v1] → [k2,v2].

Au final, la table de hachage ressemble donc à :
```
41 → [« bar », « foo »]
42 → [« clé 1 », « A noir »] → [« clé 2 », « E blanc »] → …
```
- [^] # Re: Collisions dans une table de hachage
  
  Posté par ɹǝıʌıʃO le 31 décembre 2011 à 10:32. Évalué à 2.
  
  Anéfé. Pour être complet (?) sur les erreurs de ce paragraphe, j'en profite pour présenter mes excuses à Arthur, qui avait choisi un ordre non-alphabétique pour ses voyelles, ce qui ne m'arrangeait pas.
# faut chercher

Posté par TImaniac (site web personnel) le 31 décembre 2011 à 10:43. Évalué à 1.

Les développeurs de Perl ont réagi dans la foulée en modifiant légèrement leur fonction de hachage, ceux de CRuby également, et… c'est à peu près tout. Pratiquement tous les autres langages largement déployés sur des serveurs sont toujours vulnérables.

Microsoft propose un patch pour ASP.NET depuis 2 jours :
http://technet.microsoft.com/en-us/security/bulletin/ms11-100.mspx
# Les vrais théoriciens s'en foutent

Posté par Perthmâd (site web personnel) le 31 décembre 2011 à 10:57. Évalué à -5.

Parce que O(n) et O(n²), c'est pareil, c'est polynomial...

Et puis quelle idée d'utiliser des tables de hachage, les arbres binaires de recherche, c'est quand même plus classe !
- [^] # Re: Les vrais théoriciens s'en foutent
  
  Posté par rewind (Mastodon) le 31 décembre 2011 à 11:26. Évalué à 4.
  
  Les théoriciens te diront alors que l'insertion dans un arbre binaire de recherche, c'est en O(log n) tandis que dans une table de hachage, c'est en O(1) (en moyenne).
  - [^] # Re: Les vrais théoriciens s'en foutent
    
    Posté par Batchyx le 31 décembre 2011 à 11:56. Évalué à 2.
    
    Un théoricien qui considère que comparer deux chaînes se fait en O(1), c'est pas un théoricien.
    
    Hasher une chaîne c'est toujours O(l), alors que comparer une chaîne, c'est O(l), au pire. Si tes chaînes commencent pas par les mêmes lettres (ce qui est courant), ta complexité est bien réduite.
    
    Et la dernière fois que j'ai regardé, rééquilibrer un arbre binaire ça coûte moins cher que d'augmenter la taille d'une table de hachage.
    
    Enfin bref, selon le jeu de données, les résultats sont différents. C'est ça, de la bonne théorie. :)
    
    (La pratique, c'est lorsqu'on se tape le cache du CPU, la rotation des disques et l'OS)
    - [^] # Re: Les vrais théoriciens s'en foutent
      
      Posté par neologix le 31 décembre 2011 à 12:20. Évalué à 4.
      
      Et la dernière fois que j'ai regardé, rééquilibrer un arbre binaire ça coûte moins cher que d'augmenter la taille d'une table de hachage.
      
      Ah bon ?
      Rééquilibrer un arbre binaire, c'est O(log n).
      Augmenter la taille d'une table de hachage, c'est un coût amorti de O(1), pour peu que tu utilises une progression géométrique.
      - [^] # Re: Les vrais théoriciens s'en foutent
        
        Posté par Batchyx le 31 décembre 2011 à 13:03. Évalué à 2.
        
        Augmenter la taille d'une table de hachage, c'est un coût amorti de O(1), pour peu que tu utilises une progression géométrique.
        
        C'est un coût amorti de O(1) que pour ceux qui considère que hasher une chaîne se fait en O(1). Moi je parlait d'un coût en O(l) pour une chaîne de taille l.
        
        [^] # Re: Les vrais théoriciens s'en foutent
        
        Posté par neologix le 31 décembre 2011 à 13:36. Évalué à 4.
        
        C'est un coût amorti de O(1) que pour ceux qui considère que hasher une chaîne se fait en O(1). Moi je parlait d'un coût en O(l) pour une chaîne de taille l.
        
        Ca ne change rien : si tu considères que hasher une chaîne se fait en O(l), le coût amorti est en O(l).
        Mais rééquilibrer ton arbre se fait aussi en O(l log n) : il faut bien comparer ton élément, non ? (même si la comparaison est en O(l) dans le pire cas alors que le hash est en O(l) dans tous les cas, c'est pareil).
        Et ce serait pareil avec un trie, tu auras toujours ce facteur O(l), étant donné que la comparaison/égalité est en O(l).
        Ensuite, par exemple dans CPython, les hashs des objets immutables (string, bytes...) sont stockés avec l'objet, donc tu ne passes pas ton temps à les recalculer.
        
        [^] # Re: Les vrais théoriciens s'en foutent
        
        Posté par Batchyx le 31 décembre 2011 à 15:14. Évalué à 3.
        
        Mais rééquilibrer ton arbre se fait aussi en O(l log n) : il faut bien comparer ton élément, non ?
        
        Ben, non, justement. Il faut juste regarder la forme de l'arbre et faire les rotations qu'il faut.
        
        [^] # Re: Les vrais théoriciens s'en foutent
        
        Posté par neologix le 31 décembre 2011 à 16:44. Évalué à 4.
        
        Ben, non, justement. Il faut juste regarder la forme de l'arbre et faire les rotations qu'il faut.
        
        Pour un rééquilibrage, oui, mais tu ne fais pas un rééquilibrage pour le fun, non ?
        C'est toujours dans le cadre d'une insertion ou d'un suppression d'élément (c'est le scénario qu'envisageait rewind dans son message).
        Pour insérer ou supprimer ton élément, ta complexité est bien en O(l log n), contre O(l) pour une table de hashage, malgré le redimensionnement. Si tu veux du lookup en O(l) et insertion/suppression en O(lr)/O(l+r) où r est le radix), alors effectivement un trie est une bonne idée.
        Après, je suis d'accord avec toi :
        - dans le cas de longues chaînes, la comparaison est souvent bien plus rapide que O(l), contrairement au hashage (mais voir la remarque sur le fait que le hash d'un objet immutable est souvent conservé)
        - en oubliant la longueur des chaînes, avec un arbre binaire ton insertion est O(log n) dans le pire des cas, contre O(n) pour une table de hashage (d'où cette vulnérabilité, et potentiellement un problème avec des contraintes temps réel)
    - [^] # Re: Les vrais théoriciens s'en foutent
      
      Posté par barmic le 31 décembre 2011 à 18:00. Évalué à 4.
      
      Un théoricien qui considère que comparer deux chaînes se fait en O(1), c'est pas un théoricien.
      
      Hasher une chaîne c'est toujours O(l), alors que comparer une chaîne, c'est O(l), au pire.
      
      Faudrais savoir ce que l'on veut mesurer. Si on cherche à mesurer le nombre de comparaison (ce qui est généralement le cas quand on parle des tables de hashage).
      
      De plus dans le cas que tu parle, le hash c'est O(l) et la comparaison c'est O(l/2). Ils font donc partie de la même classe de complexité, c'est peut être une amélioration, mais ça se rapproche plus de la micro-optimisation qu'autre chose.
      
      Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)
    - [^] # Re: Les vrais théoriciens s'en foutent
      
      Posté par Krunch (site web personnel) le 31 décembre 2011 à 19:52. Évalué à 3. Dernière modification le 31 décembre 2011 à 19:53.
      
      Hasher une chaîne c'est toujours O(l)
      
      Bah non. Tu peux définir une fonction de hashage qui n'examine que les N premiers caractères par exemple. Ça sera O(1). En pratique ça peut même être une bonne idée selon les données et qu'on veut pas s'amuser à implémeter un trie.
      
      pertinent adj. Approprié : qui se rapporte exactement à ce dont il est question.
- [^] # Re: Les vrais théoriciens s'en foutent
  
  Posté par zerkman (site web personnel) le 31 décembre 2011 à 16:59. Évalué à 6.
  
  Parce que O(n) et O(n²), c'est pareil, c'est polynomial...
  
  jamais un théoricien ne te dira que O(n) et O(n²), c'est pareil...
  
  Sinon par récurrence on pourrait affirmer que O(n^42) c'est pareil que O(n), alors qu'en fait, non.
  - [^] # Re: Les vrais théoriciens s'en foutent
    
    Posté par Batchyx le 31 décembre 2011 à 21:55. Évalué à 4.
    
    Ça dépend lesquels. Ceux qui ont l'habitude de bosser sur des problèmes NP, quand ils tombent sur un algo polynomial, ils sont content, peu importe qu'il soit O(n) ou O(n⁴²).
    - [^] # Re: Les vrais théoriciens s'en foutent
      
      Posté par zerkman (site web personnel) le 01 janvier 2012 à 12:11. Évalué à 1.
      
      C'est parce qu'ils se foutent de résoudre des instances réelles du problème ?
      
      Dans la pratique, un algo en O(n⁴²) n'a pas vraiment d'intérêt, on préférera dans ce cas avoir recours à des méthodes approchées ou de la recherche exhaustive.
      - [^] # Re: Les vrais théoriciens s'en foutent
        
        Posté par Zarmakuizz (site web personnel) le 01 janvier 2012 à 12:58. Évalué à 2.
        
        Ils se disent que s'ils ont un algo polynomial, avec un peu de chance quelqu'un d'aussi génial qu'eux saura diminuer la complexité jusqu'à ce que ça devienne utilisable.
        
        Commentaire sous licence LPRAB - http://sam.zoy.org/lprab/
      - [^] # Re: Les vrais théoriciens s'en foutent
        
        Posté par Batchyx le 01 janvier 2012 à 19:14. Évalué à 1.
        
        C'est parce qu'ils se foutent de résoudre des instances réelles du problème ?
        
        Oui, et il n'y a pas qu'eux : Personne sur cette planète n'en à rien à foutre de résoudre le problème. Ce qui les importes, c'est de savoir que "ça c'est dans P".
        
        Peu leur importe de savoir que en fait leur algo était aussi O(n¹⁴·⁷) et qu'on pouvait faire des algos O(n³) avec des améliorations chiantes à prouver. Par contre, les théorèmes intermédiaires (ou la démarche pour les obtenir) pourront être réutilisés pour faire quelque chose d'utile.
        
        Dans la pratique, un algo en O(n⁴²) n'a pas vraiment d'intérêt
        
        Y a des algos exponentiels qui sont utilisés pour traiter des problèmes NP avec des instances avec des tailles en millions. Par contre ils ont des tas d'heuristiques qui détectent les instances ou les parties d'instances faciles ...
        
        [^] # Re: Les vrais théoriciens s'en foutent
        
        Posté par Thomas Douillard le 02 janvier 2012 à 14:42. Évalué à 3.
        
        C'est pas tout a fait exact, on peut lire ce genre de choses sur un blog de théoriciens on peut difficilement faire plus pur jus (suffit de lire le titre du blog déja) After a great deal of work, we were able to show how to improve Barrington’s initial bound from {2} to {1.81}. http://rjlipton.wordpress.com/2009/06/09/computing-very-large-sums/
        
        En plus le complexity zoo est suffisament fourni pour qu'il y ait une petite place, peut être :) http://qwiki.stanford.edu/index.php/Complexity_Zoo
        
        [^] # Re: Les vrais théoriciens s'en foutent
        
        Posté par zerkman (site web personnel) le 02 janvier 2012 à 20:17. Évalué à 2.
        
        Personne sur cette planète n'en à rien à foutre de résoudre le problème.
        
        Bah écoute, mon boulot c'est de faire des solveurs pour des problèmes industriels, donc c'est bien pour qu'à la fin il y ait un logiciel qui trouve des solutions à des instances. Je peux t'assurer que je ne me ferais pas chier à paralléliser mes algos de recherche locale s'il existait des algos en O(n³).
    - [^] # Re: Les vrais théoriciens s'en foutent
      
      Posté par Yusei (Mastodon) le 02 janvier 2012 à 10:04. Évalué à 2.
      
      Et ils sont beaucoup plus contents si c'est O(n) que si c'est O(n^42)...
# Bernstein ???

Posté par khivapia le 31 décembre 2011 à 11:29. Évalué à 2.

Aucune fonction de hachage utilisées en pratique en cryptographie sont issues de travaux de Bernstein. Les fonctions MD4 et MD5, longtemps utilisées, ont été crées par Ronald Rivest (le R de RSA), la fonction RIPEMD par un consortium européen, la fonction SHA-1 par ~~la NSA~~ le NIST, les fonctions SHA-256 à SHA-512 idem.

Il y a une compétition pour désigner le futur standard de fonction de hachage, SHA-3, et les 5 finalistes ne sont pas des fonction de hachage proposées par Bernstein (sa fonction, Cubehash, a été attaquée (quoique légèrement) et n'a pas passé le deuxième tour).
- [^] # Re: Bernstein ???
  
  Posté par ɹǝıʌıʃO le 31 décembre 2011 à 11:48. Évalué à 8.
  
  Aucune fonction de hachage utilisées en pratique en cryptographie sont issues de travaux de Bernstein
  
  En crypto, non, mais ce n'est pas le sujet. Les fonctions de hachage pour tables de hachage dans les environnements visés sont issues de ses travaux. Je n’ai cité la crypto que pour situer le personnage, l'apposition ne devait pas être comprise comme un rapport logique. J’aurais d’ailleurs peut-être mieux fait de parler de sécurité, terme plus général, puisqu'il ne fait pas que de la crypto.
  - [^] # Re: Bernstein ???
    
    Posté par Jux (site web personnel) le 31 décembre 2011 à 14:20. Évalué à 4.
    
    Surtout qu'une fonction de hachage pour une table de hachage, on s'en fout un peu de savoir s'il est possible de trouver une première ou une seconde pré-image. Les propriétés les plus importantes ce sont la vitesse du hachage et la fréquence des collisions (alors qu'en crypto, la vitesse n'est pas le premier critère, il faut d'abord de la solidité).
    - [^] # Re: Bernstein ???
      
      Posté par Nicolas Boulay (site web personnel) le 02 janvier 2012 à 15:05. Évalué à 1.
      
      (alors qu'en crypto, la vitesse n'est pas le premier critère, il faut d'abord de la solidité).
      
      Et surtout que l'on ne veut pas du tout de collision.
      
      "La première sécurité est la liberté"
      - [^] # Re: Bernstein ???
        
        Posté par Antoine le 02 janvier 2012 à 16:34. Évalué à 3.
        
        Pas du tout ? Va falloir limiter la taille des données d'entrée :)
        
        [^] # Re: Bernstein ???
        
        Posté par barmic le 02 janvier 2012 à 17:11. Évalué à 2.
        
        Ou ne pas limiter la taille du hash :)
        
        Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)
# "et paf l'attaque"

Posté par reno le 31 décembre 2011 à 12:32. Évalué à 5.

Hum, ce n'est pas si simple: randomiser une seed a comme effet de bord (il me semble) que les performances de deux serveurs configurés identiquement et testés avec les mêmes entrées peuvent être différentes..
Pas sympa si on tombe dans un cas pathologique pour reproduire le problème! A priori ça a très peu de chance d'arriver, m'enfin Murphy il ne faut pas trop le chercher..
- [^] # Re: "et paf l'attaque"
  
  Posté par ɹǝıʌıʃO le 31 décembre 2011 à 13:47. Évalué à 3.
  
  En principe oui, mais avec une probabilité extrêmement faible. Si un risque aussi faible n’est pas acceptable, il vaut mieux laisser tomber directement les tables de hachage et utiliser une structure de données (l’un des nombreux types d’arbres…) qui garantit un pire cas en n log n (voire utiliser des tables de hachage que l'on remplace à la volée par des arbres si on détecte un scénario pathologique). Et toujours si on refuse un risque aussi faible, il faut tellement tout contrôler qu'il est pratiquement impensable d’utiliser un langage de haut niveau (haut comme Perl, C étant considéré comme bas).
# « These are things in PHP which make me sad. »

Posté par Anonyme le 31 décembre 2011 à 13:47. Évalué à 3.

« They are real, objective issues which I have personally encountered in my normal day-to-day activites. »
# Super article

Posté par Jux (site web personnel) le 31 décembre 2011 à 14:22. Évalué à 10.

Merci pour cet article fort intéressant et bien écrit !
# Perl et la complexité

Posté par Thomash le 01 janvier 2012 à 22:24. Évalué à 1.

La dépêche présente Perl comme le premier de la classe, je voudrais nuancer un peu cette vision des choses. Allez lire cet article sur les expressions régulières et Perl.
- [^] # Re: Perl et la complexité
  
  Posté par ɹǝıʌıʃO le 02 janvier 2012 à 00:01. Évalué à 3.
  
  Attention : l'article parle des expressions régulières au sens académique du terme, pas au sens « Perl » du terme. Voir par exemple cette discussion à laquelle participent des développeurs de Perl et l'auteur de l'article en question. En particulier, il a fallu un article paru plus tard pour avoir des NFA / DFA prenant en charge les références arrière, et ce n'est que l'un des aspects qui rendent l'article inapplicable en l'état.
  - [^] # Re: Perl et la complexité
    
    Posté par Thomash le 02 janvier 2012 à 10:03. Évalué à 2.
    
    L'article dit que lorsque les expressions régulières utilisées sont de vraies expressions régulières il existe une implémentation beaucoup plus efficace que celle de Perl et que cela ne coûterait pas grand chose de regarder si une expression régulière est ou non une vraie expression régulière. Cela permettrait donc d'accélérer grandement le traitement des expressions régulière dans de nombreux cas sans ralentir les cas où on a vraiment besoin de l'implémentation actuelle.
    - [^] # Re: Perl et la complexité
      
      Posté par ɹǝıʌıʃO le 02 janvier 2012 à 10:58. Évalué à 3.
      
      lorsque les expressions régulières utilisées sont de vraies expressions régulières il existe une implémentation beaucoup plus efficace que celle de Perl
      
      Oui, du moins si d'autres conditions sont remplies. Par exemple, sa façon d'évacuer le problème d'Unicode est une plaisanterie.
      
      Cela permettrait donc d'accélérer grandement le traitement des expressions régulière dans de nombreux cas sans ralentir les cas où on a vraiment besoin de l'implémentation actuelle.
      
      Ça, c'est beaucoup moins sûr. Pour que cette solution ait un intérêt, il faudrait être sûr que la construction de l'automate ne coute pas plus cher que l'exécution du code actuel. Or, tout comme il existe des cas limites pour la méthode utilisée par Perl, il existe des cas limites pour les automates, avec la différence que l'explosion ne concerne pas seulement le temps d'exécution (facile à contrôler avec un chien de garde), mais une combinaison de temps et de mémoire, et, selon le type d'automate, à la construction et/ou à l'exécution. Voilà qui devient amusant à surveiller…
      
      Par exemple, classiquement, les grosses répétitions et les grandes classes de caractères posent problème. Est-il vraiment une bonne idée d'avoir une implémentation pour ga?bu et une autre pour \w{2,3000}ga?bu : c'est douteux, surtout s'il faut entrer dans le cas pathologique pour s'apercevoir qu'on aurait mieux fait de ne pas y aller. Mais tout ça, et bien plus, est couvert dans la discussion ci-dessus.
# C'est dans le Cormen

Posté par DanielAugot le 02 janvier 2012 à 11:35. Évalué à 1.

Plutôt que de saler, comme on dit dans ce forum, la solution propre est la notion de fonction de hachage universelle. C'est très perturbant quand on voit ça la première fois, mais c'est un concept puissant. Voir le Cormen et al, 2nd edition sous-section 11.3.3. Il s'agit d'une famille proprement randomisée de fonctions de hachage, et au départ de l'application, on en choisit une au hasard. Si la famille est bien construite, on évite des comportements de pire cas adverse comme celui décrit ici. Un cas d'école cette attaque.
- [^] # Re: C'est dans le Cormen
  
  Posté par Antoine le 02 janvier 2012 à 13:55. Évalué à 2.
  
  Cela revient juste à remplacer une randomisation (aléatoirisation ?) par une autre, non ?
  - [^] # Re: C'est dans le Cormen
    
    Posté par DanielAugot le 02 janvier 2012 à 15:49. Évalué à 1. Dernière modification le 02 janvier 2012 à 15:49.
    
    Dans la construction des fonctions de hachage universelles, il est demandé certaines propriétés combinatoires plus fortes que de randomizer n'importe comment. Du coup, ça se trouve pas sous le sabot d'un cheval : http://en.wikipedia.org/wiki/Universal_hashing
    - [^] # Re: C'est dans le Cormen
      
      Posté par GreGre le 02 janvier 2012 à 16:11. Évalué à 1.
      
      C'est effectivement plus rigoureux/propre... d'utiliser des fonctions de hachage universelles. Elles ne sont pas difficiles à programmer et en plus elles sont très efficaces.
      
      Pour avoir une idée des performances,on peut regarder le papier de Crosby et
      Wallach à USENIX Security 2003 Papier (section 5.2.2 et Figure 7).

# PHP 806

Posté par LupusMic (site web personnel, Mastodon) le 02 janvier 2012 à 12:34. Évalué à 6.

./Zend/zend_hash.h:228

/*
 * DJBX33A (Daniel J. Bernstein, Times 33 with Addition)
 *
 * This is Daniel J. Bernstein's popular `times 33' hash function as
 * posted by him years ago on comp.lang.c. It basically uses a function
 * like ``hash(i) = hash(i-1) * 33 + str[i]''. This is one of the best
 * known hash functions for strings. Because it is both computed very
 * fast and distributes very well.
 *
 * The magic of number 33, i.e. why it works better than many other
 * constants, prime or not, has never been adequately explained by
 * anyone. So I try an explanation: if one experimentally tests all
 * multipliers between 1 and 256 (as RSE did now) one detects that even
 * numbers are not useable at all. The remaining 128 odd numbers
 * (except for the number 1) work more or less all equally well. They
 * all distribute in an acceptable way and this way fill a hash table
 * with an average percent of approx. 86%. 
 *
 * If one compares the Chi^2 values of the variants, the number 33 not
 * even has the best value. But the number 33 and a few other equally
 * good numbers like 17, 31, 63, 127 and 129 have nevertheless a great
 * advantage to the remaining numbers in the large set of possible
 * multipliers: their multiply operation can be replaced by a faster
 * operation based on just one shift plus either a single addition
 * or subtraction operation. And because a hash function has to both
 * distribute good _and_ has to be very fast to compute, those few
 * numbers should be preferred and seems to be the reason why Daniel J.
 * Bernstein also preferred it.
 *
 *
 *                  -- Ralf S. Engelschall <rse@xxxx>
 */

# Outil de test

Posté par Guillaume Maillard (site web personnel) le 16 janvier 2012 à 19:38. Évalué à 1.

Au passage, un outil pour tester la faille sur son serveur perso: http://www.magic-hash.com

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.