首页
论坛
课程
招聘
[原创] KCTF2022春季赛 第十一题 虫洞末世
2022-6-4 15:44 5887

[原创] KCTF2022春季赛 第十一题 虫洞末世

2022-6-4 15:44
5887

前言

第一次参与KCTF,毕竟难得遇到密码题可以试试身手。中间遇到了一些由于在之前其他密码题里的惯性思维带来的坑,但好在吹了个风及时冷静下来,最后拿到了三血,也算是个不错成绩。仅在此记录,希望还能启发其他师傅。

流程分析

本题只有两个主要函数,createkey和cheakkey。主流程里对输入的数据先进行createkey再进行cheakkey。

createkey

一个生成函数createkey,输入为一个字符串,正常输出为一个浮点数数组,异常输出为-1。合法输入长16,合法输入字符为可见字符;合法输出数组长为8。

 

具体流程分为四大步:

  1. 字符转整数,将非数字字符的ascii+100,将数字字符的ascii+175.这里导致了本题主要的多解:'0'和'{','1'和'|' ,'2'和'}' ,'3'和'~',这四组字符的映射值一致。所以这一步得到的是一个16长数组,每个位置共有94-4=90种合法状态。
  2. 数组压缩,将上一步得到的数组每连续两个整数通过
    1
    p=lists[2*i]**2*lists[2*i+1]+i**2
    压缩为一个新的数据,最终得到一个8长的整数数组k1,可以发现这个时候由于偶数位乘了两次,而奇数位只乘了一次,所以二者地位不均等,还有一个位置标记i也会影响会得到的结果,因而共有90*90*8种合法状态,但需要注意,在具体到每一位只有90*90种状态。同时维护一个k2数组,其是k1数组中对应元素的下一个奇数。本身并没有提供额外变量,主要是为下一步提供部分随机性。
  3. 维护控制变量Q。Q通过k2数组除去k2[3]外累乘初始化得到,然后根据Q是否整除于k1[j]为Q增加$$\Pi_{m=0}^{j-1}k1[m]$$ (j=0时则为1),直到Q整除于其中一个变量为止,并退出循环。如果这个循环的过程少于600000次则成功进入下一步,否则返回报错。

  4. 用Q去依次浮点除k1得到finalkey输出。

cheakkey

输入为一个八个浮点数的数组,输出是否正确。硬编码了四个比对变量,两个浮点rkey和两个整数rmode;还定义了一个变换方法doom,输入两个数,输出一个数,数学表达$doom(x,y)=min(x,y)*abs(x-y)$。

 

具体对比项目如下:

  1. 将输入的key[0]和key[-1]与两个浮点rkey对比,相等则通过;
  2. 取某两个剩下的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:142.47it/s](197, 215) (208, 214)
100%|███████████████████████████████████████████| 96/96 [00:39<00:002.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:281.53it/s]
 (189, 224) (225, 223)
100%|███████████████████████████████████████████| 96/96 [01:02<00:001.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:111.47s/it]
 (225, 232) (227, 199)
100%|███████████████████████████████████████████| 96/96 [02:21<00:001.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:061.49s/it]
 (188, 221) (226, 224)
100%|███████████████████████████████████████████| 96/96 [02:24<00:001.51s/it]

至此逆向了所有合法值。虽然有多解,但是本着数字可读性高于符号的原则,所以,逆向编码后优先得到数字字符,Serial:lrY1314cXy2920as。

题目总结

这个题之所以被定义为密码题,是因为与传统逆向题更重视处理流程相比,这个题在流程上无障碍,其主要考点在于数据信息的变换情况。流程上被刻意破坏/隐藏的环节其信息为了使程序能正常运行必须始终存在,但数据上的信息如果丢失就是丢失了,无法逆回去,除非可以通过其他方案消去其影响。而数据的丢失在计算机中无外乎以下几种情况:

  1. 数据丢弃,这样的情况是丢失了这个信息的全部,必须通过消去该变量取消其影响;
  2. 精度损失,在浮点下每一次乘除运算会明显带来数据的精度损失,虽然损失都是小量,但对于精密计算影响较大。精度的损失可以通过连续情况下的单调性逼近尽可能恢复;
  3. 有限域溢出,整数溢出等可以认为是特殊的有限域上的信息损失,这些损失只能通过数学方式处理。

在python中整数乘法原则上不会导致溢出,所以其整数乘法并没有完全损失相乘的两个数的信息,这两个数都是数学上可枚举的,只要实际规模属于可计算的情况,即可以在其他约束帮助下恢复。这也是本题的突破口。希望本题和本篇题解可以给大家带来一些新的思考。
PS.看雪啥时候支持公式输入啊,因为这事这一年都没用过看雪,推荐尽快完善QAQ。


看雪招聘平台创建简历并且简历完整度达到90%及以上可获得500看雪币~

收藏
点赞4
打赏
分享
最新回复 (0)
游客
登录 | 注册 方可回帖
返回