mcfx's blog - 2021年3月
/2021/03/
个人博客，（曾经）基本只放题解，现在随便写点啥了吧（
-
腾讯极客技术挑战赛 第三期 码上种树 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]