Codegate CTF 2020 Preliminary Writeup March 1, 2020 # Misc ## Verifier 一个用 ply.yacc 实现的语法分析器，要写一段代码 print 一个小于 0 的数。但是他会先进行预处理，并求出每个变量可能的最小值和最大值，当 print 的输入的最小可能值小于 0 时会退出。 在预处理 while 时，他只会尝试运行 3 次，那么一个在第 4 次或之后才被修改的值就不会被预处理考虑到。 ``` T=10;A=1;B=1;[T>1{T=T+-1;A==5?{B=-1}:{A=A};A==-1?{A=5}:{A=A};A==0?{A=-1}:{A=A};A==4?{A=0}:{A=A};A==3?{A=4}:{A=A};A==2?{A=3}:{A=A};A==1?{A=2}:{A=A};!T}];!B ``` # Crypto ## halffeed 程序每轮会把一个 tag 和明文异或得到密文，然后 `tag=cipher[:8]+plain[8:]` ，然后用 key 对 tag 加密，同时 key 本身也会被加密（相当于一个固定的 key 生成器）。 需要得到一个包含 `;cat flag;` 的字符串，但是不能直接对包含 `cat flag` 的字符串加密。 Tag 可以直接由明密文异或得到，考虑 `randchar`\*8 + `;cat fla` 和 `randchar`\*16+`g;`+.....，他们处理后的tag有概率前两位相同（生日攻击），这样就可以拼出一个完整的 cat flag。 ```python from pwn import * import random def getconn(): #return process(['python3','prob.py']) return remote('110.10.147.44',7777) def encrypt(s): if type(s) is str: s=s.encode() print(s.hex()) r=getconn() r.send('1\n') r.send(s.hex()+'\n') r.recvuntil('ciphertext = ') cipher=bytes.fromhex(r.recv(len(s.hex())).decode()) r.recvuntil('tag = ') tag=bytes.fromhex(r.recv(32).decode()) r.send('4\n') r.close() return cipher,tag def getflag(nonce,cipher,tag): r=getconn() r.send('3\n') r.send(nonce.hex()+'\n') r.send(cipher.hex()+'\n') r.send(tag.hex()+'\n') r.interactive() def xor(a,b): return bytes(b1 ^ b2 for b1, b2 in zip(a,b)) def getrnd(n): return bytes([random.randint(0,255)for i in range(n)]) #print(encrypt(b'\0'*128)) a=b'\0'*8+b';cat fla' b=b'\0;'+b'\0'*14 br=b'g;'+b'\0'*14 mapa={} mapb={} res=None #mapa[b'\x99(']=b'\xa3\xab\xcd\xa6W\xbaT\xc8;cat fla' #mapb[b'\x99(']=b'\x93\xf0\x0f\xd9m\xb7\xa1gy\x07\nX\nY\xed\xe3' #res=b'\x99(' while 1: at=getrnd(8)+a[8:] ci,ta=encrypt(at+b) ac=ci[:16] bc=ci[16:] tb=xor(b,bc) bc2=xor(br,tb) nt=bc2[:8]+b[8:] #print(nt[:2]) mapa[nt[:2]]=at ut=getrnd(16) ci,ta=encrypt(ut+b'\0'*32) xc=ci[:16] yc=ci[16:32] zc=ci[32:] #print(yc[:2]) mapb[yc[:2]]=ut for i in mapa: if i in mapb: res=i if res is not None: break #print(res,mapa[res],mapb[res]) at=mapa[res] ci,ta=encrypt(at+b) #print('A',(at+b).hex()) ac=ci[:16] bc=ci[16:] tb=xor(b,bc) bc2=xor(br,tb) nt=bc2[:8]+b[8:] ut=mapb[res] ci,ta=encrypt(ut+b'\0'*32) xc=ci[:16] yc=ci[16:32] nt2=yc[:8]+b'\0'*8 #print(nt2.hex()) zc=ci[32:] #print(yc[:2]) #print(ci,ta) #print(xor(yc,nt)) #print(xor(nt2,nt)) #print((xor(nt2,tb)[:8]+nt2[8:]).hex()) #src= at+xor(nt2,tb)[:8]+nt2[8:]+b'\0'*16 getflag(b'\0'*16,ac+xor(xor(nt2,tb)[:8]+nt2[8:],tb)+zc,ta) ``` ## MUNCH 需要分解 1024 位的 n。其中 p 给出了 从 0,146,292,438 bit 开始的 111bit。 给出的方法是，另外钦定一个质数 mod，然后给出若干对 k_i\*px%mod 的高几十位。这些 k_i 基本都是随机的。 考虑 LLL 算法可以求出若干个向量的较小的线性组合，可以构造下面这些向量： ``` (每个 k_i*px 的有效值) + (若干 0) (每个 k_i) + 一个奇怪的常数 C + (若干 0) 接下来若干行，每行是 (前若干个里，第 i 行的第 i 个位置是 mod) + 0 + (后若干个里，第 i 行的第 i 个位置是 1) ``` 这样的话，一种可能较小的线性组合就是第一个向量加上若干个后面的向量再减若干个第二个向量。这时那个奇怪的常数就是求出的 px 了。至于这个常数应该取多少，以及这为啥能奏效，我就不知道了（试出来的结果是 1<<100 能求出解 ```python s=open('output').readlines() n,seed=map(int,s[4].strip().split(' ')) t=[] for i in range(200): t.append(int(s[7+i])) seeds=[] for i in range(200): seeds.append(seed) seed=seed**2%n for i in t: assert (i<<460)<n u=list(range(2,200,4)) M=[] c=len(u) V=100 M.append([t[i]<<460 for i in u]+[0]*(c+1)) M.append([seeds[i] for i in u]+[1<<V]+[0]*c) for i in range(c): M.append([n if i==j else 0 for j in range(c)]+[0]+[1 if i==j else 0 for j in range(c)]) M=Matrix(M) print(M[0][c]) M2=M.LLL() print(M2[0][c]) for i in range(5): if not M2[i][c]: continue assert M2[i][c]%(1<<V)==0 print(i,M2[i][0],M2[i][c]//(1<<V)) ``` 剩下的可以参考 [这个](https://link.springer.com/chapter/10.1007/978-3-540-89255-7_25) 和 [这个](https://gist.github.com/jhs7jhs/0c26e83bb37866f5c7c6b8918a854333)。 ## Polynomials NTRUEncrypt，给了私钥里 -1 0 1 的个数。 不过实际上并没有用到，直接参考下面论文里的 LLL 做法就能解出。 https://sci-hub.tw/https://link.springer.com/chapter/10.1007%2F978-3-540-74143-5_9# ```python import random n=60 p=3 q=1499 h=[314, 1325, 1386, 176, 369, 1029, 877, 1255, 111, 1226, 117, 0, 210, 761, 938, 273, 525, 751, 1085, 372, 1333, 898, 780, 44, 649, 1463, 326, 354, 116, 1080, 1065, 1109, 358, 275, 1209, 964, 101, 950, 415, 1492, 1197, 921, 1000, 1028, 1400, 43, 1003, 914, 447, 360, 1171, 1109, 223, 1134, 1157, 1383, 784, 189, 870, 565] c=(20,20,20) ks={} while True: rnds=[random.randint(1,10)for i in range(n*2)] #rnds=[8]*n+[1]*n M=Matrix(n*2,n*2) for i in range(n): M[i,i]=q*rnds[i] for i in range(n): for j in range(n): M[i+n,j]=h[(j-i)%n]*rnds[j] for i in range(n): M[i+n,i+n]=1*rnds[i+n] M2=M.LLL() #print(M2[0]) #print(M2[1]) #ts=[] rcnt=0 for i in range(n*2): tl=list(M2[i])[:n] tr=list(M2[i])[n:] for j in range(n): tl[j]=tl[j]//rnds[j]%q tr[j]=tr[j]//rnds[j+n]%q if tr[0]==q-2: tr[0]-=1 elif tr[0]==2: tr[0]+=1 cntl=0 for j in tl: if j%q==3 or j%q==0 or j%q==q-3: cntl+=1 cntr=0 for j in tr: if j%q==3 or j%q==0 or j%q==q-3: cntr+=1 if cntl==n and cntr==n and sum(tl): print(tl,tr) exit() if cntl>=n-1 or cntr>=n-1: if str(tr) not in ks: print(cntl,cntr,tr) ks[str(tr)]=1 rcnt+=1 print(rcnt,len(ks)) ``` # Reverse ## SimpleMachine 一个虚拟机，把和 flag 有关的跳转钦定为不跳转，然后丢进 z3，就好了。（太懒了不想手解） ```python def get2b(a,b): return a[b]+(a[b+1]<<8) def set2b(a,b,c): a[b]=c&255 a[b+1]=c>>8&255 get_2b=get2b def read_bytes(a,b,c): #print('read:',b,c) global str_pos for i in range(c): #print(str_pos) if str_pos==len(str_to_read): a[b+i]=255 else: a[b+i]=str_to_read[str_pos] str_pos+=1 def write_bytes(a,b,c): global str_res for i in range(c): str_res+=chr(a[b+i]) def step1(): #print('step1') v1=stat[58] if v1==2: set2b(mem,get2b(stat,60),get2b(stat,62)) else: assert v1==0 v2=get2b(stat,60) if v2!=65535: set2b(stat,2*v2+28,get2b(stat,62)) def step2(): global cons op=stat[48] #print('step2',op) if op==0: set2b(stat,62,get2b(stat,52)) elif op==1: set2b(stat,62,get2b(stat,52)+get2b(stat,54)) elif op==2: set2b(stat,62,get2b(stat,52)*get2b(stat,54)) elif op==3: set2b(stat,62,get2b(stat,52)^get2b(stat,54)) elif op==4: #print('#',get2b(stat,52),get2b(stat,54)) #set2b(stat,62,get2b(stat,52)<get2b(stat,54)) #print(get2b(stat,52),get2b(stat,54)) rt=get2b(stat,52)<get2b(stat,54) if type(rt) is bool: set2b(stat,62,rt) else: set2b(stat,62,0) #assert get2b(stat,52)==0 if get2b(stat,52)==0: cons.append(get2b(stat,54)==0) elif op==5: #cons.append(get2b(stat,52)==0) if get2b(stat,52): stat[46]=0 stat[56]=0 stat[64]=0 set2b(stat,34,get2b(stat,54)) return pass elif op==6: read_bytes(mem,get2b(stat,52),get2b(stat,54)) elif op==7: write_bytes(mem,get2b(stat,52),get2b(stat,54)) elif op==8: stat[46]=0 stat[56]=0 stat[64]=0 for i in range(4): stat[24+i]=0 return stat[64]=1 stat[58]=stat[49] set2b(stat,60,get2b(stat,50)) def step3(): #print('step3') v1=stat[64] v2=stat[38] v3=stat[39] do_label15=True if v1 and stat[58]==v2 and get2b(stat,60)==get2b(stat,42): set2b(stat,52,get2b(stat,62)) #goto label 15 elif v2==2: set2b(stat,52,get_2b(mem,get2b(stat,42))) v2=stat[58] else: if v2==1: set2b(stat,52,get2b(stat,42)) if v1==0: do_label15=False #goto label 8 v2=stat[58] #goto label 15 else: if v2: assert False set2b(stat,52,get2b(stat,2*get2b(stat,42)+28)) v2=stat[58] if do_label15 and v3==v2 and get2b(stat,60)==get2b(stat,44): set2b(stat,54,get2b(stat,62)) #goto label 12 elif v3==2: set2b(stat,54,get_2b(mem,get2b(stat,44))) elif v3==1: set2b(stat,54,get2b(stat,44)) elif v3: assert False stat[56]=1 stat[48]=stat[36] stat[49]=stat[37] set2b(stat,50,get2b(stat,40)) def step4(): global res_pos,res_naive #print('step4') a=get2b(stat,34) #if a==416: # res_naive=True #if not res_naive: # res_pos=a #print(a) v1=get2b(mem,a) #print(v1,hex(v1)) stat[36]=v1&0x7f stat[37]=v1>>7&7 stat[38]=v1>>10&7 stat[39]=v1>>13&7 for i in range(6): stat[40+i]=mem[a+2+i] stat[46]=1 set2b(stat,34,a+8) #print(stat[34:46]) pass from z3 import * mem=[] stat=[] mem=[0]*0x10000 t=open('target','rb').read() for i in range(len(t)): mem[i]=t[i] stat=[0]*72 stat[24]=1 #str_to_read=[0]*36 str_to_read=[] cons=[] for i in range(36): t=BitVec('s'+str(i), 16) cons.append((t&255)==t) str_to_read.append(t) str_pos=0 str_res='' res_pos=0 res_naive=False while stat[24]: if stat[64]: step1() if stat[56]: step2() if stat[46]: step3() step4() print(str_res) #solve(cons) so=Solver() so.add(cons) print(so.check()) m=so.model() res='' for i in range(36): res+=chr(m.evaluate(str_to_read[i]).as_long()) print(res) ``` ## malicious 一个病毒（？）程序，会获取一个网址的信息解密一段代码。虽然这个网址无法访问，但是他把这个信息求了 md5，反解得到 activate。代入运行，解密的代码会向硬盘直接写入一个 dos 扇区。 这个 dos 扇区又混淆了一次代码，但是我还没逆到那，比赛就结束了，后来看别的 wp 知道是我的世纪 < 0x30 所以看不到 flag。
前排
你是神吗啊啊啊 BV号哪个太nb了