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

在这场终局之战中，有近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