Un Denis de Service en Regex

Les expressions régulières : un outil pour vous

Lorsque nous utilisons des expressions régulières, nous nous disons constamment que c'est une formidable invention, car elle nous permet d'économiser un nombre impressionnant de lignes de codes. Elles ne représentent qu'un moyen efficace de vérifier des informations ou de récupérer certaines parties de texte.
On entend souvent dire que les expressions régulières sont puissantes parce qu'elles conviennent à énormément de cas, mais on le sait tous, les outils flexibles amènent toujours un peu d'insécurité.

Et un outil contre vous

Les expressions régulières sont très flexibles notamment grâce aux métacaractères qui permettent de valider un certain nombre de fois des sous-patterns ou des classes de caractères. Ils permettent de valider énormément de chaines différentes selon les cas. Il y a aussi une autre fonctionnalité qui influe sur les regex : c'est la possibilité de capturer des morceaux de chaines avec les parenthèses. En effet, lorsqu'on utilise un regex replace (re.sub() en Python) vous utiliser les parenthèses pour spécifier des parties d'une chaine que vous souhaitez utiliser. Et lorsque vous utilisez juste les parenthèses pour spécifier un bloc de texte vous suffixez la première parenthèse avec ?: pour les rendre non capturantes.
Cette capture met en mémoire une partie de la chaine et, dans la majorité des cas, plus il y a des parties capturantes plus la regex prendra de temps à s'exécuter.

Exemple de regex pour un DOS

Voici une table d'exemple avec des chaines, la regex qui leur est appliquée et le temps d'exécution sur ma machine (selon les performances des machines, cette durée change).

Chaine
Regex
Temps d'exécution
aaaaaaaaaaaaaaaaaaaaaah^(a+)+$33
aaaaaaaaaaaaaah^((a+)+)+$35
aaaaaaaaaah ^((((a+)+)+)+)+$122

Un JSfiddle pour tester vous même

C'est un exemple simple, mais il fonctionne parfaitement. Vous n'aurez pas de déni de service sur votre machine car le code Javascript trop long est stoppé par le navigateur. Ce code JSfiddle permet juste de voir le temps utilisé pour interpréter une chaine et comment modifier la regex pour que le temps d'exécution s'allonge !
http://jsfiddle.net/jedema/ecdy7w29/

Comment effectuer un DOS réel

Ce type de Déni de service peut être pratique pour rendre un serveur inaccessible quelque temps (ou amoindrir ces performances). Il faut pour cela que le développeur utilise le texte de l'utilisateur pour effectuer une regex. Et ça arrive ! En effet, lorsque certains développeurs utilisent une liste déroulante HTML, ils oublient parfois que l'utilisateur peut envoyer n'importe quelle valeur (même si elle n'est pas contenue dans les options du select). Il suffit donc d'injecter une chaine qui sera utilisée en tant qu'expression régulière par le serveur.
Souvent les protections contre les dénis de services permettent de blacklister une adresse IP si elle envoie trop de requêtes, les attaques reDOS passent au travers de ces protections. En effet, régulièrement les scripts PHP ont une limite d'exécution de 30 secondes, donc une requête toutes les 30 secondes peuvent largement affecter les performances du serveur ciblé.

Exemple concret

Un commerçant a commandé un site vitrine sur mesure pour présenter son matériel de pêche. En effet, il reçoit de ses fournisseurs des fichiers CSV contenant:
Son prestataire voulait développer une interface pour sauvegarder en base de données les données contenues dans chaque CSV pour les rechercher en SQL. Le montant du devis était trop élevé pour le client. Donc le prestataire propose de tout faire à partir des CSV comme si les fichiers CSV étaient une base de données. Le client accepte.
Le code qui nous intéresse est le champ de recherche qui permet au client de rechercher des articles. Ce code est composé d'une page HTML avec un formulaire contenant un champ texte pour spécifier le texte à rechercher. Le code PHP (mais ça aurait pu être n'importe quelle technologie utilisant les regex), génère une expression régulière à partir du texte entré par le client

preg_match('#([^;]*'.$_POST['texte_cherche'].'[^;]*)#', $csv_produit, $produit_list);
Vous voyez bien dans cette ligne de code que le texte du formulaire n'est pas vérifié et que n'importe quelle regex peut être entrée. Ce formulaire de recherche est donc faillible à ce type d'attaque.

Éviter les reDOS

Tout d'abord et comme d'habitude il est conseillé de toujours vérifier les valeurs envoyées par le client. Là, le prestataire aurait dû vérifier la chaine envoyée par le client avant d'utiliser une regex. (aparté : il existe des algo de recherche bien plus efficace qu'une simple regex, il suffit de chercher).
En sortant de l'injection effectuée par le client, faites attention lorsque vous écrivez vos regex. Vous pourriez sans le vouloir en écrire une très complexe et qui plombe vos performances en fonction des données envoyées par le client.

Bonne (journ|soir)ee, et chouchoutez vos regex !