Wednesday 26 October 2011

Exploiting 'INSERT INTO' SQL Injections Ninja Style

In the deep hours of the night you stumble upon a form where you are asked for, among other things, your nickname. You enter a single quote ' as your name and you get an error message saying: "You have an error in your SQL syntax". With high probability the SQL injection is taking place in an INSERT statement. Now, you could simply start sqlmap and let it try to do the dirty work. But there's a disadvantage: An automated tool will probably send some request where the INSERT statement succeeds. This will create strange entries in the database. We must avoid this to remain stealthy.

Let's create a similar situation locally and demonstrate this. Our test code is:

 <?php  
 $con = mysql_connect("localhost", "root", "toor") or die(mysql_error($con));  
 mysql_select_db("testdb", $con) or die(mysql_error($con));  
 $var = $_POST['post'];  
 mysql_query("INSERT INTO data VALUES ('one', '$var')") or die(mysql_error($con));  
 mysql_close($con) or die(mysql_error($con));  
 echo "The values have been added!\n";  
 ?>  

Normally a good programmer will write better code than that, but it's just an example and will suffice to demonstrate the exploit. We run sqlmap against this using the command
./sqlmap.py -u "http://localhost/test.php" --data "post=ValidValue" -v 3
The (partly redacted) output of the command can be seen on pastebin. It found an error-based SQL injection. We will return to this result at the end of the post. For now we will ignore the error-based SQL injection and only notice that unwanted new database entries have been added by using sqlmap:


Avoiding unwanted inserts

We must find a query that is syntactically correct yet contains a semantic error. Moreover the semantic error should only be detectable by executing the query. I immediately thought of scalar subqueries. These are subqueries that must return only a single row, otherwise an error is thrown. As quoted from the MySQL manual:
In its simplest form, a scalar subquery is a subquery that returns a single value. A scalar subquery is a simple operand, and you can use it almost anywhere a single column value or literal is legal, and you can expect it to have those characteristics that all operands have: a data type, a length, an indication that it can be NULL, and so on.
An artificial example is:
SELECT (SELECT name FROM users WHERE email = 'bobby@tables.com')
If the subquery is empty it's converted to the value NULL. Now, if email is a primary key then at most one name will be returned. If email isn't a primary key it depends on the contents of the database. This proves that we must first execute the subquery and only then will we know if it's really a scalar subquery or not! Another variation where the subquery must be scalar is:
SELECT 'Your name is: ' || (SELECT name FROM users WHERE email = 'bobby@tables.com')
Here || stands for the string concatenation. The following query will always return the error "#1242 - Subquery returns more than 1 row" (tested with MySql).
SELECT (SELECT nameIt FROM ((SELECT 'value1' AS nameIt) UNION (SELECT 'value2' AS nameIt)) TEST)
Alright so we have a query that is executed yet returns an error. This prevents the original INSERT INTO command from being executed, yet our own SQL code will be executed. I will now show how to turn this into a usable blind SQL injection. We will create different behavior/results based on a boolean condition. We can follow two strategies to achieve this. The first is to find another semantic error and output a different error based on the boolean condition. The second strategy is to use a timing attack: If the condition is true the query will complete instantly, otherwise it takes a longer time. The timing attack is the easier one to create. Consider the following SQL statement, where we replaced the nameIt column of the previous SQL statement with a more advanced expression:
SELECT (SELECT CASE WHEN <condition> THEN SLEEP(3) ELSE 'anyValue' END FROM ((SELECT 'value1' AS nameIt) UNION (SELECT 'value2' AS nameIt)) TEST)
If <condition> is true the server will sleep for 3 seconds and then throw an error that the subquery returned more than one result. Otherwise, if <condition> is false, it will instantly throw the error. All that is left to do is to measure the time it takes for the server to answer the query so we know whether the condition was true or not. We can use automated tools that perform the timing attack based on this foundation.


Let's return to our example php code. What do we need to set our argument called post to in order to launch the attack? Try figuring it out yourself first. This is something you must learn to do on your own, especially since you are given the source code.

Sending the following will do the trick:
' || (SELECT CASE WHEN <condition> THEN SLEEP(3) ELSE 'anyValue' END FROM ((SELECT 'value1' AS nameIt) UNION (SELECT 'value2' AS nameIt)) TEST) || '
This will expand to:
INSERT INTO data VALUES ('one', '' || (SELECT CASE WHEN <condition> THEN SLEEP(3) ELSE 'anyValue' END FROM ((SELECT 'value1' AS nameIt) UNION (SELECT 'value2' AS nameIt)) TEST) || '')
Which is valid SQL syntax!

Speeding up the attack

This is all good and well, but because it's a time based attack it can take an extremely long time to execute. We focus on the other strategy where we trigger different errors based on the boolean condition. First we need to find another error that we can trigger based on a boolean condition. Sound fairly straightforward, but it turns out generating an error is easy, yet finding errors that are generated whilst executing the query and controllable by a boolean condition can be quite hard. After more than an hour of messing around with some SQL statements and reading the MySQL documentation I finally found something usable! I got the following SQL statement:
SELECT 'canBeAnyValue' REGEXP (SELECT CASE WHEN <condition> THEN '.*' ELSE '*' END)
Here the construct 'value' REGEXP 'regexp' is a boolean condition that is true when value matches the regular expression regexp and is false otherwise. Note that '.*' is a valid regular expression and '*' is not. So when <condition> is true the regular expression will simply be evaluated. When it's false an invalid regular expression is detected and MySql will return the error "#1139 - Got error 'repetition-operator operand invalid' from regexp". Excellent! We can now create a boolean based blind SQL injection where the subquery error is returned if the condition is true, and the regular expression error is returned when the condition is false.

But there's a snag: One must be careful with the REGEXP error. Say you modify the time based SQL attack statement to the following:
SELECT (SELECT CASE WHEN <condition> THEN 'anyValue' REGEXP '*' ELSE 'AnyValue' END FROM ((SELECT 'value1' AS nameIt) UNION (SELECT 'value2' AS nameIt)) TEST)
You reason as follows: If <condition> is false it will return 'thisCanBeAnyValue' twice and then throw an error that the subquery returned more than one result. If <condition> is true it tries to evaluate 'anyValue' REGEXP '*' and throw the regular expression error. But this is not what will happen! With this line you will always end up with the regular expression error. Why? Because MySql knows that 'anyValue' REGEXP '*' is a constant expression and doesn't depend on anything. Therefore it will optimize the query and calculate this value in advance. So even though <condition> is false it still attempts to evaluate the regular expression during the optimization step. This always fails, and hence the regular expression error is always returned. The trick is to put the '*' and '.*' in a separate SELECT CASE WHEN .. END control flow so it won't be optimized.

We conclude our story with the following SQL statement against our example code:
' || (SELECT 'thisCanBeAnyValue' REGEXP (SELECT CASE WHEN <condition> THEN '.*' ELSE '*' END) FROM ((SELECT 'value1' AS nameIt) UNION (SELECT 'value2' AS nameIt)) TEST) || '
When the condition is false the regular expression error will be returned, and when the condition is true the subquery error will be returned. All this happens without the actual INSERT statement being successfully executed even once. Hence the website administrator will notice no weird entries in his database. And last but not least, this attack is faster compared to the earlier time based attack. Beautiful! :D

Even better: Error-based SQL injection

The previous methods were ideas I found myself. However the website is returning an error message, and there is a known error-based SQL injection technique that can return database entries in the error message. This is the type of attack that sqlmap also returned. With an error-based SQL injection we can greatly speed up the attack. The technique is based on the follow query:
SELECT COUNT(*), CONCAT('We can put any scalar subquery here', FLOOR(RAND(0)*2)) x FROM information_schema.tables GROUP BY x
When we execute this command I get the message "ERROR 1062 (23000): Duplicate entry 'We can put any scalar subquery here' for key 'group_key'". As you can see the original input string is returned in the error message! In fact we can put any value we want there, including scalar subsqueries. Let's first investigate why this error is returned. In the MySql documentation we first notice: "You cannot use a column with RAND() values in an ORDER BY clause, because ORDER BY would evaluate the column multiple times". RAND() will also be evaluated multiple times in a GROUP BY clause. Each time RAND() is evaluated it will return a new result. Okay, so according to the documentation we're actually not allowed to use the function RAND() like this. Why? Because the function returns a new value each time it's evaluated yet MySql expects a function to always return this same value. This can cause strange error messages like the one we just got.

One possible description of an Advanced Persistant Threat.
... people smarter than me found the "non-blind" error-based attack ...

Nevertheless the error message contains a user controllable string! Meaning we can let it return any database entry we want, which greatly speeds up the attack. But perhaps you're still wondering why this particular query fails. Well, answering that question means knowing exactly how the DBMS executes the query. Investigating this is way out of scope for this post. Just remember that in our query the problem is caused because the RAND() function is internally reevaluated and will return a different value, which is something the DBMS is not expecting.

Let's put this in our example code again. Something like the following will suffice:
' || (SELECT 'temp' FROM (SELECT COUNT(*), CONCAT((subquery returning the value we want to retrieve), FLOOR(RAND(0)*2)) x FROM information_schema.tables GROUP BY x) FromTable) || '
Et voila, we have a very fast SQL injection. Depending on the tables we can access, this example might need to be modified in order to work properly. In particular we can also include one of the previous SQL injections that always generate an error. This way we will be sure data is never inserted. After all, we are relying on undefined behavior which causes the error to show up. Who knows if there exists another DBMS that handles these queries with RAND() in them differently and they don't produce an error.

As a last note, being stealthy is always a relative notion. In some cases SQL errors could be logged and an administrator could be notified when they happen. In such a situation this attack wouldn't be stealthy at all!

Follow me on twitter @vanhoefm


Addendum:
  • For Oracle 8, 9 and 10g databases the function utl_inaddr.get_host_name can be used to launch an error-based SQL injection. For Oracle 11g ctxsys.drithsx.sn and other functions can be used. [Source1] [Source2]