首页
论坛
课程
招聘

看雪·深信服 2021 KCTF 春季赛 | 第十题设计思路及解析

2021-05-31 16:42


跟随武林少侠“飞停”,一路闯荡江湖,终于来到终点。

在这场终局之战中,有近1700人围观,历时3天,只有一支战队——金左手,挑战成功!

究竟是什么样的赛题难倒了大家呢?



出题团队简介简介:


大龙猫超大只,兔斯基毛茸茸。兔斯基保护协会光杆司令大龙猫是一只软件保护和逆向爱好者龙猫,爱做难题也爱出难题的格子衫程序员。团队价值观是,友谊第一,趣味至上!大龙猫会继续萌力创作,给大家带来更多有趣的赛题,用快乐和理性致敬大自然!


专家点评

金左手 战队队长 ccfer 点评:


程序核心是一个数字逻辑电路的矩阵运算,难点在于对输入三元组做了个非线性映射,并对映射关系做了逻辑膨胀化处理,使得代码量大幅增加,分析路径变长。解题时需要正确识别出每个逻辑单元,对两种功能单元做出逻辑化简,输入三元组的逆映射可以通过真值表解决,然后从三元组映射输出端来看就是个简单的线性变换了,解方程组即可。


赛题设计思路

本题采用规则二,且不涉及VM。

 

在本文中,
+表示异或,提到“加”说的也是异或。
“乘”表示“与”,AB表示A乘以B,即A&B.
!表示非,有最高的运算优先级(仅低于取下标)
^表示幂。
*表示矩阵乘法时,矩阵元素的加法是异或

 

SOP (sum of products),这个大一计算机知识是本题的核心。


考虑逻辑门RGX(Reversible Gate X,这是本题自己命名的,基于经典的逻辑门RUG)。ABC是输入,PQR是输出,RGX是这样的:(就是RUG的PQ互换)
P=AB+!A!C
Q=AB+BC+CA
R=B!C+!BC
这个门的描述是SOP形式(non-canonical SOP),从ABC到PQR是双射。

 

Q=AB+BC+CA=(ABC + AB!C) + (ABC + !ABC) + (ABC+A!BC) = ABC + !ABC + A!BC+ AB!C


即 Q=non-cannonical SOP = 展开 = 合并同类项 = cannonical SOP,这个过程很重要。

 

Q=ABC + !ABC + A!BC+ AB!C,每项Product对应Q=1时的一个解,依次对应四个解是ABC={111,011,101,110},如果Q=0则解集是其补集。


根据P和R的值求得相应解集,解集求交即为解。对于可逆电路,有且只有唯一解。


有能存储的下的cannonical SOP的时候,求解极为简单。只有 non-canonical SOP 时,除一些特殊情况外,求解过程等价于求cannonical SOP。


对于非局域化可逆电路,cannonical SOP和真值表都是同等量级的,暴力方法在工程上不可用,这就是本题的难度原理。

 

可以用cannonical SOP求解PGX的逆运算,求得的逆运算InvRGX为:
P=!A!B!C+AB!C+BC
Q=B!C+AC
R=B!C+!AC
当然,这样小规模,也可以用真值表求得

 

当输入很多的时候,展开的复杂度是很高的,对于“不可局域化”(不能拆分成两个门的并联)且“Product因子数很少”的时候,


从non-cannonical SOP 到 cannonical SOP 的计算量很大。


当“Product因子数只有一个的时候”,SOP等价于矩阵乘法,求解简单。

 

本题通过两层计算构建“输入很多,为126”且“非局域化”(可以局域化但需要技巧)且“Product因子数很少”的SOP,这种构造使得对SOP的逆向难度适中。

 

本题采用先并联3输入3输出RGX门,再乘以可逆矩阵M,获取这样的126输入126输出大规模SOP。

 

RGX是SOP形式,矩阵乘法是SOP形式(矩阵乘法的P只有一个因子)


两层SOP的计算结果是一层SOP,多少层SOP的计算结果都是一层SOP


先RGX并联再矩阵乘法,得到一层non-cannonical SOP

 

这是本题核心模块,叫K吧(Kernel)
C=K(P) = M*RGX(P)

 

逆运算:
P=InvK(C)=InvRGX(InvM*C)
其中InvM是M的逆矩阵,RGX函数是RGX门的大规模并联,InvRGX是InvRGX门的大规模并联。

 

InvRGX上文已经求得了,现在说说如何求得InvM,也就是如何逆向出M,求逆矩阵谁都会嘛。

 

对于某一位输出output,如果对应的矩阵的M的行为全1,那么,
output=P[0]+Q[0]+R[0]+P[1]+Q[1]+R[1]+...+P[41]+Q[41]+R[41]=3341项Products,其中P[i]Q[i]R[i]是第i组RGX的PQR输出。


根据程序中Products的缺失情况,可以得到M的这一行哪些元素为0。


对每一个输出位做这个判断,直接得出M的每一行。

 

如果我把顺序打乱,那么会更不明显,更不容易还原,但我没有这样做。不想让题在这个步骤太难。

 

另外,SOP的问题还有一个,就是有些对于某些输出数值,特解特别好找。


所以,我要让破解者真正逆向出算法,或者至少找到十几个解,以避免因为碰到特解好找而太过简单。

 

方法就是,我用Kernel代替了AES算法的AddRoundKey过程!


这个AES除了AddRoundKey被替换之外,完全没有改其它,边界明显。

 

1、非局域化
2、合适的Products因子数
3、不是求单一特解
这三个条件的题目难度的必要条件,算一个难点。而且有些简单。

 

增加点料,两个难点更适合。
我要掩饰一下SOP
AB=!A<B
A+B=!(!A!B)


用这个把一部分“与”和“异或”变成了“<”参与的运算,这样就行了!


这个变化不是看起来那么雕虫小技,而是利用了编译器不优化时,对<运算的处理。


编译结果没有复杂多少,膨胀比例等同于真实的编码比例,但是,乍一看,长得像VM。利用长得像,哈哈哈哈!本题就是这样简洁!

 

为了拉票,我介绍一下本题的潜力:


本题,我本质上实现了一个大规模NC1电路,而这个电路,可以用MBP转化为矩阵计算,再加上随机化,逆向难度大幅增加,是一个可以实用的软件保护方案(缺点是代码大)

 

祝大家玩的开心!



赛题解析

本赛题解析由看雪论坛 ccfer 给出:


完整解析文章看这里:https://bbs.pediy.com/thread-267878.htm



往期解析


1. 看雪·深信服 2021 KCTF 春季赛 | 第二题设计思路及解析

2. 看雪·深信服 2021 KCTF 春季赛 | 第三题设计思路及解析

3. 看雪·深信服 2021 KCTF 春季赛 | 第四题设计思路及解析

4. 看雪·深信服 2021 KCTF 春季赛 | 第五题设计思路及解析

5. 看雪·深信服 2021 KCTF 春季赛 | 第六题设计思路及解析

6. 看雪·深信服 2021 KCTF 春季赛 | 第七题设计思路及解析

7. 看雪·深信服 2021 KCTF 春季赛 | 第八题设计思路及解析

8. 看雪·深信服 2021 KCTF 春季赛 | 第九题设计思路及解析



主办方


看雪CTF(简称KCTF)是圈内知名度最高的技术竞技之一,从原CrackMe攻防大赛中发展而来,采取线上PK的方式,规则设置严格周全,题目涵盖Windows、Android、iOS、Pwn、智能设备、Web等众多领域。


看雪CTF比赛历史悠久、影响广泛。自2007年以来,看雪已经举办十多个比赛,与包括金山、360、腾讯、阿里等在内的各大公司共同合作举办赛事。比赛吸引了国内一大批安全人士的广泛关注,历年来CTF中人才辈出,汇聚了来自国内众多安全人才,高手对决,精彩异常,成为安全圈的一次比赛盛宴,突出了看雪论坛复合型人才多的优势,成为企业挑选人才的重要途径,在社会安全事业发展中产生了巨大的影响力。


合作伙伴


图片


深信服科技股份有限公司成立于2000年,是一家专注于企业级安全、云计算及基础架构的产品和服务供应商,致力于让用户的IT更简单、更安全、更有价值。目前深信服在全球设有50余个分支机构,员工规模超过7000名。



公众号ID:ikanxue

官方微博:看雪安全

商务合作:wsc@kanxue.com



声明:该文观点仅代表作者本人,转载请注明来自看雪专栏
最新评论 (0)
登录后即可评论