这是一场人类与超智能AI的“生死”较量
请立刻集结，搭乘SpaceX，前往AI控制空间站
智慧博弈 谁能问鼎
看雪·2023 KCTF 年度赛于9月1日中午12点正式开赛！比赛基本延续往届模式，设置了难度值、火力值和精致度积分。由此来引导竞赛的难度和趣味度，使其更具挑战性和吸引力，同时也为参赛选手提供了更加公平、有趣的竞赛平台。
*注意：签到题持续开放，整个比赛期间均可提交答案获得积分
今天中午12:00第二题《CN星际基地》已截止答题，该题围观人数2500+，共有11支战队成功提交flag。前三名战队分别是：98k、Nano、qswjjw
接下来一起看下该题的设计思路和解析吧。
出题战队：心学
战队成员：htg
题目类型：Windows CrackMe
一
题目概述
设计一个称量方法，从 39 个球体中找到唯一一个重量异常的球体（轻、重未知），称量方法是一个矩阵，矩阵就是序列号经过转换后得到的，矩阵的每一行就是每次称量的策略，通过记录每次称量结果，即可找到对应的异常球体的编号及轻重。
数学思路：
如果可以无限次的称量，则逐个测量即可找出异常球体。如果考虑次数最少，那最少是多少了？能否考虑一种通用方法，使得每个球体检测出来的次数均相同的，但次数最少？
我们知道每次称量结果，只有三种结果：相等、左重、右重，那如果称量次数为 n 次，那么有
种结果，每一种结果可对应于一种异常的球体的编号及轻重，这样从理论上可以计算出相应的次数。
39个球体（含轻重）就有39*1=78种结果，考虑到每次称量结果有3种，且
也就是说39个球体（含轻重）最少需要称量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，减半，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值满足要求
后续：考虑序列号压缩，能够缩减字符数量。
本题解析由看雪论坛会员 Zero*/ 提供：
一
过反调试
二
分析流程
读取输入：
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);
判断输入长度是否是156：
if ( v10 != 156 ){LABEL_16:v15 = sub_7FF6DD8E2F10(std::cout, "fail");std::ostream::operator<<(v15, sub_7FF6DD8E30E0);goto LABEL_233;}
分割字符串：
# 输入的序列号1234567812345678# 分割后的序列号# 我这里一行只有四个，题目中一行有39个值，因为输入总长度为156，分割为4组1234567812345678# 此时每轮v25的值就是'1515'、'2626'...以此类推
然后if语句的三个判断条件主要是判断长度和上述分割出来的string中是否包含’2′(50的ascii)
判断四个二：
单调递增
所以这段代码的核心逻辑的意思是每一组分割后的字符串的十进制值都要比前一组的大，所以输入的串根据前面的分割逻辑分割之后的列向量需要是单调递增的。
还有一个细节就是v130的初始值是0，v26要大于v130，所以我们的输入的不能包含’0000′
矩阵存储
从这里也可以看出我们的输入只能包含’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 ){**)((char *)off_7FF6ED1798B8 + v64) = 0;}else{v96 = -1;if ( v65 < v66 )v96 = 1;**)((char *)off_7FF6ED1798B8 + v64) = v96;}if ( v67 )goto LABEL_16;
md5判断
三
总结
-
序列号矩阵的列向量不能包含：’0000’，’1111’，’2222′
-
序列号矩阵的列向量组成的整数单调递增
-
序列号矩阵只能由’0′,’1′,’2’三个元素组成
-
序列号矩阵的每个行向量中’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 Falseif len(r) == 0x9C:# print(r)if compute_md5(r) == 'aac82b7ad77ab00dcef90ac079c9490d':print(f'flag: {r}')return Trueelse:return False# 每个选中的下标数组中都不能同时包含reverse的键值对def check_combo(combo):for i in combo:if i in reverse and reverse[i] in combo:return Falsereturn 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):continuefor 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:continuefor combo2 in itertools.combinations(y, 13):combo2 = list(combo2)if check(sorted(combo0 + combo1 + combo2)):sys.exit()# flag: 000000000000011111111111112222222222222000011111111100001122222220000011222222011100011122200120200112220112202001122101201201201212001212020120121202010201
在这个充满变数的赛场上，没有人能够预料到最终的结局。有时，优势的领先可能只是一时的，一瞬间的失误就足以颠覆一切。而那些一直默默努力、不断突破自我的人，往往会在最后关头迎头赶上，成为最耀眼的存在。
谁能保持领先优势？谁能迎头赶上？谁又能突出重围成为黑马？
球分享
球点赞
球在看
点击阅读原文进入比赛
原文始发于微信公众号（看雪学苑）：看雪·2023 KCTF 年度赛 | 第二题设计思路及解析
