首页
论坛
课程
招聘
[原创]MRCTF2022 llvmvm出题以及解题
2022-5-2 23:07 6504

[原创]MRCTF2022 llvmvm出题以及解题

2022-5-2 23:07
6504

0x1 LLVMVM题目介绍

  • 该题目是一个elf文件,一个典型的虚拟机保护的代码,当时认为仅仅一个虚拟机保护效果有限,还加上了一层数据混淆,属实失策,导致最后0解。这里对于数据流混淆不做讨论。
  • 本题目对于两个重要函数都进行了虚拟化保护,虚拟机的形式是一样的,虚拟机存在一个内存空间,内存可以存储数据和指针,虚拟机能够通过预先写入到虚拟机内存中的指针访问函数传入的参数和变量等。
  • 同时虚拟机还存在一个栈,这个栈不同于数据栈,这个栈使用于保存地址的,指令通过取出栈里的地址,然后根据地址去虚拟机内存中找数据进行运算,并且存入到对应的内存地址的内存中去,这个内存地址往往是存在指令中。然后也有操纵地址栈的指令。
  • 题目每个函数的虚拟机虚拟化后的handler和对应的op码都不一样。
  • 题目文件和相关资料可以在这里下载,llvmvm是题目本体,已经是去掉数据流混淆的程序。
    题目下载

0x2 出题过程

  • 这个题目的混淆过程在于虚拟化,采用llvm进行混淆,虚拟化pass是自己写出来的,具体原理是直接将llvm的ir转化为虚拟机opcode运行,具体的代码可以查看。
    虚拟化混淆pass源码
  • 题目在进行虚拟化之前,对llvm的ir加上了控制流平坦化混淆,所以虚拟机运行的opcode其实也是存在控制流平坦化的混淆的。这里也是一个难点。
  • 被保护的主要加密代码如下。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    bool __attribute((__annotate__(("virtualization")))) function2(uint8_t *key,uint8_t *text)
    {
      for(int i=0;i<16;i++)
          key[i]=R8(key[i]^(i+3),i%8);
      uint32_t a=*((uint32_t*)&key[0]),b=*((uint32_t*)&key[4]),c=*((uint32_t*)&key[8]),d=*((uint32_t*)&key[12]);
      uint32_t key_stream[16],tmp[16];
      for(int i=0;i<4;i++)
      {
          a=((b*c)&0xdeadbfef)+(a<<3)+(d>>29);
          b=((c*d)&0xdefdbeef)+(b<<7)+(a>>25);
          c=((d*a)&0xdfadbeef)+(c<<9)+(b>>23);
          d=((a*b)&0xdeadbeff)+(d<<1)+(c>>31);
          key_stream[4*i]=d+0xdeadbeef;
          key_stream[4*i+1]=c+0xaa114514;
          key_stream[4*i+2]=a+0xf1919810;
          key_stream[4*i+3]=b+0x1abcdef1;
          //printf(" key stream : %x %x %x %x\n",key_stream[4*i],key_stream[4*i+1],key_stream[4*i+2],key_stream[4*i+3]);
      }
      for(int i=0;i<32;i++)
      {
          uint8_t c=text[i];
          c=((c&0xaa)>>1)|((c&0x55)<<1);
          c=((c&0xcc)>>2)|((c&0x33)<<2);
          c=((c&0xf0)>>4)|((c&0x0f)<<4);
          text[i]=c;
          for(int j=0;j<32;j++)
              text[j]^=R32(key_stream[j%16],j)&0xff;
          function1(tmp,key_stream);
          for(int j=0;j<16;j++)
              key_stream[j]=tmp[j];
      }
      for(int x=0;x<4;x++)
      {
          uint8_t t=text[8*x];
          for(int y=0;y<100;y++)
          {
              for(int i=0;i<8;i++)
              {
                  t=t+(key[2*i]^key[2*i+1]);
                  t=Sbox[t]+text[8*x+(i+1)%8];
                  t=(t<<1) | (t>>7);
                  text[8*x+(i+1)%8]=t;
              }
          }
      }
      uint32_t *ptr=(uint32_t *)text;
      for(int i=0;i<8;i++)
      {
          uint64_t v=0;
          for(int j=0;j<32;j++)
          {
              int b=(ptr[i]>>j)&1;
              v+=weights[j]*b;
              v%=mod;
          }
          if(v!=sums[i])
              return false;
      }
      return true;
    }

0x3 how to decompile

  • 要解出这个题,首先的得明白并不是所有的函数都需要逆向的,这里有两个函数我们需要评估一下,不难发现有一个函数输入的数据和拿出来的数据都是固定的,所以其实可以dump即可,重点分析main函数调用的那个函数就行了。
  • 首先是对代码进行分块,对就是将代码分成一个个基本块,这样就能将代码块直接的控制流关系清楚的表示出来,也方便进行数据流分析,具体形式参考ida的界面,按空格就会显示出基本块。

生成基本块(控制流分析)

  • 如何生成一块块的基本块,其实不难发现一下性质。
    1.在代码中如果出现跳转指令或者返回指令,那么该条语句前的代码和之后的代码必定属于不同的基本块。
    2.对于跳转指令跳转的目的地址,地址前和后的代码同样属于不同的基本块。
  • 于是我们可将所有跳转指令的地址,跳转的目的地址,返回语句的地址都保存下来,并且以这些地址将整个代码地址区间分成多个小区间,而这些小区间就构成了基本块的范围。
  • get_blocks函数前半部分是对指令进行解码,弄清楚每个指令起始地址,并存入到addr数组中,inv则是用于保存之前提到的用于划分基本快的地址,代码后部分则是根据inv的结果将addr数组进行划分,划分出的各个就是基本块的范围。
  • 将这些区间用一个类封装起来,BasicBlock。然后可以根据每个基本快的最后一个指令决定这个基本块可以到哪个其他的基本块。这些其他的基本块也就被称之为后继,相反的有前驱。
  • 使用这几个接口来构建一个基本块组成的图。将BasicBlock的后继和前驱都计算出来。build_graph就是用来完成这个工作。通过获取当前基本块最后一条指令的后继地址,从而找到对应的后继基本块
  • 然后可以以每个基本块为单位进行反汇编。具体的反汇编函数放在了disasm模块里,都是op+op码命名方式,然后维护一个栈,用于推演操作数地址。

  • 此时我们就获得了最基本的反编译结果了,非常类似三地址码。
  • 每一个语句都使用Stmt对象包装,其中的r和w代表着这个语句读取/写入了哪些内存中的地址。

数据流分析

  • 此时的代码非常的繁琐,因为它每一行语句都只能代表一种操作,如果出现比较复杂的运算语句就会拆分成非常多条语句,这是很麻烦的,所以要考虑去化简它。
  • 这里需要运用到数据流分析,到达定值分析,到达定值分析的运算过程是这样的。它以基本块为单位进行分析,每一个赋值都可以视为一个定值,例如这里的write(mem[435]) = 0xdeadbeef就是一个定值,除此之外每个基本块都有四个集合:gen,kill,in,out,这里引用了哈工大编译原理课程图片,如有侵权,联系就删。
  • 如果存在一条从紧跟在定值d后面的点到达某一程序点p的路径,而且在此路径上d没有被"杀死" (如果在此路径上有对变量x的其它定值d′,则称变量x被这个定值d′ "杀死"了) ,则称定值d到达程序点p。
  • 下面两个函数就计算了每个语句杀死和生成的定值的集合,用于后文计算。

    1. gen集合代表的是这个基本块生成的定值,意思是这个基本块中产生的一些定值。
    2. kill集合代表的是这个基本块杀死的其他的定值,这些被杀死的定值可能存在其他的基本块中。

    3. in集合代表的是所有能够到达该基本块的定值。例如这里d6,d7就可以到达B2,存在于B2的in集合中。
    4. out集合代表的是所有从该基本块流出的定值。例如这里d3就可以从B2中流出,即存在于B2的out集合中。
  • 那么计算in/out集合就是到达定值分析的主要问题,可以写出如下数据流方程。
  • 对于一个基本快的kill集合,直接将其中每个语句杀死的定值取并集即可。

  • 对于一个基本快的gen集合,从后往前计算即可。

  • 然后使用迭代的方式计算数据流方程,不断地应用上文的数据流方程,直到in/out集合都没有发生改变的时候(趋于一个平衡点),就代表计算完成。
  • 计算完到达定值分析后就能干很多事情了,比如计算use/def链等等。这里额外计算了对于一个语句,它需要读取的变量可能是被哪些语句所定义的。
  • 例如下方图片中对a的访问如果在他之前a已经被赋值,那么这个a肯定来自于基本快里的赋值a的值,否则这个a可能就是来自于外部,即当前基本块中的in集合中与a有关的定值。
  • 具体计算代码如下。就是对于每个语句的每个访问,都从他往前面找,如果找到了相关的定值,则直接确定这个访问的定值就是由这个语句定义的,否则说明定值来自于基本块外部,直接找in集合中相关的定值即可。
  • 这样我们就能很方便的知道,这个语句读取的变量的值是由哪个语句所定义的。

对代码化简

  • 我们需要对代码化简,本质上就是需要把一些拆开的语句给塞回去,让他成为一个更长的语句,同时不能让代码的原语义发生改变。例如
    1
    2
    3
    4
    5
    6
    7
    8
    9
    old:
    a = b + c
    ...
    y = x * a
    ->
    new:
    a = b + c
    ...
    y = x * (b + c)
  • 稍加分析就能发现,如果一个语句a能够带入到另一个语句y的话,则需要确定几件事情。
  1. y中的a的定义必须是唯一确定的,如果有多种a的定值能够到达y的话则说明不能带入。
  2. 在从y到a的过程中,a所引用的定值是不能发生改变的,例如这里b和c在到达y之前不能被杀死,否则语义将发生改变。
  • 所以先将所有能够带入的定值带入,这样就能产生较长的语句,同时能够更好的阅读。具体的带入算法如下。
    1. 对于每个基本块的每一个语句,分析他读取的变量,如果发现变量的定值是唯一确定的的,则进一步确认,如果定值的语句来自于基本块外,那么就得从基本块开头语句开始,否则就从该语句位置开始,向后遍历,确定在到达这个正在处理的语句之前,定值所引用的其他变量没有被修改。
    2. 找到这样一个能够带入的语句后,记录下来,包括带入语句和正在处理的语句。
    3. 在处理完一个语句后,将能够带入的语句全部带入到这个刚刚处理完毕的语句中,然后修改一下带入后的读取/写入集合,跟新一下ud_chain,由于数据流之和语句的w有关,所以不需要重新计算。
    4. 处理完所有基本块的所有语句为一轮,如果一轮完毕没有语句带入,则说明已经实现所有的带入,循环停止,否则重新处理。
  • 具体实现如下。
  • 然后我们只需要删除一些无用的语句和跳转即可。
  • 此时就能够得到了可读性更强,更简洁的反编译结果了。

去除控制流平坦化

  • 因为控制流平坦化的存在,此时的控制流图仍然比较复杂。
  • 控制流平坦化的原理比较简单,这里的实现也比较简陋与丑陋,没有通用性。大体的思路就是:
  1. 找到真实块,如果一个基本块访问了一个特定的地址,那他肯定是真实块,同时return语句所在的基本块也必定是真实块。然后从其中提取出所有的控制变量取值。
  2. 找到真实块对应的值,这个需要通过正则抽取if中比较的数值,确定控制变量取值对应哪个基本块。设置一个ptr指向基本块,满足条件则往正确的基本块移动,直到ptr指向了除去entry以外的真实块,则可以说明这个真实块对应当前的值。
  3. 根据每个基本块写入的控制变量取寻找对应的基本块,从而计算出基本快的后继。删除不必要的基本块。
  • 此时就能得到非常漂亮的控制流图了,配合化简后的代码,非常易懂。

0x4 后记

  • 这个题目本来想使用angr来处理的,分割基本块,以基本块为单位分开处理,通过监听内存的写入过程来更好的推测程序在干啥,结果效果非常一般。
  • 然后觉得单纯的动调写出来的wp非常没意思,于是就试着以这样一种方式来反编译,感觉非常有意思,这个过程中也学到了很多,理解了反编译的一些过程,但是这里对于控制流的重建还没有完成,就是没有识别for/while等结构。。

脚本下载


【看雪培训】《Adroid高级研修班》2022年夏季班招生中!

最后于 2022-5-6 17:50 被R1mao编辑 ,原因: 添加题目elf文件
上传的附件:
收藏
点赞8
打赏
分享
最新回复 (8)
雪    币: 6171
活跃值: 活跃值 (3604)
能力值: ( LV13,RANK:239 )
在线值:
发帖
回帖
粉丝
sunfishi 活跃值 3 2022-5-2 23:10
2
0
mark
雪    币: 2494
活跃值: 活跃值 (1836)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
默NJ 活跃值 2022-5-2 23:17
3
0
强!
雪    币:
活跃值: 活跃值 (386)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
mb_rhynjqzk 活跃值 2022-5-3 12:22
4
0
(所以数据流混淆有无啥好办法解决呢
雪    币: 6645
活跃值: 活跃值 (2739)
能力值: ( LV4,RANK:45 )
在线值:
发帖
回帖
粉丝
v0id_ 活跃值 2022-5-3 13:38
5
0
雪    币: 1526
活跃值: 活跃值 (2205)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
霸气压萝莉 活跃值 2022-5-3 14:19
6
0
附件地址不对
雪    币: 1620
活跃值: 活跃值 (1308)
能力值: ( LV6,RANK:80 )
在线值:
发帖
回帖
粉丝
R1mao 活跃值 1 2022-5-3 14:50
7
0
mb_rhynjqzk (所以数据流混淆有无啥好办法解决呢
理论上用编译优化就能做到,加在虚拟机上的话,直接把虚拟机的f5伪代码抄出来用O2编译优化下,再反编译应该就去掉了
雪    币: 9217
活跃值: 活跃值 (34300)
能力值: (RANK:105 )
在线值:
发帖
回帖
粉丝
Editor 活跃值 2022-5-6 16:37
8
0

附件本地上传一份,另外,目标程序楼主能否也上传一份?


上传的附件:
雪    币: 1620
活跃值: 活跃值 (1308)
能力值: ( LV6,RANK:80 )
在线值:
发帖
回帖
粉丝
R1mao 活跃值 1 2022-5-6 17:50
9
0
Editor 附件本地上传一份,另外,目标程序楼主能否也上传一份?
已上传
游客
登录 | 注册 方可回帖
返回