Skip to main content

Asymmetric denial of service - ReDoS

Need​

Mitigation of Regular Expression Denial of Service (ReDoS) attacks

Context​

  • Usage of Dart 2.0 for building high-performance, cross-platform applications
  • Usage of Shelf for managing and organizing data in a Node.js application

Description​

Non compliant code​

import 'package:shelf/shelf.dart' as shelf;
import 'dart:io';
import 'dart:async';
import 'dart:convert';

void main(List<String> args) {
  var handler = const shelf.Pipeline().addMiddleware(shelf.logRequests()).addHandler(_echoRequest);

  io.serve(handler, 'localhost', 8080);
}

Future<shelf.Response> _echoRequest(shelf.Request request) async {
  var data = await request.readAsString();
  var regex = new RegExp(r'(a+)+$'); // Dangerous regular expression

  if (regex.hasMatch(data)) {
    return shelf.Response.ok('Match found');
  } else {
    return shelf.Response.ok('No match found');
  }
}

The above code is a simple server that listens to incoming requests and checks if the request data matches a regular expression. The vulnerability lies within the _echoRequest function where a dangerous regular expression is used.

The regular expression (a+)+$ is considered dangerous because it falls into a category of regular expressions that can cause a ReDoS (Regular Expression Denial of Service) attack.

ReDoS is a form of Denial of Service attack that targets the CPU time of a server. It does so by providing a regular expression that takes a very long time to evaluate.

In this case, the regular expression (a+)+$ can take an exponential amount of time to evaluate for long strings of 'a'. This is because the '+' operator is greedy and will try to match as many 'a' characters as possible, and the enclosing parenthesis and '+' operator will cause this matching to happen multiple times.

If an attacker sends a long string of 'a' characters, the server could spend an excessive amount of time trying to evaluate the regular expression, thus causing the server to become unresponsive or crash.

This vulnerability is particularly dangerous in a backend application, as it opens up the potential for any client to crash the server, simply by sending a specially crafted string in a request.

Steps​

  • Identify the dangerous regular expressions in your code. In this case, it's the '(a+)+$' regular expression.
  • Understand the potential catastrophic backtracking in the regular expression. This happens when a regular expression has nested quantifiers like '(a+)+$'.
  • Simplify the regular expression to avoid catastrophic backtracking. In this case, the regular expression can be simplified to 'a+$' which will match one or more 'a' characters at the end of a string.
  • Test the new regular expression to ensure it works as expected and does not introduce new vulnerabilities.
  • Review other parts of your code to identify any other potentially dangerous regular expressions and repeat the process.

Compliant code​

import 'package:shelf/shelf.dart' as shelf;
import 'dart:io';
import 'dart:async';
import 'dart:convert';

void main(List<String> args) {
  var handler = const shelf.Pipeline().addMiddleware(shelf.logRequests()).addHandler(_echoRequest);

  io.serve(handler, 'localhost', 8080);
}

Future<shelf.Response> _echoRequest(shelf.Request request) async {
  var data = await request.readAsString();
  var regex = new RegExp(r'a+$'); // Simplified regular expression

  if (regex.hasMatch(data)) {
    return shelf.Response.ok('Match found');
  } else {
    return shelf.Response.ok('No match found');
  }
}

The original code contained a dangerous regular expression (a+)+$ which could lead to a Regular Expression Denial of Service (ReDoS) attack. This type of attack occurs when a regular expression has nested quantifiers, which can cause the regular expression engine to enter a state of catastrophic backtracking when trying to find a match. This can lead to the server becoming unresponsive or crashing.

The regular expression was simplified to a+$ to avoid this vulnerability. This regular expression will match one or more 'a' characters at the end of a string, which is the intended functionality of the original regular expression, but without the risk of a ReDoS attack.

It's important to review other parts of the code to identify any other potentially dangerous regular expressions and repeat the process. Regular expressions should be as simple as possible to avoid unnecessary complexity and potential vulnerabilities.

References​

Last updated on