团队名称：兔斯基保护协会

参赛题目：见附件，是题目exe和按照Windows Crackme规则2要求提供的公开“用户名-序列号”
题目答案：
2D3FE4FB28EC609C4B7090BB9451CF85

题目设计和详细的破解方法：

本题采用规则二，且不涉及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转化为矩阵计算，再加上随机化，逆向难度大幅增加，是一个可以实用的软件保护方案（缺点是代码大）

祝大家玩的开心！

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课