Vulnérabilité des applications due aux fonctions de hachage non aléatoires

Question

L'extrait ci-dessous est tiré d'un article qui explique la possibilité d'une attaque par déni de service (DoS) à cause des fonctions de hachage non aléatoires utilisées dans les structures de données de hachage.

[ ] cette condition peut être exploitée en exploitant les collisions prévisibles dans les algorithmes de hachage sous-jacents.

Afin de le vérifier, j'ai parcouru l'implémentation de référence de Java HashMap d'Oracle et j'ai effectivement trouvé une fonction de hachage statique utilisée :

    static int hash(int h) {
       h ^= (h >>> 20) ^ (h >>> 12);
       return h ^ (h >>> 7) ^ (h >>> 4);
    }

Un autre papier sur le sujet raconte :

Un serveur Tomcat 6.0.32 analyse une chaîne de 2 MB de clés en collision en environ 44 minutes de temps CPU i7, donc un attaquant avec environ 6 kbit/s peut garder un cœur i7 constamment occupé. Si l'attaquant dispose d'une connexion Gigabit, il peut occuper environ 100 000 cœurs i7.

Comment se prémunir contre cette vulnérabilité. D'autant plus que de nombreux logiciels que nous utilisons sont open source (Tomcat, etc.) et reposent sur cette implémentation.

Answer 1

Comprendre le vecteur d'attaque

Comment fonctionnent les HashMaps

Supposons qu'un formulaire de commentaire sur un blog accepte les paramètres - prénom, nom, commentaire - comme paramètres de poste. En interne, Tomcat stocke ces paramètres comme un HashMap.

El structure logique de ce HashMap est comme ceci -

"first_name" --> "Sripathi"
"last_name" --> "Krishnan"
"comment" ---> "DoS using poor Hashes"

Mais le structure physique est différent. Les clés sont d'abord converties en un hashCode, puis le hashCode est converti en un index de tableau.

El structure physique idéale devient donc -

0 --> "Sripathi"
1 --> "Krishnan"
2 --> "DoS using poor Hashes"

Mais les clés possibles sont infinies. Donc, à un moment donné, deux clés auront le même code de hachage. Cela devient une collision de hachage.

Avec les collisions, les structure physique devient :

0 --> "Sripathi", "Krishnan"
1 --> Empty
2 --> "DoS using poor hashes"

Collisions de hachage et impact sur les performances

En cas de collisions de hachage, l'insertion d'une nouvelle entrée implique d'itérer sur tous les éléments d'un même "seau" de hachage. séquentiellement juste pour savoir si elle existe déjà dans la carte. L'insertion d'un élément peut approcher la complexité O(n) si tous les éléments sont hachés à la même valeur. L'insertion de n éléments dans ce pire cas rend la complexité O(n*n).

En bref : Si vous insérer des milliers de clés qui ont le même hashCode le serveur aura besoin de beaucoup de cycles CPU.

Comment générer des clés avec le même Hash ?

En Java, "Aa" et "BB" ont le même code de hachage.

Grâce à une propriété appelée "Sous-chaînes équivalentes", nous pouvons générer plusieurs autres chaînes avec le même code de hachage, en commençant simplement par ces deux chaînes.

Première itération : "AAAA", "AABb", "BbAA", "BbBb" ont le même code de hachage.

Maintenant, nous avons 4 chaînes de caractères avec le même code de hachage. Nous pouvons les permuter pour générer 16 chaînes de caractères qui auront le même code de hachage. Par exemple :

"AaAaAaAa", "AaAaBBBB", "AaAaAaBB", "AaAaBBAa",
"BBBBAaAa", "BBBBBBBB", "BBBBAaBB", "BBBBBBAa",
"AaBBAaAa", "AaBBBBBB", "AaBBAaBB", "AaBBBBAa",
"BBAaAaAa", "BBAaBBBB", "BBAaAaBB", "BBAaBBAa",

Ces 16 chaînes de caractères ont toutes le même code de hachage.

Vous pouvez maintenant prendre ces 16 chaînes et générer 256 chaînes qui ont le même code de hachage.

En bref : il est très facile de générer un grand ensemble de chaînes de caractères qui auront le même code de hachage.

Comment attaquer le serveur ?

1. Créez des milliers de chaînes de caractères ayant le même code de hachage (voir ci-dessus).
2. Construisez une requête POST comme ceci - AaAa=&AaBB=&BBAa=&BBBB= ....
3. Soumettre le formulaire
4. Répétez l'opération en boucle, et créez plusieurs threads pour que toutes les ressources du serveur soient utilisées.

Comme il s'agit simplement d'une demande POST, un attaquant peut également utiliser des navigateurs innocents pour attaquer un serveur. Il suffit de trouver un site Web présentant une vulnérabilité de type "cross site scripting", d'intégrer un code pour effectuer une requête POST, puis d'utiliser l'ingénierie sociale pour diffuser le lien à autant d'utilisateurs que possible.

Prévention

En général, la plate-forme sous-jacente ne peut pas résoudre ce problème. On considère qu'il s'agit d'un problème de cadre d'application. En d'autres termes, c'est Tomcat qui doit résoudre ce problème, et non Oracle/Sun.

Les corrections possibles comprennent :

1. Limiter le nombre de paramètres POST - Tomcat 6.0.35+ a un nouveau paramètre maxParameterCount . La valeur par défaut est de 10 000. Plus elle est faible, mieux c'est, tant qu'elle ne casse pas votre fonctionnalité.

2. Limiter la taille de la requête POST - Pour que l'attaque fonctionne, la charge utile doit être énorme. Le POST par défaut autorisé par Tomcat est de 2MB. Réduire cela à disons 200KB réduira l'efficacité de cette attaque. Le paramètre dans Tomcat est maxPostSize

3. Pare-feu pour applications Web - Si vous disposez d'un pare-feu d'application Web, vous pouvez le configurer pour qu'il bloque les demandes qui semblent suspectes. Il s'agit d'une mesure réactive, mais elle est utile au cas où vous ne pourriez pas utiliser l'une des solutions ci-dessus.

FYI - La documentation de Tomcat est ici - http://tomcat.apache.org/tomcat-6.0-doc/config/http.html

Answer 2

La solution la plus simple est de passer à une version corrigée de tomcat. Cependant, je soupçonne que vous voulez connaître les détails de ce que les gens de tomcat devraient changer.

Cette attaque fonctionne en exploitant un détail d'implémentation commun des structures de données de hachage - l'utilisation de listes liées pour contenir toutes les valeurs dont le hachage est le même. L'ajout de valeurs à cette liste liée est inefficace lorsque la taille de la liste augmente. Un attaquant peut créer une liste de valeurs connues pour générer des hachages en collision, forçant ainsi ce comportement inefficace. Afin de se protéger contre cela, vous avez quelques options :

• Empêcher les collisions - empêcher l'attaquant de générer des valeurs contradictoires en intégrant un facteur (pseudo) aléatoire dans votre fonction de hachage. Perl fait cela depuis longtemps.

• Utilisez autre chose que des listes liées pour vos buckets - l'attaque fonctionne parce que l'insertion de N éléments dans une liste liée a une croissance N^2. Si vous utilisez un arbre équilibré ou une autre structure qui a une croissance N logN lors de l'insertion, le problème devrait être atténué. Cela peut sacrifier une partie des performances dans le meilleur/moyen des cas afin de limiter la gravité du pire des cas.

Answer 3

Les versions de Tomcat concernées sont Apache Tomcat <= 5.5.34, <= 6.0.34, <= 7.0.22 selon le lien que vous avez fourni. La page liste Apache Tomcat >= 5.5.35, >= 6.0.35, >= 7.0.23 comme versions corrigées.

Answer 4

Voici un code python pour générer ces clés... Je ne l'ai pas encore testé, mais je serais intéressé par un retour d'information à ce sujet :

#!/usr/bin/python
import sys
alphabet = ["Aa","BB"]

def func(str, length):
                global alphabet
                if(length != 0):
                                for x in alphabet:
                                                new_str = str+x
                                                func(new_str, length-1)
                else:
                                sys.stdout.write(str+"=&")

for x in range(1,16):
        func("",x)

Answer 5

Java HashMap/HashTable peut effectuer l'opération de "redimensionnement" lorsque l'entrée remplie atteint le seuil. Il est difficile de dire qu'il y a un seau fixe HashMap qui vous attend. En effet, l'opération de sélection d'un seau se fait en deux étapes : l'une consiste à prendre la valeur de hachage de la clé spécifiée ; une autre étape primaire est l'opération du reste de la taille totale du seau (la taille a été modifiée par le redimensionnement).