出题团队简介简介：
专家点评
金左手 战队队长 ccfer 点评：
赛题设计思路
+表示异或，提到“加”说的也是异或。
“乘”表示“与”，AB表示A乘以B，即A&B.
!表示非，有最高的运算优先级（仅低于取下标）
^表示幂。
*表示矩阵乘法时，矩阵元素的加法是异或
考虑逻辑门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=non-cannonical SOP = 展开 = 合并同类项 = cannonical SOP，这个过程很重要。
根据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
当然，这样小规模，也可以用真值表求得
从non-cannonical SOP 到 cannonical SOP 的计算量很大。
当“Product因子数只有一个的时候”，SOP等价于矩阵乘法，求解简单。
两层SOP的计算结果是一层SOP，多少层SOP的计算结果都是一层SOP
先RGX并联再矩阵乘法，得到一层non-cannonical SOP
C=K(P) = M*RGX(P)
逆运算：
P=InvK(C)=InvRGX(InvM*C)
其中InvM是M的逆矩阵，RGX函数是RGX门的大规模并联，InvRGX是InvRGX门的大规模并联。
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的每一行。
所以，我要让破解者真正逆向出算法，或者至少找到十几个解，以避免因为碰到特解好找而太过简单。
这个AES除了AddRoundKey被替换之外，完全没有改其它，边界明显。
1、非局域化
2、合适的Products因子数
3、不是求单一特解
这三个条件的题目难度的必要条件，算一个难点。而且有些简单。
我要掩饰一下SOP
AB=!A<B
A+B=!(!A!B)
这个变化不是看起来那么雕虫小技，而是利用了编译器不优化时，对<运算的处理。
编译结果没有复杂多少，膨胀比例等同于真实的编码比例，但是，乍一看，长得像VM。利用长得像，哈哈哈哈！本题就是这样简洁！
本题，我本质上实现了一个大规模NC1电路，而这个电路，可以用MBP转化为矩阵计算，再加上随机化，逆向难度大幅增加，是一个可以实用的软件保护方案（缺点是代码大）
赛题解析
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
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
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
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)
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
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
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
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
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)
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
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
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)
0 0 0 ：1 0 00 0 1 ：0 0 10 1 0 ：0 1 10 1 1 ：1 0 11 0 0 ：0 0 01 0 1 ：0 1 01 1 0 ；1 1 11 1 1 ：1 1 0
往期解析
1. 看雪·深信服 2021 KCTF 春季赛 | 第二题设计思路及解析
新思路奖
长按二维码前往投票
最受欢迎战队奖
长按二维码前往投票
投票时间：5月31日 12:00 ～6月7日 12:00
评选方式：登陆看雪账号，并为喜欢的战队投票，每支战队可投一票。
奖励：
球分享
球点赞
球在看
本文始发于微信公众号（看雪学院）：看雪·深信服 2021 KCTF 春季赛 | 第十题设计思路及解析
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论