感谢 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:
逆向
逆向我来啦