感谢 zejax (微信号:zej***)的投稿

我们使用Feistel结构设计了一个整型上的密码,并附有编译后的程序。该算

法把数字(a,b)在密钥k的前提下变成另外的数字(c,d)。现在请你编写解密算法,把下面的(c,d)变回(a,b):

860103762,1574863430。flag的形式:CTF{a,b}

这是一道逆向工程题,所谓逆向工程,就是已知编译后的程序(.exe),反推出程序运行方式(源代码)。首先要指出的一点是,这个程序运行时会闪退,没有任何输入输出,因为出题人根本就没写输入输出语句,因此非进行逆向工程不可。

此时,或许我们首先应该去搜索一下,什么叫作Feistel结构?不难搜到这张图:

西普CTF-流水线-以夕阳落款

左侧由上而下是加密算法,右侧由上而下是解密算法,K代表密钥,F代表一个函数,圈中十字那个符号代表异或(XOR)运算,在C语言中对应的运算符是^。

可以看出,Feistel结构的加密算法首先需要一组密钥(K0~Kn),一个函数(F)。它将输入的原文分为两个部分,暂且称为L和R,不断重复以下过程:

  1. 将R和K进行F运算,得到的结果再和L做异或运算,得到的结果成为下一轮的R;
  2. R直接成为下一轮的L。
  3. 例外:最后一轮后不交换L和R。

解密过程完全相同,只不过把K全都反过来了,先用Kn,最后用K0。于是,确定算法的K和F就是我们接下来的目标。

逆向工程用什么工具好呢?在网上稍作搜索,很容易发现一款叫作IDA的软件被称为神器,因为它包含一个Hex Rays插件——能产生C语言源代码(当然可读性肯定还是比不上真正的源代码),而不像别的反汇编工具只能产生汇编语言源代码。对于新手和初学者,当然是C语言比较容易读懂了。我们下载、安装并使用IDA处理这个程序,如图导出全部C源代码:

西普CTF-流水线-以夕阳落款

这里插一句:即使源代码只有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:

温馨提示: 此处内容需要评论本文后刷新才能查看,支付2元即可直接查看所有Flag。

小广告:关于获取西普实验吧所有Writeup请点击这里查看索引

查看所有Flag需要付费,需要获取所有Flag的童鞋请访问这里成为付费用户,可以自助把自己的注册邮箱加入网站白名单,即可免回复看到本站所有Flag

Flag大全地址:所有Flag

PS:本站不是实验吧的官方站点,纯粹是个人博客,收取Flag费用仅是维持服务器费用,做站不易,且行窃珍惜,如果喜欢我的博客,愿意捐赠的,可以扫描下面的二维码

微信二维码:
支付宝二维码: