-
-
[推荐]看雪·安恒 2020 KCTF 春季赛 | 十二题设计思路及解析
-
发表于: 2020-5-18 17:40
-
在比赛过程中，本场的黑马战队横空出世，在非洲看雪战队的gannicusx凭借十二题《白云苍狗》的一血，从三百多支队伍中脱颖而出，虽然此前该战队只攻破了签到题，但一出手就逆袭成功，挤进防守方总排行的前十。
金左手战队的ccfer顺利拿到Flag，带领战队登上攻击方排行榜首，可谓一荣俱荣！
出题团队简介
大龙猫是一只好可爱好大只的龙猫，兔斯基是大龙猫的爱犬。大龙猫最近痴迷于逻辑“细胞”，这个与非门写的RSA是一次好有趣的尝试呢～当然，照顾爱妻还是大龙猫的主业
设计思路
题目设计
本题的变体RSA算法是由与非门实现的！
亮点
使用与非门（and和not的连续组合）作为唯一算术指令实现幂运算取模（pow mod），算法部分甚至没有跳转。只有与非！（我认为这很艺术）
提供破解外星硬件的体验。笔者认为任何文明都离不开逻辑，飞碟残骸中的运算设备很可能有门结构哦~这是一种脱离了操作系统和指令集的更基础的真实！
本题的N由三个素数P1，P2，P3相乘得到。每个素数都只有3个字节，即小于等于0xFFFFFF（十进制1677215）。
可以瞬间因式分解。进而算出phi，再根据题目中公开的公钥E，算出私钥D，完成解密。
这个过程需要理解RSA的算法原理，三个素数生成的N对应的phi，算法上和标准RSA不同。但D的算法完全一致。
具体算法见“破解思路”部分。
本题的变体RSA运行了3次（由外层循环控制，算法的二进制长度几乎没有增加）。求解过程即求解密文对应的明文，再以明文为密文求其明文，再以明文为密文求其明文，得到最终的key。
本题将过小的输入的运算结果强行归0，这是为了防住一种捷径，具体也在“破解思路”中。
由于本题的变体RSA完全由与非门实现，也就是如下代码块的巨大阵列：
mov al, g_mem[J] mov ah, g_mem[K] and al, ah not al mov g_mem[I], al
是按照 Montgomery 算法由乘法封装为幂运算。
乘法则是由加法封装而成，是对数复杂度，举个例子，比如：
1011 * 1101 = 1011 * 1 +1011 * 100 + 1011 * 1000，加了11次，而不是1101次（这里的数都是二进制）
求模运算就是除法，不保留商，只保留余数。
11011 mod 101 = 111 mod 101 = 10（这里的数也都是二进制）
除法里包括了减法实现，和加法类似，不赘述。
尽管如此，本题的算法速度极快！
破解思路
算法部分
由程序逆向得到N和E。由于P1,P2,P3都很小，直接因式分解 N = P1*P2*P3
计算得到，phi = (P1 - 1)*(P2 - 1)*(P3 - 1)
用扩展欧几里得算法，求解 E*D + phi*F = 1 的整数解 (D, F)，则 D 即为私钥。（事实上这个方程的整数解构成一个序列，取其中一个 D，则 D + phi * 正整数 都是其解，都可作为私钥，我们可以取其最小正值）
我们考虑这样一个场景：一个RSA，假设E=3，我们发现密文是8，则明文是什么？
因为 8 = 2*2*2
为了防止攻防用小数字做加密尝试轻易获取算法的指数特征，进而直接判断为RSA。我做了两件事。
一是在计算过程中将过小的数字的运算结果强行置0，以后算什么都是0。
逆向部分（也就是获取 N 和 E 的部分）
由于代码都是与非门连接而成，分析自然从数据流（宏观的数据流和局部的连接关系）入手。
从整体上，按源操作数，目的操作数，看看与非的指令流，像加法和减法，都有明显的从低位到高位连续移动的特征。
到此处，先不去识别更高层次的结构。而是转向微观。既然按位运算的结构已经识别。就拿出其中一个单元来研究，即运算某一位时的代码块。
先定义一个概念。每一种运算中重复的计算单元，我们称之为“运算单元”。
比如，每一位加法代码都不长，且都有 xor，我们把这种“加法对单独一位的操作”涉及的代码叫“加法单元”。
“加法单元”很简单，就是 xor 操作和计算进位 carry 的操作。
类似，还有减法单元、数据移动单元、置位单元。就这几个单元。大规模重复的就是这四种运算单元。复杂度都很低。
not x = x nand x （此处和下文中 not 皆指由一个 nand 实现的 not 门，而不代表汇编 not 指令）
x and y = not (x nand y)
识别xor难度要大一些，我的实现方法是由四个nand来实现，（我认为无法化简成更短）
x = y nand z
t = x nand y
x = x nand z
x = x nand t
xor 是加法识别的关键！识别了 xor 就可以分析出运算单元的结构和总体的运算功能，从而识别出“加法单元”。
xor 运算不像其它运算那么明显，但有四种方法可以识别。
识别 xor 的方法有：
第一种是，在运算单元中使用真值表。运算单元很短，从中节选一些片段做做真值表，容易识别 xor 逻辑。
第二种是，在加法单元内，先把已识别的 and, not, or 之类通通标准，对剩下的部分进行分析，列算式和真值表都可以识别 xor。
第三种是，自己尝试实现 xor，并力求简短，那么尽管运算顺序实现的和我有出入，却可以得到不包含可合并为 and 和 not 的代码块的 4 个连续 nand 的结构。以此为特征来识别。
第四种是，对运算单元使用整体真值表，然后得出整体功能，按需拆解。（因为整体功能都识别了，没有必要一定要识别哪里是 xor，当然，分析出来对于后续分析还是有帮助的）
加减法每块初始时的源操作数和目的操作数，在块际上（就是连续的块之间），乘法（除法）分别由由低位到高位（从高位到低位）的特征。
这样就识别出了乘法、取模。
乘法，取模，这类运算之间还有数据移动的整体操作。
置位模块相对零散，但结构特别简单。
看乘法模块怎么组合的，就知道了 E。
解析过程
一、女装游戏开始了
int sub_A7E490()
{
int result; // eax
signed int v1; // [esp+0h] [ebp-8h]
signed int v2; // [esp+0h] [ebp-8h]
signed int i; // [esp+4h] [ebp-4h]
v1 = sub_401000();
if ( v1 )
{
for ( i = 0; i < 3; ++i )
sub_4013E0(v1);
v2 = sub_401220();
if ( v2 == 1 )
sub_A808A2("You Win! You are very clever!");
else
sub_A808A2("Game Over");
sub_A807EB(v2);
result = 0;
}
else
{
sub_A808A2("Game Over");
sub_A807EB(0);
result = 0;
}
return result;
}输入转成72位的全局变量A919DF处，经过sub_4013E0运算，输出也从这里返回。
比较结果的地方在这里：
00401398 0FB691 DF19A900 MOVZX EDX,BYTE PTR DS:[ECX+A919DF] 0040139F 83E2 01 AND EDX,1 004013A2 8B45 A0 MOV EAX,DWORD PTR SS:[EBP-60] 004013A5 0FB64C05 B4 MOVZX ECX,BYTE PTR SS:[EBP+EAX-4C] 004013AA 3BD1 CMP EDX,ECX 004013AC 74 09 JE SHORT Totoro20.004013B7 先把KCTF对应的结果抓出来备用： 00 00 01 00 01 00 01 00 01 00 01 01 01 01 01 00 00 00 00 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
sub_4013E0里面非常长，清一色的与非门操作，一共是340181个与非门。
这么大规模的与非门化简，是准备要玩点技术了，经过两天奋战，发现实力它不允许啊，得到的还是10几万行操作。
二、换成没有技术的战术
输入输出在A919DF，与非门操作的数据从A918B8开始：
先从sub_4013E0入口开始玩，把A919DF处72字节改成: 01 01 01 00 00 ... 在A919DF下个硬件内存写断点，运行第一次断下来： 005F8BE2 A2 DF19A900 MOV BYTE PTR DS:[A919DF],AL 005F8BE7 A0 DF19A900 MOV AL,BYTE PTR DS:[A919DF] 005F8BEC 8A25 DF19A900 MOV AH,BYTE PTR DS:[A919DF] 005F8BF2 22C4 AND AL,AH 005F8BF4 F6D0 NOT AL 005F8BF6 A2 DF19A900 MOV BYTE PTR DS:[A919DF],AL 005F8BFB A0 E019A900 MOV AL,BYTE PTR DS:[A919E0] 观察A918B8： 01 00 00 00 01 01 00 00 ... ...
多试几个不同的情况，发现A918B8处刚好是输入的平方，sub_4013E0已经跑过了大概四分之一，这四分之一的操作只是个平方x*x，那整个操作估计也就4步运算。
然后发现输出总是0，感觉有什么问题，可能输入被改小了，被检查到了。
反正已经知道一步操作是平方了，用公开的一组正常key，等到第二次写断点的时候差不多函数要结束了。
所以取消A919DF的硬件写断点，在前面得到的5F8BFB处下个int3断点，断下来后在A919DF设置成硬件读取断点。
把A918B8的144位乘法结果全清0，改成小点的数方便观察。
运行在这里断下来：
00740513 A0 DF19A900 MOV AL,BYTE PTR DS:[A919DF] 00740518 8A25 281AA900 MOV AH,BYTE PTR DS:[A91A28] 0074051E 22C4 AND AL,AH 00740520 F6D0 NOT AL 00740522 A2 4819A900 MOV BYTE PTR DS:[A91948],AL
看进度又推进了大约四分之一，并发现A918B8处的结果一直没有变化，直到前一步把A918B8处的144位乘法结果改成后72位不是0的时候结果才会发生剧烈变化。
这是什么算法？乘法后还要可逆，首先想到的是取模，并且符合小于模的数输出不变，超过模以后会剧烈变化。
再重来一下推算这个模n，A918B8处前72位全填0，第73位填1，后面全0。
得到：
01 00 01 00 00 01 01 01 01 00 00 01 00 01 01 01 01 00 01 00 01 01 00 00 00 00 01 01 01 01 00 01 00 01 01 00 00 00 01 01 00 00 01 00 01 01 00 00 01 01 00 00 00 00 00 01 01 00 00 00 00 00 01 01 01 00 01 00 01 00 00 00 这样用2的72次方减去它得到模n（实际就是把上面一行取反加1）： 01 01 00 01 01 00 00 00 00 01 01 00 01 00 00 00 00 01 00 01 00 00 01 01 01 01 00 00 00 00 01 00 01 00 00 01 01 01 00 00 01 01 00 01 00 00 01 01 00 00 01 01 01 01 01 00 00 01 01 01 01 01 00 00 00 01 00 01 00 01 01 01
最终得到运算关系：
y = xxx % n
n=0xEA3E7CCB3943CA161B
y=0x87D54
得到：4A3A9740B735704562
[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课
|
|
|---|---|
