Misc

Verifier

一个用 ply.yacc 实现的语法分析器，要写一段代码 print 一个小于 0 的数。但是他会先进行预处理，并求出每个变量可能的最小值和最大值，当 print 的输入的最小可能值小于 0 时会退出。
在预处理 while 时，他只会尝试运行 3 次，那么一个在第 4 次或之后才被修改的值就不会被预处理考虑到。

  1. 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。

  1. from pwn import *
  2. import random
  4. def getconn():
  5.     #return process(['python3','prob.py'])
  6.     return remote('110.10.147.44',7777)
  8. def encrypt(s):
  9.     if type(s) is str:
  10.         s=s.encode()
  11.     print(s.hex())
  12.     r=getconn()
  13.     r.send('1\n')
  14.     r.send(s.hex()+'\n')
  15.     r.recvuntil('ciphertext = ')
  16.     cipher=bytes.fromhex(r.recv(len(s.hex())).decode())
  17.     r.recvuntil('tag = ')
  18.     tag=bytes.fromhex(r.recv(32).decode())
  19.     r.send('4\n')
  20.     r.close()
  21.     return cipher,tag
  23. def getflag(nonce,cipher,tag):
  24.     r=getconn()
  25.     r.send('3\n')
  26.     r.send(nonce.hex()+'\n')
  27.     r.send(cipher.hex()+'\n')
  28.     r.send(tag.hex()+'\n')
  29.     r.interactive()
  31. def xor(a,b):
  32.     return bytes(b1 ^ b2 for b1, b2 in zip(a,b))
  34. def getrnd(n):
  35.     return bytes([random.randint(0,255)for i in range(n)])
  37. #print(encrypt(b'\0'*128))
  39. a=b'\0'*8+b';cat fla'
  40. b=b'\0;'+b'\0'*14
  41. br=b'g;'+b'\0'*14
  43. mapa={}
  44. mapb={}
  45. res=None
  47. #mapa[b'\x99(']=b'\xa3\xab\xcd\xa6W\xbaT\xc8;cat fla'
  48. #mapb[b'\x99(']=b'\x93\xf0\x0f\xd9m\xb7\xa1gy\x07\nX\nY\xed\xe3'
  49. #res=b'\x99('
  52. while 1:
  53.     at=getrnd(8)+a[8:]
  55.     ci,ta=encrypt(at+b)
  56.     ac=ci[:16]
  57.     bc=ci[16:]
  59.     tb=xor(b,bc)
  60.     bc2=xor(br,tb)
  61.     nt=bc2[:8]+b[8:]
  62.     #print(nt[:2])
  63.     mapa[nt[:2]]=at
  65.     ut=getrnd(16)
  66.     ci,ta=encrypt(ut+b'\0'*32)
  67.     xc=ci[:16]
  68.     yc=ci[16:32]
  69.     zc=ci[32:]
  70.     #print(yc[:2])
  71.     mapb[yc[:2]]=ut
  73.     for i in mapa:
  74.         if i in mapb:
  75.             res=i
  76.     if res is not None:
  77.         break
  78. #print(res,mapa[res],mapb[res])
  81. at=mapa[res]
  83. ci,ta=encrypt(at+b)
  84. #print('A',(at+b).hex())
  85. ac=ci[:16]
  86. bc=ci[16:]
  88. tb=xor(b,bc)
  89. bc2=xor(br,tb)
  90. nt=bc2[:8]+b[8:]
  92. ut=mapb[res]
  93. ci,ta=encrypt(ut+b'\0'*32)
  94. xc=ci[:16]
  95. yc=ci[16:32]
  96. nt2=yc[:8]+b'\0'*8
  97. #print(nt2.hex())
  98. zc=ci[32:]
  99. #print(yc[:2])
  100. #print(ci,ta)
  102. #print(xor(yc,nt))
  103. #print(xor(nt2,nt))
  105. #print((xor(nt2,tb)[:8]+nt2[8:]).hex())
  107. #src= at+xor(nt2,tb)[:8]+nt2[8:]+b'\0'*16
  111. 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 算法可以求出若干个向量的较小的线性组合，可以构造下面这些向量：

  1. (每个 k_i*px 的有效值) + (若干 0)
  2. (每个 k_i) + 一个奇怪的常数 C + (若干 0)
  3. 接下来若干行，每行是
  4. (前若干个里，第 i 行的第 i 个位置是 mod) + 0 + (后若干个里，第 i 行的第 i 个位置是 1)

这样的话，一种可能较小的线性组合就是第一个向量加上若干个后面的向量再减若干个第二个向量。这时那个奇怪的常数就是求出的 px 了。至于这个常数应该取多少，以及这为啥能奏效，我就不知道了（试出来的结果是 1<<100 能求出解

  1. s=open('output').readlines()
  2. n,seed=map(int,s[4].strip().split(' '))
  3. t=[]
  4. for i in range(200):
  5.     t.append(int(s[7+i]))
  6. seeds=[]
  7. for i in range(200):
  8.     seeds.append(seed)
  9.     seed=seed**2%n
  11. for i in t:
  12.     assert (i<<460)<n
  14. u=list(range(2,200,4))
  16. M=[]
  17. c=len(u)
  18. V=100
  19. M.append([t[i]<<460 for i in u]+[0]*(c+1))
  20. M.append([seeds[i] for i in u]+[1<<V]+[0]*c)
  21. for i in range(c):
  22.     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)])
  23. M=Matrix(M)
  24. print(M[0][c])
  25. M2=M.LLL()
  26. print(M2[0][c])
  27. for i in range(5):
  28.     if not M2[i][c]: continue
  29.     assert M2[i][c]%(1<<V)==0
  30.     print(i,M2[i][0],M2[i][c]//(1<<V))

剩下的可以参考 这个 和
这个。

Polynomials

NTRUEncrypt，给了私钥里 -1 0 1 的个数。

不过实际上并没有用到，直接参考下面论文里的 LLL 做法就能解出。

https://sci-hub.tw/https://link.springer.com/chapter/10.1007%2F978-3-540-74143-5_9#

  1. import random
  2. n=60
  3. p=3
  4. q=1499
  6. 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]
  7. c=(20,20,20)
  9. ks={}
  10. while True:
  11.     rnds=[random.randint(1,10)for i in range(n*2)]
  12.     #rnds=[8]*n+[1]*n
  14.     M=Matrix(n*2,n*2)
  15.     for i in range(n):
  16.         M[i,i]=q*rnds[i]
  17.     for i in range(n):
  18.         for j in range(n):
  19.             M[i+n,j]=h[(j-i)%n]*rnds[j]
  20.     for i in range(n):
  21.         M[i+n,i+n]=1*rnds[i+n]
  22.     M2=M.LLL()
  23.     #print(M2[0])
  24.     #print(M2[1])
  25.     #ts=[]
  27.     rcnt=0
  29.     for i in range(n*2):
  30.         tl=list(M2[i])[:n]
  31.         tr=list(M2[i])[n:]
  32.         for j in range(n):
  33.             tl[j]=tl[j]//rnds[j]%q
  34.             tr[j]=tr[j]//rnds[j+n]%q
  35.         if tr[0]==q-2:
  36.             tr[0]-=1
  37.         elif tr[0]==2:
  38.             tr[0]+=1
  39.         cntl=0
  40.         for j in tl:
  41.             if j%q==3 or j%q==0 or j%q==q-3:
  42.                 cntl+=1
  43.         cntr=0
  44.         for j in tr:
  45.             if j%q==3 or j%q==0 or j%q==q-3:
  46.                 cntr+=1
  47.         if cntl==n and cntr==n and sum(tl):
  48.             print(tl,tr)
  49.             exit()
  50.         if cntl>=n-1 or cntr>=n-1:
  51.             if str(tr) not in ks:
  52.                 print(cntl,cntr,tr)
  53.                 ks[str(tr)]=1
  54.             rcnt+=1
  55.     print(rcnt,len(ks))

Reverse

SimpleMachine

一个虚拟机，把和 flag 有关的跳转钦定为不跳转，然后丢进 z3，就好了。（太懒了不想手解）

  1. def get2b(a,b):
  2.     return a[b]+(a[b+1]<<8)
  4. def set2b(a,b,c):
  5.     a[b]=c&255
  6.     a[b+1]=c>>8&255
  8. get_2b=get2b
  10. def read_bytes(a,b,c):
  11.     #print('read:',b,c)
  12.     global str_pos
  13.     for i in range(c):
  14.         #print(str_pos)
  15.         if str_pos==len(str_to_read):
  16.             a[b+i]=255
  17.         else:
  18.             a[b+i]=str_to_read[str_pos]
  19.             str_pos+=1
  21. def write_bytes(a,b,c):
  22.     global str_res
  23.     for i in range(c):
  24.         str_res+=chr(a[b+i])
  26. def step1():
  27.     #print('step1')
  28.     v1=stat[58]
  29.     if v1==2:
  30.         set2b(mem,get2b(stat,60),get2b(stat,62))
  31.     else:
  32.         assert v1==0
  33.         v2=get2b(stat,60)
  34.         if v2!=65535:
  35.             set2b(stat,2*v2+28,get2b(stat,62))
  37. def step2():
  38.     global cons
  39.     op=stat[48]
  40.     #print('step2',op)
  41.     if op==0:
  42.         set2b(stat,62,get2b(stat,52))
  43.     elif op==1:
  44.         set2b(stat,62,get2b(stat,52)+get2b(stat,54))
  45.     elif op==2:
  46.         set2b(stat,62,get2b(stat,52)*get2b(stat,54))
  47.     elif op==3:
  48.         set2b(stat,62,get2b(stat,52)^get2b(stat,54))
  49.     elif op==4:
  50.         #print('#',get2b(stat,52),get2b(stat,54))
  51.         #set2b(stat,62,get2b(stat,52)<get2b(stat,54))
  52.         #print(get2b(stat,52),get2b(stat,54))
  53.         rt=get2b(stat,52)<get2b(stat,54)
  54.         if type(rt) is bool:
  55.             set2b(stat,62,rt)
  56.         else:
  57.             set2b(stat,62,0)
  58.         #assert get2b(stat,52)==0
  59.         if get2b(stat,52)==0: cons.append(get2b(stat,54)==0)
  60.     elif op==5:
  61.         #cons.append(get2b(stat,52)==0)
  62.         if get2b(stat,52):
  63.             stat[46]=0
  64.             stat[56]=0
  65.             stat[64]=0
  66.             set2b(stat,34,get2b(stat,54))
  67.             return
  68.         pass
  69.     elif op==6:
  70.         read_bytes(mem,get2b(stat,52),get2b(stat,54))
  71.     elif op==7:
  72.         write_bytes(mem,get2b(stat,52),get2b(stat,54))
  73.     elif op==8:
  74.         stat[46]=0
  75.         stat[56]=0
  76.         stat[64]=0
  77.         for i in range(4):
  78.             stat[24+i]=0
  79.         return
  80.     stat[64]=1
  81.     stat[58]=stat[49]
  82.     set2b(stat,60,get2b(stat,50))
  84. def step3():
  85.     #print('step3')
  86.     v1=stat[64]
  87.     v2=stat[38]
  88.     v3=stat[39]
  89.     do_label15=True
  90.     if v1 and stat[58]==v2 and get2b(stat,60)==get2b(stat,42):
  91.         set2b(stat,52,get2b(stat,62))
  92.         #goto label 15
  93.     elif v2==2:
  94.         set2b(stat,52,get_2b(mem,get2b(stat,42)))
  95.         v2=stat[58]
  96.     else:
  97.         if v2==1:
  98.             set2b(stat,52,get2b(stat,42))
  99.             if v1==0:
  100.                 do_label15=False
  101.                 #goto label 8
  102.             v2=stat[58]
  103.             #goto label 15
  104.         else:
  105.             if v2: assert False
  106.             set2b(stat,52,get2b(stat,2*get2b(stat,42)+28))
  107.             v2=stat[58]
  108.     if do_label15 and v3==v2 and get2b(stat,60)==get2b(stat,44):
  109.         set2b(stat,54,get2b(stat,62))
  110.         #goto label 12
  111.     elif v3==2:
  112.         set2b(stat,54,get_2b(mem,get2b(stat,44)))
  113.     elif v3==1:
  114.         set2b(stat,54,get2b(stat,44))
  115.     elif v3:
  116.         assert False
  117.     stat[56]=1
  118.     stat[48]=stat[36]
  119.     stat[49]=stat[37]
  120.     set2b(stat,50,get2b(stat,40))
  122. def step4():
  123.     global res_pos,res_naive
  124.     #print('step4')
  125.     a=get2b(stat,34)
  126.     #if a==416:
  127.     #    res_naive=True
  128.     #if not res_naive:
  129.     #    res_pos=a
  130.     #print(a)
  131.     v1=get2b(mem,a)
  132.     #print(v1,hex(v1))
  133.     stat[36]=v1&0x7f
  134.     stat[37]=v1>>7&7
  135.     stat[38]=v1>>10&7
  136.     stat[39]=v1>>13&7
  137.     for i in range(6):
  138.         stat[40+i]=mem[a+2+i]
  139.     stat[46]=1
  140.     set2b(stat,34,a+8)
  141.     #print(stat[34:46])
  142.     pass
  144. from z3 import *
  146. mem=[]
  147. stat=[]
  149. mem=[0]*0x10000
  150. t=open('target','rb').read()
  151. for i in range(len(t)):
  152.     mem[i]=t[i]
  153. stat=[0]*72
  154. stat[24]=1
  156. #str_to_read=[0]*36
  157. str_to_read=[]
  158. cons=[]
  159. for i in range(36):
  160.     t=BitVec('s'+str(i), 16)
  161.     cons.append((t&255)==t)
  162.     str_to_read.append(t)
  163. str_pos=0
  164. str_res=''
  166. res_pos=0
  167. res_naive=False
  169. while stat[24]:
  170.     if stat[64]:
  171.         step1()
  172.     if stat[56]:
  173.         step2()
  174.     if stat[46]:
  175.         step3()
  176.     step4()
  177. print(str_res)
  178. #solve(cons)
  179. so=Solver()
  180. so.add(cons)
  181. print(so.check())
  182. m=so.model()
  183. res=''
  184. for i in range(36):
  185.     res+=chr(m.evaluate(str_to_read[i]).as_long())
  186. print(res)

malicious

一个病毒（？）程序，会获取一个网址的信息解密一段代码。虽然这个网址无法访问，但是他把这个信息求了 md5，反解得到 activate。代入运行，解密的代码会向硬盘直接写入一个 dos 扇区。

这个 dos 扇区又混淆了一次代码，但是我还没逆到那，比赛就结束了，后来看别的 wp 知道是我的世纪 < 0x30 所以看不到 flag。