Se protéger des attaques par déni de service, n’est plus un luxe ! La plupart des fournisseurs de CDN (Content Delivery Network) proposent une protection contre les attaques DDOS (Distributed Denial Of Service) protocolaires (du TCP au HTTP en passant par le TLS). L’attaquant doit trouver une alternative pour mener son attaque : le ReDoS !

Dans le meilleur des mondes, le traitement d’une expression régulière s’effectue en moins d’une milliseconde. Mais si le moteur d’expression régulière ne trouve pas de solution, le temps d’exécution augmente légèrement, le temps de tester toutes les combinaisons possibles. Jusqu’à présent, rien d’effrayant !

Et maintenant, si nous pouvions augmenter suffisamment ce temps de traitement, nous serions en mesure de monopoliser les ressources du serveur (mémoire et CPU). Cette attaque ReDoS nous permettrait ainsi de rendre le service indisponible pour les utilisateurs légitimes.

Et contrairement à ce que l’on pourrait croire, il y a fort à parier que votre application web soit sujette à cette attaque, même si elle n’a pas de formulaires !

Démonstration d’une attaque ReDoS

Pour cette démonstration, prenons l’expression régulière suivante permettant de vérifier la conformité d’une adresse mail :

[a-z]+@[a-z]+([a-z\.]+\.)+[a-z]+

La vérification d’une adresse mail légitime (contact@mail.example.com) s’effectue rapidement. La commande suivante vous donnera le temps d’exécution sur votre matériel (27ms dans mon cas) avec Node.js mais il en sera de même dans la plupart des langages (Perl, python, java…).

$ time node -e '/[a-z]+@[a-z]+([a-z\.]+\.)+[a-z]+/.test("contact@mail.example.com")'

Mais avec une chaîne de caractères spécialement formatée (mail@e...............................), le temps d'exécution s’allonge (plus de 10 secondes dans mon cas). Et pour augmenter d’avantage la durée de traitement, ajoutez simplement des points.

$ time node -e '/[a-z]+@[a-z]+([a-z\.]+\.)+[a-z]+/.test("mail@e......................................")'

Cette chaîne de caractères ne représente pas une adresse mail valide mais elle permet d’exploiter la complexité algorithmique présente dans la plupart des moteurs d’expression régulière : le backtracking !

Dans la suite de cet article, nous allons approfondir le fonctionnement d’un moteur d’expression régulière pour bien comprendre l’origine du backtracking. Puis nous verrons comment s’en prémunir pour éviter que cela tourne à la catastrophe.

Ce qu’il faut savoir

Pour comprendre cette attaque, il faut avoir quelques notions sur le fonctionnement d’un moteur d’expression régulière. Il en existe beaucoup (irregex, Onigmo, Onig…), mais ils fonctionnent tous de la même manière :

Phase 1 : la compilation

Cette phase de compilation consiste à modéliser une expression régulière en un automate fini. Par exemple, l’expression régulière ab sera modélisée par l’automate fini suivant :

Il s’agit ici d’un automate fini déterministe car nous pouvons prédire son exécution : l’automate commence toujours à l’état numéro 1 puis passera à l’état numéro 2 en consommant la lettre “a”. Mais lorsque l’expression régulière est un peu plus complexe, disons aa|ab, elle peut être modélisée par l’automate fini suivant :

Il s’agit ici d’un automate fini non déterministe car nous ne pouvons pas prédire le fonctionnement de l’automate. Il commencera à l’état numéro 1 puis il devra choisir l’une des deux options possibles.

Phase 2 : l’exécution de l’automate fini

Cette phase consiste à exécuter l’automate fini pour atteindre un état valide.

L’exécution d’un automate fini déterministe ne présente pas de difficulté particulière. Il suffit de suivre les différentes transitions puisqu’un seul chemin est possible.

Cela se complique pour un automate fini non déterministe car il faut parcourir les différents chemins possibles dans l’automate. Mais en y regardant d’un peu plus près, un automate fini ressemble étrangement à un graphe orienté ! Et il existe déjà de nombreux algorithmes pour trouver son chemin dans un graphe. Nous en retiendrons deux :

• algorithme de parcours en profondeur ou Depth-First Search (DFS) en anglais
• algorithme de parcours en largeur ou Breadth-First Search (BFS) en anglais

Parcours en Profondeur

L’idée de cet algorithme est de commencer par un noeud puis d’explorer aussi loin que possible. En cas d’erreur, l’algorithme revient en arrière pour essayer une autre option.

Voici un exemple d’exécution de l’expression régulière aa|ab pour “ab” :

Cet algorithme est utilisé par la plupart des moteurs d’expression régulière comme, python, perl, nodejs (irregex) ou encore .Net. Cet algorithme est vulnérable au backtracking en cascade car la philosophie de ces moteurs est de laisser au développeur le soin de s’en protéger.

Parcours en largeur

L’idée de cet algorithme est d’explorer les noeuds voisins avant de passer aux noeuds du niveau inférieur.

Voici un exemple d’exécution de l’expression régulière aa|ab pour “ab” :

Cet algorithme a l’avantage de s’affranchir du backtracking, il est donc non vulnérable au ReDoS. Cependant, il consomme davantage de mémoire car il faut sauvegarder tous les états de l’automate. C’est l’algorithme utilisé par certains moteurs d’expression régulière comme Rust ou RE2, un moteur sûr et rapide proposé par Google.

Vous pensiez y échapper !

Sans le savoir, votre application utilise des expressions régulières que ce soit via les dépendances applicatives ou par certaines fonctions qui, indirectement, utilisent des expressions régulières.

Les dépendances

Les bibliothèques utilisées par votre application ont fort probablement recours aux expressions régulières.
Voici un exemple pour Node.js avec le package content (devenu maintenant @hapi/content) qui est utilisé pour lire les entêtes HTTP “content-type”. L’expression régulière utilisée est la suivante :

/^([^\/ ]+\/[^\s;] +)(? :(?:\s *;\s* boundary =(? :"([^"] +)"|( [^;" ] +)))|(?:\s*;\ s*[^=] +=(? :(?:"(?:[^"] +)")|(? :[^;"]+))))* $/i

Vous trouverez d’autres exemples de packages vulnérables sur ce repository Freezing the Web: A Study of ReDoS Vulnerabilities in JavaScript-based Web Servers”

Les fonctions

Certaines fonctions peuvent accepter une simple chaine de caractère (string) mais en réalité, elle sera traitée comme une expression régulière. C’est le cas par exemple en javascript avec les fonctions String.prototype.search() ou String.prototype.match().

Le code suivant serait ainsi vulnérable au ReDoS :

password.match(username);

Ce code permet de vérifier que le mot de passe défini par un utilisateur, lors de l’inscription, ne soit pas identique à son adresse mail. L’attaquant peut ainsi définir l’expression régulière de son choix en tant qu’utilisateur et un mot de passe spécialement conçu pour mener une attaque ReDoS.

Comment s’en protéger ?

Fort heureusement, toutes les expressions régulières ne sont pas sensibles au ReDoS. Il faut simplement éviter la répétition d’un groupe de capture ayant lui même une répétition ou une alternative avec un recouvrement. Voici quelques exemples:

Mais il est difficile de rester vigilant lors de l’écriture d’une expression régulière complexe. Cloudflare a par exemple introduit, le 2 juillet 2019, une expression régulière vulnérable dans son pare-feu applicatif.

Ainsi, en complément de votre vigilance, les outils d’analyse de code ou SAST (Static Application Security Testing) sont indispensables pour détecter les expressions régulières vulnérables. Voici un exemple d’alerte remontée par SonarQube :

Par ailleurs, il existe des moteurs d’expression régulière plus rapides et plus sûrs pour se protéger des attaques ReDoS. voici un exemple avec RE2 porté sur nodejs:

const RE2 = require("re2");

const safeRegex = text => {
        
  const regex = new RE2('[a-z]+@[a-z]+([a-z\.]+\.)+[a-z]+');
  let startTime = process.hrtime()
  regex.test(text)
  let endTime = process.hrtime(startTime);
  console.info('Execution time: %ds %dms \n', endTime[0], endTime[1] / 1000000)
    
};

console.log('Safe Regex with valid data :');
safeRegex('mail@octo.com');
//Execution time: 0s 0.036401ms 
  
console.log('Safe Regex with evil data :');
safeRegex('mail@e.........................................');
// Execution time: 0s 0.015162ms 

Conclusion

Le ReDoS (Regular expression Denial of Service) est donc une attaque exploitant la complexité algorithmique présente dans la plupart des moteurs d’expression régulière. En profitant d’une expression régulière vulnérable, un attaquant peut déclencher un backtracking en cascade qui utilisera toutes les ressources disponibles (CPU et mémoire) sur le serveur.

source: XKCD Perl Problems, sous licence CC BY-NC 2.5

Pour éviter qu’une expression régulière ne devienne un problème, il faut être vigilant lors de sa conception en s’aidant des outils d’analyse de code. Pour les plus exigeants, il faudra choisir un moteur d’expression régulière n’ayant pas recours au backtracking.