Security Thoughts

Friday, October 05, 2007, 17:47

Optimizing the number of requests in blind SQL injection

Blind injection is often considered as an On/Off binary research accomplished using the bisection algorithm.
When the bisection algorithm is applied the complexity is O(Log2 n) where n is in the case of the extended ASCII character set is 255.
So for each character at a given position 'p' the total number of requests will be:

Log2 n = Log2 255 = ~7

So if the lenght of the information to be retrieved is 8,
the total number of requests to be sent is

8 * Log2 255 = 56

Let's suppose now, there is the following situation:

http://vi.ctim/page.jsp?id=1

where page.jsp is a script which loads dinamically content by using the SQL query:

qry= "Select content from pages where id="+Request.value("id");

Let's suppose the rest of the application gives no clue about SQL errors or the possibility to use other tricks in order to force the web application to display the informations we want.
This is a classical Blind SQL Injection case.

But what happens if by changing 'id' values results displaying different pages?

The attacker could use the different responses in order to map the results of an injected conditional sql statement.

That is.
Let's suppose there are more than 255 values for the 'id' parameter

"http:// vi.ctim/page.jsp?id=1"
"http:// vi.ctim/page.jsp?id=2"
...
"http://vi.ctim/page.jsp?id=255"

then let's map every single snippet of unique text content for every request.
Then by setting

For (pos = 1; pos<LEN(@@version)){
idval="(CASE substr(@@version,"+pos+",1)
   when char(1) then 1
   when char(2) then 2
   when char(3) then 3
   when char(4) then 4
   when char(4) then 5
   etc
   end )"
get response for:
"http://vi.ctim/page.jsp?id=idval"
}

the attacker will have to accomplish only

LEN(@@version)

requests, because for every request the application will return the page mapped to the character value.

Now, this is the best case.
For every character value exists a single id value.

There could be a number of id values which is less than 255
(or # printable chars for non binary information).

Let's suppose there exist only 4 unique id values corresponding to 4 unique responses.
Then the injected query will be (in pseudo code):

res=substr(@@version,pos,1);

if(res>191 and res<255)
  then 1
else if(res>127 and res<192)
  then 2
else if(res>63 and res<128)
  then 3
else
    4

For each result, the set of values we are analysing will be 1/4 of the previous set.

This algorithm has O(Log4 255), which will correspond to

LEN*Log4 255 = LEN*3.9

requests to be sent.

The worst case is the On/Off bisection algorithm already described in several papers.

I don't have the time to implement it now, but I hope to see some tool with this (maybe) new approach in it:)

Comments:

Wisec, Tuesday, October 09, 2007, 00:20

Just a couple of corrections:
--

Log2(256) = 8
Log2(255) = 7.99
so getting a 8 chars length data takes 64 requests and not 56 (my bad:).

--

There are at least three ways to do the mapping of ID <-> Response:
1. Spidering (which is always done during the information gathering phase)
2. Googling (ditto - i.c.s.)
3. Id Bruteforcing

That means there are at least 256 requests to be sent, before the blind sql Injection attack, in order to map unique response with IDs, but once the mapping is done, the number of requests tends asynthotically to be proportional to the length of the information to be inferred.
This means that, considering the 3. case which is about bruteforcing IDs, when the sum of the length length of the informations an attacker wants to retrieve is higher than:

256*log2(256)= 2048

this approach is worth using.

Anyway considering the number of requests during spidering and googleing is more than 256 it's like economical amortization.
The more Kilobytes you'll get, the best this approach will save your time.

I forgot to say that:
comments are appreciated and welcome as usual.

Bedirhan Urgun, Tuesday, October 09, 2007, 15:54

Hi,
very clever idea for "mappable" sql injection points.

I'm not really a math guy, but if you please, I'll post some of the derivings I got after your post.

When we compare the two approaches, the normal one and yours;

NoOfReqs#1 = L * log2(256)
NoOfReqs#2 = Y + L * logx(256)

L: length
Y: no of initial ID bruteforce requests
let's take 256 as opposed to 255 for the extended ascii range.

We try to find a relation bet. L and Y where;

NoOfReqs#2 < NoOfReqs#1

that is,

Y + L * logx(256) < L * log2(256)

which after some calculation (for Y > 0) comes up to;

Y < 4*L , for x=4
Y < (5.3)*L , for x=8
...
Y < 7*L , for x=256

these are the relations for a criteria to select bet. normal approach and your approach.

Wisec, Tuesday, October 09, 2007, 16:27

Hi Bedirhan,
thank you!
You completed the math concepts of this post and I really appreciate it :)

Yes, there are cases in which the normal approach is better. For example when you know the DB structure and you just want to get a specific user password or something like that.

When indeed, during black box pen tests, I have to test Web application security, the first thing to do is spidering the entire application.
This means that, after the spidering, it is possible to already have the informations we need.

Moreover, during blackbox testing if the tester finds a "Mappable" Blind Injection the whole accessible information has to be extracted, so Length (L) could be also some MB, making my approach probably worth using.

Bedirhan Urgun, Tuesday, October 09, 2007, 19:29

Hi Stefano, :)

Open source (blind sql injection) db dumpers are most of the time "ready to go". However, with this approach there's also an additional customization phase for mapping.

Nevertheless, your approach is a clever and economical way to accomplish the task at hand.

Wisec, Tuesday, October 09, 2007, 19:38

Thanks Bedirhan :)

All in one Web scanner could use it as the spidering stage is embedded, and probably some open source tool using this approach will come out.
Who knows ;)

Wisec, Tuesday, October 09, 2007, 19:43

Ah, thanks to your definition Bedirhan,
I would like to officially call this approach:

"Mappable Blind Sql Injection"

Bedirhan Urgun, Wednesday, October 10, 2007, 07:50

You are right. It shouldn't be that hard for an automatic scanner to find "maps" for a blind sql injection. :) Just one bit, IDs might not just comprise of numerical/incrementing values but, for example, some sparse account numbers or even e-mail addresses. Anyways, for a really less noisy blind SQLi exploits, your approach should help a lot!

And yes, "mappable blind sql injection" it is! :)
thanks.

Bernardo Damele, Thursday, October 11, 2007, 15:43

Hi Stefano,

I find this new approach to blind SQL injection interesting. I wrote a post on my blog with some notes about it if you want to have a look, http://tinyurl.com/363hso

Security Thoughts

Wisec is brought to you by...