看雪2022 KCTF 春季赛 | 第11题设计思路及解析

WriteUp 2年前 (2022) admin
735 0 0
看雪 2022 KCTF春季赛 于5月10日中午12点正式开赛!

第11题《虫洞末世》已于昨日中午12点截止答题。经统计,7队成功提交flag。

看雪2022 KCTF 春季赛 | 第11题设计思路及解析


他们分别是:

看雪2022 KCTF 春季赛 | 第11题设计思路及解析

接下来和我一起来看看该赛题的设计思路和相关解析吧!



出题团队简介


第11题《虫洞末世》出题方 【一个人的浪漫】


看雪2022 KCTF 春季赛 | 第11题设计思路及解析


赛题设计思路


看雪2022 KCTF 春季赛 | 第11题设计思路及解析

参赛题目:ydmp <<原点磨盘>>

题目答案:lrY1314cXy2920as

 

现在终于发现怎么应用于加密了,原来的我总是因出题而自我限制自己。方法那就是在每一轮对每一个加数计次,并由总轮次减去某个数的加数次数。(称之为每个数的差省值),而到最后只需要开放差省值、总轮次和生成的大公倍数充当校验即可。


这时,磨盘本身就是解的对象,问题并未得到转移。但想到按这个方法出题又得重新设计,那就算了吧。

 

题目设计:

1.数字映射为对应ascii码+175,字符映射为对应ascii码+100(1.式)

 

2.1.式分两个一组,第一项的平方*第二项+项数的平方(2.式)(由于差异较大,保证了这一步无多解发生)

 

3.判断奇偶,奇数+2,偶数+1(3.式)

 

4.磨盘(用以生成一个不能确定的公倍数)
由在3.式项数同乘的基础上分别相加得到此基础上的2.式的公倍数(Q)(不是很规则)并由公倍数作除得到最终值。

 

5.检验
最终开放首末最终值和其中6项的两两比值的doom后的值作为效验

解题思路:

开放首末项意味着Q和这几位对应的二式可以求出,但是这里一直沿用的是浮点运算,尤其是后边有一段代号doom的函数专门扩大了浮点数产生的误差,所以要解的同时得进行误差分析。

 

最终由已知关系即可求出2.式的所有项,此时只需要求解出对应的编码再转换一下就解出来了。



赛题解析


本赛题解析由看雪论坛专家 Zuni-W 给出:

看雪2022 KCTF 春季赛 | 第11题设计思路及解析 


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


流程分析

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


createkey

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

 

具体流程分为四大步:

1、字符转整数,将非数字字符的ascii+100,将数字字符的ascii+175.这里导致了本题主要的多解:’0’和'{‘,’1’和’|’ ,’2’和’}’ ,’3’和’~’,这四组字符的映射值一致。所以这一步得到的是一个16长数组,每个位置共有94-4=90种合法状态。

2、数组压缩,将上一步得到的数组每连续两个整数通过

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)有较大误差,本身就带来了不可逆性,所以第一层到第二层,第二层到第三层必须要枚举;但是第三四层由于是先进行了整数处理,所以是精准数据,本身具有理论可逆性,但需要看数据规模观察是否可计算,看数据细节判断是否多解。


看雪2022 KCTF 春季赛 | 第11题设计思路及解析



解题流程


第一步:

在第一层进行初始化,将字符映射为整数,处理出第一层的合法数据集合s。

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,所以可以通过相比消除掉影响,这时数据被提升到第二层,但仍可进行枚举。

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,发现

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的可能范围:

sage: factor(m0)                                                               2^6 * 3^3 * 19 * 19301 * 5651461 * 18765679 * 452548673sage: factor(m1)                                                               2^5 * 13 * 29 * 181 * 353 * 641 * 929 * 270532579 * 400359419sage: 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)                                                        8961536


因子个数都在2000以内,可枚举。

 

对第一种情况进行枚举,得到一组可行解;

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}


对另外两种情况进行枚举,没有合法解。

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上一步中是多解,所以也都需要进行判断。

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。



题目总结


这个题之所以被定义为密码题,是因为与传统逆向题更重视处理流程相比,这个题在流程上无障碍,其主要考点在于数据信息的变换情况。


流程上被刻意破坏/隐藏的环节其信息为了使程序能正常运行必须始终存在,但数据上的信息如果丢失就是丢失了,无法逆回去,除非可以通过其他方案消去其影响。


而数据的丢失在计算机中无外乎以下几种情况:

  1. 数据丢弃,这样的情况是丢失了这个信息的全部,必须通过消去该变量取消其影响;

  2. 精度损失,在浮点下每一次乘除运算会明显带来数据的精度损失,虽然损失都是小量,但对于精密计算影响较大。精度的损失可以通过连续情况下的单调性逼近尽可能恢复;

  3. 有限域溢出,整数溢出等可以认为是特殊的有限域上的信息损失,这些损失只能通过数学方式处理。

在python中整数乘法原则上不会导致溢出,所以其整数乘法并没有完全损失相乘的两个数的信息,这两个数都是数学上可枚举的,只要实际规模属于可计算的情况,即可以在其他约束帮助下恢复。这也是本题的突破口。希望本题和本篇题解可以给大家带来一些新的思考。


 

看雪2022 KCTF 春季赛 | 第11题设计思路及解析

看雪2022 KCTF 春季赛 | 第11题设计思路及解析
本赛季最后一题

第12题《尊严之战》正在进行中

?还在等什么,快来参赛吧!


如何成为一名出色的CTF选手?
看雪2022 KCTF 春季赛 | 第11题设计思路及解析
看雪2022 KCTF 春季赛 | 第11题设计思路及解析
*点击图片查看详情

入门-基础-进阶-强化,只需四个阶段!摇身一变成为主力、中坚力量

看雪2022 KCTF 春季赛 | 第11题设计思路及解析



看雪2022 KCTF 春季赛 | 第11题设计思路及解析
– End –

看雪2022 KCTF 春季赛 | 第11题设计思路及解析


看雪2022 KCTF 春季赛 | 第11题设计思路及解析

球分享

看雪2022 KCTF 春季赛 | 第11题设计思路及解析

球点赞

看雪2022 KCTF 春季赛 | 第11题设计思路及解析

球在看



看雪2022 KCTF 春季赛 | 第11题设计思路及解析
“阅读原文展开第12题的战斗!

原文始发于微信公众号(看雪学苑):看雪2022 KCTF 春季赛 | 第11题设计思路及解析

版权声明:admin 发表于 2022年6月6日 下午6:01。
转载请注明:看雪2022 KCTF 春季赛 | 第11题设计思路及解析 | CTF导航

相关文章

暂无评论

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