Regular expressions

Regular expressions are one of the most used programming functions. Almost all big programming languages such as Java, C# have them embedded in their language.

But before we go deeper in to the topic you first need to understand what a regular expression ( regex) is. Regex is a character set witch describes certain patterns its is mostly used to match and locate text in a string.

A regular expressions is a way to describe patterns. A computer can recognize these regular expressions and will be able to recognize text inside for example a document. You can for example use a regular expression to search through a text or check if an email-address is correctly formatted.

There are a lot of character used in a regular expression and it can be unreadable to the untrained eye.

Cheat sheet summary

To make a regex yourself you need to understand the list below. in doing so you have to understand what each character means and does.

ass you can see its quite an extensive list of characters

Regex is a realy powerfull tool to restrict string inputs

By default the community made some standard expressions you can use for your goal so you don't have to create one yourself. But you must be able to understand what is being performed in such an expression.

Cyber

Denial of service attack (ReDoS)

A denial of service attack is when an attacker makes an online service slow down or become unavailable to its users.

Denial-of-service for regular expressions (ReDoS) is a denial-of-service attack that takes advantage of the fact that most implementations of regular expressions can get into extreme situations that make them work very slowly (exponentially depending on the input size). An attacker can use a [stripped down] regular expression to get a program into these extreme situations and then get stuck for a long time.

Evil Regex

A regex pattern is known as a evil regex if it can get stuck in the generated input that is given.

Evil regex contains :

• Grouping with a lot of repetition
• Inside of repetition group
  • Again repetition (many nested repertitions)
  • Alternation with overlapping

some examples

• ^(a+)+$
  

• ([a-zA-Z]+)*
  

• (a|aa)+
  

• (a|a?)+
  

• (.*a){x} for x \> 10
  

• \^([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}))$ 
  

These regex expressions are all sensitive to the string input:

•     aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!
  

var validUrlRegex = /^(https?:\/\/)?([\da-z\.-]+)\.([a-z\.]{2,6})([\/\w \.-]*)*\/?$/
var url = 'https://google.com/'

console.time('regex evaluation time')

if (url.match(validUrlRegex)) {
  console.log(url + ' is a valid url')
} else {
  console.log(url + ' is not a valid url')
}

console.timeEnd('regex evaluation time')

The output should be:

https://google.com/ is a valid url
regex evaluation time: 2ms

But now consider to apply the regular expression on a bad url introduced in our code by an attacker.

var validUrlRegex = /^(https?:\/\/)?([\da-z\.-]+)\.([a-z\.]{2,6})([\/\w \.-]*)*\/?$/
var badUrl = 'https://google.com/aaaaaaaaaaaaaaaaaaaaaaaa@'

console.time('regex evaluation time')

if (badUrl.match(validUrlRegex)) {
  console.log(badUrl + ' is a valid url')
} else {
  console.log(badUrl + ' is not a valid url')
}

console.timeEnd('regex evaluation time')

Output:

https://google.com/aaaaaaaaaaaaaaaaaaaaaaaa@ is not a valid url
regex evaluation time: 2196ms

As you can observe, the evaluation time of regex has been increased by 1000 times by adding only 25 characters to previous url. Let's see why.

_Fair warning, I actually managed to crash my computer when trying this out by giving a super long string as input.

The attack

Prevent This Vulnerability

Recognizing evil regular expressions requires in-depth knowledge / experience with them. There are also tools to recognize these types of regular expressions. As a software-engineer you have to be vary careful when applying regular expressions in your code. Always have a limit on how many characters to accept from a input. Or use standard libraries to check certain expressions. "Sanitize and filter user's inputs" this is a rule valid also for other type of attacks. Since the attack can be originated from a input string, filter and sanitize it before to evaluate it to avoid unhandled errors or attacks.