学习
实践
活动
工具
TVP
写文章
专栏首页极客挑战赛腾讯极客挑战赛丨来自冠军选手的解题思路
原创

腾讯极客挑战赛丨来自冠军选手的解题思路

各位爱挑战爱学习的coder们,第三期极客挑战赛的解题思路来啦!(原赛题传送门:腾讯极客挑战赛邀你“码上种树”

在“码上种树”赛题公布后,冠军同学仅用时25小时26分钟即完成通关,夺得本期赛事第一名。下面由他带来解题思路分享,也欢迎小伙伴们在文末留言,期待看到大家各种精妙的解题技术思路,共同交流探讨,一起享受技术带来的无穷乐趣~


批量种树 & 前两题

首先 F12 一下,看看请求,可以发现先 pull 了一个 js,然后把 js 运行的结果返回上去,就成功种下一棵树。那么可以写个脚本快速种树:

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()

第三题(100000)

题目中有用的部分如下:

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;
};

只需要优化内层循环就可以有足够的速度了。(下面的代码需要加在前面的脚本的后面)

  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。虽然之前看到过类似的混淆,但是没搜到直接能用的反混淆工具。

观察发现这里面大量代码只是为了生成常量,比如

(!![] + [][(![] + [])[+[]] + ([![]] + [][[]])[+!+[] + [+[]]] + (![] + [])[!+[] + !+[]] + (!![] + [])[+[]] + (!![] + [])[!+[] + !+[] + !+[]] + (!![] + [])[+!+[]]])[+!+[] + [+[]]]

只是为了生成 o。手动发现并替换掉这些常量后,代码就可读了不少:

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,_,+[],+[],+[])

格式化并替换掉变量名:

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的部分可以用排序代替。

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 代码:

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'

  } // <No else block>
local2}

可以看出,程序把 local2 的每一位用两个外部函数(ffimport)运算,然后乘积加回到 local2 上,重复 local0 这么多次。

而直接查看 wasm 就可以得知这两个外部函数分别是 min 和 max:

这样就可以用 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 个数

而答案是:

于是用快速幂(比如 python 的 pow)来完成这个操作即可。

小插曲(1010000)

脚本跑到 1010000 时,发现下发的 js 变了。下载下来查看,发现还是虚拟机,但是指令编码变了,内置的常数也变了。那么我们应该需要一个办法来快速找到这些常数。

这个虚拟机构造字符串的方法是:

其中 op 是指令编号,char_i 是字符串的第 i 个字符。由于这些 BigInt 也是如此构造的,可以发现这些 char_i 全是数字,而利用这个特点可以高效地找到所需的常数。具体可以看下面的代码。

def find_q6_nums(s):
    def isnum(x):
        return x >= 48 and x <= 57
    i = 1
    res = {}
    while i < len(s):
        if not isnum(s[i]):
            i += 1
            continue
        j = i
        a = set()
        b = []
        while j < len(s) and isnum(s[j]):
            if len(a | set([s[j - 1]])) > 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] <= 10**7:
                        r2.append(t[i - 1])
            return r2, mod
    return None

第七题(2000000)

拿到题目,发现又是个栈式虚拟机。但是这次的指令多了不少。反汇编器的代码也放在 https://github.com/mcfx0/qq_geek_tree 。

这次的字符串拼接等指令要更恶心一点,所以反汇编器里面还需要对栈上的状态做少量模拟,这样更方便人查看。

21980  push ""                          ; {25} '' [[], 0] []
21981  push 8                           ; {26} 8 '' [[], 0]
21983  concat s2, chr(s1 + 59)          ; {26} 8 'C' [[], 0]
21985  mov s1, 62                       ; {26} 62 'C' [[], 0]
21987  push 26                          ; {27} 26 62 'C'
21989  pop 1: sub s2, s1                ; {26} 36 'C' [[], 0]
21990  concat s2, chr(s1 + 67)          ; {26} 36 'Cg' [[], 0]
21992  mov s1, 53                       ; {26} 53 'Cg' [[], 0]
21994  push 2                           ; {27} 2 53 'Cg'
21996  pop 1: sub s2, s1                ; {26} 51 'Cg' [[], 0]
21997  concat s2, chr(s1 + 60)          ; {26} 51 'Cgo' [[], 0]
21999  mov s1, 38                       ; {26} 38 'Cgo' [[], 0]
22001  push 30                          ; {27} 30 38 'Cgo'
22003  pop 1: add s2, s1                ; {26} 68 'Cgo' [[], 0]
22004  concat s2, chr(s1 + 40)          ; {26} 68 'Cgol' [[], 0]
22006  mov s1, 37                       ; {26} 37 'Cgol' [[], 0]
22008  push 17                          ; {27} 17 37 'Cgol'
22010  pop 1: add s2, s1                ; {26} 54 'Cgol' [[], 0]
22011  concat s2, chr(s1 + 11)          ; {26} 54 'CgolA' [[], 0]
22013  mov s1, 57                       ; {26} 57 'CgolA' [[], 0]
22015  push 31                          ; {27} 31 57 'CgolA'
22017  pop 1: sub s2, s1                ; {26} 26 'CgolA' [[], 0]
22018  concat s2, chr(s1 + 80)          ; {26} 26 'CgolAj' [[], 0]
22020  mov s1, 19                       ; {26} 19 'CgolAj' [[], 0]
22022  push 47                          ; {27} 47 19 'CgolAj'
22024  pop 1: add s2, s1                ; {26} 66 'CgolAj' [[], 0]
22025  concat s2, chr(s1 + 45)          ; {26} 66 'CgolAjo' [[], 0]
22027  mov s1, 46                       ; {26} 46 'CgolAjo' [[], 0]
22029  push 17                          ; {27} 17 46 'CgolAjo'

反汇编出来之后,看到他一开始又在拼接 base64 字符串,盲猜又是个虚拟机套娃。

对反汇编器做了若干改进(上面 github 放的已经是最终版本了),可以把 base64 字符串和那个巨大的数组给提出来。由于这里和之前 js 比较相似,盲猜是同一个虚拟机,只是指令编码有所区别,那么我们需要快速找到每个指令的编码是多少。

受到上一题的影响,我怕到 2010000 或者 2020000 时又来一套换编码的虚拟机,我决定用程序来自动分析每个指令是在哪个函数中实现的。由于这个虚拟机基本只是把 js 翻译了一遍,每个函数还是有很强的特征,比如每个算术指令的函数中,一定出现了两个 length,一个 pop,和一个对应操作的指令。不过程序中还有很多花指令,这些也需要想办法剔除掉。这部分代码也可以在 github 中查看。

把这个套娃的虚拟机解出来之后,好家伙,他也是个套娃。不过由于之前写了通用的处理方法,只需要再调用一遍就能再次解开。

最内层的虚拟机有一个挺长的主函数,应该就是题目需要的函数了。一开始,为了图方便,我把这个函数的字节码转成可以在最外层虚拟机运行的,但是丢进去发现跑不起来。又试了把第二层虚拟机转成最外层等各种方法,最终也还是没能跑起来。

仔细研究发现,这个函数有 7 个参数,其中第一个是题目,而后面 6 个是外面两层传进去的一些参数(其实是 6 个函数),这就导致需要找到这些参数才能解出题目。通过把内层虚拟机拿到外层跑,以及在合适的位置输出整个栈,可以拿到这些函数。不过试图搞三个虚拟机来分别跑这三份代码的尝试失败了。总之只能先读代码了。手动反编译得到如下结果:

arg3, func4 ~ func9

a_tmp_15=a_arr.slice(0)
cnt_16=func5()
var_17=0
if(a.length<16)goto label_360
label_394:
if(cnt_16!=0)goto label_415
if(cnt_16<0)goto label_719
push String.fromCharCode(102) // 'f'
'f'+'l'
'fl' + func7(a_tmp_15, var_17)
'fl'+func7(a_tmp_15, var_17)+'{'
'fl'+func7(a_tmp_15, var_17)+'{'+func8(input['t'], cnt_16)
'fl'+func7(a_tmp_15, var_17)+'{'+func8(input['t'], cnt_16)+func9(a_tmp_15, var_17)
return

label_719: infinite loop

label_415:
if(func4(cnt_16)!=cnt_16)goto label_451
i_18=0
label_496:
if(i_18<a.length)goto label_589
cnt_16=func5()
goto label_394

label_589:
var_17=func6(cnt_16^a_tmp_15[i_18],var_17)
i_18++
goto label_496

label_451: infinite loop

label_360: infinite loop

由于可以拿到这些函数的 js 对象,经过实验可以发现,其中 func4(x) 大概是输出 x-1,func5 每次调用会 -1,func6 是模 2^32 意义下的加法,func7 对于题目的 a 只会输出 ag,func8(x,y) 是 x.repeat(y+1),func9 对于题目的 a 只会输出 }

于是最后的答案便是 flag{题目的 t}。

另外多说一句,label_415 处的 if(func4(cnt_16)!=cnt_16)goto label_451 似乎一定会返回 true,然后就跳到 label_451 去死循环了,这也许就是硬跑跑不出来的原因?。。

第八题(2000001)

代码很简单:

window.C37CD28B=function({a}){let max=1n;let sum=0n;for(let i=0;i<a[0];i++)max*=10n;loop:for(let i=2n;i<max;i++){for(let j=2n;j<i;j++){if(i%j==0n)continue loop;}sum^=i;}return sum+"";}

是求所有小于等于10的13次方的质数的异或和。

使用 fast prime sieve 之类的关键词可以搜索到 primesieve 这个项目,而他的示例中给出了一个多线程求和的代码(https://github.com/kimwalisch/primesieve#libprimesieve-multi-threading)。改成异或就可以了。


原创声明,本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

登录 后参与评论
0 条评论

相关文章

  • 谁是鹅罗斯方块最终冠军?腾讯极客挑战赛榜单揭晓

    腾讯云+社区联合腾讯码客、腾讯安全平台部全新打造的创新赛事——腾讯极客挑战赛 | 鹅罗斯方块,已于8月8日圆满落幕。本次比赛共有上千家高校和企业单位的4570人...

    腾小云
  • 【内有福利】真实云上攻防10.24开战,探索产业安全新边界

    你可能听说过给手机、电脑、智能设备、甚至智能网联汽车找漏洞,给云服务“挖”漏洞的比赛,见过吗? 云计算在现实世界正在扮演者越来越重要的角色,用户衣食住行的背后...

    云鼎实验室
  • “垫底”逆袭!从一次错误中转换思路迎来破局

    在第二期极客挑战赛的ARM64赛道中,“HOOCCOOH”同学以480字节的成绩摘得赛道冠军。值得一提的是,这位同学为了参加arm64赛道,几乎是现学现用aar...

    腾讯极客挑战赛
  • 15日晚七点半,GeekPwn云安全挑战赛赛前大揭秘!

    第二届GeekPwn云安全挑战赛要来了! 10月15日,作为此次大赛的前一站,一场精彩的赛前对话将通过线上直播形式和大家见面。相比去年,今年的比赛无论从赛制、...

    云鼎实验室
  • 【参赛经验分享】【极客-腾讯内部赛道】一个菜鸡的解题思路

    tetris是参加【极客技术挑战赛第四期】鹅罗斯方块 的项目,这个项目是给定一个俄罗斯方块的固定序列,看看谁能消除的分数最高。

    esrrhs
  • 打造人类高质量极客,腾讯云开发者社区开启竞赛「寻知计划」

    腾讯云+社区联合腾讯码客、腾讯安全平台部全新打造的创新赛事——腾讯极客挑战赛 | 鹅罗斯方块(以下简称“极客挑战赛”),已于8月8日圆满落幕。本次比赛共有上千家...

    腾讯云开发者社区
  • “极客全明星赛”TCTF2019上海开战:争夺DEF CON CTF最后一席

    “极客全明星赛”——第三届腾讯信息安全争霸赛(Tencent Capture The Flag,简称TCTF)线下决赛于北京时间6月8日上午10:00,在上海西...

    腾讯云开发者社区
  • 云上神仙打架,速来!| 内含福利

    大风起兮云飞扬 在产业互联网的大风中 最飞扬的~ 莫过于云计算了 云作为一个庞大的资源池 云上用户可以实现 anytime、anywhere、anything ...

    云鼎实验室
  • 代码真的——无所不能!不服来战

    是由腾讯安全平台部发起,联合腾讯码客共同举办的一项属于技术人的赛事,旨在为技术爱好者提供一个相互切磋、展示自我的舞台。这将是一项长期的持续性赛事,每期比赛形式有...

    腾讯极客挑战赛
  • 赛前重点|考官揭秘GeekPwn云靶场挑战赛关键点

    7月11日-12日,第二届GeekPwn云靶场挑战赛线上热身赛正式开赛。今年的比赛相较往年来说,无论是赛制、赛程还是奖励等方面,都会有明显的不同。对于选手们而...

    云鼎实验室
  • Hard模式赛道如何破关?这种“朴素”方法也管用

    在第二期极客挑战赛的MIPS64赛道中,“我就看看不参加”同学以581字节的成绩最终获得赛道冠军。除了是赛道第一名,他还是所有赛道中累计提交次数最多的同学(共8...

    腾讯极客挑战赛
  • 腾讯安全 X GeekPwn,一场产业安全攻防大秀 | 1024

    今天,国际安全极客大赛GeekPwn2019在上海正式拉开帷幕。作为GeekPwn的“老朋友”,腾讯安全连续六年来到现场,与GeekPwn一起见证极客的奇思妙想...

    腾讯安全
  • GeekPwn云安全挑战赛赛前大揭秘!

    作为此次大赛的前一站,一场精彩的赛前对话将通过线上直播形式和大家见面。相比去年,今年的比赛无论从赛制、赛程还是奖励等方面,都会有所不同。今年比赛有哪些看点,赛制...

    腾讯安全
  • PWN个痛快!我们就是要让新基建更安全

    今天,又是1024程序员节,又是一年一度GeekPwn 国际安全极客大赛举办的大日子。

    腾讯安全
  • 我通过“种树”,拿下鹅厂实习offer

    最近,随着春季校园招聘和实习生招聘的启动,一大批朝气蓬勃的新鹅即将加入鹅厂。在大浪淘沙的招聘中,同学们八仙过海各显神通。其中,有的同学则另辟蹊径,凭借“种树”...

    腾讯技术工程官方号
  • TCTF 2019收官 倾力打造“双一流”安全人才培养平台

    经过30小时不间断的激烈角逐,6月9日,有着“极客全明星赛”之称的第三届腾讯信息安全争霸赛(Tencent Capture The Flag,简称TCTF)在上...

    腾讯云开发者社区
  • 极棒2018:腾讯安全云鼎实验室夺奖 展现AI技术硬实力

    10月24日-25日,以“人攻智能,洞见未来”为主题的GeekPwn2018国际安全极客大赛在上海圆满落下帷幕。在数字追踪挑战赛中,来自中科院、清华大学、重庆邮...

    腾讯云安全
  • 【最强大脑】全球脑王的极客挑战赛之路:1413876分夺冠如何炼成?

    导语 | 在腾讯云+社区联合腾讯码客、腾讯安全平台部全新打造的创新赛事【腾讯极客挑战赛 | 鹅罗斯方块】中,4570名参赛者为我们带来前所未有、异彩纷呈的作品。...

    腾小云
  • 第二届云安全挑战赛落幕,九大云安全趋势重磅发布

    10月24日,由腾讯安全云鼎实验室联合GeekPwn发起的第二届云安全比赛在上海落下帷幕,包括Nu1L、r3kapig、NeSE、0ops、天枢 Dubhe等7...

    腾讯安全

扫码关注腾讯云开发者

领取腾讯云代金券