PlaidCTF 2020 Writeup

# 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()
```

PlaidCTF 2020 Writeup

最新文章

最近回复

分类

归档

其它