首页
论坛
课程
招聘
[原创] 喵喵幼儿园【中娅之戒】 - KCTF 2021 秋季赛 第3题设计思路
2021-10-15 16:38 7771

[原创] 喵喵幼儿园【中娅之戒】 - KCTF 2021 秋季赛 第3题设计思路

2021-10-15 16:38
7771

题目名:喵喵幼儿园
团队名称:中娅之戒(Zhongya's Ring)

 

出题者:海风月影

 

=====================================================
比赛公开信息:
KCTF2021 秋季赛 CrackMe
--- Coded by 海风月影[ZysR]

 

参赛队伍:中娅之戒(Zhongya's Ring)

 

规则走方案二:有混淆,无VM

 

文件名:cm.exe
文件大小:6.63 MB (6,962,176 字节)
CRC32: BDC342F3
MD5: 18CE92A6F3F7CCEFE7F78FF0AF4F4BE9
SHA256: 5106D6BDEF101BCD3113CB065C0849B823B5074412F1B11D4E46681428795B02

 

给一组正确的序列号:

 

name: 5106D6BDEF101BCD
serial: 7280A2E68D16E3BE47DC69F8FDD0304E65DF5DA7F04BFDB1936CE8620211CFFC


[2022冬季班]《安卓高级研修班(网课)》月薪三万班招生中~

最后于 2021-11-22 12:05 被kanxue编辑 ,原因:
上传的附件:
收藏
点赞1
打赏
分享
最新回复 (6)
雪    币: 7062
活跃值: 活跃值 (3346)
能力值: (RANK:1130 )
在线值:
发帖
回帖
粉丝
海风月影 活跃值 22 2021-10-15 16:40
2
0

题目很难,4天基本上做不出来
1,申请放最后一题
2,如果4天无人破解,申请延长时间
3,如果可以延长时间,我可以放一个无混淆的版本(即编译出来的版本,让大家比较容易理解题目算法,当然也可以多给出一组对应hash的name/serial,难度降低90%)

最后于 2021-10-18 13:57 被海风月影编辑 ,原因:
雪    币: 7062
活跃值: 活跃值 (3346)
能力值: (RANK:1130 )
在线值:
发帖
回帖
粉丝
海风月影 活跃值 22 2021-10-19 10:35
3
0

===============故事背景===============

喵喵幼儿园里有很多个喵宝宝
每天早上园长都要让所有宝宝签到
宝宝们活波好动 不守规矩
于是园长想出了一个好玩的签到办法
园长准备了一个毛线球给宝宝们玩 宝宝们都争相上去用小爪子拍它 毛线球被拍得乱飞
只有当毛线球被所有喵宝宝都拍过之后 它就会自动爆开 变成一场漂亮的毛线雨
毛线雨落到地上 正好是园长的名字
园长和喵宝宝们就都开心了


===============整体架构设计===============

输入:园长名(name),序列号(serial),name任意长度,serial 256bit
输出:是否成功

园长:维护一张宝宝签到表,一个伪随机数发生器DRNG(内部64bit,输入输出32bit),SHA256(name),serial,这4个是全局的
宝宝:一共31个,每个宝宝有一个特性值VI(256bit)

验证流程:
0,用name初始化伪随机数发生器,初始化所有宝宝的VI,园长名取SHA256(name),保证过程不可逆,serial,256bit,直接作为园长的毛线球
1,开始选择第一个宝宝,把毛线球给他
2,当前拿毛线球的宝宝CurrentBaby签到,然后随机选择另一个宝宝TargetBaby,改变TargetBaby的特性值VI
3,当前宝宝改变园长的毛线球(serial)
4,如果所有宝宝均已签到完成,跳转到步骤7
5,当前宝宝随机选择另一个宝宝Baby2,然后毛线球传给Baby2,用Baby2,修改当前宝宝CurrentBaby的特性值VI
6,跳转到步骤2
7,毛线球爆炸
8,判断爆炸后的毛线雨落在地上,判断是否正好是输入的name

上述过程中的算法:
1,伪随机数发生器:DRNG,rand的改造版,无法逆运算,无法轻易预测,有两个过程
       0)更新 -> 输入32bit,改变内部结构
       1)输出 -> 改变内部结构,输出32bit
2,RunVM:RunVM(A, B),输入两个256bit大数,A,B
       将A,逐步更新到DRNG中
       从DRNG中,取32bit中的最低2bit,有4种可能性
       1)喵算法
       2)MixColumn-cbc
       3)XTEA-cbc
       4)Dummy-cbc
       分别用4种算法,对B进行修改,整个过程,会修改B的值,此为可逆运算

3,修改园长的status:RunVM(Baby->VI, serial)
4,一个宝宝改变另一个宝宝的个性数据:流程如下,
       saveVI = tarBaby->VI;
       RunVM(currBaby->VI, tarBaby->VI)
       tarBaby->VI ^= saveVI
       整个过程,被修改的VI,此为不可逆运算
5,选择一个宝宝:DRNG随机数选择一个宝宝
6,毛线球爆炸:椭圆曲线混淆版点乘算法,此为可逆运算

===============具体算法===============
OI1:喵算法,本身算法没有什么特殊意义,把256bit分成8个32bit,分别加减异或,全部看懂逻辑后,逐步可逆
OI2:MixColumn-cbc,基础算法是Aes里面的MixColumn,矩阵系数改了,处理32bit,看懂 https://bbs.pediy.com/thread-267902.htm 帖子后,轻松黑盒搞定
OI3:XTEA-cbc,改了系数的标准XTEA算法,处理64bit,常量0x9E3779B9改成了0xB7E15163
OI4:Dummy-cbc,32bit,在48组可逆算法中选择一组进行加密,每组都由简单异或取反加减等算法组成

以上4个算法,会调用很多遍,都是分组算法,分别为:256bit一组,32bit一组,64bit一组,32bit一组,组与组直接,由CBC模式连接,如需要key,iv,从DRNG输出中获取

OI0:毛线球爆炸,椭圆曲线中的半点乘算法,椭圆曲线使用国密SM2(推广宣传国密算法)

       SM2: y^2 = x^3 + ax + b
       Fp - 256
       p =FFFFFFFE FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 00000000 FFFFFFFF FFFFFFFF
       a =FFFFFFFE FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 00000000 FFFFFFFF FFFFFFFC
       b =28E9FA9E 9D9F5E34 4D5A9E4B CF6509A7 F39789F5 15AB8F92 DDBCBD41 4D940E93
       n =FFFFFFFE FFFFFFFF FFFFFFFF FFFFFFFF 7203DF6B 21C6052B 53BBF409 39D54123
       Gx=32C4AE2C 1F198119 5F990446 6A39C994 8FE30BBF F2660BE1 715A4589 334C74C7
       Gy=BC3736A2 F4F6779C 59BDCEE3 6B692153 D0A9877C C62A4740 02DF32E5 2139F0A0

       定义点乘算法:y = kx(k, x)
       y = k * x,k,y,x均为256bit
       正常椭圆曲线的点乘,Y = k * X,Y和X都是坐标,都由2个256bit组成
       这里的算法中,小写表示只有256bit,由于缺失了半个坐标,使整个过程有点难懂
       构造特殊的 y,使得进行逆运算能够有正确的x解
       求k对于椭圆曲线阶的逆   revK = k^-1 MOD N,其中N是椭圆曲线的阶(公开常量,谷歌搜索)
       由于 y = k*x,所以 x = y/k = kx(revK, y),得解

       最后的毛线球爆炸,就是让y = name, x = serial,验证 k * serial 必须等于 name,其中k是DRNG中输出的
       毛线球爆炸的算法OI0只用一次



===============破解思路===============
1,解决反调试和内存校验,找到正确的3个内存校验值,并patch程序,三个校验值分别为:011EE725,B06B784D,3F93CAB9
2,找到修改园长Serial的RunVM,hook这里,得到整个运行的全部序列以及相应的参数context_logs
3,搞定OI0 - OI4这5个算法,写出逆算法,其中OI4,不需要全部搞定,只需要找到对应的那几个即可
4,写程序,根据上面的context_logs,逆运算求解即可


===============题目答案===============
name: KCTF
serial: CCBFB1FA4D9333348E946BBDF0A809129C7051780B7873C589DFCBA0C84B214B



================点评=================
算法难点:
       OI0,需要对椭圆曲线算法比较了解,需要有一定的数学功底

       OI1,不是单步逆向的算法,需要整体看懂,才能逆运算
       OI2,加密解密由查表异或完成,表经过了复杂的处理,但整体是线性运算,因此黑盒比较容易解
       OI3,常量换了,需要很熟悉XTEA才能看懂
       OI4,内置了48组算法(但一个name跑下来,未必覆盖所有算法),需要一定的工作量

逆向难点:
       1,大数运算库自写,整个流程完全内联,使得函数超级长,不容易分割处理。
       2,整个程序全部使用了混淆(无VM),进一步加大逆向难度(主要是无法用IDA F5了)。
       3,加了内存校验,一共3处,3次的校验一共有3个校验值,分别输入到DRNG随机数中干扰过程输出,因此一旦内存校验不通过,最后结果是不正确的。而内存校验的过程中会触发反调试检查,而反调试检查会干扰内存校验值,使得整体调试变得非常困难,需要一定的技巧才能正确跑通。
       4,整体算法流程是单向的,中间的4个算法,由于name不同,所以DRNG初始化是不同的,中途输出的所有随机数,都不相同,因此调用OI1-OI4的顺序也是不一样的。这使得攻击者,必须先逆出4个算法,然后还得找到正确的顺序,才能求解。




最后于 2021-10-24 21:32 被海风月影编辑 ,原因:
雪    币: 584
活跃值: 活跃值 (11141)
能力值: (RANK:350 )
在线值:
发帖
回帖
粉丝
kanxue 活跃值 8 2021-11-14 19:39
4
0
第三题 蒙混过关
雪    币: 3982
活跃值: 活跃值 (947)
能力值: ( LV12,RANK:279 )
在线值:
发帖
回帖
粉丝
htg 活跃值 3 2021-11-22 17:34
5
0
看题目思路,也是云里雾里。中娅之戒厉害。
雪    币: 7062
活跃值: 活跃值 (3346)
能力值: (RANK:1130 )
在线值:
发帖
回帖
粉丝
海风月影 活跃值 22 2021-11-22 18:57
6
2

放个无混淆,无anti版本吧

供大家赛后研究算法


上传的附件:
雪    币: 13484
活跃值: 活跃值 (1859)
能力值: ( LV15,RANK:2603 )
在线值:
发帖
回帖
粉丝
poyoten 活跃值 22 2021-11-22 21:57
7
0
kanxue 第三题 蒙混过关
第3题名字应该叫硬核过关
游客
登录 | 注册 方可回帖
返回