===========================
Indexed blind SQL injection
===========================

:Author: gamma95 <gamma95 [at] gmail> and his minions
:Date: December 03, 2011


Time based blind SQL attack suffers from low bit/request ratio. Each request produces only one valuable bit of information. This paper describes a tweak that produces higher yield at the expense of longer runtime. Along the way, some issues and notes of applicability are also discussed.


Background
++++++++++

Time based blind SQL injection attack is probably the most well-known technique in the planet. The method works by analyzing the time difference in various queries. Because query execution time is a side effect of a query, no visible output is required for this method to succeed. For example, a query could request that the DBMS to sleep for 10 seconds if the first character of the username is ``A``.

Usually, time based technique go hand in hand with binary search. Instead of asking if the first character is ``1``, then ``2``, then ``3``, it could partition the possible values into two ranges (say from ``0`` to ``4`` and ``5`` to ``9``) and ask if the first character is less than ``5``. Depending on the result, it picks out the more likely range and repeats the process until there is only one possible value. This effectively puts a logarithmic bound on number of requests to the DBMS.

In other words, each request gives us one bit of information.


Increasing the usable bit/request ratio
+++++++++++++++++++++++++++++++++++++++

Due to low bit/request ratio, an attack attempt usually leaves behind too many requests in access log. This is undesirable.

A better approach could be to encode the correct value into query execution time itself. For example, if we know the value is a number from 0 to 9, we could ask DBMS to sleep for that many seconds straight. In this case, one request carries more than 3 bits of usable information.

This is the principal idea behind our tweak.


Indexed time based attack
+++++++++++++++++++++++++

To encode more bits into the execution time, we must work with variable numeric delay values. Therefore, we need two things:

    + A measurable delay interval. Too short the interval and network latency could negatively affect our measurement. Too long the delay will also waste our time.

    + And its mapping to target values. A delay of one second could mean character ``A`` or it could also mean some other value, depending on the possible domain.
 
These necessitate an array-like index search. Say, if our domain is ten (character) values from ``0`` to ``9``, then we can easily combine them into an array like shown below.

::

       1   2   3   4   5   6   7   8   9  10   (index)
       |   |   |   |   |   |   |   |   |   |
       v   v   v   v   v   v   v   v   v   v
     +---+---+---+---+---+---+---+---+---+---+
     | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | (value)
     +---+---+---+---+---+---+---+---+---+---+

Given a random character, we can tell in one request if it is in this set, and if it is, what specific character it actually is. The way to do that is by delaying query time by the index of the character. If the input character is not in the set, there will be no delay. If it is, its index is determinable from the sleep time.


An example
++++++++++

Suppose we are trying to grab version information from a **MySQL** server. Possible characters include 0-9 and period. Observe the execution time.

::

    select sleep(find_in_set(mid(@@version, 1, 1), '0,1,2,3,4,5,6,7,8,9,.')); 
    1 row in set (6.04 sec)
    # index 6, value '5'

    select sleep(find_in_set(mid(@@version, 2, 1), '0,1,2,3,4,5,6,7,8,9,.')); 
    1 row in set (11.00 sec)
    # index 11, value '.'

    select sleep(find_in_set(mid(@@version, 3, 1), '0,1,2,3,4,5,6,7,8,9,.')); 
    1 row in set (2.00 sec)
    # index 2, value '1'

    ...

Each request gives us exactly one character (not bit).


Notes of applicability
++++++++++++++++++++++

Adjusting sleep time
====================

Faster sleep time is easily achievable by multiplying the index with some factor smaller than 1. For example, we can sleep half the time as before::

    select sleep(0.5 * find_in_set(mid(@@version, 1, 1), '0,1,2,3,4,5,6,7,8,9,.')); 
    1 row in set (3.00 sec)
    # index 6, value '5'

Similarly, longer sleep time can use factors greater than 1.

Guarding against network latency
================================

Time based attack generally works best in a fast and reliable networked environment. Small jitters in latency could skew the measurements and affect end result. However, this technique we are describing here could be modified to support network latency.

The idea is that since sleeping time is a calculated number, we could add to it a fixed amount of time for latency, or prepend some invalid characters (such as ``a`` when the domain is 0-9) in the domain set.

::

    select sleep(find_in_set(mid(@@version, 1, 1), 'a,a,a,a,0,1,2,3,4,5,6,7,8,9,.'));
    1 row in set (10.00 sec)
    # index 10, value '5'

We can also sprinkle invalid characters in between valid characters to manually adjust amount of sleeping time.

Picking an acceptable domain
============================

The set of possible values should be carefully picked to match the value that one expects. Wide domain (more values) has a better chance of catching the input, but it requires a longer sleep time on average. Narrow domain (less values) has slimmer chance to catch the input, but it generally finishes faster on average.

Some web frameworks enforce a maximum execution time. A query that takes more than, say, 30 seconds will be prime target for an early termination (and possibly logging). Therefore, picking out an acceptable domain is not only an optimization but sometimes a necessity.

Using other functions
=====================

``find_in_set`` is only one of the string search functions that MySQL supports. One can also use other functions such as ``instr``, ``locate``, and ``position``.

Sleeping in ``WHERE`` clause
============================

Most of the time, the injection point is in a ``WHERE`` clause. Because the ``WHERE`` clause is tested against all candidate rows, we better make sure that there is only **one** candidate. We can do that by making sure the table scan produces one row. Otherwise, our sleep measure will be multiplied up by the number of candidates.

::

    create table test (a int primary key, b char(16));
    insert into test values(1, 'abcd');
    insert into test values(2, 'zyxw');

    select count(*) from test;
    +----------+
    | count(*) |
    +----------+
    |        2 |
    +----------+
    # we have 2 rows in table test

    select * from test where sleep(locate(mid(@@version, 1, 1), '0123456789.'));
    Empty set (12.00 sec)
    # here we sleep for 12 seconds because all (2) rows are tested

    select * from test where a=1 and sleep(locate(mid(@@version, 1, 1), '0123456789.'));
    Empty set (6.00 sec)
    # here we sleep for 6 seconds because only one row is tested


Conclusion
++++++++++

This paper described a small tweak to the well-known time based SQL injection technique. The principle behind the increase in bit/request ratio is encoding more information in the query execution time. This is done with index based array search functions such as ``find_in_set``. The desirably smaller number of requests comes at the expense of generally longer execution time.

This paper also discussed about some technical concerns that one must pay close attention to when employing the technique. Minute aspects such as table scan, applicable value domain, network latency, and amount of sleep time are at the top list to watch out for.


Acknowledgement
+++++++++++++++

Thanks go to Nam Nguyen for his early review and support.