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

  • A+
所属分类:逆向工程

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

跟随武林少侠“飞停”,一路闯荡江湖,终于来到终点。
在这场终局之战中,有近1700人围观,历时3天,只有一支战队——金左手,挑战成功!
看雪·深信服 2021 KCTF 春季赛 | 第十题设计思路及解析
究竟是什么样的赛题难倒了大家呢?


出题团队简介简介:


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

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



专家点评


金左手 战队队长 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 给出:

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



先找到验证点:
006CC088  PUSH KCTF2021.006E29C0           ; 输入的key006CC08D  CALL KCTF2021.006CC0F0           ; 解码006CC092  ADD ESP,4006CC095  PUSH 10006CC097  PUSH KCTF2021.006E28B8           ; name006CC09C  PUSH KCTF2021.006E29C0           ; 解码后的key006CC0A1  CALL KCTF2021.006CD1F0           ; 比较函数006CC0A6  ADD ESP,0C006CC0A9  TEST EAX,EAX006CC0AB  JNZ SHORT KCTF2021.006CC0CB006CC0AD  PUSH KCTF2021.006DC1D8           ; ASCII "Right! You are very clever!"006CC0B2  CALL KCTF2021.006D08D2

浏览一下解码函数6CC0F0,流程和aes算法类似:
006CC0F0  PUSH EBP006CC0F1  MOV EBP,ESP006CC0F3  PUSH ECX006CC0F4  MOV BYTE PTR SS:[EBP-1],0006CC0F8  MOV EAX,DWORD PTR SS:[EBP+8]006CC0FB  PUSH EAX006CC0FC  CALL KCTF2021.00401020           ; 龙猫变换006CC101  ADD ESP,4006CC104  MOV BYTE PTR SS:[EBP-1],1006CC108  JMP SHORT KCTF2021.006CC113006CC10A  MOV CL,BYTE PTR SS:[EBP-1]006CC10D  ADD CL,1006CC110  MOV BYTE PTR SS:[EBP-1],CL006CC113  MOV EDX,DWORD PTR SS:[EBP+8]006CC116  PUSH EDX006CC117  CALL KCTF2021.006CC600           ; 字节代换006CC11C  ADD ESP,4006CC11F  MOV EAX,DWORD PTR SS:[EBP+8]006CC122  PUSH EAX006CC123  CALL KCTF2021.006CC3D0           ; 行移位006CC128  ADD ESP,4006CC12B  MOVZX ECX,BYTE PTR SS:[EBP-1]006CC12F  CMP ECX,0E006CC132  JNZ SHORT KCTF2021.006CC136006CC134  JMP SHORT KCTF2021.006CC150006CC136  MOV EDX,DWORD PTR SS:[EBP+8]006CC139  PUSH EDX006CC13A  CALL KCTF2021.006CC160           ; 列混合006CC13F  ADD ESP,4006CC142  MOV EAX,DWORD PTR SS:[EBP+8]006CC145  PUSH EAX006CC146  CALL KCTF2021.00401020           ; 龙猫变换006CC14B  ADD ESP,4006CC14E  JMP SHORT KCTF2021.006CC10A006CC150  MOV ECX,DWORD PTR SS:[EBP+8]006CC153  PUSH ECX006CC154  CALL KCTF2021.00401020           ; 龙猫变换006CC159  ADD ESP,4006CC15C  MOV ESP,EBP006CC15E  POP EBP006CC15F  RETN

重点就是401020这个龙猫变换了,首先把16个BYTE转成128个bit,最后在超级长的函数401610里实现门电路逻辑阵列变换。

因为都是位运算,后面我不用~表示取反运算,而是用^1,因为取反会影响字节里其它7位。

代码还是很有规律的,先列举一下几种单元门:

单元门1:
00401651  MOV EAX,100401656  IMUL ECX,EAX,000401659  ADD ECX,DWORD PTR SS:[EBP+C]0040165C  MOVZX EDX,BYTE PTR DS:[ECX]0040165F  TEST EDX,EDX00401661  JNZ SHORT KCTF2021.0040166F00401663  MOV DWORD PTR SS:[EBP-A5C],10040166D  JMP SHORT KCTF2021.004016790040166F  MOV DWORD PTR SS:[EBP-A5C],0等价于:t = a ^ 1

单元门2:
00401679  MOV EAX,10040167E  SHL EAX,000401681  ADD EAX,DWORD PTR SS:[EBP+C]00401684  MOVZX ECX,BYTE PTR DS:[EAX]00401687  CMP DWORD PTR SS:[EBP-A5C],ECX0040168D  JGE SHORT KCTF2021.0040169B0040168F  MOV DWORD PTR SS:[EBP-A60],100401699  JMP SHORT KCTF2021.004016A50040169B  MOV DWORD PTR SS:[EBP-A60],0等价于:t = a & (b ^ 1)

单元门3:
004016CC  MOV ECX,1004016D1  IMUL EDX,ECX,0004016D4  ADD EDX,DWORD PTR SS:[EBP+C]004016D7  MOVZX EAX,BYTE PTR DS:[EDX]004016DA  CMP EAX,DWORD PTR SS:[EBP-A64]004016E0  JGE SHORT KCTF2021.004016EE004016E2  MOV DWORD PTR SS:[EBP-A68],1004016EC  JMP SHORT KCTF2021.004016F8004016EE  MOV DWORD PTR SS:[EBP-A68],0等价于:t = (a ^ 1) & b

单元门4:
004017C3  MOV EAX,DWORD PTR SS:[EBP-A74]004017C9  CMP EAX,DWORD PTR SS:[EBP-A7C]004017CF  JL SHORT KCTF2021.004017DD004017D1  MOV DWORD PTR SS:[EBP-A80],1004017DB  JMP SHORT KCTF2021.004017E7004017DD  MOV DWORD PTR SS:[EBP-A80],0等价于:t = ((a ^ 1) & b) ^ 1

单元门5:
00401A7D  MOV EDX,DWORD PTR SS:[EBP-AB0]00401A83  CMP EDX,DWORD PTR SS:[EBP-AB8]00401A89  JGE SHORT KCTF2021.00401A9700401A8B  MOV DWORD PTR SS:[EBP-ABC],100401A95  JMP SHORT KCTF2021.00401AA100401A97  MOV DWORD PTR SS:[EBP-ABC],0等价于:t = (a ^ 1) & b

单元门6:
00401805  MOVZX EAX,BYTE PTR SS:[EBP-1]00401809  MOVZX ECX,BYTE PTR SS:[EBP-2]0040180D  XOR EAX,ECX0040180F  MOV BYTE PTR SS:[EBP-1],AL等价于:t = t ^ a

单元门7:
00401FC8  MOV EAX,100401FCD  IMUL ECX,EAX,0A00401FD0  ADD ECX,DWORD PTR SS:[EBP+C]00401FD3  MOVZX EDX,BYTE PTR DS:[ECX]00401FD6  AND EDX,DWORD PTR SS:[EBP-B2C]00401FDC  MOV EAX,100401FE1  IMUL ECX,EAX,0B00401FE4  ADD ECX,DWORD PTR SS:[EBP+C]00401FE7  MOVZX EAX,BYTE PTR DS:[ECX]00401FEA  AND EAX,DWORD PTR SS:[EBP-B30]00401FF0  XOR EDX,EAX00401FF2  MOV BYTE PTR SS:[EBP-2],DL等价于:t = (a & b) ^ (c & d)

单元门8:
004027EB  MOV EDX,1004027F0  IMUL EAX,EDX,1F004027F3  ADD EAX,DWORD PTR SS:[EBP+C]004027F6  MOVZX ECX,BYTE PTR DS:[EAX]004027F9  MOV EDX,1004027FE  SHL EDX,500402801  ADD EDX,DWORD PTR SS:[EBP+C]00402804  MOVZX EAX,BYTE PTR DS:[EDX]00402807  AND ECX,EAX00402809  XOR ECX,DWORD PTR SS:[EBP-BE4]0040280F  MOV BYTE PTR SS:[EBP-2],CL等价于:t = (a & b) ^ c

然后由上面这些单元门组成两种复合型的功能门。

第1种功能门g1:
t1 = a ^ 1;t2 = b & (t1 ^ 1);t3 = c ^ 1;t4 = (a ^ 1) & t3;t5 = (t2 ^ 1) & t4;t6 = c ^ 1;t7 = (a ^ 1) & t6;t8 = a ^ 1;t9 = b & (t8 ^ 1);t10 = ((t7 ^ 1) & t9) ^ 1;t11 = ((t5 ^ 1) & t10) ^ 1;等价于:t = (a | c) ^ (a & b) ^ 1

第2种功能门g2:
t1 = a ^ 1;t2 = b & (t1 ^ 1);t3 = a ^ 1;t4 = c & (t3 ^ 1);t5 = (t2 ^ 1) & t4;t6 = a ^ 1;t7 = c & (t6 ^ 1);t8 = a ^ 1;t9 = b & (t8 ^ 1);t10 = ((t7 ^ 1) & t9) ^ 1;t11 = ((t5 ^ 1) & t10) ^ 1;t = (b & c) ^ t11;等价于:t = (a & b) ^ (b & c) ^ (c & a)

按照上述规则,进行一翻代换得到一万多行全是xor操作的代码。

把128位的输入,3位一组,一共42组,最后再单独补两位。

每组3位(a,b,c),选择变换或不变换,如果变换,则得到新的3位:g1(a,b,c), g2(a,b,c), b^c。

这里浪费了很多时间,开始一直没把b^c组合起来看待,那样的话是170个变量的非齐次方程组,各种尝试都解不出来。最后观察发现b和c从来都是成对出现的,这才决定组合起来看待。

全xor操作可以按128*128的矩阵解GF2的线性方程组。

然后这个g1(a,b,c), g2(a,b,c), b^c三位组还原到a,b,c我用真值表枚举了一下,刚好是一一映射,对应关系:

最后得到:
0 0 0 :1 0 0 0 0 1 :0 0 1 0 1 0 :0 1 1 0 1 1 :1 0 1 1 0 0 :0 0 0 1 0 1 :0 1 0 1 1 0 ;1 1 1 1 1 1 :1 1 0

KCTF:
2D3FE4FB28EC609C4B7090BB9451CF85

kg和整理后的龙猫变换函数,请前往此地址下载附件:
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 春季赛 | 第九题设计思路及解析



目前新思路奖、最受欢迎战队奖正在火热进行中!
快来为你喜欢的战队投票吧!


新思路奖


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

长按二维码前往投票



最受欢迎战队奖


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


长按二维码前往投票



投票时间:5月31日 12:00 ~6月7日 12:00

评选方式:登陆看雪账号,并为喜欢的战队投票,每支战队可投一票。

奖励

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


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



主办方

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

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

合作伙伴

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

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



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



看雪·深信服 2021 KCTF 春季赛 | 第十题设计思路及解析
公众号ID:ikanxue
官方微博:看雪安全
商务合作:[email protected]




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

球分享

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

球点赞

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

球在看



看雪·深信服 2021 KCTF 春季赛 | 第十题设计思路及解析
“阅读原文一起来充电吧!

本文始发于微信公众号(看雪学院):看雪·深信服 2021 KCTF 春季赛 | 第十题设计思路及解析

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: