题解、Writeup、游记和碎碎念
In the matrix, each operation will add a matrix to the original one, and modulo each entry with some . (For the first several levels, , and or later)
We can compute a basis to solve this problem.
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()
A maze. However, there are some hidden mines in the map. So just mark them and avoid them.
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()
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 be: round , current shield , current attack , stores remaining ships. The dp relation is obvious.
#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:
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))
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.
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.
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.
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.
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'))
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.
日期： 2019-12-16
这是一篇旧文，原始文章及评论可在 https://oldblog.mcfx.us/archives/276/ 查看。