CTFZone 2019 Quals Writeup

# PPC
### Fridge
In the $$n\times n$$ matrix, each $$(i,j)$$ operation will add a matrix to the original one, and modulo each entry with some $$P$$. (For the first several levels, $$P=2$$, and $$P=8$$ or $$16$$ later)
We can compute a basis to solve this problem.
```python
import socket
import random
import sys
from copy import deepcopy

_debug=False

class Remote:
	def __init__(self,ip,port):
		self.s=socket.socket(socket.AF_INET, socket.SOCK_STREAM)
		self.s.connect((ip,port))
		self.buf=''
	def send(self,s):
		self.s.send(s.encode())
	def recvbyte(self):
		if len(self.buf)==0:
			self.buf=self.s.recv(1024).decode().replace('\r','')
		res=self.buf[0]
		self.buf=self.buf[1:]
		if _debug:
			sys.stdout.write(res)
			sys.stdout.flush()
		return res
	def unrecv(self,s):
		self.buf=s+self.buf
	def recvuntil(self,s):
		res=''
		while res[-len(s):]!=s:
			res+=self.recvbyte()
		return res

r=Remote('ppc-fridge.ctfz.one',31337)

def getlvl():
	s=[]
	s+=[list(map(lambda x:int(x,16),r.recvuntil('\n').split(' ')))]
	for i in range(len(s[0])-1):
		s+=[list(map(lambda x:int(x,16),r.recvuntil('\n').split(' ')))]
	return s

def test(x,y):
	r.send(str(x)+','+str(y)+'\n')
	t=r.recvbyte()
	if t=='t':
		r.recvuntil('\n')
		return True
	r.unrecv(t)
	return False

def hash(x):
	res=0
	for i in x:
		for j in i:
			res=res*2+j
	return res

def umax(s):
	res=0
	for i in s:
		res=max(res,max(i))
	return res

def test8(cur,n,m):
	print('test8=============================')
	P=umax(cur)+1
	def add(x,y):
		res=deepcopy(x)
		for i in range(n):
			for j in range(m):
				res[i][j]=(res[i][j]+y[i][j])%P
		return res
	def sub(x,y):
		res=deepcopy(x)
		for i in range(n):
			for j in range(m):
				res[i][j]=(res[i][j]+P-y[i][j])%P
		return res
	op=[[0 for i in range(m)]for j in range(n)]
	for i in range(n):
		for j in range(m):
			if test(i,j):return
			nxt=getlvl()
			op[i][j]=sub(nxt,cur)
			print(i,j,op[i][j])
			cur=nxt
	for i in range(10):
		x=random.randint(0,n-1)
		y=random.randint(0,m-1)
		print('random test:',x,y)
		if test(x,y):return
		nxt=getlvl()
		assert nxt==add(op[x][y],cur)
		cur=nxt
	sc=[[0 for i in range(m)]for j in range(n)]
	sv=[[0 for i in range(m)]for j in range(n)]
	for i in range(n):
		for j in range(m):
			oc=op[i][j]
			ov=[[0 for i in range(m)]for j in range(n)]
			ov[i][j]=1
			flag=False
			for x in range(n):
				if flag:continue
				for y in range(m):
					if oc[x][y]:
						if sc[x][y]==0:
							print(x,y,oc)
							sc[x][y]=oc
							sv[x][y]=ov
							flag=True
							break
						tc=sc[x][y]
						tv=sv[x][y]
						assert tc[x][y]
						while oc[x][y]:
							o=tc[x][y]//oc[x][y]
							for uu in range(o):
								tc=sub(tc,oc)
								tv=sub(tv,ov)
							oc,tc=tc,oc
							ov,tv=tv,ov
						sc[x][y]=tc
						sv[x][y]=tv
	oc=cur
	ov=[[0 for i in range(m)]for j in range(n)]
	print('try to find sol')
	for x in range(n):
		for y in range(m):
			if oc[x][y]:
				tc=sc[x][y]
				tv=sv[x][y]
				while oc[x][y]:
					oc=add(oc,tc)
					ov=add(ov,tv)
	for x in range(n):
		for y in range(m):
			assert oc[x][y]==0
	print('find sol:',ov)
	for i in range(n):
		for j in range(m):
			for k in range(ov[i][j]):
				print('work:',i,j)
				if test(i,j):return
				cur=getlvl()

def work():
	global _debug
	print('try to get lvl')
	_debug=True
	s=getlvl()
	_debug=False
	n=len(s)
	m=len(s[0])
	print(s)
	test8(s,n,m)

while True:
	work()
```

### Labyrinth
A maze. However, there are some hidden mines in the map. So just mark them and avoid them.
```python
import socket
import random
import sys
from copy import deepcopy
import json
import os
from pwn import *

_debug=True

r=remote('ppc-labyrinth.ctfz.one',4340)

N=41
M=201

def recvmap():
	res=[]
	for i in range(min(N,curx+601)):
		res.append(r.recvuntil('\n').decode().strip())
		if res[-1][:9]=='Exception':
			print(res[-1])
			markmine()
			r.interactive()
	return res

known_map={}

curx=0

def rmap():
	global cury
	fe=False
	t=recvmap()
	n=len(t)
	for i in range(n):
		if len(t[i])!=201:
			if t[i][0]!='#':print(t)
			assert t[i][0]=='#' and t[i][-1]=='#'
			while len(t[i])<201:
				t[i]+=' '
		for j in range(M):
			if t[i][j]=='@':
				cury=j
				ux=i
				t[i]=t[i][:j]+' '+t[i][j+1:]
			elif t[i][j]=='E':
				t[i]=t[i][:j]+' '+t[i][j+1:]
				fe=True
			elif t[i][j]!='#' and t[i][j]!=' ':
				print('find strange point:',i,j)
				print(t[i])
	for i in range(n):
		px=i-ux+curx
		if px in known_map:
			for j in range(201):
				assert known_map[px][j]=='*' or known_map[px][j]==t[i][j]
		else:
			known_map[px]=t[i]

vis={}

def getm(x,y,tx,ty):
	if tx==x+1:return 'down'
	if tx==x-1:return 'up'
	if ty==y+1:return 'right'
	return 'left'

def upmove(ss):
	global curx,guessy
	guessy=cury
	for s in ss:
		if s=='up':curx-=1
		if s=='down':curx+=1
		if s=='left':guessy=guessy-1
		if s=='right':guessy=guessy+1
	r.send(','.join(ss)+'\n')
	rmap()

guessy=0
def markmine():
	t=known_map[curx]
	t=t[:guessy]+'*'+t[guessy+1:]
	known_map[curx]=t
	save()

def find_path(sx,sy,tx,ty):
	if sx==sy and tx==ty:return []
	q=[(tx,ty)]
	fa={(tx,ty):0}
	i=0
	res=[]
	while i<len(q):
		x,y=q[i];i+=1
		def chk(nx,ny):
			if ny<201 and nx in known_map and known_map[nx][ny]!='#' and known_map[nx][ny]!='*' and (nx,ny) not in fa:
				fa[(nx,ny)]=(x,y)
				q.append((nx,ny))
				if nx==sx and ny==sy:
					while nx!=tx or ny!=ty:
						gx,gy=fa[(nx,ny)]
						res.append(getm(nx,ny,gx,gy))
						nx=gx;ny=gy
		chk(x+1,y)
		chk(x-1,y)
		chk(x,y+1)
		chk(x,y-1)
		if len(res):return res

def get_reach(sx,sy):
	q=[(sx,sy)]
	fa={(sx,sy):0}
	i=0
	while i<len(q):
		x,y=q[i];i+=1
		def chk(nx,ny):
			#print(nx,ny)
			if ny<201 and nx in known_map and known_map[nx][ny]!='#' and known_map[nx][ny]!='*' and (nx,ny) not in fa:
				fa[(nx,ny)]=(x,y)
				q.append((nx,ny))
		chk(x+1,y)
		chk(x-1,y)
		chk(x,y+1)
		chk(x,y-1)
	return fa

def print_whole_map():
	t=list(known_map)
	t.sort()
	for i in t:
		u=''
		for j in range(201):
			u+='@' if curx==i and cury==j else known_map[i][j]
		print(u)

def print_reachable():
	t=list(known_map)
	t.sort()
	rcs=get_reach(curx,cury)
	for i in t:
		u=''
		for j in range(201):
			if curx==i and cury==j:
				u+='@'
			elif (i,j) in rcs:
				u+='-'
			else:
				u+=known_map[i][j]
		print(u)

def save():
	open('map.txt','w').write(json.dumps(known_map))
def load():
	global known_map
	t=json.loads(open('map.txt').read())
	for i in t:
		known_map[int(i)]=t[i]

def random_walk():
	while True:
		nx=random.randint(-300,0)
		ny=random.randint(150,200)
		if known_map[nx][ny]==' ':
			break
	pt=find_path(curx,cury,nx,ny)
	for i in range(0,len(pt),20):
		upmove(pt[i:i+20])
		print('R',i,len(pt),curx,cury,pt[i])

if os.path.exists('map.txt'):load()
rmap()
print_whole_map();#exit()
print()
print_reachable()
save();#exit()

while True:
	t=list(known_map)
	t.sort()
	pt=False
	for i in t:
		for j in range(201):
			if known_map[i][j]==' ' and (i,j) not in vis:
				pt=find_path(curx,cury,i,j)
				if pt:break
				print(i,j,'failed')
		if pt:break
	print(pt)
	i=-40
	if curx>=-500:
		for i in range(0,len(pt),40):
			upmove(pt[i:i+40])
			print(i,len(pt),curx,cury,pt[i])
			if curx<-500:break
	st=i+40
	for i in range(st,len(pt),1):
		upmove(pt[i:i+1])
		print(i,len(pt),curx,cury,pt[i])
	print_whole_map()
	print(curx,cury)
	save()
```

### StarWars
When we successfully attacked some ship, our shield will be the max of our old one and shield of that ship, our attack will be the sum modulo 256.
The action of other players are always the same. So the current state is only related with current shield and attack, and the remaining ships.
So we can use dp to solve this. Let $$dp[i][j][k][mask]$$ be: round $$i$$, current shield $$j$$, current attack $$k$$, $$mask$$ stores remaining ships. The dp relation is obvious.
```cpp
#include<bits/stdc++.h>

typedef std::pair<int,int> pii;
template<typename T> inline T max(T a,T b){return a>b?a:b;}

#define xx first
#define yy second
#define mp(a,b) std::make_pair(a,b)
#define pb push_back
#define fo0(i,n) for(int i=0,i##end=n;i<i##end;i++)

const int system_ships_t[16][2]={
 {20,10},
 {60,10},
 {30,20},
 {80,20},
 {100,20},
 {200,25},
 {600,25},
 {400,50},
 {800,20},
 {1000,100},
 {1600,125},
 {2000,100},
 {3000,150},
 {6000,100},
 {20000,255},
 {10000,1},
};
const int ships_t[17][2]={
 {50,10},
 {30,20},
 {10,60},
 {100,6},
 {20,30},
 {50,15},
 {70,10},
 {120,5},
 {800,1},
 {350,2},
 {10,100},
 {40,15},
 {35,20},
 {70,15},
 {60,20},
 {88,8},
 {99,9},
};
const int attack_order[17][24]={
 {0,0,0,0,0,0,2,3,2,5,2,5,4,7,7,5,0,1,8,2,8,7,0,14},
 {1,2,2,1,1,3,4,3,0,4,7,15,4,11,6,0,0,2,8,6,10,7,5,8},
 {2,1,1,1,0,3,5,2,2,1,3,5,0,3,3,4,15,13,0,4,8,10,13,1},
 {2,0,0,2,0,3,5,1,5,4,2,4,8,0,15,9,4,8,3,1,7,9,0,6},
 {1,1,0,0,1,3,5,1,1,2,5,2,8,8,6,4,7,5,9,2,3,2,8,4},
 {2,1,2,0,1,5,4,2,1,0,1,1,8,5,7,2,7,5,8,4,0,15,8,3},
 {2,1,2,0,1,3,5,5,5,3,7,5,1,5,8,4,5,15,1,9,10,0,10,0},
 {1,2,0,2,1,5,2,2,3,4,3,2,8,1,3,5,7,8,1,2,2,0,4,1},
 {0,1,1,1,1,0,0,5,2,0,0,6,2,3,3,5,2,4,7,15,2,2,1,6},
 {0,2,0,0,1,4,0,3,0,2,1,8,3,6,2,7,15,4,6,2,15,6,5,0},
 {2,0,1,2,2,5,0,4,0,3,0,2,1,4,2,3,15,0,0,5,9,9,1,4},
 {2,2,0,1,0,0,3,4,15,9,0,13,4,3,4,0,5,2,7,10,9,10,1,11},
 {1,0,2,0,1,1,5,5,3,2,3,0,6,0,7,2,4,8,1,5,15,4,3,9},
 {2,1,1,1,1,4,5,4,3,2,7,8,6,4,4,0,3,6,7,2,6,2,9,3},
 {2,0,0,1,1,5,1,3,3,2,8,5,1,3,7,1,7,2,9,8,0,2,4,1},
 {0,2,2,0,2,0,5,2,3,3,0,7,0,5,4,0,6,6,0,3,6,3,8,9},
 {0,0,1,2,0,4,1,0,15,4,11,4,12,8,3,4,6,10,12,13,1,11,4,9},
};

pii ssp[16],sp[17],spo[16][25];

bool work(pii a,pii b,pii&res)
{
	int ac=a.yy?b.xx/a.yy:1e9,bc=a.xx/b.yy;
	if(ac<=bc)
	{
		res=mp(max(a.xx,b.xx),(a.yy+b.yy)&0xff);
		return 1;
	}
	return 0;
}

int hc,hid[23333],hv[33];

std::bitset<1<<16|5> f[25][33][256];

std::vector<int> find_seq(int ti,int tj,int tk,int tl)
{
	if(ti==0)return std::vector<int>();
	int i=ti-1;
	std::vector<std::pair<pii,pii>>ef;
	fo0(j,hc)fo0(k,256)
	{
		for(int l=f[i][j][k]._Find_first();l<f[i][j][k].size();l=f[i][j][k]._Find_next(l))
		{
			fo0(x,17)
			{
				pii tmp;int mask;
				if(x)
				{
					int t=x-1;
					if(l>>t&1)continue;
					if(!work(mp(hv[j],k),spo[t][i],tmp))continue;
					mask=l|1<<t;
				}
				else tmp=mp(hv[j],k),mask=l;
				if(!work(tmp,ssp[attack_order[0][i]],tmp))continue;
				if(hid[tmp.xx]==tj&&tmp.yy==tk&&mask==tl)ef.pb(mp(mp(j,k),mp(l,x)));
			}
		}
	}
	std::vector<int>res=find_seq(ti-1,ef[0].xx.xx,ef[0].xx.yy,ef[0].yy.xx);
	res.pb(ef[0].yy.yy);
	return res;
}

int main()
{
	fo0(i,16)ssp[i]=mp(system_ships_t[i][0],system_ships_t[i][1]);
	fo0(i,17)sp[i]=mp(ships_t[i][0],ships_t[i][1]);
	memset(hid,0xff,sizeof hid);
	fo0(i,16)if(!~hid[ssp[i].xx])hv[hid[ssp[i].xx]=hc++]=ssp[i].xx;
	fo0(i,17)if(!~hid[sp[i].xx])hv[hid[sp[i].xx]=hc++]=sp[i].xx;
	fo0(i,16)
	{
		spo[i][0]=sp[i+1];
		fo0(j,24)
		{
			assert(work(spo[i][j],ssp[attack_order[i+1][j]],spo[i][j+1]));
		}
	}
	f[0][hid[sp[0].xx]][sp[0].yy]=1;
	fo0(i,24)
	{
		fo0(j,hc)
		{
			fo0(k,256)
			{
				for(int l=f[i][j][k]._Find_first();l<f[i][j][k].size();l=f[i][j][k]._Find_next(l))
				{
					fo0(x,17)
					{
						pii tmp;int mask;
						if(x)
						{
							int t=x-1;
							if(l>>t&1)continue;
							if(!work(mp(hv[j],k),spo[t][i],tmp))continue;
							mask=l|1<<t;
						}
						else tmp=mp(hv[j],k),mask=l;
						if(mask==65535)
						{
							std::vector<int>ans=find_seq(i,j,k,l);
							ans.pb(x);
							for(auto i:ans)printf("%d ",i);puts("");
							exit(0);
						}
						if(!work(tmp,ssp[attack_order[0][i]],tmp))continue;
						f[i+1][hid[tmp.xx]][tmp.yy][mask]=1;
					}
				}
			}
		}
	}
}
```

After running this, we find the unique sequence that leads to win.
However, the output part failed to run on my computer, so here is a python code to output the flag:
```python
import hashlib

s=[0,0,0,0,0,0,0,11,16,0,1,10,6,13,3,2,9,15,8,14,12,5,4,7]
hs=hashlib.sha256(bytes(s)).digest()
u=[514320763,1323926996,700138656,849420235,427957186,1264587960,734406206,1885512490]
ut=[]
for i in u:
	ut.append(i&255)
	ut.append(i>>8&255)
	ut.append(i>>16&255)
	ut.append(i>>24&255)
ut=bytes(ut)
ans=[]
for i in range(32):
	v=(ut[i]^hs[i])%127
	ans.append(v if v>=32 else v+32)
print(bytes(ans))
```

# Reverse

### Baby rev
A dos executable. It reads a file and divide it into parts. In each part, it’s compared each byte to some value.
The following script is to extract these compared values from the asm presented by IDA.
```python
s=[-1 for i in range(480)]
for i in open('tmp.txt').readlines():
	t=i[23:].strip()
	if t.startswith('cmp     byte ptr') and '+' in t:
		t=t[t.find('+')+1:]
		o=t[:t.find('h')]
		if ']' in o:o=o[:o.find(']')]
		o=int(o,16)
		t=t[t.find(',')+1:]
		v=t[:t.find('h')]
		v=int(v,16)
		s[o]=v

s[0]=0xdb
for i in range(480):
	if s[i]==-1:print(i)
open('test.bin','wb').write(bytes(s))
```
File tmp.txt contains asm like:
```
seg000:0214 loc_10214:                              ; CODE XREF: sub_101FA+15↑j
seg000:0214                 cmp     byte ptr [si+1], 0DBh
seg000:0218                 jz      short loc_1021D
seg000:021A                 jmp     loc_10426
seg000:021D ; ---------------------------------------------------------------------------
seg000:021D
seg000:021D loc_1021D:                              ; CODE XREF: sub_101FA+1E↑j
seg000:021D                 cmp     byte ptr [si+2], 0DBh
seg000:0221                 jz      short loc_10226
seg000:0223                 jmp     loc_10426
```
Finally run “BABY_REV test.bin” we got the flag.

### CSES
The program requires lua, and it communicates with the server to execute commands.
In the main function, an array is decoded, and then it’s the lua bytecode.
I used luadec to decompile the bytecode, but some functions were incorrect.
However, in the handle_answer function, we saw the command.
```lua
handle_answer = function(answer)
  -- function num : 0_14 , upvalues : _ENV
  enc_index = (string.find)(answer, "encrypt::")
  dec_index = (string.find)(answer, "decrypt::")
  command = rc4_cipher("ctfzone2019", base64_dec("1bC87lzEebgL"))
  bin_index = (string.find)(answer, command)
  if enc_index == 1 or dec_index == 1 or bin_index == 1 then
    print_result(answer)
  end
End
```
I patched this function, and find that command is “gpsjdeadk”.
Then I send this to the server, an large base64 encoded string is returned. It contains an ELF file, the server.
The server encrypts flag with an hard coded AES key, and use the encrypted flag as IV and key for later encryption.
The following script is to find the encrypted flag. The final decryption is too easy, and I won’t put it here.
```python
import socket
import random
import sys
from copy import deepcopy
from pwn import *

r=remote('re-cses.ctfz.one',3607)

def encrypt(s):
	r.send('encrypt::'+s+'\n')
	return r.recvuntil('\0')[:-2].decode('base_64')

def decrypt(s):
	r.send('decrypt::'+s.encode('base_64').strip()+'\n')
	res=''
	for i in range(len(s)):
		t=r.recv(1)
		if t=='\0':break
		res+=t
	return res

def xor(a,b):
	r=''
	for i in range(len(a)):
		r+=chr(ord(a[i])^ord(b[i]))
	return r

a='1'*16
x=encrypt(a)[:16]

xu=decrypt(x+x)
b=xu[:16]
c=xu[16:]
print b.encode('hex'),c.encode('hex')

rc=xor(c,x)
flag_enc=xor(rc,a)
print(flag_enc.encode('hex'))
```

### Strange_pdf
The comment starting with % in pdf file will be ignored by pdf-viewer, and there is one program in the comment just after header. Also, there is anther comment later which is “55 AA”, the end signature of MBR. So the program is a 16-bit x86 program and it print 99399 on screen, which is x.

CTFZone 2019 Quals Writeup

最新文章

最近回复

分类

归档

其它