CTFZone 2019 Quals Writeup December 16, 2019 # PPC ### Fridge In the $$n\times n$$ matrix, each $$(i,j)$$ operation will add a matrix to the original one, and modulo each entry with some $$P$$. (For the first several levels, $$P=2$$, and $$P=8$$ or $$16$$ later) We can compute a basis to solve this problem. ```python 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. ```python 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]$$ be: round $$i$$, current shield $$j$$, current attack $$k$$, $$mask$$ stores remaining ships. The dp relation is obvious. ```cpp #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: ```python 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. ```python 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. ```lua 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. ```python 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.
HITCON CTF 2019 Quals Writeup October 15, 2019 # Misc ### EmojiiVM It's too long to directly print each character, but we can push 1,1,1,2,...,9,9 into the stack, and write a simple loop to print the table. Unfortunately my blog doesn't support emojis, so here's no solution. ### heXDump Xxd only overwrites the first bytes of the file, so we can just enumerate each byte. ```python from pwn import * r=remote('13.113.205.160',21700) def get(): r.recvuntil('0) quit\n') r.send('2\n') return r.recvuntil('\n')[:-1] r.recvuntil('0) quit\n') r.send('1337\n') fh=get() known='hitcon{' while True: flag=False for j in range(32,127): print j t=known+chr(j) r.recvuntil('0) quit\n') r.send('1\n') r.recvuntil('format)\n') r.send(t.encode('hex')+'\n') if get()==fh: known=t flag=True break print known if not flag: break ``` # Crypto ### Very Simple Haskell If a bit in the flag is 1, the answer will multiply square of a specific prime number. Then we can use meet-in-middle to find the answer. However, here N is too big, so just factorize the primes is okay. ```python from gmpy2 import * from Crypto.Util.number import isPrime primes=[] pinv={} for i in range(2,5000): if isPrime(i): pinv[i]=len(primes) primes.append(i) print(len(primes)) n=134896036104102133446208954973118530800743044711419303630456535295204304771800100892609593430702833309387082353959992161865438523195671760946142657809228938824313865760630832980160727407084204864544706387890655083179518455155520501821681606874346463698215916627632418223019328444607858743434475109717014763667 base=129105988525739869308153101831605950072860268575706582195774923614094296354415364173823406181109200888049609207238266506466864447780824680862439187440797565555486108716502098901182492654356397840996322893263870349262138909453630565384869193972124927953237311411285678188486737576555535085444384901167109670365 req=84329776255618646348016649734028295037597157542985867506958273359305624184282146866144159754298613694885173220275408231387000884549683819822991588176788392625802461171856762214917805903544785532328453620624644896107723229373581460638987146506975123149045044762903664396325969329482406959546962473688947985096 req=req*invert(base,n)%n flag='hitcon{' for i in range(6): t=0 for j in range(8): r=28+i*8-j if req%primes[r]==0: t|=1<<j flag+=chr(t) print flag+'}' ``` ### Rᴀɴᴅᴏᴍʟʏ Sᴇʟᴇᴄᴛ A In the signing process, whatever we send to the server, the deflated data is ~90 bytes, then after padding they will have common high bits. Now we have some equations like $$a^3=bN+c+K$$ ($$a<n$$, $$c<\sqrt{n}$$ and $$K$$ is constant). It means $$(a^3-K)$$ is very close to a multiple of N. We can use some linear combinations of these $$a^3-K$$ to make a number very close to N. Assume we have a set of these close-multiple of N, then we can take two numbers from the set, make the difference, then insert back to the set. Each time we do this, and maintain the smallest numbers, finally we can get a number close to N. Also we know some linear equations of $$(a^3-K)$$ that resulted in N, gaussian elimination these equations, we can find b in the original equations. Then N is also found. After knowing N, we can send any command to the server. But we still need to sign it. When signing, we need to calculate the cube root of a padded string. We can use Bleichenbacher’s Low-Exponent Attack, but the deflated string is too long, so this will probably fail. Then I wrote the deflate algorithm myself, and changed the huffman tree to lower the size, and just enumerate nonce and wait until we find one. Signing script: ```python import sys import zlib,hashlib,random from gmpy2 import * import numba as nb from multiprocessing import Pool @nb.jit(nopython=True) def get_hdict(codelengths): mp={} nextcode = 0 for codelength in range(1, max(codelengths) + 1): nextcode <<= 1 startbit = 1 << codelength for (symbol, cl) in enumerate(codelengths): if cl != codelength: continue mp[symbol]=startbit | nextcode nextcode += 1 return mp @nb.jit(nopython=True) def upd(a,au,b,c,d): if not b in a: a[b]=c au[b]=d else: if c<a[b]: a[b]=c au[b]=d @nb.jit(nopython=True) def cal_huffman(s): ps=[0] for i in s: ps.append(ps[-1]+i) f=[{(0,2):0}] for i in range(19): f.append({(100+i,0):0}) g=[{(0,2):(0,0)}] for i in range(19): g.append({(100+i,0):(0,0)}) best=10**10 bp=0,0,0 LIM=450 if len(s)>15 else 120 for i in range(1,16): for j in f[i-1]: x,y=j if y>len(s)-x: continue v=f[i-1][j] for k in range(1+min(y,len(s)-x)): if (y-k)*2>len(s)-(x+k): continue nv=(ps[x+k]-ps[x])*i+v upd(f[i],g[i],(x+k,(y-k)*2),nv,j) if x+k==len(s): if nv<best: best=nv bp=i,x+k,y-k res=[0] t,x,y=bp for i in range(t,0,-1): ox,oy=g[i][x,y] res+=[i]*(x-ox) x,y=ox,oy return res[:0:-1] @nb.jit(nopython=True) def getkl(s): s2=[] for ii in s: if len(s2)==0 or s2[-1][0]!=ii: s2.append([ii,1]) else: s2[-1][1]+=1 re=[(0,0)] for i in s2: if i[0]==0: if i[1]<3: for j in range(i[1]): re.append((0,0)) elif i[1]<11: re.append((17,i[1]-3)) else: re.append((18,i[1]-11)) continue if i[1]<=3: for j in range(i[1]): re.append((i[0],0)) continue if i[1]<=7: re.append((i[0],0)) re.append((16,i[1]-4)) else: re.append((i[0],0)) re.append((16,3)) if i[1]-7<=2: for j in range(i[1]-7): re.append((i[0],0)) else: re.append((16,i[1]-10)) return re[1:] @nb.jit(nopython=True) def ad(s,l,x): if l!=-1: for i in range(l): s.append(x>>i&1) else: assert x t=0 while x>>t: t+=1 for i in range(t-2,-1,-1): s.append(x>>i&1) @nb.jit(nopython=True) def compress(s): t={-1:-1} t.pop(-1) for i in s: t[i]=0 for i in s: t[i]+=1 for i in range(10): t[i+48]+=100 t[34]+=40 t2=[] for i in t: t2.append((t[i],i)) t=t2 t.sort() t=t[::-1] tx=[] for i2 in t: tx.append(i2[0]) tx.append(1) tp=[4]*11+[5]*8+[6]*4 tpx=[0 for i in range(257)] for i in range(len(t)): tpx[t[i][1]]=tp[i] tpx[256]=tp[-1] tpc=get_hdict(tpx) tl=getkl(tpx+[0]) tlu={} for ii in tl: tlu[ii[0]]=0 for ii in tl: tlu[ii[0]]+=1 tlux=[] for i in tlu: tlux.append((tlu[i],i)) tlux.sort() tlux=tlux[::-1] tlk_=[] for ii in tlux: tlk_.append(ii[0]) tlkl=cal_huffman(tlk_) tlklu=[0]*19 for i in range(len(tlux)): tlklu[tlux[i][1]]=tlkl[i] res=[0] res.pop() res+=[1] #final ad(res,2,2) #type ad(res,5,0) #hlit ad(res,5,0) #hdist tlklc=get_hdict(tlklu) rest=[0] rest.pop() ad(rest,3,tlklu[16]) ad(rest,3,tlklu[17]) ad(rest,3,tlklu[18]) ad(rest,3,tlklu[0]) tlklu[16]=0 tlklu[17]=0 tlklu[18]=0 tlklu[0]=0 for i in range(100): su=0 for j in tlklu: su+=j if su==0:break j = (8 + i // 2) if (i % 2 == 0) else (7 - i // 2) ad(rest,3,tlklu[j]) tlklu[j]=0 ad(res,4,(len(rest)-12)/3) #hclen res+=rest for ii in tl: ad(res,-1,tlklc[ii[0]]) if ii[0]==16: ad(res,2,ii[1]) elif ii[0]==17: ad(res,3,ii[1]) elif ii[0]==18: ad(res,7,ii[1]) for i in s: ad(res,-1,tpc[i]) ad(res,-1,tpc[256]) while len(res)%8: res+=[0] fin=[] for i in range(0,len(res),8): tuu=0 for j in range(8): tuu+=res[i+j]<<j fin.append(tuu) return fin def real_comp(s): fin=''.join(map(chr,compress(list(map(ord,list(s)))))) ss=zlib.compress(s) return '789c'.decode('hex')+fin+ss[-4:] def sign(m_): m,id=m_ h=int(hashlib.sha256(m).hexdigest(),16) ni=0 hh=str(h) mi=10**15 posi=0 while True: a=ni%(len(hh)-7);b=ni/(len(hh)-7) t='{"hash":%d,"nonce":"%s"}'%(h,''.join([random.choice(list('0123456789'))for _ in range(8)])) x=real_comp(t) if len(x)<=83:posi+=1 u='\xCA\xFE\x12\x04'+x+'\0'*(251-len(x)) v=int(u.encode('hex'),16) g=iroot(v,3) g=g[0] if g[1] else g[0]+1 v=g**3 rv=('%x'%v).decode('hex') ut=int(rv[4:4+len(x)].encode('hex'),16)^int(x.encode('hex'),16) if ut<mi: mi=ut print 'cur best(%d):'%id,mi if rv[4:4+len(x)]==x: open('result.txt','ab').write(m+' '+rv+'\n') print rv return rv ni+=1 if ni%1000==0: print ni,posi if __name__ == '__main__': pool = Pool(processes=4) pool.map(sign,[('meow*',_) for _ in range(4)]) ``` Attack script: ```python from pwn import * from gmpy2 import gcd,iroot import zlib,hashlib r=remote('54.92.6.97', 3239) def geto(): r.recvuntil('meow?\n') r.send('meow~\n') r.recvuntil('meow~\n') r.send('a\n') return int(r.recvuntil('\n')) diff=0xcafe1204<<2008 s=[] for i in range(12): print 'retrieve:',i s.append(geto()) s=list(map(lambda x:x**3-diff,s)) s.sort() os=s[0].bit_length() print(os) sold=s st=[] for i in range(len(s)): st.append((s[i],[1 if _==i else 0 for _ in range(len(s))])) s=st K=1000 cnt=0 def sub(a,b): t=[] for i in range(len(a)): t.append(a[i]-b[i]) return t def mul(a,b): t=[] for i in range(len(a)): t.append(a[i]*b) return t def subx(a,b): return (a[0]-b[0],sub(a[1],b[1])) for i in range(5000): t=[] if len(s)<K*.9: for j in range(len(s)): t.append(s[j]) for k in range(j+1,min(len(s),j+4)): t.append(subx(s[k],s[j])) else: for j in range(len(s)-1): t.append(subx(s[j+1],s[j])) for j in range(min(len(s),1000)): t.append(s[j]) t.sort() t2=[] for j in t: if j[0]<(1<<1900):continue if len(t2)==0 or j[0]>t2[-1][0]+(1<<1900) or (t2[-1][0].bit_length()==2048 and j[0].bit_length()==2048 and t2[-1]!=j): t2.append(j) t=t2 t=t[:K] tb=t[0][0].bit_length() if i%10==0: print i+1,os-tb,'%.5f'%((os-tb)/(i+1.)) s=t if t[0][0].bit_length()==2048: cnt+=1 if cnt>=15: break full=(1<<2048)-1 mask=full for i in range(len(s)-1): if s[i+1][0].bit_length()!=2048: continue t=full^s[i][0]^s[i+1][0] if (t>>2045)!=7: continue mask&=t mask^=full t=0 while (1<<t)<mask: t+=1 mask=full^(1<<t)-1 print(t) req=s[0][0]&mask sn=[] for i in s: if (i[0]&mask)==req: sn.append(i[1]) s=[] for i in range(len(sn)-1): s.append(sub(sn[i],sn[i+1])) while len(s[0])>2: sn=[] st=[] for j in s: if j[-1]: st.append(j) else: sn.append(j[:-1]) for j in range(len(st)-1): a=st[j] b=st[j+1] at=mul(a,b[-1]) bt=mul(b,a[-1]) t=sub(at,bt) assert t[-1]==0 sn.append(t[:-1]) s=sn for i in s: if i[0]: a,b=i g=gcd(a,b) a/=g;b/=g tn=sold[0]/abs(b) tn*=req/tn if req%tn<tn/2 else req/tn+1 n=tn print 'found n:',n def encrypt(s): return '%0512x'%pow(int(('\xCA\xFE\x12\x04'+'\0'*(251-len(s))+s).encode('hex'),16),3,n) keys={} keys['meow*']='%0512x'%4643124907324364176541919631092611537462168169113368694062754706716345623066850854804612072567302665612238408034253132873785414030172160601569222092854027911483401638265250179534654654959278137810816171464 r.recvuntil('meow?\n') r.send('meow!\n') r.recvuntil('meow meow~\n') e=encrypt('meow*') r.send(e+'\n') r.recvuntil('meow meow meow?\n') r.send(keys['meow*']+'\n') r.interactive() ``` # Reverse ### EmojiVM It requires some token to print flag. The token is encrypted. ```python s=[142, 99, 205, 18, 75, 88, 21, 23, 81, 34, 217, 4, 81, 44, 25, 21, 134, 44, 209, 76, 132, 46, 32, 6, 0] s2=[] for i in range(25): if i%4==0: s2.append(s[i]-30) elif i%4==1: s2.append((s[i]^7)+8) elif i%4==2: s2.append(((s[i]+4)^68)-44) else: s2.append(s[i]^4^101) print(''.join(map(chr,s2[:-1]))) ``` Use the script above to find the token. Then just paste the token to get flag. ### Suicune It requires a key in 0~0xffff to encrypt a given message of length N. The encryption is in 16 rounds, in each rounds, the key is uses to shuffle a permutation of 0~255, then the first N bytes of the permutation will be processed, then xor to the original message. The process is to regard it as a permutation, and next it K times, where K is related to key. ```python def fcount(s): res=0 for i in range(len(s)): c=0 for j in range(i+1,len(s)): c+=s[j]>s[i] res+=c*fac[len(s)-i-1] return res def fkth(n,k): s=[0 for i in range(n)] for i in range(n-1,-1,-1): s[i]=n-i-1-(k%fac[n-i]//fac[n-i-1]) for j in range(i+1,n): if s[j]>=s[i]: s[j]+=1 return s def fwalk(s,k): t=fcount(s) t=max(0,t-k) st=fkth(len(s),t) s.sort() res=[] for i in st: res.append(s[i]) return res fac=[1] for i in range(1,100): fac.append(fac[-1]*i) def ROR4(x,y): x%=(1<<32) assert y>=0 and y<32 return ((x>>y) | (x<<(32-y))) % (1<<32) def keystr(s): r='%016x'%s u='' for i in range(16,0,-2): u+=r[i-2:i] return u L=49 enc='04dd5a70faea88b76e4733d0fa346b086e2c0efd7d2815e3b6ca118ab945719970642b2929b18a71b28d87855796e344d8' for key in range(1<<16): raw=[0]*L okey=key key=(6364136223846793005*(key%0x10000)+6364136223846793006)%(1<<64) for T in range(16): Carr=[_ for _ in range(256)] for v41 in range(255,0,-1): v154=v41+1 v51=key if ((1<<32)-v154)%v154: v155=key while True: v155 = (1 + 6364136223846793005 * v155) % (1<<64) v156 = ROR4((v51 ^ (v51 >> 18)) >> 27, v51 >> 59) v51 = v155 if v156 < (1<<32) - (((1<<32)-v154) % v154): break else: v155 = (1 + 6364136223846793005 * v51) % (1<<64) v157 = (v51 ^ (v51 >> 18)) >> 27 v51 >>= 59 v156 = ROR4(v157, v51) key = v155 v158 = v156 % v154 Carr[v41],Carr[v158]=Carr[v158],Carr[v41] dest = 0 for i in range(0,64,32): dest += ROR4((key ^ (key >> 18)) >> 27, key >> 59) << i key = (1 + 6364136223846793005 * key) % (1<<64) Darr = Carr[:L] Darr=fwalk(Darr,dest) tmp=[] for i in range(L-1,-1,-1): tmp.append(raw[i]^Darr[i]) raw=tmp res='' ok=True for i in range(0,L*2,2): t=int(enc[i:i+2],16)^raw[i//2] res+=chr(t) ok=ok and t>=32 and t<=127 if ok: print(res) if okey%100==0: print(okey) ```