上上周的一道字符串替换实现的虚拟机的题目
脑昏看错题了，以为字节码只会被遍历一次，一直尝试暴力反向替换搜索答案发现解不出来，浪费了很多时间。
然后重新看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:]
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:
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)
最后于 2024-7-31 16:22
被wx_御史神风编辑
，原因：
