Google CTF Quals 2019: GLotto Writeup2019-06-27
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.
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.
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
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
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
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.
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
7 to it. To do so, we can simply perform the operation:
r8 = N % 8. Indeed, if
0, this means that
N is in the first of the 8 subparts. If
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.
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,
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
r2 through the injection (we'll see later that's it's a bit tougher).
Now, how do we reconstruct N from our
rs ? This is easily done by working our way up the equation system:
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
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
2019-03-10). In the second, date number
Now, to convert the table we obtain after our SQLi into the real remainders
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
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
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).
Building the list of
r2 is easy; we can use a subquery and make aliases:
@v is the number between
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.
<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
i2, which are the column indices that correspond to our
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 !
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.