-
-
[原创]ImaginaryCTF2024 re vokram wp 马尔可夫算法实现的虚拟机
-
发表于: 2024-7-31 16:20 1585
-
上上周的一道字符串替换实现的虚拟机的题目
脑昏看错题了,以为字节码只会被遍历一次,一直尝试暴力反向替换搜索答案发现解不出来,浪费了很多时间。
然后重新看vm代码才发现字节码是重复使用的,只能老实去分析字节码的含义。
初步分析
字节码是替换关系
每次选最先匹配上的规则进行替换
最后要求输入能被替换成Correct
Wrong的规则一定不能触发
比如bba,a替换b,得到bbb
bbb,反向b替换a有三种可能:abb,bab,bba
还有一种可能是原本就是bbb,没有替换成功
反向替换会产生太多分支,导致复杂度爆炸
寻找替换规则的规律
规则分析
(行从1开始计数)
1~77行是 ♂
+ascii 转 ????????
+♂
,没有纯????????
构成pat的规则
78行是去掉♂
79~2103是前转中, ????????
转 ????????
(????
=[????????]
,``=[^????????]
)
2104是去掉``
2105~3441是单转多,转`????`(
=[^????????]
)
3442是判定Correct,``+????
*225 转 Correct
3443~3445是``吞掉后续的一个????????
3446是判定Wrong
3447行是大保底,当其他规则都不满足,执行这一条,在最前面添加♂
特殊表情
作为pat只有:2104=:
作为repl只在79~2103是前转中 出现9次
作为pat只在2105~3441单转多中出现一次:2694=:????
作为repl只有:3447=:♂
作为pat只在2105~3441单转多中出现一次:2969=:????
作为repl只在2105~3441单转多中出现一次:2694=:????
作为pat在79~2103是前转中出现多次
有关的:2235=:????
,3442~3446
虚拟机逻辑分析
开头分析
猜测输入格式是ictf{aaaa}
没有表情,执行保底第3447行,变成♂ictf{aaaa}
多次执行第1~77行,♂
+ascii 转 ????????
+♂
,变成[????????]+♂
执行第78行,去掉♂
,变成[????????]+
没有纯????????
的pat,含``的唯一pat是2694,变成????[????????]+`
失败情况分析
出现``,且不满足3442~3446,就会失败
构造Correct过程
由开头分析可知
现在从????[????????]+
开始,要变成``+[????????]
*225
显然要消掉[^????????]
,并生成一个``
消掉[^????????]
的方法只有 作为repl的9条79~2103前转中规则 变[????????][????????]
,然后2104消掉
由此可以反推出,correct中的????两两作为一组,一定是由????????得到的,然后???????? 由????????得到的(????=[????????]
,=[^????????]
)
(n是flag的长度,猜测是225/5=45)
1 2 3 4 5 | :???? [????????] + = > ????[????????]{n * 5 } :???? ????[????????] + = > ????????[????????]{n * 5 } :???? ????????[????????] + = > ????????????[????????]{n * 5 } ... :???? (????) + [????????] + = > (????){ 1337 }[????????]{n * 5 } |
跟踪发现,``一定且只能通过多次 2105~3441单转多,变成(????)+
故输入一定会从????[????????]+
变成(????)+[????????]+
含菠萝的前转中比较特别????:け
,是三转二,不是前转中,是吞一个(到这里猜测菠萝是模三加减法),重新分析:
388 ???? け????
670 ???????? け
1022 け????
1313 ???? け
1448 ???? け????
1664 ???????? け????
1889 ???????? け????
1917 ???????? け????
2086 ???? け
(1)首先从最后一个菠萝开始,是三转二
(2~225)接着通过79~2103前转中变成其他表情,直到变成,经过遍历发现这一步一共重复224次
(226)然后2104消掉
回到(1)消去下一个菠萝
1 2 3 4 5 6 | 1 (????){ 1337 }[????????]{n * 5 } = > (????){ 1336 }け[????????][????????]{n * 5 - 1 } 2 (????){ 1336 }け[????????][????????]{n * 5 - 1 } = > (????){ 1336 }[????????]{ 1 }[????????][????????]{n * 5 - 2 } 3 (????){ 1336 }[????????][????????][????????]{n * 5 - 2 } = > (????){ 1336 }[????????]{ 2 }????[????????][????????]{n * 5 - 3 } ... 225 (????){ 1336 }[????????]{ 2223 }[????????][????????]{n * 5 - 224 } = > (????){ 1336 }[????????]{ 224 }[????????][????????]{n * 5 - 225 } 226 (????){ 1336 }[????????]{ 224 }[????????][????????]{n * 5 - 225 } = > (????){ 1336 }[????????]{ 225 }[????????]{n * 5 - 225 } |
解密
第一步及之前的操作是可以忽略的,显然由到的过程是与输入无关的,只有后面的225个[????????]是由输入替换得到的
故根据前面分析的可知反向过程是在最后两个表情中间插入(226逆操作),然后中转前224次(225~2逆操作),重复该过程1337次(有1337个菠萝)
这样就能得到后225个[????????],然后反向替换回ascii字符
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | source_file = 'check_flag.vokram' with open (source_file, encoding = 'utf-8' ) as f: program = parse(f.read()) correct = 3441 wrong = 3445 polo_num = 1337 trans_num = 224 repl2pat = {} for pat, repl, _ in program: repl2pat[repl] = pat final = program[correct][ 0 ] mid = final[:] for j in range (polo_num): mid = mid[: - 1 ] + '' + mid[ - 1 :] # print(f'len(mid)={len(mid)}\n{mid}') for i in range ( 224 , 0 , - 1 ): repl = mid[i:i + 3 ] if repl in repl2pat: pat = repl2pat[repl] mid = mid.replace(repl, pat, 1 ) if i > = 223 or i < = 2 : # print(f'{i} len(mid)={len(mid)}\n{mid}') pass mid = mid[: 1 ] + mid[ 2 :] mm = { 'Z' : '????????????' , 'M' : '????????????????' , ...} flag = mid[ - 225 :] rmm = {} for pat, repl in mm.items(): rmm[repl] = pat flag2 = '' for i in range ( 0 , len (flag), 5 ): repl = flag[i:i + 5 ] if repl in rmm: pat = rmm[repl] flag2 + = pat else : flag2 + = repl print (flag2) |
utf-8在windows的兼容问题
调windows cmd输出支持utf-8表情包chcp65001
出题原理猜测
????????
代表0、1、2
菠萝等表情可能是模三加减法
赛后
马尔可夫算法(类似形式文法的字符串操作)实现的虚拟机,图灵完全
出题人提供的wp和源码:[My-CTF-Challenges/ImaginaryCTF 2024/vokram at master · maple3142/My-CTF-Challenges (github.com)](https://github.com/maple3142/My-CTF-Challenges/tree/master/ImaginaryCTF 2024/vokram)
官方wp和源码(内容同上):ImaginaryCTF-2024-Challenges-Public/Reversing/vokram at main · ImaginaryCTF/ImaginaryCTF-2024-Challenges-Public (github.com)
[培训]内核驱动高级班,冲击BAT一流互联网大厂工作,每周日13:00-18:00直播授课