ReDoS

Quinta-feira passada, eu estava procrastinando como sempre, quando me deparei com um vídeo de uma talk chamada “The State of the Web”. O título do vídeo em questão era “JavaScript Vulnerabilities”. Como amante de web pretensioso que sou, logo pensei “vou abrir, mas duvido que aprenda algo novo”. Apenas 51 segundos depois, o entrevistado disse a seguinte frase (traduzida):

Também há coisas que as pessoas não pensam sobre, como regular expression denial-of-service.

Congelei imediatamente. Já conhecia Denial-of-Service e também já mexi (mais do que gostaria) com RegEx. Mas DoS usando RegEx⁈ Fui pesquisar.

Ao que me parece, esse tipo de ataque não é dos mais comuns, por depender muito de casos específicos em código utilizando RegEx. De qualquer forma, conhecimento nunca é demais. Trago aqui, então, um overview do que descobri em minhas pesquisas.

Como funciona

Um ReDoS depende, primeiramente, da utilização de input do usuário em algum RegEx. Além disso, a expressão regular utilizada deve intrinsicamente conter alguma vulnerabilidade na sua formação. Alguns padrões, como repetições de repetições, costumam ser os causadores de ReDoS. A Open Web Application Security Project (OWASP), uma organização com foco em segurança na web, separa em dois casos:

a expressão regular aplica repetição (+, *) a uma subexpressão complexa (possivelmente esta também com repetições);
para a subexpressão repetida, existe uma correspondência que também é sufixo de outra correspondência válida.

No exemplo a seguir, usamos ^(a+)+$ como RegEx malicioso — vamos dissecá-lo para melhor entendimento:

^ procura pelo início de uma string;
() cria um ‘grupo’;
a procura pelo caractere ‘a’;
+ procura por 1 ou mais ocorrências do item precedendo-o — seja este um caractere ou um grupo;
$ procura pelo final de uma string.

O problema está no fato de que a+ procura a de 1 a n vezes até parar. Portanto, a combinação de (a+) com + faz com que ele procure de 1 a n vezes para a e de 1 a n vezes para cada tentativa em (a+), criando um crescimento exponencial de tentativas. Em nosso benchmarking, tivemos os seguintes resultados — a adição de somente um a dobra o tempo necessário para avaliar a expressão:

{% highlight js %} const a1 = “aaaaaaaaaaaaaaaaaaaaaaaaaaa!”; const a2 = “aaaaaaaaaaaaaaaaaaaaaaaaaaaa!”;

/^(a+)+$/.test(a1); //=> 1056.115967 ms

/^(a+)+$/.test(a2); //=> 2092.657715 ms {% endhighlight %}

Na vida real

Para você que está pensando: “muito legal, mas aonde isso ocorreria na vida real? Parece específico demais”, não tema! Para testar essa vulnerabilidade em um caso “real”, criei um pequeno prompt de e-mail, para um suposto cadastro em uma Newsletter.

Porém, precisamos garantir que o input contém um e-mail! Para isso, podemos pesquisar online por um RegEx que detecte e-mails, como esse:

{% highlight js %} let exp = /^([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}))$/; {% endhighlight %}

É muito extenso, então ao invés de tentar entender o que ele faz, vamos testar para ver se funciona!

O sistema está funcional e quase não nos custou tempo! Perfeito!

Ou… quase. A maior causa[citation needed] de vulnerabilidades não serem detectadas é a falta de testes nos inputs. Um lema muito conhecido na área de segurança da informação é “Nunca confie em input do usuário” (como exemplificado nesse XKCD). Isso se dá pelo fato de que, na maioria das vezes, desenvolvedores assumem que o input não receberá nada fora do esperado, como nos exemplos acima, em que eu só testei para casos ‘plausíveis’ de e-mail. Agora, vamos ver o que acontece com um input muito longo, por exemplo:

A expressão que usamos para esse exemplo de e-mail está listada na Wikipedia como exemplo de RegEx vulnerável, devido à este fragmento:

(([\-.]|[_]+)?([a-zA-Z0-9]+))*

que é parecido com nosso primeiro exemplo, (a+)+:

(( … +)?( … +))*

Nesse exemplo, a expressão regular está sendo avaliada no front-end. Por isso, o maior dano que ela fará é travar a página em que está aberta, e nada mais. Contudo, caso fosse utilizada no lado do servidor, essa demora seria crítica, podendo afetar a velocidade da conexão de outros clientes com o servidor, sendo então considerada um ataque de DoS.

Fique sempre atento ao utilizar quaisquer expressões regulares copiadas da internet! Evidentemente, existem várias outras expressões regulares para detecção de e-mails mais bem formuladas, que não possuem essa vulnerabilidade.

Conclusão

Não me considero um expert no assunto, muito pelo contrário. Porém, espero que, se como eu, você nunca tinha ouvido falar de ReDoS antes, agora você já tenha alguma ideia do que é e como se prevenir.

Para aprender mais sobre ReDoS, abaixo estão as referências e links recomendados.

Mas, antes, deixo um fato que você não pediu sobre algo que você não se interessa:

Assim como humanos, gatos também podem ser destros, canhotos ou ambidestros — e essa característica está relacionada ao temperamento do animal. Além disso, felinos com preferências de pata mais proeminentes tendem a ser mais confiantes, afetivos, ativos e amigáveis. [ref 1] [ref 2] [ref 3] [ref 4]