# Introduction

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 `r`s ? 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 `n`th 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.