mcfx's blog - 2020年3月
/2020/03/
个人博客，（曾经）基本只放题解，现在随便写点啥了吧（
-
Codegate CTF 2020 Preliminary Writeup
/archives/279/
2020-03-01T04:58:48+08:00
# 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