[KCTF2021]第十题 一统江湖 WriteUp

龙猫变换 黑盒解法

一，    分析篇

a)      程序整体流程很简单，如图：

大致流程就是，key做一个变换（Aes256Encrypt，随手写的名字，其实不是），跟name比较一下，相等则成功。

Name需要扩展到16字节：

Key由16进制字符串转成字节码

Aes256Encrypt，跟https://github.com/kokke/tiny-AES-c/blob/master/aes.c，里面的Cipher结构一模一样。

只是AddRoundKey不一样而已,AddRoundKey做了一点点事情，见下图

b)      一个让IDA死掉的函数

里面有大约2.5M的汇编代码。至于是啥，完全不知道。

c)      所以结论：完全不想逆401610这个函数。

二，    猜想篇

还好，401610里面没有anti，写个程序调用一下（这里为了方便，直接调用上面的AddRoundKey函数（因为进出都是16字节）

我们输入 00000000000000000000000000000000

发现输出了6DE448F7A5202570F7283A8BF98BCC63

然后输入了00000000000000000000000000000001

发现输出了EFD30F8DCF306277DEDA00D2E7F06DC4

然后输入了80000000000000000000000000000000

发现输出了CDF38AF72C4C18072CD8D383C7599A74

然后输入了80000000000000000000000000000001

发现输出了4FC4CD8D465C5F00052AE9DAD9223BD3

然后发现 6DE448F7A5202570F7283A8BF98BCC63 xor EFD30F8DCF306277DEDA00D2E7F06DC4 xor CDF38AF72C4C18072CD8D383C7599A74 = 4FC4CD8D465C5F00052AE9DAD9223BD3

看上去就是一个巧合！！

逆不了题目，我们靠猜来弥补：

首先我们假设作者的这个函数是可逆的（一定可逆），而且没有多解！！！（有多解可以看到女装照）

所以，我们假设作者这个AddRoundKey里面设置了128个向量表和一个基础0号向量base（6DE448F7A5202570F7283A8BF98BCC63），按照输入的bit位是否为1，决定了是否异或向量表中的这一项。换句话说，就是128个向量的叠加（有限域2的世界里面，加法就是异或运算）。

即 Y = A*x + B。A是128向量矩阵，B是base向量，x是输入，Y是输出。

然后调用exe里面的AddRoundKey把这128个向量(输出结果要异或一下base向量)给抓出来（不列举了）：

然而很快就被打脸了！！

按照上面的猜想 “00000000000000000000000000000001” 与 “00000000000000000000000000000002” 输出叠加后应该是“00000000000000000000000000000003”的输出，结果却等于了“00000000000000000000000000000004”的输出，恰好等于我们的2号向量（1 <<2）

不仅这一组，我们发现，还有很多组都是这样的。写个程序，跑一下我们的iv表，得出例外（3个向量异或值为全0），这样一共有42组（下图）：也就是说，我们的向量表，实际上不能生成叠加后的任意值，不是线性无关的128个向量。一共42组，每组3个，覆盖了126bit。

每个bit，只出现了一次，没有重叠！没有重叠！没有重叠！重要的事情说三遍，如果重叠了，直接就放弃了！

基于我们大概率看不到女装照，所以应该想办法把向量弄成线性无关的。

我们继续靠猜想来弥补：

观察0，1，2这组，其实是 1，2，4bit位的向量值

按我们上面的猜想理论，1和2应该是叠加成3的输出，结果却出现了4，如果3和4的输入，在叠加向量前被交换了呢？那结果不就符合实验数据了吗？1，2，4bit，可以组成8个数，除了0以外，还有7个数字。调用exe的函数，穷举一下：

不难发现，3和4交换后，用1，2，4向量就可以生成其他所有输出，然后细节处还发现了，6和7 也被交换了！！这7个向量中，找出任意3个线性不相关的向量，就可以生成出其他4个，为了简便运算，我们直接固定1，2，强行交换3和4，这样，7个都能生成出来了，然后再判断一下，5，6，7是否被交换过（只可能交换一次）。

这样，我们抓出线性不相关的128个向量表，以及交换表（3和4强制交换）：

三，    解题篇

核心猜想：作者设计的算法，可逆！无多解！

总结一下思路：

函数的输入128bit，输出128bit，由于可逆，无多解，我们可以函数的一个完全等价体是：有一张超级大的映射表，对于每一个输入，都有唯一的输出，映射表的有2^128行，这个完全不可能存下来，所以，我们在这个表里面，找出128+1个线性无关的向量（那一个是全0的输出，我们称为base，设为B），列出一个128bit矩阵的表达式：

Y = A*x + B

其中，B是常量，Y是输出，x是输入，A是128个向量的矩阵

逆向运算，就是在已知Y的情况下，求x。这样可以展开成128元一次方程组。方程组中，每个数都是2进制的。

由于依次对128bit设置为1，看输出，发现有42组的3bit生成的向量和为0，说明2^128的向量表有些项被交换过了。

所以，这个AddRoundKey过程，可以用这样的算法来描述：

那么逆运算就是：

四，    代码篇

首先把Aes256框架抄过来：

https://github.com/kokke/tiny-AES-c/blob/master/aes.c

然后F5掉几个函数

由于exe带重定位，因此我们直接调用401610函数

然后，抓出128 + 1个向量

处理交换表，并修复向量表

然后打印出来，作为预加载部分代码：

以后就调用preload就行了，就是上面超长的函数

写出逆向的AddRoundKey：

然后Aes框架抄一下：换成我们改好的InvAddRoundKey

最后kg，结束

代码，在vs2017中编译通过。

五，    鸣谢

大龙猫（作者）

看场雪（看雪密码学版主）

还有几位科锐的学生

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