看雪·2023 KCTF 年度赛 | 第二题设计思路及解析

WriteUp 10个月前 admin
169 0 0

看雪·2023 KCTF 年度赛 | 第二题设计思路及解析

这是一场人类与超智能AI的“生死”较量

请立刻集结,搭乘SpaceX,前往AI控制空间站

智慧博弈  谁能问鼎


看雪·2023 KCTF 年度赛于9月1日中午12点正式开赛!比赛基本延续往届模式,设置了难度值、火力值和精致度积分。由此来引导竞赛的难度和趣味度,使其更具挑战性和吸引力,同时也为参赛选手提供了更加公平、有趣的竞赛平台。

*注意:签到题持续开放,整个比赛期间均可提交答案获得积分


今天中午12:00第二题《CN星际基地》已截止答题,该题围观人数2500+,共有11支战队成功提交flag。前三名战队分别是:98k、Nano、qswjjw


接下来一起看下该题的设计思路和解析吧。


出题团队简介


出题战队:心学

战队成员:htg

看雪·2023 KCTF 年度赛 | 第二题设计思路及解析


设计思路



题目类型:Windows CrackMe






题目概述


设计一个称量方法,从 39 个球体中找到唯一一个重量异常的球体(轻、重未知),称量方法是一个矩阵,矩阵就是序列号经过转换后得到的,矩阵的每一行就是每次称量的策略,通过记录每次称量结果,即可找到对应的异常球体的编号及轻重。


数学思路:
如果可以无限次的称量,则逐个测量即可找出异常球体。如果考虑次数最少,那最少是多少了?能否考虑一种通用方法,使得每个球体检测出来的次数均相同的,但次数最少?


我们知道每次称量结果,只有三种结果:相等、左重、右重,那如果称量次数为 n 次,那么有
看雪·2023 KCTF 年度赛 | 第二题设计思路及解析种结果,每一种结果可对应于一种异常的球体的编号及轻重,这样从理论上可以计算出相应的次数。


39个球体(含轻重)就有39*1=78种结果,考虑到每次称量结果有3种,且看雪·2023 KCTF 年度赛 | 第二题设计思路及解析也就是说39个球体(含轻重)最少需要称量4次。

看雪·2023 KCTF 年度赛 | 第二题设计思路及解析
假定:球体的编号依次为 1 2 3 4 5 6 …… 38 39

而每次测量,如何选取球体?哪些放在左侧?哪些放在右侧?

我们把每次称量的方法作为矩阵的一行,0 表示不选取,1 表示放在右侧,-1 表示放在左侧。

比如某一个称量矩阵。

看雪·2023 KCTF 年度赛 | 第二题设计思路及解析


第一行表示:1-13球体不参与,14-20、22、32、33、37-39,放在右侧,21、23-31、34-36 放在左侧。

称量结果:如果相等,为0;如果左侧重,为 -1 ;如果右侧重,为 1。

这样称量4次之后,会得到一个向量:
看雪·2023 KCTF 年度赛 | 第二题设计思路及解析





题目逻辑


获取序列号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,减半,81−1=80,80/2=40),而只需要 39 个即可,另外考虑到至少有一个 0 的列向量(必须选择)有 32 个,还需要从剩余的8(40−32=8)个找到 7 个列向量(39−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,那么不分析具体算法,其解题空间非常大 ,基本排除纯暴力破解。






解题思路


具体的破解过程详见 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值满足要求


给出的序列号:

看雪·2023 KCTF 年度赛 | 第二题设计思路及解析


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



赛题解析


本题解析由看雪论坛会员 Zero*/ 提供:

看雪·2023 KCTF 年度赛 | 第二题设计思路及解析






过反调试


ida打开先看初始化部分,有一个反调试,直接patch掉。

IsDebuggerPresent的if判断取个反:
看雪·2023 KCTF 年度赛 | 第二题设计思路及解析





分析流程


直接调试main函数,主要逻辑如下(以下代码来自ida7.7):


读取输入:

v3 = 0i64;v132 = 0;v4 = time64(0i64);srand(v4);v5 = sub_7FF6DD8E2F10(std::cout, &unk_7FF6DD8E66E8);v6 = std::ostream::operator<<(v5, sub_7FF6DD8E30E0);sub_7FF6DD8E2F10(v6, "Serial:tt");v154 = 0i64;v155 = 15i64;LOBYTE(Src) = 0;sub_7FF6DD8E2A90(&Src, &unk_7FF6DD8E6698, 0i64);LOBYTE(v7) = 10;v8 = std::ios::widen((char *)&std::cin + *(int *)(std::cin + 4i64), v7);sub_7FF6DD8E32F0(std::cin, &Src, v8);

打印提示字符:”Serial:tt”,然后std::cin读取用户输入,存在src中。


判断输入长度是否是156:

  if ( v10 != 156 )  {LABEL_16:    v15 = sub_7FF6DD8E2F10(std::cout, "fail");    std::ostream::operator<<(v15, sub_7FF6DD8E30E0);    goto LABEL_233;  }

分割字符串:


看雪·2023 KCTF 年度赛 | 第二题设计思路及解析

上述代码生成了一个string,根据调试结果得知v25(也就是string)是将输入等分为长度为39的四组,取每组的第i个元素(外层还有while)组成一个四字节的字符串。v26是将v25按照10进制转换为整数,留着后面用。

对于分割可以做如下理解:
# 输入的序列号1234567812345678# 分割后的序列号# 我这里一行只有四个,题目中一行有39个值,因为输入总长度为156,分割为4组1234567812345678# 此时每轮v25的值就是'1515'、'2626'...以此类推


然后if语句的三个判断条件主要是判断长度和上述分割出来的string中是否包含’2′(50的ascii)

(1)如果包含’2’则继续;
(2)如果不包含’2’就将其按照2进制转换为整数,判断转换是否成功,并且转换之后的结果不能等于15,否则就退出,15的二进制是’1111’,所以输入的字符分组后不能有’1111′


判断四个二:


看雪·2023 KCTF 年度赛 | 第二题设计思路及解析


判断分割后的字符串中是否有2,有2的情况下判断有几个2,如果四个都是2就退出,所以输入的字符串分割后不能有’2222′


单调递增

看雪·2023 KCTF 年度赛 | 第二题设计思路及解析
v26就是之前将分割后是string按照10进制转换为整数,v130初始值是0,但是每次比较完之后会将v26赋给v130,由于在while循环中,如果break,就会输出fail并退出。

所以这段代码的核心逻辑的意思是每一组分割后的字符串的十进制值都要比前一组的大,所以输入的串根据前面的分割逻辑分割之后的列向量需要是单调递增的。

还有一个细节就是v130的初始值是0,v26要大于v130,所以我们的输入的不能包含’0000′

矩阵存储

看雪·2023 KCTF 年度赛 | 第二题设计思路及解析
这段逻辑就是将输入的值分为四行,每行39个元素,按照矩阵的形式存入off_7FF6ED1798A8地址中。并且将2转换为-1。

从这里也可以看出我们的输入只能包含’0′,’1′,’2’三个元素。


循环运算

while ( 1 )      {        v65 = 0;        v66 = 0;        v67 = 0;        v68 = *(_QWORD *)((char *)off_7FF6ED1798A8 + v64);        v69 = 2;        for ( j = 12i64; j < 168; j += 52i64 )        {          v71 = *(_DWORD *)(j + v68 - 12);          if ( v71 == -1 )          {            v65 += v69 - 1 == v63;          }          else if ( v71 == 1 )          {            v66 += v69 - 1 == v63;          }          v72 = v71 + v67;          v73 = *(_DWORD *)(j + v68 - 8);          if ( v73 == -1 )          {            v65 += v69 == v63;          }          else if ( v73 == 1 )          {            v66 += v69 == v63;          }          v74 = v73 + v72;          v75 = *(_DWORD *)(j + v68 - 4);          if ( v75 == -1 )          {            v65 += v69 + 1 == v63;          }          else if ( v75 == 1 )          {            v66 += v69 + 1 == v63;          }          v76 = v75 + v74;          v77 = *(_DWORD *)(j + v68);          if ( v77 == -1 )          {            v65 += v69 + 2 == v63;          }          else if ( v77 == 1 )          {            v66 += v69 + 2 == v63;          }          v78 = v77 + v76;          v79 = *(_DWORD *)(j + v68 + 4);          if ( v79 == -1 )          {            v65 += v69 + 3 == v63;          }          else if ( v79 == 1 )          {            v66 += v69 + 3 == v63;          }          v80 = v79 + v78;          v81 = *(_DWORD *)(j + v68 + 8);          if ( v81 == -1 )          {            v65 += v69 + 4 == v63;          }          else if ( v81 == 1 )          {            v66 += v69 + 4 == v63;          }          v82 = v81 + v80;          v83 = *(_DWORD *)(j + v68 + 12);          if ( v83 == -1 )          {            v65 += v69 + 5 == v63;          }          else if ( v83 == 1 )          {            v66 += v69 + 5 == v63;          }          v84 = v83 + v82;          v85 = *(_DWORD *)(j + v68 + 16);          if ( v85 == -1 )          {            v65 += v69 + 6 == v63;          }          else if ( v85 == 1 )          {            v66 += v69 + 6 == v63;          }          v86 = v85 + v84;          v87 = *(_DWORD *)(j + v68 + 20);          if ( v87 == -1 )          {            v65 += v69 + 7 == v63;          }          else if ( v87 == 1 )          {            v66 += v69 + 7 == v63;          }          v88 = v87 + v86;          v89 = *(_DWORD *)(j + v68 + 24);          if ( v89 == -1 )          {            v65 += v69 + 8 == v63;          }          else if ( v89 == 1 )          {            v66 += v69 + 8 == v63;          }          v90 = v89 + v88;          v91 = *(_DWORD *)(j + v68 + 28);          if ( v91 == -1 )          {            v65 += v69 + 9 == v63;          }          else if ( v91 == 1 )          {            v66 += v69 + 9 == v63;          }          v92 = v91 + v90;          v93 = *(_DWORD *)(j + v68 + 32);          if ( v93 == -1 )          {            v65 += v69 + 10 == v63;          }          else if ( v93 == 1 )          {            v66 += v69 + 10 == v63;          }          v94 = v93 + v92;          v95 = *(_DWORD *)(j + v68 + 36);          if ( v95 == -1 )          {            v65 += v69 + 11 == v63;          }          else if ( v95 == 1 )          {            v66 += v69 + 11 == v63;          }          v67 = v95 + v94;          v69 += 13;        }        if ( v65 == v66 )        {          **(_DWORD **)((char *)off_7FF6ED1798B8 + v64) = 0;        }        else        {          v96 = -1;          if ( v65 < v66 )            v96 = 1;          **(_DWORD **)((char *)off_7FF6ED1798B8 + v64) = v96;        }        if ( v67 )          goto LABEL_16;

之后会进入一个超大的循环进行判断,我们调试的时候追踪一下v67的值可以发现他就是我们输入的每一行值之和(当然是2被转换为-1之后的),如果v67不为0,就退出程序,所以可以得出我们输入的每一行当中’1’和’2’的个数要一样,这样当2转换为-1之后,他们之和才会为0。

md5判断


看雪·2023 KCTF 年度赛 | 第二题设计思路及解析

最后对输入做了一次md5计算,并且判断md5的值。至此有了思路,根据上述对输入的控制条件,以及最终的md5值,可以爆破出输入的序列号。






总结


上述分析中对于输入需要满足的要求都已经粗体显示了,这里总结一下:
  1. 序列号矩阵的列向量不能包含:’0000’,’1111’,’2222′

  2. 序列号矩阵的列向量组成的整数单调递增

  3. 序列号矩阵只能由’0′,’1′,’2’三个元素组成

  4. 序列号矩阵的每个行向量中’1’和’2’的个数要一样多


再加上提示中的两个条件:

1、列向量组里不存在相反值,如[1,-1,1,0]与[-1,1,-1,0]不能同时存在,对应矩阵存储前的值就是[1,2,1,0]和[2,1,2,0]不能同时存在。

2、每个行向量里的0的数量 占 1/3,即每行有13个0。






爆破脚本


结合上述条件可以爆破一下,大概两分钟就能跑完。
import sysimport copyimport itertoolsimport hashlibfrom itertools import product # 计算md5值def compute_md5(input_string):    m = hashlib.md5()    m.update(input_string.encode('utf-8'))    return m.hexdigest() # 生成所有由0,1,2组成的四位数,并且不能包含0000,1111,2222# sorted保持单调递增def generate_numbers(n):    return sorted((''.join(p)) for p in product('012', repeat=n) if p != ('0','0','0','0') and p != ('1','1','1','1') and p != ('2','2','2','2')) numbers = generate_numbers(4)# print(len(numbers))# print(numbers) # 将所有可能的四位数按照如下a数组的形式打印出来,并且复制给a。# 我们输入的序列号就在a当中产生,a总共有78列,我们取39列,然后拼接成一行即为序列号# print afor i in range(4):    for number in numbers:        print(number[i], end='')    print() a = [    '000000000000000000000000001111111111111111111111111122222222222222222222222222',    '000000001111111112222222220000000001111111122222222200000000011111111122222222',    '001112220001112220001112220001112220001122200011122200011122200011122200011122',    '120120120120120120120120120120120120120201201201201201201201201201201201201201',] # 将所有互为相反的列向量的下标以键值对的形式存入reverse字典中# 该字典中的每对key:value都不能同时存在需要输入的序列号中# get get the opposite combinationreverse = {}for i in range(len(numbers)):    x = (numbers[i]).replace('1', 'temp').replace('2', '1').replace('temp', '2')    if (x) in numbers:        reverse[i] = numbers.index((x))print(len(reverse))print(reverse)  # 分别计算第0行元素为0,1,2的所有下标list_0 = [index for index, char in enumerate(a[0]) if char == '0']list_1 = [index for index, char in enumerate(a[0]) if char == '1']list_2 = [index for index, char in enumerate(a[0]) if char == '2'] def check(combo):    r = ''    for row in a:        s = [row[i] for i in combo]         # 1和2的个数相等        # 由于有1/3的0所以0,1,2的个数都是13个        if s.count('1') == s.count('2') == 13:            r += ''.join(s)        else:            return False     if len(r) == 0x9C:        # print(r)        if compute_md5(r) == 'aac82b7ad77ab00dcef90ac079c9490d':            print(f'flag: {r}')            return True        else:            return False # 每个选中的下标数组中都不能同时包含reverse的键值对def check_combo(combo):    for i in combo:        if i in reverse and reverse[i] in combo:            return False    return True  # 只需要爆破长度为39的下标数组,然后从a中选择这39个列,拼接成一行即为序列号# 由于1,2的个数相等,0占了1/3,所以0,1,2的个数都是13个# 由于单调递增,所以第一行一定是:000000000000011111111111112222222222222# 所以爆破的时候从第一行可以分为0,1,2三组来爆破,每组取13个值即可for combo0 in itertools.combinations(list_0, 13):    combo0 = list(combo0)    # 0相反元素还是0,所以需要检查自己是否包含相反元素    if not check_combo(combo0):        continue     for combo1 in itertools.combinations(list_1, 13):        combo1 = list(combo1)         # 2相反元素是1        # 所以需要从2开头的下标数组中,把和已选中的1开头的下标数组相反的下标移除        y = copy.deepcopy(list_2)        for i in combo1:            if i in reverse:                if reverse[i] in y:                    y.remove(reverse[i])         if len(y) < 13:            continue         for combo2 in itertools.combinations(y, 13):            combo2 = list(combo2)             if check(sorted(combo0 + combo1 + combo2)):                sys.exit()# flag: 000000000000011111111111112222222222222000011111111100001122222220000011222222011100011122200120200112220112202001122101201201201212001212020120121202010201


看雪·2023 KCTF 年度赛 | 第二题设计思路及解析

看雪·2023 KCTF 年度赛 | 第二题设计思路及解析

今天中午12:00
第三题《秘密计划》已开赛!

看雪·2023 KCTF 年度赛 | 第二题设计思路及解析

欢迎参赛

在这个充满变数的赛场上,没有人能够预料到最终的结局。有时,优势的领先可能只是一时的,一瞬间的失误就足以颠覆一切。而那些一直默默努力、不断突破自我的人,往往会在最后关头迎头赶上,成为最耀眼的存在。


谁能保持领先优势?谁能迎头赶上?谁又能突出重围成为黑马?




看雪·2023 KCTF 年度赛 | 第二题设计思路及解析


看雪·2023 KCTF 年度赛 | 第二题设计思路及解析

球分享

看雪·2023 KCTF 年度赛 | 第二题设计思路及解析

球点赞

看雪·2023 KCTF 年度赛 | 第二题设计思路及解析

球在看


看雪·2023 KCTF 年度赛 | 第二题设计思路及解析

点击阅读原文进入比赛

原文始发于微信公众号(看雪学苑):看雪·2023 KCTF 年度赛 | 第二题设计思路及解析

版权声明:admin 发表于 2023年9月5日 下午4:33。
转载请注明:看雪·2023 KCTF 年度赛 | 第二题设计思路及解析 | CTF导航

相关文章

暂无评论

您必须登录才能参与评论!
立即登录
暂无评论...