dwndoc

User Tools

Site Tools

Trace: • regular_expression_denial_of_service_-_re_do_s
hack:regular_expression_denial_of_service_-_re_do_s

Table of Contents

Introduction

L' expression Regular Denial of Service (ReDoS) est une attaque de Denial of Service, qui exploite le fait que la plupart des implémentations de “ Regular Expression ” peuvent atteindre des situations extrêmes qui les font travailler très lentement (exponentiellement rattachée à la taille de l'entrée). Un attaquant peut alors créer un programme en utilisant une “ Regular Expression ” pour atteindre ces situations extrêmes et être ensuite suspendu pour une très longue période.

Description

La problématique de l'algorithme naïf Regex

L'algorithme naïf de la “ Regular Expression ” construit un Nondeterministic Finite Automaton (NFA)http://en.wikipedia.org/wiki/Nondeterministic_finite_state_machine, qui est une machine publique finie où pour chaque paire d'état et de symbole entrant on peut donner plusieurs états suivants possibles. Alors le moteur commence à faire la transition jusqu'à la fin de l'entée. Puisqu'il peut y avoir plusieurs états suivants possibles, un algorithme déterministe est utilisé. Cet algorithme essaie un par un tous les “paths” possibles (si besoin est) jusqu'à un “match” soit trouvé (ou tous les “paths” sont essayés et échouent). Pour exemple, la Regex ^(a+)+$ est représentée par la NFA suivante:

il manque la figure

Pour l'entrée aaaaX il y a 16 “paths” possibles dans le susdit graphique. Mais pour aaaaaaaaaaaaaaaaX il y a 65536 “paths” possibles et le nombre est double pour chaque a supplémentaire. C'est un cas extrême où l'algorithme naïf est problématique, parce qu'il doit poursuivre beaucoup beaucoup de “paths” et échouer ensuite. Remarquez, tous les algorithmes ne sont pas naïfs, et actuellement les algorithmes de Regex peuvent être écrits d'une façon efficace. Malheureusement, la plupart des moteurs Regex essaient aujourd'hui de résoudre non seulement les Regexes “purs”, mais ont aussi “développé” des Regexes avec des “adjonctions spéciales”, comme le “special additions”, comme avec une référence arrière qui ne peut pas être toujours être résolue efficacement (voir des Dessins pour des langues non régulières dans Wiki-Regex http://en.wikipedia.org/wiki/Regular_expression pour plus de détails). Ainsi même si le Regex n'est pas “développé”, un algorithme naïf est utilisé.

Regexes "evil"

On appelle un Regex “evil” s'il peut coller à l'entrée faite à la main. Le dessin du Regex “ evil ” contient: Le groupement avec répétition A l'intérieur du groupe répété : Répétition Alternance avec le fait de recouvrir partiellement

Exemples de dessins “ Evil “ : 

 (a+)+ 
 ([a-zA-Z]+)* 
 (a|aa)+ 
 (a|a?)+ 
 (.*a){x} | for x > 10

Tout le susdit est susceptible à l'entrée aaaaaaaaaaaaaaaaaaaaaaaa! (La longueur de l'entrée minimum pourrait changer légèrement, en utilisant plus vite ou plus lentement les machines).

Attaques

L'attaquant pourrait utiliser la susdite connaissance pour chercher des applications qui utilisent des “Regular expressions”, contenant un Regex “evil” et envoyer une entrée faite à la main correctement, qui suspendra le système. Autrement, si un Regex lui-même est affecté par une entrée d'utilisateur, l'attaquant peut injecter un Regex “evil”et rendre le système vulnérable.

Facteurs de risque

Le Web Regex-Based est :

Dans chaque couche du WEB il y a des “Regular Expressions”, qui pourraient contenir un Regex “evil”. Un attaquant peut suspendre un navigateur WEB (sur un ordinateur ou potentiellement aussi sur un mobile), suspendre une “Web Application Firewall” (WAF), attaquer une base de données et même “ stacker ” un serveur WEB vulnérable. Par exemple, si un programmeur utilise un Regex pour valider le côté client d'un système et que le Regex contient un Regex “evil”, l'attaquant peut supposer que le même Regex vulnérable est utilisé du côté serveur et envoyer une entrée faite à la main correctement, qui “stack” le serveur WEB.

Exemples

Regex vulnérable dans des dépôts en ligne

  • ReGexLib,id=1757 (email validation)http://regexlib.com/REDetails.aspx?regexp_id=1757– voit la parties audacieuse, qui est un Regex “ evil ”

    ^([a-zA-Z0-9])(([-.]|[_]+)?([a-zA-Z0-9]+))*(@){1}[a-z0-9]+[.]{1}(([a-z]{2,3})| ([a-z]{2,3}[.]{1}[a-z]{2,3}))$

Entrée : 

aaaaaaaaaaaaaaaaaaaaaaaa!
- OWASP Validation Regex Repositoryhttps://www.owasp.org/index.php/OWASP_Validation_Regex_Repository, Java Classname – voit la partie audacieuse, qui est un Regex " evil " 
^(([a-z])+.)+[A-Z]([a-z])+$

Entrée : 

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!

Attaque d'application Web

  • Ouvrir un JavaScript
    • Trouver un Regex “ evil ”
    • Faire à la main une entrée malicieuse pour trouver le Regex
    • Soumettre une valeur valide en interceptant le proxy
    • Changer la requête qui contient l'entrée malicieuse
    • Vous êtes faits !

ReDoS via injection de Regex

L'exemple suivant vérifie si le nom d'utilisateur fait partie du mot de passe entré par l'utilisateur. 

String userName = textBox1.Text;
String password = textBox2.Text;
Regex testPassword = new Regex(userName);
Match match = testPassword.Match(password);
if (match.Success)
{
   MessageBox.Show("Do not include name in password.");
}
else
{
   MessageBox.Show("Good password.");
}

Si un attaquant entre ^(([a-z])+.)+A-Z+$ comme nom d'utilisateur et aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa! comme mot de passe, le programme sera suspendu.

References

hack/regular_expression_denial_of_service_-_re_do_s.txt · Last modified: 2019/02/13 13:10 by 127.0.0.1