mcfx's blog - 2019年10月

mcfx's blog - 2019年10月个人博客，（曾经）基本只放题解，现在随便写点啥了吧（ 2019-10-15T00:48:00+08:00 Typecho /feed/atom/2019/10/ <![CDATA[HITCON CTF 2019 Quals Writeup]]> /archives/268/ 2019-10-15T00:48:00+08:00 2019-10-15T00:48:00+08:00 admin

# 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)
```

]]>