[分享] 看雪.安恒2020 KCTF春季赛 第六题 一尺之棰

7小时前 78

[分享] 看雪.安恒2020 KCTF春季赛 第六题 一尺之棰

看雪.安恒2020 KCTF春季赛 第六题 一尺之棰

分析

程序逻辑比较简单，拿 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());
}

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

求解

写一个算术编码的解码程序即可。注意不要改变上述的任何计算的形式以免引入数值精度问题。考虑到数据不大，可以写的暴力一点。详细见附件。

运行即可得到答案 504964774D526B756F467A705C4D654B7645587746634A7A75505F757A75776C。

[培训]《安卓高级研修班(网课)》6月班开始招生！一年后遇见不一样的自己！（现在进入看雪课程可以试看两节）[3万班售罄！ 2万班还有一个名额]