首页
论坛
课程
招聘
[推荐]看雪·安恒 2020 KCTF 春季赛 | 第六题设计思路及解析
2020-5-6 18:11 4409

[推荐]看雪·安恒 2020 KCTF 春季赛 | 第六题设计思路及解析

2020-5-6 18:11
4409


第六题《一尺之棰》历时3天,共有1645人围观,最终共有3支战队成功破解。


在比赛过程中,辣鸡战队xym在凌晨成功攻破题目,从排行榜十名开外一跃成为攻击方总排行第一名。

随后,其他战队也不甘示弱,123456789战队和金箍棒配色的泰迪熊战队陆续成功攻破此题,再次颠覆排名,可谓风云变幻。
没有做出来的战队也不要灰心,学习解题思路也是一种收获,也能为接下来的比赛积攒经验,让我们一起来看一下这道题的设计思路和详细解析吧。



赛题点评


本题点评由 123456789 战队的 香菇滑稽 提供:

此题关键点是 printf 函数改变了舍入控制位域,如果对浮点数运算过程不够熟悉很容易忽略其对计算结果的影响。之后,只要耐心的重构出算法,计算出答案的过程并不困难。


出题团队简介


本题出题战队 金左手



设计思路


题目答案: 
504964774D526B756F467A705C4D654B7645587746634A7A75505F757A75776C

题目类型:Window平台CrackMe

系统需求:WIN10/64

成功提示:Good job!


1设计说明


早在1948年,香农就提出将信源符号依其出现的概率降序排序,用符号序列累计概率的二进值作为对信源的编码,并从理论上论证了它的优越性。1960年,Peter Elias提出了算术编码的概念,Elias没有公布他的发现,因为他知道算术编码在数学上虽然成 立,但不可能在实际中实现。

1976年,R. Pasco和J. Rissanen分别用定长的寄存器实现了有限精度的算术编码。1979年Rissanen和G. G. Langdon一起将算术编码系统化,并于1981年实现了二进制编码。

1987年Witten等人发表了一个实用的算术编码程序,即CACM87(后用于H.263视频压缩标准)。

IBM公司也发表过著名的Q-编码器(后用于JPEG和JBIG图像压缩标准)。从此,算术编码迅速得到了 广泛的注意。

算术编码的基本原理是将编码的消息表示成实数0和1之间的一个间隔,消息越长,编码表示它的间隔就越小,表示这一间隔所需的二进制位就越多。

算术编码用到两个基本的参数:符号的概率和它的编码间隔。

信源符号的概率决定压缩编码的效率,也决定编码过程中信源符号的间隔,而这些间隔包含在0到1之间。编码过程中的间隔决定了符号压缩后的输出。

算术编码可以是静态的或者自适应的。在静态算术编码中,信源符号的概率是固定的。在自适应算术编码中,信源符号的概率根据编码时符号出现的频繁程度动态地进行修改,在编码期间估算信源符号概率的过程叫做建模。
(上面描述基本摘自参考资料)

在本题目中,利用了算术编码的编码原理,不考虑压缩率,所以输入的key经过16轮的编码后会越来越大。编码过程就是对一个小数区间无限细分,小数点后的位数或者是精度不断增加的过程。

考虑到直接常规编码的话题目难度太低,所以故意增加几处难点:

a.把浮点运算的舍入模式ROUND_NEAREST修改为ROUND_UP,使得误差积累到一定程度会产生不同的运算结果;

b.做了一个简单的宏把浮点数存储前做些移位交换,读出后再还原,这个也不算是障碍,ida下F5后会一览无余,虽然把整个表的257项都计算了,实际每个字符只用到其中一项;

c.频度自适应略作修改,每轮权重因子定长+1



2解题思路


1. 程序不大,结构简单,都在一个main函数里,ida里F5一下,基本和源码差不太多了。

2. 可以还原整理出代码,都在main函数里,也就100多行,自己编译模拟计算过程,大概可以猜出是个压缩编码算法,熟悉的话也能确定是属于算数编码。

然后跟踪运算流程,对比可以发现,自己编译的出程序和题目程序在运算过程中会存在很小的误差。在这里可以思考一下,如果能想到浮点运算的默认舍入模式,就可以几种都尝试对比一下,找到一种匹配的,或许你可能发现下面一条提到的暗桩。

3. 暗桩位置在printf内部有几行被patch过:

        0000000140002ED1                 push    rax
        0000000140002ED2                 stmxcsr dword ptr [rsp]
        0000000140002ED6                 pop     rax
        0000000140002ED7                 and     ah, 0DFh
        0000000140002EDA                 or      ah, 40h
        0000000140002EDD                 push    rax
        0000000140002EDE                 ldmxcsr dword ptr [rsp]
        0000000140002EE2                 pop     rax
        查询SSE指令集得知,这是把浮点运算的默认舍入模式ROUND_NEAREST修改为ROUND_UP

4. 正确设置浮点 舍入模式之后,运算结果可以完全匹配了。

不用汇编的正常调用方式可以这样:

        #include <float.h>
        _set_controlfp(RC_UP,MCW_RC);

5. 求逆

这个编码有个特点,以字节为单位往后进行的,所以每个字节可以穷举,对浮点值区间进行匹配,得到正确输入,其实只有256个分片的升序区间总是要做遍历的,不用穷举(而用二分法?)的话也好不了太多吧。

keygen见附件的Julia脚本(设计题目的起因主要就是想测试一下Julia)
参考资料:hxxps://zhuanlan.zhihu.com/p/23834589


解析过程


本题解题思路由金箍棒配色的泰迪熊战队Riatre提供: 


1分析


程序逻辑比较简单,拿 IDA 简单看看,可以看出程序的结构是将输入编码了 16 轮,与固定的输出比较。


编码过程中大量用了浮点数。将 F5 出来的验证代码直接复制出来,胡乱改一改,可以整理出还算漂亮的形式:


double XJBShuffleBit1(double x) {
  auto v = bit_cast<_QWORD>(x);
  v = ((v & 0x7FFFFFFC00ll | ((LOBYTE(v) & 7 | ((v & 0xFFFFFFFFFFFFFFF8ull) << 30)) << 6)) << 18) | ((v & 0x10000000000000ll | (((v >> 1) ^ (v ^ (v >> 1)) & 0xFFF8000000000ull) >> 14)) >> 25);
  return bit_cast<double>(v);
}
 
double XJBShuffleBit2(double x) {
  auto v = bit_cast<_QWORD>(x);
  v = ((v & 0x8000000 | ((v & 0x1FFF | (2 * (v & 0xFFFFFFFFFFFFE000ull))) << 14)) << 25) | ((v & 0x1FFFFFFF0000000ll | (((v >> 30) ^ ((unsigned int)v ^ (unsigned int)(v >> 30)) & 0x7000000) >> 6)) >> 18);
  return bit_cast<double>(v);
}
 
bool Check(unsigned char hexdecoded[32]) {
  int prob[257];              // [rsp+60h] [rbp-A0h]
  double ep[257];             // [rsp+470h] [rbp+370h]
  unsigned char bits[1024];   // [rsp+1040h] [rbp+F40h]
  unsigned char output[8192]; // [rsp+1440h] [rbp+1340h]
  unsigned char input[8192];  // [rsp+3440h] [rbp+3340h]
 
  memset(input, 0, sizeof(input));
  memset(output, 0, sizeof(output));
  memcpy(input, hexdecoded, 32);
  int input_len = 32;
  int output_len = 0;
  auto Emit = [&](int byteidx, int bitcnt = 8) {
    char packed = 0;
    for (int bi = 0; bi < bitcnt; bi++) {
      packed |= bits[8 * byteidx + bi] << (7 - bi);
    }
    output[output_len++] = packed;
  };
  for (int round = 0; round < 16; round++) {
    double lower = 0.0;
    double upper = 1.0;
 
    memset(bits, 0, sizeof(bits));
    memset(ep, 0, sizeof(ep));
    int total_bits = 0;
 
    // First 2 bytes: input_len
    *(unsigned short *)output = input_len;
    output_len = 2;
 
    for (int i = 0; i < 257; i++) {
      prob[i] = i;
    }
    unsigned int output_byte_cnt = 0;
    for (int idx = 0; idx < input_len + 5; idx++) {
      unsigned char tch = (idx < input_len) ? input[idx] : (idx & 1);
      double unit = (upper - lower) / (double)prob[256];
      for (int i = 0; i < 257; i++) {
        ep[i] = XJBShuffleBit1((double)prob[i] * unit + lower);
      }
      lower = XJBShuffleBit2(ep[tch]);
      upper = XJBShuffleBit2(ep[tch + 1]);
 
      double dlower = lower * 2.0;
      double dupper = upper * 2.0;
      while ((int)dlower == (int)dupper) {
        assert(!isnan(dlower) && !isnan(dupper));
        bits[total_bits++] = (int)dlower;
        upper = dupper - (int)dupper;
        lower = dlower - (int)dlower;
        dupper = upper * 2.0;
        dlower = lower * 2.0;
      }
      output_byte_cnt = total_bits / 8;
      total_bits %= 8;
      for (int t = 0; t < output_byte_cnt; t++) {
        Emit(t);
      }
      memmove(bits, &bits[8 * output_byte_cnt], total_bits);
      for (int j = tch + 1; j < 257; ++j) {
        prob[j] += tch % (round + 16) + round + 16;
      }
    }
    if (total_bits) {
      Emit(output_byte_cnt, total_bits);
    }
 
    memmove(input, output, output_len);
    input_len = output_len;
  }
  return output_len == 906 && memcmp(output, answer_bin, 906) == 0;
}


可以看出在浮点数运算中穿插的 XJBShuffleBit1 和 XJBShuffleBit2 互为逆运算,可以去掉。剩下的部分看起来就是一个用浮点数做的算术编码。


用浮点数做的算术编码一定存在精度问题,整理出程序之后我们首先来尝试把两边的输出对上。


随便输入一个数据(比如 0000000000000000000000000000000000000000000000000000000000000000),可以发现上面贴的代码和原始程序的输出并不相符。


打印 lower、upper、unit 并在调试器里观察对应的值,发现大约第三轮左右开始出现了最低位差 1 的情况。


遇到这种东西第一反应自然是 rounding 参数不同。


x86 CPU 有两个地方可以控制 rounding mode,一个是 FPU ControlWord,还有一个是 MXCSR。


该程序里 x87 指令和 SIMD 指令似乎都有用到(没仔细看),我们把这两个值从调试器里抄出来在自己的程序里设置上:


void InitializeCPUState() {
  fpu_control_t fpu_cw;
  _FPU_GETCW(fpu_cw);
  fprintf(stderr, "old fpu_cw = %#x\n", fpu_cw);
  fpu_cw = 0x27F;
  _FPU_SETCW(fpu_cw);
  fprintf(stderr, "new fpu_cw = %#x\n", fpu_cw);
 
  fprintf(stderr, "old MXCSR = %#x\n", _mm_getcsr());
  _mm_setcsr(0x5FA0);
  fprintf(stderr, "new MXCSR = %#x\n", _mm_getcsr());
}


设置完后会发现编码结果已经可以对上了。


2 、求解


写一个算术编码的解码程序即可。注意不要改变上述的任何计算的形式以免引入数值精度问题。考虑到数据不大,可以写的暴力一点。详细见附件。(https://bbs.pediy.com/thread-259160.htm)

 

运行即可得到答案504964774D526B756F467A705C4D654B7645587746634A7A75505F757A75776C。



[注意] 欢迎加入看雪团队!base上海,招聘CTF安全工程师,将兴趣和工作融合在一起!看雪20年安全圈的口碑,助你快速成长!

收藏
点赞0
打赏
分享
最新回复 (0)
游客
登录 | 注册 方可回帖
返回