首页
社区
课程
招聘
[原创]看雪 2023·KCTF 年度赛 Crackme by 心学
2023-5-29 01:09 3695

[原创]看雪 2023·KCTF 年度赛 Crackme by 心学

htg 活跃值
4
2023-5-29 01:09
3695

题目类型:Windows CrackMe

一、题目概述:

设计一个称量方法,从 39 个球体中找到唯一一个重量异常的球体(轻、重未知),称量方法是一个矩阵,矩阵就是序列号经过转换后得到的,矩阵的每一行就是每次称量的策略,通过记录每次称量结果,即可找到对应的异常球体的编号及轻重。
数学思路
如果可以无限次的称量,则逐个测量即可找出异常球体。如果考虑次数最少,那最少是多少了?能否考虑一种通用方法,使得每个球体检测出来的次数均相同的,但次数最少?
我们知道每次称量结果,只有三种结果:相等、左重、右重,那如果称量次数为 n 次,那么会有 3n3^n 种结果,每一种结果可对应于一种异常的球体的编号及轻重,这样从理论上可以计算出相应的次数。 39个球体(含轻重)就有 392=7839*2=78 种结果,考虑到每次称量结果有3种,且 33=273^3 = 2734=813^4 = 81,也就是说39个球体(含轻重)最少需要称量4次。
次数:n=1n=1 ,结果:3n=31=33^n=3^1=3
次数:n=2n=2 ,结果:3n=32=93^n=3^2=9
次数:n=3n=3 ,结果:3n=33=273^n=3^3=27
次数:n=4n=4 ,结果:3n=34=813^n=3^4=81
次数:n=5n=5 ,结果:3n=35=2433^n=3^5=243
........
假定:球体的编号依次为 1 2 3 4 5 6 …... 38 39
而每次测量,如何选取球体?哪些放在左侧?哪些放在右侧?
我们把每次称量的方法作为矩阵的一行,0 表示不选取,1 表示放在右侧,-1 表示放在左侧。
比如 某一个称量矩阵。
[000000000000011111111111111111111111111000011111111100000000011111111111111111011100011111100011111100011111000111111101101101101101101101101101011011011011]\left[ \begin{matrix} 0&0&0&0&0&0&0&0&0&0&0&0&0&1&1&1&1&1&1&1&-1&1&-1&-1&-1&-1&-1&-1&-1&-1&-1&1&1&-1&-1&-1&1&1&1\\0&0&0&0&1&1&1&1&1&1&1&1&1&0&0&0&0&0&0&0&0&0&-1&-1&-1&-1&-1&-1&-1&-1&1&-1&-1&1&1&1&-1&-1&-1\\0&1&1&1&0&0&0&1&1&1&-1&-1&-1&0&0&0&1&1&1&-1&1&-1&0&0&0&-1&-1&1&1&1&0&0&0&-1&-1&-1&-1&-1&-1\\1&0&1&-1&0&1&-1&0&1&-1&0&1&-1&0&1&-1&0&1&-1&0&-1&-1&0&-1&1&0&1&0&-1&1&0&1&-1&0&-1&1&0&1&-1 \end{matrix} \right]
第一行表示:1-13球体不参与,14-20、22、32、33、37-39,放在右侧,21、23-31、34-36 放在左侧。
称量结果:如果相等,为0;如果左侧重,为 -1 ;如果右侧重,为 1。
这样称量4次之后,会得到一个向量,
比如[0010]\left[ \begin{matrix}0&0&1&0 \end{matrix} \right],其值刚好为第2个列向量,则表示第2个球体为重;
比如[0011]\left[ \begin{matrix}0&0&-1&1 \end{matrix} \right],其值刚好为第4个列向量的相反值,则表示第4个球体为轻(相反值)。

二、题目逻辑:

获取序列号SN

1、读入用户输入序列号SN:SN是一个仅由[0-2]三种字符组成的字符串,长度为 156。

转换称量矩阵

2、将SN转换成称量矩阵Matrix:按照每行 39 个字符(数值),一共 4 行,且将字符串转换成数值,2 变成 -1

验证所有球体

3、验证过程:
模拟称量过程,依次读取每行的 39 个数值,0 表示不选取,1 表示放在右侧,-1 表示放在左侧。
逐个球体校验,假定球体 i 为重,则通过测量的4次结果是否与称量矩阵Matrix的第 i 列向量相等,且没有其余列向量与其相等或相反(向量乘以-1)。
如果所有球体(39个)均通过验证,则序列号正确,否则失败。

约束限制多解

4、考虑到称量矩阵(也就是序列号SN)存在很多种可能性,有如下约束
(1)列向量升序排列:称量矩阵转换成列向量(2暂时不替换成-1),每个列向量转换成整数数值,则这个列表应该是升序排列的。
(2)剔除全1列向量:称量矩阵的列向量(正、反考虑为一种)初始选择会有 40 种(剔除0,减半,811=8081-1=8080/2=4080/2=40),而只需要 39 个即可,另外考虑到至少有一个 0 的列向量(必须选择)有 32 个,还需要从剩余的8(4032=840-32=8)个找到 7 个列向量(3932=739-32=7),即有8种可能性,我们只考虑一种,比如把全 1 的列向量剔除。此时,就保证了初始的称量矩阵唯一。
(3)枚举所有可能:此时,答案还不唯一,而且很大,超过10000个,此时还需要做约束:
如果某个列向量的首位为0时,那逐步深入下去,第一个非0的数值为1,而不是2(-1)。比如 0001、0012、1000、1021、2021 满足要求,0021、0200不满足要求,经过此种方法操作,答案限定为 3781 个,耗时约 27 min,如果考虑签名验证,期望耗时约 14 min
(4)签名锁定唯一:为了更进一步限定唯一性,采用md5对SN进行签名认证。也就是第3步是一个需要穷举的过程。

本题仅考虑数学算法,不考虑其他保护措施,比如反调试、反反汇编、混淆处理。
输入字符串:156个,只能输入0/1/2,那么不分析具体算法,其解题空间非常大 ,基本排除纯暴力破解。
3156=2697216055906075632621068704072868536119388901841080479112694314649744735213^{156} = 269721605590607563262106870407286853611938890184108047911269431464974473521

三、题目解题思路:

具体的破解过程详见 WP,pyhon代码。
首先要从题目中意识到这是一个39个球体的称量问题。

1、获取初步的39个列向量,组成称量矩阵

(1)、找到40个“初步候选列向量”:排除[0,0,0,0],每个列向量均有相反数,仅保留列向量(2开头、1开头、0开头且深入下去首个非0为1),排除列向量(0开头且深入下去首个非0为2)
(2)、从40个“初步候选列向量”找到32个“初步永久列向量”,即每个列向量中至少有一个0
(3)、从剩余的8个“初步可选列向量”任意选择7个,与上面的32个组成最终比较的称量矩阵,进行称量验证。

2、判断“称量矩阵”是否满足要求

(1)、升序排列
(2)、满足约束条件:每个列向量均不一样,即没有重复的;每行的0和1和2的数量均相等。
(3)、序列号的md5值满足要求

#给出的序列号:
000000000000011111111111112222222222222000011111111100001122222220000011222222011100011122200120200112220112202001122101201201201212001212020120121202010201

md5 = aac82b7ad77ab00dcef90ac079c9490d

[[ 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 1 1 1 -1 -1 1 -1 -1 -1 1
-1 -1 -1 -1 -1 1 -1 1 1 1 -1 1 1 1 1]
[ 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 -1 1
-1 -1 -1 -1 -1 1 1 -1 -1 -1 1 -1 -1 -1 -1]
[ 0 1 1 1 0 0 0 1 1 1 -1 -1 -1 0 0 0 1 -1 -1 -1 1 1 0 0
0 -1 -1 1 1 -1 0 0 0 1 -1 1 -1 -1 -1]
[ 1 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0 -1 1 0 -1 1 0 1
1 0 1 0 -1 -1 0 1 -1 0 -1 -1 0 1 -1]]

[[0,0,0,0,0,0,0,0,0,0,0,0,0,-1,1,1,1,-1,-1,1,-1,-1,-1,1,-1,-1,-1,-1,-1,1,-1,1,1,1,-1,1,1,1,1]
,[0,0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,-1,1,-1,-1,-1,-1,-1,1,1,-1,-1,-1,1,-1,-1,-1,-1]
,[0,1,1,1,0,0,0,1,1,1,-1,-1,-1,0,0,0,1,-1,-1,-1,1,1,0,0,0,-1,-1,1,1,-1,0,0,0,1,-1,1,-1,-1,-1]
,[1,0,1,-1,0,1,-1,0,1,-1,0,1,-1,0,1,-1,0,-1,1,0,-1,1,0,1,1,0,1,0,-1,-1,0,1,-1,0,-1,-1,0,1,-1]]

[[0,0,0,0,0,0,0,0,0,0,0,0,0,2,1,1,1,2,2,1,2,2,2,1,2,2,2,2,2,1,2,1,1,1,2,1,1,1,1]
,[0,0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,2,1,2,2,2,2,2,1,1,2,2,2,1,2,2,2,2]
,[0,1,1,1,0,0,0,1,1,1,2,2,2,0,0,0,1,2,2,2,1,1,0,0,0,2,2,1,1,2,0,0,0,1,2,1,2,2,2]
,[1,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,2,1,0,2,1,0,1,1,0,1,0,2,2,0,1,2,0,2,2,0,1,2]]

a=[
[0,0,0,0,0,0,0,0,0,0,0,0,0,2,1,1,1,2,2,1,2,2,2,1,2,2,2,2,2,1,2,1,1,1,2,1,1,1,1],
[0,0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,2,1,2,2,2,2,2,1,1,2,2,2,1,2,2,2,2],
[0,1,1,1,0,0,0,1,1,1,2,2,2,0,0,0,1,2,2,2,1,1,0,0,0,2,2,1,1,2,0,0,0,1,2,1,2,2,2],
[1,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,2,1,0,2,1,0,1,1,0,1,0,2,2,0,1,2,0,2,2,0,1,2]]

后续:

考虑序列号压缩,能够缩减字符数量。


[培训]内核驱动高级班,冲击BAT一流互联网大厂工作,每周日13:00-18:00直播授课

最后于 2023-9-5 12:01 被kanxue编辑 ,原因:
上传的附件:
收藏
免费 0
打赏
分享
最新回复 (7)
雪    币: 35388
活跃值: (19185)
能力值: (RANK:350 )
在线值:
发帖
回帖
粉丝
kanxue 8 2023-5-29 09:40
2
0
题目收到,请再补充一篇设计思路文档
雪    币: 5568
活跃值: (3107)
能力值: ( LV12,RANK:394 )
在线值:
发帖
回帖
粉丝
htg 4 2023-5-29 19:01
3
0
好的,我得完善下可能存在的多解问题。
雪    币: 5568
活跃值: (3107)
能力值: ( LV12,RANK:394 )
在线值:
发帖
回帖
粉丝
htg 4 2023-6-2 15:59
4
0
题目的相关资料已完成。
雪    币: 35388
活跃值: (19185)
能力值: (RANK:350 )
在线值:
发帖
回帖
粉丝
kanxue 8 2023-6-2 16:08
5
0
没看到题目附件,是那个附件图片?
雪    币: 5568
活跃值: (3107)
能力值: ( LV12,RANK:394 )
在线值:
发帖
回帖
粉丝
htg 4 2023-6-2 16:17
6
0
kanxue 没看到题目附件,是那个附件图片?
已补充。
雪    币: 28
活跃值: (179)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
tgcwc 2024-5-21 11:19
7
0
htg老师您好,购买了您的.net课程,怎么下载课件和加入微信群,麻烦您了?
雪    币: 5568
活跃值: (3107)
能力值: ( LV12,RANK:394 )
在线值:
发帖
回帖
粉丝
htg 4 2024-5-27 12:54
8
0
tgcwc htg老师您好,购买了您的.net课程,怎么下载课件和加入微信群,麻烦您了?
请联系 Editor@看雪 进入微信群,课件可从课程里的课件栏目下的附件处下载。
游客
登录 | 注册 方可回帖
返回