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

Posté par  . Édité par baud123, claudex, Benoît Sibaud et patrick_g. Modéré par Malicia. Licence CC By‑SA.
Étiquettes :
78
30
déc.
2011
Sécurité

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.

Sommaire

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

  • # CRuby

    Posté par  . É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  . É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  . É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  . É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  . É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  . É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  . É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  . É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  . É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  . É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  . É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  . É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  . É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  . É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  (site web personnel) . É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  . É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  . É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  (site web personnel) . É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  . É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  . É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  . É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  (site web personnel) . É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  (site web personnel) . É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  (Mastodon) . É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  . É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  . É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  . É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  . É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  . É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  . É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  . É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  (site web personnel) . É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  (site web personnel) . É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  . É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  (site web personnel) . É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  (site web personnel) . É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  . É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  (Mastodon) . Évalué à 2.

          Et ils sont beaucoup plus contents si c'est O(n) que si c'est O(n^42)...

  • # Bernstein ???

    Posté par  . É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  . É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  (site web personnel) . É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  (site web personnel) . É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  . Évalué à 3.

            Pas du tout ? Va falloir limiter la taille des données d'entrée :)

            • [^] # Re: Bernstein ???

              Posté par  . É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  . É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  . É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  . Évalué à 3.

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

  • # Super article

    Posté par  (site web personnel) . Évalué à 10.

    Merci pour cet article fort intéressant et bien écrit !

  • # Perl et la complexité

    Posté par  . É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  . É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  . É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  . É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  . É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  . Évalué à 2.

      Cela revient juste à remplacer une randomisation (aléatoirisation ?) par une autre, non ?

      • [^] # Re: C'est dans le Cormen

        Posté par  . É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  . É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  (site web personnel, Mastodon) . É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  (site web personnel) . É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.