mcfx's blog

题解、Writeup、游记和碎碎念

CTFZone 2019 Quals Writeup

PPC

Fridge

In the n×nn\times n matrix, each (i,j)(i,j) operation will add a matrix to the original one, and modulo each entry with some PP. (For the first several levels, P=2P=2, and P=8P=8 or 1616 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()

Labyrinth

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

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]dp[i][j][k][mask] be: round ii, current shield jj, current attack kk, maskmask 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))

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.

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.

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'))

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.

日期: 2019-12-16

标签: CTF Writeup

这是一篇旧文,原始文章及评论可在 https://oldblog.mcfx.us/archives/276/ 查看。