I recently came across an article in MSDN magazine called Regular Expression Denial of Service Attacks and Defenses.  This article detailed a relatively new breed of Denial of Service (DOS) attack that exploits a feature of Nondeterministic Finite Automaton regex engines.  This is the type of regex engine used by .NET, Perl, Pyton, Ruby and PHP to name a few.  One thing that is so disturbing about this type of attack is how easy it is for malicious web users to find a vulnerability in your site if you are doing any kind of client side validation.  I for one have lived by the motto, "Use client side validation for user experience and server side validation for security."  Unfortunately with this type of attack sending your regex to the client will make it much easier for malicious users to find vulnerabilities in your site.

The problem regexs are ones that have something called exponential complexity.  This basically means that the number of paths that must be evaluated increases exponentially with every character added.  You run into this situation when you create a regex that has a grouping expression with repetition that is repeated itself.  Typically this basic example is given: ^(\d+)+$. 

For the purposes of our example we will use a slightly more complex regex that I found on RegexLib.  This regex is used to validate email addresses (nested repetition has been bolded): ^([0-9a-zA-Z]([-.\w]*[0-9a-zA-Z])*@([0-9a-zA-Z][-\w]*[0-9a-zA-Z]\.)+[a-zA-Z]{2,9})$

I suspect that this is a widespread problem and I plan on reviewing my own code to see if I have put any vulnerabilities out there.  To demonstrate this vulnerability I have put together a small application to run some tests against.  First I created an aspx page with a TextBox, a RegularExpressionValidator, a Label and a Button:

For the purpose of this demonstration I have set "CausesValidation" to false in my Button.  This control is only setup like this so that we can time processing time on the server side.  Below is the code for btn_SubmitClick:

In this code we are just measuring how long it takes for the validation to take place.  Lets give our page a run:

I know... not that exciting.  But now lets take a look at the rendered HTML

Notice the area highlighted in red.  This serves to make the life of any evil doers much easier.  Since the regex is on the clientside they can examine each one and look for weaknesses.  Think they will face the same delay on the client side? Not if they use something like BurpSuite to yank the javascript.  Think you can limit the number of characters they enter into the text box?  Again not if they use something like BurpSuite...  Now that we have established that you are screwed lets take a look at what some sample inputs do. 

First lets try 15 characters:

.012 seconds? Piece of cake...  Lets try 20:

.39 seconds?  Still not that scary... Lets try 25:

12.542 seconds! Now it's getting a little scary.... Lets push it to 28:

93.381 seconds...  And lets take a look at my CPU during that time:

90 seconds of hell.  I'll leave it to you to go beyond 28 characters, but I waited for quite a while at 30 characters before I gave up. 

As you can imagine a few malicious users or a small bot net could bring a website to it's knees if they have vulnerable regexs out there.  Unfortunately I don't know of a quick fix for this problem.  The best solution I've seen so far involves finding all vulnerable Regular Expressions and rewriting them.  The article mentioned at the beginning of this post goes over a good "Regex Fuzzer" (a way to find problem regular expressions), and it's definitely worth looking at.

Good luck!

When creating a web application that accepts input from users one important step to ensure that you application is secure, is assigning a maximum length to user input.  Keep in mind that input length validation is just the tip of a very large iceberg when it comes to web application security, but it is a good first step.  It's safe to say that if someone is trying to put in 1200 characters for their first name that something fishy is going on.

As much as I love ASP.NET I've found that it can easily lull some programmers into a false sense of security when it comes to input length validation.  To demonstrate what I am talking about I have put together a small application that will show how simple it is to pass longer than expected input to an application that would appear (to the uninformed programmer at least) to limit input length.

To begin I have created the basic aspx page below.  Notice the MaxLength attribute that is highlighted in red:

This is where our security troubles often begin....  It seems like this MaxLength is telling us that it won't let anything over 9 characters get passed to our beloved server.  Don't believe it!  IT'S LYING!!!  To understand why the MaxLength attribute dosn't do everything it claims it does lets go ahead and run out application and take a look at the rendered HTML:

As you can see, our seemingly invincible asp:TextBox control has been rendered as a standard html input with a maxlength of 9.  This is bad because this on the client's side, so the client can change whatever they would like and send it back to the server.  To show you what i'm talking about I am going to make use of a neat application called Burp Suite.  Burp Suite is a collection of tools that can be used for attacking web applications.  If you are at all interested in web security I recommend you download it and check out some of it's features.  For the porpouse of this post we will be using Burp Proxy, which is a HTTP Proxy server that allows you to intercept, inspect and modify the raw http traffic being passed in both directions. 

First I will go to the webpage with the vulnerability without intercepting anything.  I attempt to add more than 9 characters and, as advertised, I am not able to. 

Now I will begin capturing http traffic and submit the search text to the server.  This is where things get interesting...  Notice the red box in the image below:

So at this point burp suite has captured this HTTP request, showed me what params are in it (as well as letting me look at and mess with a whole lot of other info in the request).  It is basically in a holding state at this point until I have modified what I want and decide to forward it to the server.  So next I will change the value of tb_SearchBox and forward the request.  See below:

As you can see i've added what ever I wanted to the value of tb_SearchBox and this will now be passed to the server when I click the "forward" button.

Alright... so now that we have an idea of why this is a vulnerability how do we fix it?  The answer is by adding server side input validation.  I've found that the simplest way to do this is to compare the text length to the MaxLength of the TextBox control.  If the former is longer than the latter then your website is under attack.  Period.  What you do at that point is up to you but I recommend at a minimum doing what the comments in the IF statement from the image below suggest.

I hope this helps to make your website just a little more secure.  Remember, always be wary of built in ASP.NET validation and when in doubt, go ahead and check it on the server side.