Plaid CTF dr

打比赛的时候,后面一直在看dr这个题,把大概逻辑逆清楚(后来发现逆向一点用都没,感觉还不如猜呢,tcl,rust逆的很慢),一开始觉得有点类似自动机,后面发现是正则之后,巨神两个小时就秒了(tql

拖了很久才来复现,稍微记录一下,免得之后忘记了

程序逻辑

虽然是 rust 写的,但是程序逻辑比较简单,可以分为三部分,前面第一部分和第三部分都是定死的字符串 “3” 和 “yes”

第二部分输入的时候会出现一些奇怪的东西,到后面可以发现第二部分算是第四部分的提示

第二部分输入的是症状,第四部分是输入key,输入症状时,会出现类似自动机吃字符然后出现状态转换的提示,在这部分可以猜到一些最基本的符号表示,同时不同的症状需要的治病的费用不同,对后续的第四部分也会造成影响

第四部分输入key之后,会进行接受,并在最后将输入的内容和写在bss段的字符列表进行处理之后得到flag

正则分析

通过猜名字和对于不同的输入和提示的返回可以得到以下的分析结果

And: 满足Res中所有的要求
Alt: 满足Res中其中一个要求
Seq: 正则需要满足的序列
Lit: 一个一个匹配,字面量
Res: 数组
Star: 匹配0个或者多个
Eps: epsilon

Neg(Null): 匹配任意长度的

Neg:
    10c -> 10ca
    Neg( ... Alt(Res([Lit("af")])) ...) -> Neg( ... Alt(Res([Lit("f")])) ... )
    应该是禁止出现 af 的意思
    
    尝试 10caf 也失效了

Consider: 
    1: 1,7777,73331         0*16+1
    10: 16,7777,73331       (0*16+1)*16+0    
    100: 256,7777,73331     ((0*16+1)*16+0)*16+0
    10c: 268,7777,73331     ((0*16+1)*16+0)*16+0xc
    %733331

    相当于 Consider(Res([])) 的个数进制

Moon: 
    1: Moon([0-9],2,3), Moon([a-f],2,3), Moon( (([0-9],1,3), ([a-f],2,3)), 1, 2)
    10: Moon([0-9],3,3), Moon([a-f],2,3), Moon( (([0-9],1,3), ([a-f],2,3)), 1, 2)
    100: Moon([0-9],1,3), Moon([a-f],2,3), Moon( (([0-9],1,3), ([a-f],2,3)), 1, 2)
    10c: Moon([a-f],3,3), Moon( (([0-9],1,3), ([a-f],2,3)), 1, 2)
    
    相当于在算个数,如果个数相等了,这个 Moon 可以结束进入下一个

    100c 这个c就吃不进去,因为第一项是 Moon([0-9], 1, 3)

Fan:
    10: Neg(.. Fan([a-f], 6) ..)
    10b: Neg(.. Fan([a-f], 5) ..)
    倒数计数

条件

最后对照输入1之后的正则提示,可以分析得到以下的结果

1. Neg(Null) + Consider( [bcd], Lit("cdb")+Neg(bd) ], 0, 2, 3)  字符串 []cdb 或者 cdb[] 且不能为 cdbb cdbd
2. *[1-3] + (*[3-7] + Neg(Null))                                
3. Consider( [05a], [16b], [27cf], [38dx], [49e], 0, 0, 7 )     算法需要 最后 %7 == 0
4. Moon([0-9], 1, 3) + Moon([a-f], 2, 3) + Moon( Moon([0-9], 1, 3), Moon([a-f], 2, 3), 1, 2)    需要 数字(2 5 8...)+字符(1 4 7...)+数字(2 5 8...)+字符(1 4 7...) 
5. Moon(Lit("10"), 0, 3)                                        10需要出现36. Neg( Alt( Lit("af"), Lit("73"), 数字+Lit("a"), Lit("ccc"), Fan([0-9], 7) )  )          af 73 数字+a ccc 都不能出现 数字也不能连续超过7个
   Neg( Alt( Lit("a"), Fan([0-9], 6)))                   		a 不能出现 数字不能连续超过67. Neg( Neg(Null) + Fan([a-f]+Neg(Null), 6))                                    字母不能超过68. Consider(0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f, 0,7777,73331)

大致推测

1 4 7得 cdb 的串长度只能为 4且只能为 [b-f]cdb | cdb[cef]

主要4可以知道基本上是数字+字符+数字+字符的模式,又字符不能超过6个且连续的字符必须是1或者4个,因此要么是1+4要么是4+1

再判断一下数字只能是2+2 | 2+5 | 5+2 | 5+5,又需要出现三次10,因此只能[1010x|10x10|10] + [10xxx|x10xx|xx10x|xxx10]或者这两个的顺序可以反过来即前面是一个10后面是两个10

因此(a, b, c, d)

a: 1010x | 10x10 | 10
b: [b-f]cdb | cbd[cef]
c: 10xxx | x10xx | xx10x | xxx10
d: bcd

a c可交换,b d可交换,然后必须要10开头,必须要3个10,不能出现73,且两个Consider需要满足

因此可以写出脚本爆破,最后可以得到一堆可能的解

最后可行的结果

cough
10174cdbf10810c

PCTF{a_pr1m3_a_day_k33ps_th3_D0ctor_Firmly_Away}

附上题目和脚本 dr

我的脚本写的十分的暴力(无限套for循环),巨神写的就很简单


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!