Skip to main content

Asymmetric denial of service - ReDoS

Need​

Prevention of Regular Expression Denial of Service (ReDoS)

Context​

  • Usage of Go 1.16 for building high-performance and scalable applications
  • Usage of gin-gonic/gin for building web applications in Go
  • Usage of regular expressions for pattern matching and string manipulation

Description​

Non compliant code​

package main

import (
	"regexp"
	"github.com/gin-gonic/gin"
)

func main() {
	r := gin.Default()

	r.GET("/search", func(c *gin.Context) {
		query := c.Query("q")
		regex := regexp.MustCompile("^(a+)+$")
		
		if regex.MatchString(query) {
			c.JSON(200, gin.H{
				"message": "matched",
			})
		} else {
			c.JSON(200, gin.H{
				"message": "not matched",
			})
		}
	})

	r.Run() 
}

The above Go code is vulnerable to a Regular Expression Denial of Service (ReDoS) attack. The vulnerability lies in the regular expression ^(a+)+$ used in the GET request handler for the /search endpoint.

This regular expression is problematic because it can lead to catastrophic backtracking when certain strings are evaluated against it. The + quantifier means "one or more", and when it is used twice in succession (a+ and then another +), it creates multiple possibilities for the engine to match the input string.

For a string with many 'a' characters, the engine will try all possible permutations to find a match. This can lead to exponential growth in the number of steps the engine has to take, potentially leading to extremely long processing times, exhausting server resources and ultimately causing a denial of service.

If an attacker sends a GET request to the /search endpoint with a query string q consisting of a large number of 'a' characters, the server could be forced into a state of excessive computation, leading to a denial of service.

Steps​

  • Avoid using complex regular expressions that can lead to ReDoS vulnerabilities.
  • Use simpler regular expressions or alternative string matching techniques.
  • Validate and sanitize user input before using it in regular expressions.
  • Consider using a library or framework that provides built-in protection against ReDoS vulnerabilities.

Compliant code​

package main

import (
	"github.com/gin-gonic/gin"
)

func main() {
	r := gin.Default()

	r.GET("/search", func(c *gin.Context) {
		query := c.Query("q")
		
		if len(query) > 100 {
			c.JSON(400, gin.H{
				"message": "query too long",
			})
			return
		}

		if isSimpleString(query) {
			c.JSON(200, gin.H{
				"message": "matched",
			})
		} else {
			c.JSON(200, gin.H{
				"message": "not matched",
			})
		}
	})

	r.Run() 
}

func isSimpleString(input string) bool {
	for _, r := range input {
		if r < 'a' || r > 'z' {
			return false
		}
	}
	return true
}

The updated code no longer uses a regular expression to match the query string. Instead, it uses a simple function isSimpleString to check if the input string only contains lowercase letters. This function iterates over each rune in the string and checks if it is within the range of lowercase letters. If it encounters a rune that is not a lowercase letter, it returns false, indicating that the string does not match.

Before checking the string, the code also checks if the length of the query string is greater than 100. If it is, the code returns a 400 status code with a message indicating that the query is too long. This is a simple form of input validation that can help prevent denial of service attacks by limiting the amount of data that the server needs to process.

This approach avoids the use of complex regular expressions, which can lead to ReDoS vulnerabilities. It also validates and sanitizes user input before using it in string matching, which is a good practice for preventing a variety of security vulnerabilities.

References​

Last updated on