mcfx's blog

题解、Writeup、游记和碎碎念

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 2s and 64 1s, she needs to mark 32 of the 1s 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.

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.

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.


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

日期: 2020-04-29

标签: CTF Writeup

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