感谢 zejax （微信号：zej***）的投稿
我们使用Feistel结构设计了一个整型上的密码，并附有编译后的程序。该算
法把数字(a,b)在密钥k的前提下变成另外的数字(c,d)。现在请你编写解密算法，把下面的(c,d)变回(a,b)：
860103762,1574863430。flag的形式：CTF{a,b}
这是一道逆向工程题，所谓逆向工程，就是已知编译后的程序（.exe），反推出程序运行方式（源代码）。首先要指出的一点是，这个程序运行时会闪退，没有任何输入输出，因为出题人根本就没写输入输出语句，因此非进行逆向工程不可。
此时，或许我们首先应该去搜索一下，什么叫作Feistel结构？不难搜到这张图：
左侧由上而下是加密算法，右侧由上而下是解密算法，K代表密钥，F代表一个函数，圈中十字那个符号代表异或（XOR）运算，在C语言中对应的运算符是^。
可以看出，Feistel结构的加密算法首先需要一组密钥（K0～Kn），一个函数（F）。它将输入的原文分为两个部分，暂且称为L和R，不断重复以下过程：
- 将R和K进行F运算，得到的结果再和L做异或运算，得到的结果成为下一轮的R；
- R直接成为下一轮的L。
- 例外：最后一轮后不交换L和R。
解密过程完全相同，只不过把K全都反过来了，先用Kn，最后用K0。于是，确定算法的K和F就是我们接下来的目标。
逆向工程用什么工具好呢？在网上稍作搜索，很容易发现一款叫作IDA的软件被称为神器，因为它包含一个Hex Rays插件——能产生C语言源代码（当然可读性肯定还是比不上真正的源代码），而不像别的反汇编工具只能产生汇编语言源代码。对于新手和初学者，当然是C语言比较容易读懂了。我们下载、安装并使用IDA处理这个程序，如图导出全部C源代码：
这里插一句：即使源代码只有main一个函数，编译时编译器也会加上很多东西，这导致反编译出的代码中有一大堆搞不懂在干什么的函数。不过不用管它们，我们快速的寻找可能是加密算法的程序段——加密算法含有异或运算，所以直接在代码中搜索^符号应该就能找到它。可以注意到这一段程序最为可疑，它不调用别的奇奇怪怪的函数，还包含一些不知道代表什么的常数，并且大量使用异或运算（多到我不换行就没法把那一行放在这个页面中了），这很像加密过程：
int sub_401500()
{
signed int v0; // ebx@1
int v1; // esi@2
int v2; // ecx@2
signed int v4; // [sp+14h] [bp-18h]@1
int v5; // [sp+18h] [bp-14h]@0
int v6; // [sp+1Ch] [bp-10h]@0
sub_401F10();
v4 = 0;
v0 = 225052;
while ( v4 <= 15 )
{
v1 = v6;
v2 = ((v0 + v6) << 8)
^ v6
^ 2 * v0
^ (v6 << (v0 + 8))
^ v0 * (v6 + 4)
^ (25998 * v6 + 174 * v0)
^ v5;
if ( v4 % 3 == 1 )
v0 = __ROL4__(v0, 1);
else
v0 = __ROL4__(v0, 2);
v6 = v2;
v5 = v1;
++v4;
}
return 0;
}中间调用的sub_401F10经过检查后可以发现并没什么值得注意的，就忽略吧。我们接下来的任务是搞清楚v0、v1、v2、v4、v5、v6都是存储什么的。很容易看出v4是从0到15的循环变量，我们命名为i。观察v2=…那一段，可以发现是v0和v6先进行了复杂运算，结果再与v5进行异或运算，结果存入v2，最终又存入v6。因此有理由推测v5是L，v0是K，v6是R，v2是一个临时存储R的新值的变量，那一大段运算是F。另外，v1是一个临时存储L的旧值的变量。
等等，不是说K有很多个，应该是16轮计算中K各不相同吗？怎么成了v0呢？请看，在循环的后面，有一个动作是v0 = __ROL4__(v0, 1);或v0 = __ROL4__(v0, 2);。上网搜索可知，__ROL4__代表“向左循环移位”，这就是在旧的v0的基础上产生出一个新的v0给下一轮用啊！而且，v4是否为3的整数倍，决定了新的v0是怎么产生的。我们可以使用下面这段程序得到全部16轮使用的K：
void getKs(int K[16])
{
int i, v0 = 225052;
for(i = 0; i < 16; i++)
{
K[i] = v0;
if ( i % 3 == 1 )
v0 = __ROL4__(v0, 1);
else
v0 = __ROL4__(v0, 2);
}
}其中的__ROL4__的算法如下：
int __ROL4__(unsigned int v, int n)
{ return (v << n) | (v >> (32 - n)); }而F也很容易写出：
int F(int R, int K)
{
return ((K + R) << 8)
^ R
^ 2 * K
^ (R << (K + 8))
^ K * (R + 4)
^ (25998 * R + 174 * K);
}综上所述，对变量名进行修改，对程序进行简化后，加密过程其实就是：
void Encrypt()
{
int K[16], t, i, L, R;
getKs(K);
for(i = 0; i < 16; i++)
{
t = R;
R = F(R, K[i]) ^ L;
L = t;
}
}把K反过来使用，得解密过程：
void Decrypt()
{
int K[16], t, i, L, R;
getKs(K);
for(i = 0; i < 16; i++)
{
t = R;
R = F(R, K[15 - i]) ^ L;
L = t;
}
}为L和R赋初始值2和1（顺序是试出来的，以上程序都没有考虑结束时是否交换一次L和R的问题，所以可能要用不同的顺序多试试），运行加密过程并打印结束时的L和R，可以确认我们的程序是正确的。为L和R分别赋初始值860103762和1574863430，运行解密过程，便得到答案。
另一种解法：暴力破解……虽然极不推荐，但有人居然成功了，出于神人共欣赏的考虑，将他的解法也收录于此……
首先，为什么说不推荐呢？因为a和b都是int型整数，合起来可能的解有18446744073709551616种，若检验一个解的时间是1纳秒（事实上一般CPU1纳秒只能执行几条指令），那么需要585年才能穷举完所有解。但是！在有人劝说别人放弃暴力破解的尝试时，他无意间说“答案都是六位数”，暴露了这道题答案数字小的缺陷。如果已知a和b都是六位正整数，解就只有810000000000种了，每个解花10纳秒，只需要2.25小时就能穷举完。这使得@Core i5 2nd Generation 同学用一上午暴力破解跑出了答案！（注：他当然不能不断尝试在网站上提交，那样太慢了。他是写了个main，不断调用逆向工程得到的那个加密函数，在本地进行破解的。并且他将解分为了7部分，同时开7个程序各占一个线程进行尝试）
Flag:
支付宝二维码：
支付宝扫一扫
微信扫一扫
逆向
逆向我来啦