Asymmetric denial of service - ReDoS - Java

Asymmetric denial of service - ReDoS - Java

Need

Mitigation of Regular Expression Denial of Service (ReDoS) attacks

Context

  • Usage of Java for building scalable and robust applications
  • Usage of javax.servlet for building Java web applications with Servlet technology
  • Usage of java.io for input and output operations in Java
  • Usage of java.util.regex for regular expression matching and manipulation in Java

Description

Non compliant code

        import javax.servlet.*;
import javax.servlet.http.*;
import java.io.*;
import java.util.regex.*;

public class VulnerableServlet extends HttpServlet {
    public void doPost(HttpServletRequest request, HttpServletResponse response) throws ServletException, IOException {
        String input = request.getParameter("input");
        Pattern pattern = Pattern.compile("^(a+)+$"); 
        Matcher matcher = pattern.matcher(input);
        if (matcher.matches()) {
            response.getWriter().println("Match found");
        } else {
            response.getWriter().println("Match not found");
        }
    }
}
        
        

The above code is an example of a servlet that receives an input parameter from a POST request and checks if it matches a specific regular expression. The vulnerability lies in the regular expression used: ^(a+)+$.

This regular expression is vulnerable to a Regular Expression Denial of Service (ReDoS) attack. The regular expression is considered "dangerous" because it uses nested quantifiers ( +), which means it can take a very long time to evaluate certain strings.

For instance, if an attacker sends a string of 'a's followed by a single non-'a' character, the regular expression engine will take an exponentially increasing amount of time to determine that the string doesn't match the regular expression. This is because the engine has to backtrack and try every possible combination of 'a's to see if it can find a match.

In a real-world scenario, an attacker could send such a string as part of a POST request to the servlet, causing the server to use up a lot of resources and potentially crash, thereby denying service to legitimate users.

Steps

  • Avoid using complex regular expressions that can lead to exponential backtracking.
  • Use a more efficient regular expression pattern that does not have the potential for ReDoS.
  • Validate and sanitize user input before using it in regular expressions.
  • Implement input length limits or timeouts to prevent excessive processing time.
  • Consider using a library or framework that provides built-in protection against ReDoS.

Compliant code

        import javax.servlet.*;
import javax.servlet.http.*;
import java.io.*;
import java.util.regex.*;

public class SecureServlet extends HttpServlet {
    private static final int MAX_INPUT_LENGTH = 1000;

    public void doPost(HttpServletRequest request, HttpServletResponse response) throws ServletException, IOException {
        String input = request.getParameter("input");

        // Validate and sanitize input length
        if (input != null && input.length() > MAX_INPUT_LENGTH) {
            response.getWriter().println("Input is too long");
            return;
        }

        // Use a more efficient regular expression pattern
        Pattern pattern = Pattern.compile("^[a]+$"); 
        Matcher matcher = pattern.matcher(input);
        if (matcher.matches()) {
            response.getWriter().println("Match found");
        } else {
            response.getWriter().println("Match not found");
        }
    }
}
        
        

The updated code includes several changes to mitigate the risk of a Regular Expression Denial of Service (ReDoS) attack.

1. Input Length Validation: The code now checks the length of the input string before processing it. If the input is longer than a predefined maximum length (in this case, 1000 characters), the method returns an error message and stops processing. This prevents an attacker from causing a denial of service by sending an extremely long string.

2. Efficient Regular Expression: The regular expression has been simplified to ^[a]+$, which matches one or more 'a' characters at the start and end of the string. This pattern does not have the potential for exponential backtracking, making it more efficient and less susceptible to ReDoS attacks.

These changes help to ensure that the server can process user input quickly and efficiently, reducing the risk of a denial of service.

References