cfreal
Google CTF Quals 2019: GLotto Writeup
2019-06-27Introduction
The Google CTF 2019 Quals happened this week-end and a friend told me about the GLotto web challenge, which seemed really fun. Can you imagine this ? A fun web challenge ! I had a go at it and here's my writeup. The idea is to push an ORDER BY SQL injection to the limit, in order to get as much information as possible. This involves a little bit of math, and a little bit of SQL dance.
Challenge
Web page
Upon browsing to https://glotto.web.ctfcompetition.com/, we're presented with a page that contains multiple winning lottery tickets for different dates. There are 4 tables, one for each of the four last months. We're allowed to sort the 4 different tables by their columns, and can submit a ticket in order to know if we won the lottery. The source code of the page is reachable here.
Source
The PHP source code reveals that an SQL table is associated to each month. Four queries are ran, one for each table; in these, the order0 to order3 GET parameters are used in an ORDER BY SQL clause. They are injectable. We also learn that a lottery ticket is generated every time we visit the page. It is stored in the database as a MySQL variable, as well as in our PHP session. When we verify our ticket, the value in our PHP session is compared with the code value we submitted, and the session value is deleted.
Approaching the problem
Problem
It is easy to figure out what we need to do: we need to obtain the value of the SQL variable @lotto by performing an ORDER BY SQL injection on the four queries that are ran. What's harder is how to solve the problem.
Finding a strategy
As the generated winning ticket contains 12 characters of a 36-character charset, we have a total of 36**12 = 4738381338321616896 possible values for a ticket. It might seem like a lot, but it is around ~62 bits. Standard ORDER BY SQL injections -- in our case IF(<condition>,date,winning) -- allow us to yield n different outputs from one query, with n being the number of columns. Since here we have 2 columns per table, we can fetch 1 bit per table, and therefore a whole 4 bits using the 4 injection points, which leaves a whole 58 bits to luck. We're a little bit off.
Luckily, the standard way ORDER BY injections are exploited is far from optimal. To improve our output, we can use the position of each row in each table as a way to encode information. For instance, the 8 rows of the March table, can be displayed in 8! different orders. The second one, which has 9 rows, can yield 9! outputs. The third and last would themselves produce 7! and 4! different outputs. This gives us 8!9!7!4! = 1769804660736000 possible outputs, which is around 50 bits. In precise terms, if we obtain information through this technique, we'll have 36**12 / (8!9!7!4!) = 2677.34 possibilities left. This is bruteforcable.
Our game plan is therefore to obtain information by permuting the rows of the 4 tables, and leave the rest to a 1 out of 2678 luck. If this fails, we can repeat the process until we do indeed get lucky.
The next challenge is to properly encode and decode information: how do we transfer the lottery ticket, @lotto, using the order of the rows of the 4 different tables ?
Solving the math problem
Numbers, numbers, numbers
As usual when solving math problems, we'd like to work with numbers. First, the lottery ticket can be though of as a number in base 36. It can be converted to base 10 using CONV(@lotto, 36, 10). Then, the date column of the March table can be converted to a sequence of number between 0 and 7 using FIND_IN_SET(MID(date, 9), '01,03,05,10,13,18,23,28,30') - 1. The same logic can be applied to the 3 other tables. The problem just got a little bit simpler: we want to transmit a number by encoding it through a permutation of sequencial numbers.
Encoding, transmitting, and decoding a number
To ease our though process, we'll know consider this subproblem: how do we encode a number in [0, 8![ through the permutation of 8 rows ?
How do we get 8! possible permutations from 8 rows ?
Imagine you have 8 boxes (the positions for the columns), aligned from left to right, in which you want to put 8 different numbers, from 0 to 7 (the columns). You first focus on the first (the left-most, for instance) box. You can put in any of the 8 numbers. You pick one, put it in, and go to the next box. You can then put any of the 7 remaining numbers in. You then go to the third box, in which you can put any of the 6 remaining numbers, etc. When reaching the last box, you have only one number left, and have no choice but to put it in. This therefore gives you the following amount of choices: 8 for the first box, then 7, then 6, etc., until 1. Each of the choices you make influences the next: if you put number 1 in the first box, it cannot be put in any of the other boxes. Therefore, you get 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 8! choices.
Encoding
Let N be the number that we wish to encode. For the first box, we have 8 choices. We can therefore split N into 8 subparts, and associate a number from 0 to 7 to it. To do so, we can simply perform the operation: r8 = N % 8. Indeed, if r8 is 0, this means that N is in the first of the 8 subparts. If r8 is 1, N is in the second subpart, etc. This gives us 8 different "parts", as we wanted. Since we've encoded part of our number into 8 possible values for the first box, we can jump to the next one.
By definition, r8 = N % 8 yields the following equation: N = d8 * 8 + r8, with d8 an unknown integer.
In the second box, we can only put 7 values. Therefore, we need to split the remaining unknown number, d8, into 7 parts. Again, this can be done by using r7 = d8 % 7. Again, this yields the equation: d8 = d7 * 7 + r7. And again, we can move to the next box.
Iterating over boxes, we get the following system:
N = 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, 1]
d2 = 0
Now, by definition, r8, r7, up until r2 are the numbers that we have put in the boxes. In other words, they are the date columns displayed on the web page, in a specific order.
For instance, if r8 is 3, we'll put the third date (2019-03-05) at index 8 in the SQL result. If r7 is 4, it means that the fourth date (2019-03-10) is at index 7 in the SQL result, etc. In essence, we transmitted r8 to r2 through the injection (we'll see later that's it's a bit tougher).
Decoding
Now, how do we reconstruct N from our rs ? This is easily done by working our way up the equation system:
Example:
r = [3, 1, 4, 3, 0, 2, 1]
N = d8 * 8 + 7 | 34843 = 8 * 4355 + 3
d8 = d7 * 7 + 1 | 4355 = 7 * 622 + 1
d7 = d6 * 6 + 5 | 622 = 6 * 103 + 4
d6 = d5 * 5 + 3 | 103 = 5 * 20 + 3
d5 = d4 * 4 + 2 | 20 = 4 * 5 + 0
d4 = d3 * 3 + 2 | 5 = 3 * 1 + 2
d3 = d2 * 2 + 1 | 1 = 2 * 0 + 1
d2 = 0 | we work our way up ^
here, N is 34843.
Transmitting
Now, we'd like to think that we are almost done; nevertheless, there is a small problem that needs to be solved. In the above example, the values I want to transmit are the following:
3, 1, 4, 3, 0, 2, 1. So, in the first box, I put 3. In the second, I put 1. In the third, 4. And in the fourth, I put 3 again... but I can't, because 3 is already in the second box !
Well, that's the thing. We don't put the exact number in the box, I put nth number that is left. Let's go back to our example:
B r Numbers left PUT
0 3 0 1 2 3 4 5 6 7 3
1 1 0 1 2 4 5 6 7 1
2 4 0 2 4 5 6 7 6
3 3 0 2 4 5 7 5
4 0 0 2 4 7 0
5 2 2 4 7 7
6 1 2 4 4
7 0 2 2
Regarding our SQL query, this translates as: In the topmost column, we have date number 3 (2019-03-10). In the second, date number 1 (2019-03-03), etc.
Now, to convert the table we obtain after our SQLi into the real remainders r2 to r8, we can:
1. Read each column for the March table, and convert the dates into their associated index D = [3, 1, 6, 5, 0, 7, 4, 2].
2. Keep a list L of numbers that are left: L = [0, 1, 2, 3, 4, 5, 6, 7].
3. For each index in D, find its position in L, then remove it from L.
This gives us:
B D L r
0 3 0 1 2 3 4 5 6 7 3
1 1 0 1 2 4 5 6 7 1
2 6 0 2 4 5 6 7 4
3 5 0 2 4 5 7 3
4 0 0 2 4 7 0
5 7 2 4 7 2
6 4 2 4 1
7 2 2 0
As you can see, our remainders are back. We can then use them to reconstruct the number.
From 1 table to 4
Now that we have a fully working strategy for 1 table, we can apply it to the 3 others. The first table gets us 8! outputs, the second 9!, and the two last 7! and 4! respectively.
To merge these values into a bigger number, we can apply the same DIVMOD strategy that we did before:
@lotto = D[march] * 8! + N[march], N[march] in [0, 8![
D[march] = D[april] * 9! + N[april], N[april] in [0, 9![
D[april] = D[may] * 7! + N[may], N[may] in [0, 7![
D[may] = D[june] * 4! + N[june], N[june] in [0, 4![
Since we only have 4 tables, D[june] cannot be determined, it's the part we leave up to luck. What are the potential values of D[june] ? Well, by definition, D[june] is the total possible values of @lotto, 36**12, divided by the multiplication of previous divisors, 8!9!7!4!. This gives us 36**12 / (8!9!7!4!) = 2677.34, the number we expected to bruteforce !
Solving the math problem using MySQL
Now that we've got all our base math set up, we can try and solve the problem using our 4 SQL injections. Once again, we'll focus on the first table, as the others are similar.
We already know how to convert the ticket into a base10 number (CONV(@lotto, 36, 10)), and the dates into sequential numbers, from 0 to 7 (FIND_IN_SET(MID(date, 9), '01,03,05,10,13,18,23,28,30') - 1).
Computing remainders
Building the list of r8 to r2 is easy; we can use a subquery and make aliases:
Assuming @v is the number between 0 and 8! that we need to bruteforce, we have:
<inner_query>:
(SELECT
( (@v ) % 8 ) r8,
( (@v DIV (8 )) % 7 ) r7,
( (@v DIV ( 8 * 7 )) % 6 ) r6,
( (@v DIV ( 8 * 7 * 6 )) % 5 ) r5,
...
)
Now, we need to convert our remainders into valid indices, as we did in the above Transmitting part.
Remainders to indices
We need to find a way to maintain a list of the remaining available indices, as well as isolate which indice corresponds to which remainder. Since MySQL does not handle arrays, a string seems to be a good candidate, as it allows us to work with a lot of string functions, such as MID() (i.e. SUBSTR()).
<middle_query>:
SELECT
@s9 := '01234567', -- Initial "array" of remaining indices
MID(@s9, r8 + 1, 1) i8, -- We extract the indice i8 which corresponds to r8
@s8 := CONCAT( -- We build @s8, which contains remaining indices...
MID(@s9, 1, r8), -- by removing the indice at position r8
MID(@s9, r8 + 2) -- and we can repeat this ...
), -- until r2
MID(@s8, r7 + 1, 1) i7, -- We extract the indice i7 which corresponds to r7 from the remaining array
@s7 := CONCAT( -- We build @s7, which contains remaining indices...
MID(@s8, 1, r7), -- by removing the indice at position r7
MID(@s8, r7 + 2) -- and so on
),
...
FROM (
<inner_query>
)a
We now have i8 to i2, which are the column indices that correspond to our r8 to r2 remainders.
We want the date with index i8 to be in the first position; the date with index i7 to be in the second position, and so on.
To do so, we build a string which compares the current column with the expected indices:
<outer_query>:
SELECT CONCAT(
@x=i8,
@x=i7,
...
@x=i2
) FROM (
<middle_query>
)b
The resulting string will be something like 00001000 for each row, with the 1 indicating at which position the row should be on the list.
When applied to the ORDER BY clause, those 00010000 numbers will be used to sort the rows, which will have the expected effect of putting each date at the correct position.
For instance, if i8=4, the fourth date will yield this number: 10000000, while the others won't have their MSB set. This means that the fourth date will have the highest number,
and therefore be put first in the list.
We're done !
Exploit
Here's the exploit. Since there's a 5 seconds wait after checking if a ticket is valid, you should run around 10 of them concurrently, until you get a match. Also, there are a few tiny MySQL tricks hidden in the exploit, so you might benefit from reading it if you're new.