[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矩阵的表达式：