-
-
[原创] KCTF2022春季赛 第十一题 虫洞末世
-
2022-6-4 15:44 10074
-
前言
第一次参与KCTF,毕竟难得遇到密码题可以试试身手。中间遇到了一些由于在之前其他密码题里的惯性思维带来的坑,但好在吹了个风及时冷静下来,最后拿到了三血,也算是个不错成绩。仅在此记录,希望还能启发其他师傅。
流程分析
本题只有两个主要函数,createkey和cheakkey。主流程里对输入的数据先进行createkey再进行cheakkey。
createkey
一个生成函数createkey,输入为一个字符串,正常输出为一个浮点数数组,异常输出为-1。合法输入长16,合法输入字符为可见字符;合法输出数组长为8。
具体流程分为四大步:
- 字符转整数,将非数字字符的ascii+100,将数字字符的ascii+175.这里导致了本题主要的多解:'0'和'{','1'和'|' ,'2'和'}' ,'3'和'~',这四组字符的映射值一致。所以这一步得到的是一个16长数组,每个位置共有94-4=90种合法状态。
- 数组压缩,将上一步得到的数组每连续两个整数通过
压缩为一个新的数据,最终得到一个8长的整数数组k1,可以发现这个时候由于偶数位乘了两次,而奇数位只乘了一次,所以二者地位不均等,还有一个位置标记i也会影响会得到的结果,因而共有90*90*8种合法状态,但需要注意,在具体到每一位只有90*90种状态。同时维护一个k2数组,其是k1数组中对应元素的下一个奇数。本身并没有提供额外变量,主要是为下一步提供部分随机性。1p
=
lists[
2
*
i]
*
*
2
*
lists[
2
*
i
+
1
]
+
i
*
*
2
维护控制变量Q。Q通过k2数组除去k2[3]外累乘初始化得到,然后根据Q是否整除于k1[j]为Q增加$$\Pi_{m=0}^{j-1}k1[m]$$ (j=0时则为1),直到Q整除于其中一个变量为止,并退出循环。如果这个循环的过程少于600000次则成功进入下一步,否则返回报错。
用Q去依次浮点除k1得到finalkey输出。
cheakkey
输入为一个八个浮点数的数组,输出是否正确。硬编码了四个比对变量,两个浮点rkey和两个整数rmode;还定义了一个变换方法doom,输入两个数,输出一个数,数学表达$doom(x,y)=min(x,y)*abs(x-y)$。
具体对比项目如下:
- 将输入的key[0]和key[-1]与两个浮点rkey对比,相等则通过;
- 取某两个剩下的key相除,然后乘一个10**16进行整数化。这样得到三个mode(mode1和mode3其实是同一个数),然后分别送入doom方法得到两个Mode,与rmode对比,相等则通过。
数据流分析
可以发现数据流大概有个四层结构,第一层是输入,有90种可能,第二层为两个第一层元素组合,最终得到finalkey,有90*90可能,这两层都接受枚举;第三层为mode功能处,是将两个第二层元素组合而成,$90^4$种可能,很明显就超出了枚举的可能性;第四层是doom方法,将两个第三层元素组合,不可能枚举。
除此之外第一层和第三层均为整数,是无误差的,但第二层浮点数(python内浮点数为53位精度,等价于C中的double)有较大误差,本身就带来了不可逆性,所以第一层到第二层,第二层到第三层必须要枚举;但是第三四层由于是先进行了整数处理,所以是精准数据,本身具有理论可逆性,但需要看数据规模观察是否可计算,看数据细节判断是否多解。
解题流程
第一步
在第一层进行初始化,将字符映射为整数,处理出第一层的合法数据集合s。
1 2 3 4 5 6 7 8 9 10 11 12 | In [ 54 ]: s = set () ...: for i in string.printable: ...: p = ord (i) ...: if p< = 57 and p> = 48 : ...: p = p + 175 ...: else : ...: p = p + 100 ...: if p not in s: ...: s| = {p} ...: else : ...: print (p,i) ...: |
第二步
先从最简单的第二层到第一层的rkey逆向枚举开始。由于这两个值都是绝对值,有一个未知量Q的影响,所以需要先尽可能排除,正好我们有两个rkey,所以可以通过相比消除掉影响,这时数据被提升到第二层,但仍可进行枚举。
1 2 3 4 5 6 7 8 9 | In [ 56 ]: for i in tqdm(s): ...: for l in s: ...: for j in s: ...: for m in s: ...: if (i * * 2 * l + 7 * * 2 ) / (j * * 2 * m) = = k0 / k1: ...: print ((i,l),(j,m)) ...: 62 % |██████████████████████████▉ | 60 / 96 [ 00 : 24 < 00 : 14 , 2.47it / s]( 197 , 215 ) ( 208 , 214 ) 100 % |███████████████████████████████████████████| 96 / 96 [ 00 : 39 < 00 : 00 , 2.44it / s] |
于是处理出前两个和最后两个字符对应的值。由于得到了key和对应的rkey,所以原则上我们可以逆推出Q的值,但由于浮点精度受限,我们算出的Q有130bit的精度失准,这就堵死了我们通过整除逆向算法流程单可能性。
第三步
剩下的就是两个四层结构。注意到第四层是一个纯数学结构,我们可以先写出来:
$$abs(x-y)min(x,y)=m0,abs(x-z)min(x,z)=m1 $$
注意到均为正数,所以我们可以具体拆分为四种可能性:
$$(x-y)y=m0,(x-z)z=m1 $$,$$(y-x)x=m0,(x-z)z=m1 $$,
$$(x-y)y=m0,(z-x)x=m1 $$,$$(y-x)x=m0,(z-x)x=m1 $$,
观察四种情况,发现最后一种有公因子x,因而想到对m0和m1进行gcd,发现
1 2 | sage: gcd(m0,m1) 32 |
而由于三个数都在10**16数量级附近,所以很明显第四种情况错误。
对前三种情况求解,得到
$x=y+\dfrac{m0}{y},x=\dfrac{m1}{z}+z$
$y=x+\dfrac{m0}{x},x=\dfrac{m1}{z}+z$
$x=y+\dfrac{m0}{y},z=\dfrac{m1}{x}+x$
注意到m0m1是通过整数乘法得到,这时xyz必为相对应的因子,所以我们可以对m0m1进行因式分解,这样就得到了xyz的可能范围:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | sage: factor(m0) 2 ^ 6 * 3 ^ 3 * 19 * 19301 * 5651461 * 18765679 * 452548673 sage: factor(m1) 2 ^ 5 * 13 * 29 * 181 * 353 * 641 * 929 * 270532579 * 400359419 sage: m0f = [] ....: mtf = [ 2 , 3 , 19 , 19301 , 5651461 , 18765679 , 452548673 ] ....: for i in range ( 7 * 4 * 2 ^ 5 ): ....: k = bin (i)[ 2 :].zfill( 10 ) ....: l = [ int (k[: 3 ], 2 ), int (k[ 3 : 5 ], 2 ), int (k[ 5 ], 2 ), int (k[ 6 ], 2 ), int (k[ 7 ], 2 ), int ( ....: k[ 8 ], 2 ), int (k[ 9 ], 2 )] ....: tmp = 1 ....: for u,v in zip (mtf,l): ....: tmp * = u^v ....: m0f.append(tmp) ....: sage: m1f = [] ....: mtf = [ 2 , 13 , 29 , 181 , 353 , 641 , 929 , 270532579 , 400359419 ] ....: for i in range ( 6 * 2 ^ 8 ): ....: k = bin (i)[ 2 :].zfill( 11 ) ....: l = [ int (k[: 3 ], 2 ), int (k[ 3 ], 2 ), int (k[ 4 ], 2 ), int (k[ 5 ], 2 ), int (k[ 6 ], 2 ), int (k[ ....: 7 ], 2 ), int (k[ 8 ], 2 ), int (k[ 9 ], 2 ), int (k[ 10 ], 2 )] ....: tmp = 1 ....: for u,v in zip (mtf,l): ....: tmp * = u^v ....: m1f.append(tmp) ....: sage: len (m0f); len (m1f) 896 1536 |
因子个数都在2000以内,可枚举。
对第一种情况进行枚举,得到一组可行解;
1 2 3 4 5 6 7 8 9 10 | sage: xa = set () ....: for i in m0f: ....: xa| = {(m0 / i + i)} ....: sage: xb = set () ....: for i in m1f: ....: xb| = {(m1 / i + i)} ....: sage: xa&xb { 14109109473780244 } |
对另外两种情况进行枚举,没有合法解。
1 2 3 4 5 6 7 8 9 10 11 | sage: for y in m0f: ....: x = m0 / / y + y ....: if m1 % x = = 0 : ....: print (x) ....: sage: for z in m1f: ....: x = m1 / / z + z ....: if m0 % x = = 0 : ....: print (x) ....: sage: |
于是第四层逆向结束,计算这时对应的yz,由于其对称性,yz总有两解,这需要到第三层解决。
第四步
从第二层到第三层的逻辑主要是浮点数化整,由于精度问题,这步几乎是不可逆的,注意到题目已经进行了相对化处理,尽可能排除了Q的影响,所以与其逆向得到第二步,再尝试逆回去,不如直接一步到位,类比第一步逆回去。
定性分析虽如此,但毕竟Q的失准程度和浮点直接相除带来的误差并不好衡量,所以两种情况都进行一下枚举总是好的。此外,由于yz上一步中是多解,所以也都需要进行判断。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | In [ 63 ]: for i in tqdm(s): ...: for l in s: ...: for j in s: ...: for m in s: ...: if int (((Qi / (i * * 2 * l + 1 )) / (Qi / (j * * 2 * m + 36 ))) * 10 * * 16 ) = = x: ...: print ((i,l),(j,m)) ...: 54 % |███████████████████████▎ | 52 / 96 [ 00 : 34 < 00 : 28 , 1.53it / s] ( 189 , 224 ) ( 225 , 223 ) 100 % |███████████████████████████████████████████| 96 / 96 [ 01 : 02 < 00 : 00 , 1.53it / s] In [ 61 ]: for i in tqdm(s): ...: for l in s: ...: for j in s: ...: for m in s: ...: if int ((((i * * 2 * l + 25 )) / ((j * * 2 * m + 9 ))) * 10 * * 16 ) in {y,m0 / / y} or \ ...: int (((Qi / (j * * 2 * m + 9 )) / (Qi / (i * * 2 * l + 25 ))) * 10 * * 16 ) in {y,m0 / / y}: ...: print ((i,l),(j,m)) ...: 92 % |███████████████████████████████████████▍ | 88 / 96 [ 02 : 09 < 00 : 11 , 1.47s / it] ( 225 , 232 ) ( 227 , 199 ) 100 % |███████████████████████████████████████████| 96 / 96 [ 02 : 21 < 00 : 00 , 1.47s / it] In [ 58 ]: for i in tqdm(s): ...: for l in s: ...: for j in s: ...: for m in s: ...: if int ((((i * * 2 * l + 16 )) / ((j * * 2 * m + 4 ))) * 10 * * 16 ) in {z,m1 / / z} or \ ...: int (((Qi / (j * * 2 * m + 4 )) / (Qi / (i * * 2 * l + 16 ))) * 10 * * 16 ) in {z,m1 / / z}: ...: print ((i,l),(j,m)) ...: 53 % |██████████████████████▊ | 51 / 96 [ 01 : 16 < 01 : 06 , 1.49s / it] ( 188 , 221 ) ( 226 , 224 ) 100 % |███████████████████████████████████████████| 96 / 96 [ 02 : 24 < 00 : 00 , 1.51s / it] |
至此逆向了所有合法值。虽然有多解,但是本着数字可读性高于符号的原则,所以,逆向编码后优先得到数字字符,Serial:lrY1314cXy2920as。
题目总结
这个题之所以被定义为密码题,是因为与传统逆向题更重视处理流程相比,这个题在流程上无障碍,其主要考点在于数据信息的变换情况。流程上被刻意破坏/隐藏的环节其信息为了使程序能正常运行必须始终存在,但数据上的信息如果丢失就是丢失了,无法逆回去,除非可以通过其他方案消去其影响。而数据的丢失在计算机中无外乎以下几种情况:
- 数据丢弃,这样的情况是丢失了这个信息的全部,必须通过消去该变量取消其影响;
- 精度损失,在浮点下每一次乘除运算会明显带来数据的精度损失,虽然损失都是小量,但对于精密计算影响较大。精度的损失可以通过连续情况下的单调性逼近尽可能恢复;
- 有限域溢出,整数溢出等可以认为是特殊的有限域上的信息损失,这些损失只能通过数学方式处理。
在python中整数乘法原则上不会导致溢出,所以其整数乘法并没有完全损失相乘的两个数的信息,这两个数都是数学上可枚举的,只要实际规模属于可计算的情况,即可以在其他约束帮助下恢复。这也是本题的突破口。希望本题和本篇题解可以给大家带来一些新的思考。
PS.看雪啥时候支持公式输入啊,因为这事这一年都没用过看雪,推荐尽快完善QAQ。
[CTF入门培训]顶尖高校博士及硕士团队亲授《30小时教你玩转CTF》,视频+靶场+题目!助力进入CTF世界