mcfx's blog - 2020年3月

mcfx's blog - 2020年3月个人博客，（曾经）基本只放题解，现在随便写点啥了吧（ 2020-03-01T04:58:48+08:00 Typecho /feed/atom/2020/03/ <![CDATA[Codegate CTF 2020 Preliminary Writeup]]> /archives/279/ 2020-03-01T04:58:48+08:00 2020-03-01T04:58:48+08:00 admin

# 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。

]]>