2024 CISCN x 长城杯初赛 RE rand0m 纯静态wp

Azuria · 发表于 2024-12-19 16:29

本帖最后由 Azuria 于 2024-12-19 16:51 编辑

2024 CISCN x 长城杯初赛 RE rand0m 纯静态wp

起因是队长说我们万年不出 RE 手的学校又发现个会 RE 的（把 rand0m 做出来了，见2024长城杯初赛Reverse rand0m wp），并表示我后继有人了，才把这道题从回收站翻出来做了。

首先因为题目没给符号的缘故上手直接 f5 会很痛苦，比赛的时候也是一眼没符号丢垃圾桶，转头去做溯源的样本分析去了。

但是这题也不是不能纯静态分析，只需要一点点小技巧就可以当作有符号来做。

以同一伪代码片段为例，处理前很难分析这段代码的作用。

  v17 = PyLong_Type[0];
  v18 = *((_QWORD *)off_18000B688 + 32);
  if ( *(_QWORD *)(v12 + 8) != PyLong_Type[0] )
    goto LABEL_32;
  v19 = *(_QWORD *)(v12 + 16);
  if ( (v19 & 1) != 0 )
  {
    if ( *(_DWORD *)v12 != -1 )
      ++*(_DWORD *)v12;
    v8 = (int *)v12;
    goto LABEL_36;
  }
  if ( v19 >= 0x10 )
  {
    switch ( (v19 >> 3) * (1 - (*(_QWORD *)(v12 + 16) & 3LL)) )
    {
      case 0xFFFFFFFFFFFFFFFEuLL:
        v20 = -(__int64)(*(unsigned int *)(v12 + 24) | ((unsigned __int64)*(unsigned int *)(v12 + 28) << 30));
        goto LABEL_29;
      case 2uLL:
        v20 = *(unsigned int *)(v12 + 24) | ((unsigned __int64)*(unsigned int *)(v12 + 28) << 30);
        goto LABEL_29;
      default:
        v21 = (*(__int64 (__fastcall **)(__int64, _QWORD))(PyLong_Type[12] + 88LL))(
                v12,
                *((_QWORD *)off_18000B688 + 32));
        break;
    }
    goto LABEL_33;
  }
  LODWORD(v20) = *(_DWORD *)(v12 + 24) * (1 - (v19 & 3));
  if ( (_DWORD)v20 != (16 * (int)v20) >> 4 && (_DWORD)v20 )
  {
    v20 = (int)v20;
LABEL_29:
    if ( v20 == (__int64)(16 * v20) >> 4 )
    {
      v21 = PyLong_FromLongLong(16 * v20);
      goto LABEL_33;
    }
LABEL_32:
    v21 = PyNumber_Lshift(v12, *((_QWORD *)off_18000B688 + 32));
    goto LABEL_33;
  }
  v21 = PyLong_FromLong((unsigned int)(16 * v20));
LABEL_33:
  v12 = v21;
  v8 = (int *)v21;
  if ( !v21 )
  {
    v9 = 2639;
    v7 = 5;
    goto LABEL_77;
  }

处理后增加引用计数、<< 和异常处理的逻辑十分清楚。

  if ( v1->ob_base.ob_type != PyLong_Type.ob_base.ob_base.ob_refcnt )
    goto LABEL_32;
  ob_refcnt = v1->long_value.lv_tag;
  if ( (ob_refcnt & 1) != 0 )
  {
    if ( v1->ob_base.ob_refcnt_split[0] != -1 )
      ++v1->ob_base.ob_refcnt_split[0];
    v8 = v1;
    goto LABEL_36;
  }
  if ( ob_refcnt >= 0x10 )
  {
    switch ( (ob_refcnt >> 3) * (1 - (v1->long_value.lv_tag & 3)) )
    {
      case 0xFFFFFFFFFFFFFFFEuLL:
        v18 = -(v1->long_value.ob_digit[0] | (v1->long_value.ob_digit[1] << 30));
        goto LABEL_29;
      case 2uLL:
        v18 = v1->long_value.ob_digit[0] | (v1->long_value.ob_digit[1] << 30);
        goto LABEL_29;
      default:
        v19 = (PyLong_Type.tp_as_number->nb_lshift)(v1, __pyx_mstate[32]);
        break;
    }
    goto LABEL_33;
  }
  LODWORD(v18) = v1->long_value.ob_digit[0] * (1 - (ob_refcnt & 3));
  if ( v18 != (16 * v18) >> 4 && v18 )
  {
    v18 = v18;
LABEL_29:
    if ( v18 == (16 * v18) >> 4 )
    {
      v19 = PyLong_FromLongLong(16 * v18);
      goto LABEL_33;
    }
LABEL_32:
    v19 = PyNumber_Lshift(v1, __pyx_mstate[32]);
    goto LABEL_33;
  }
  v19 = PyLong_FromLong((16 * v18));            // v19 = v1 << 4
LABEL_33:
  v1 = v19;
  v8 = v19;
  if ( !v19 )
  {
    v9 = 2639;
    v7 = 5;
    goto LABEL_77;
  }

那么原理是什么？

接下来，Python.h 会很有用。

不要问我怎么加载 Python.h，自己去找 Parse C header file。

PyModuleDef 没啥好说的，PyInit_rand0m 里点过去就行了。

然后是 cython 最劝退人的常量池问题。

字符串常量池和 int 常量池是分开初始化的，不过指针都储存在 __pyx_mstate 里，对于 cython 逆向而言还是提前提取常量池比较好。

这也不算常量池，人家叫 module state，总之先把用到的 module state 提取出来。

__pyx_mstate = {
    19: "rand0m",
    29: 0,
    30: 1,
    31: 2,
    32: 4,
    33: 5,
    34: 8,
    35: 11,
    36: 16,
    37: 23,
    38: 65537,
    39: 37360232,
    40: 304643896,
    41: 1244723021,
    42: 2282784775,
    43: 2563918650,
    44: 2654435769,
    45: 2918417411,
    46: 3628702646,
    47: 3773946743,
    48: 4198170623,
    49: 4294967293
}

rand0m 去掉异常检查、类型检查和修改引用计数的部分可以得到较清楚的伪代码。

PyTupleObject *__fastcall rand0m(__int64 a1, PyObject *a2)
{
  // [COLLAPSED LOCAL DECLARATIONS. PRESS NUMPAD "+" TO EXPAND]

  v2 = 0LL;
  v15 = 0LL;
  v5 = 0LL;
  v14 = 0LL;
  v7 = 2;
  v8 = PyTuple_New(2LL);
  v10 = __pyx_mstate;
  v8->ob_item[0] = a2;
  v11 = v10[36];
  v8->ob_item[1] = v10[36];
  v1 = sub_1800042B0(PyLong_Type.ob_base.ob_base.ob_refcnt, v8);// v1 = int(a2, 16)
  v5 = v1;
  v14 = PyNumber_Xor(v1, __pyx_mstate[44]);     // v14 = v1 ^ 2654435769
  v15 = rshift(v1, __pyx_mstate[33], 5, 0);     // v15 = v1 >> 5
  v16 = __pyx_mstate;
  LODWORD(v18) = LODWORD(v1[1].ob_type) * (1 - (ob_refcnt & 3));
  v19 = PyLong_FromLong((16 * v18));            // v19 = v1 << 4
LABEL_33:
  v1 = &v19->ob_base.ob_base;
  v8 = v19;
  v16 = __pyx_mstate;
LABEL_36:
  v20 = PyNumber_And(v1, v16[48]);              // v20 = v19 & 4198170623
  v21 = v5;
  v5 = v20;
  v22 = rshift(v15, __pyx_mstate[37], 23, 0);   // v22 = v15 >> 23
  v8 = v22;
  v23 = PyNumber_Add(v20, v22);                 // v23 = v20 + v22
  v24 = v15;
  v15 = v23;
  v25 = rshift(v14, __pyx_mstate[35], 11, 1);   // v25 = v14 >> 11
  v27 = v14;
  v14 = v25;
  v28 = PyNumber_Power(v25, __pyx_mstate[38], Py_NoneStruct);// v28 = v25 ** 65537
  v8 = v28;
  v29 = PyNumber_Remainder(v28, __pyx_mstate[49]);// v29 = v28 % 4294967293
  v5 = v29;
  v30 = PyTuple_New(2LL);
  v30->ob_item[0] = v29;
  v30->ob_item[1] = &v15->ob_base;
  v2 = v30;
  return v2;
}

把关键部分提取出来得到：

def rand0m(a2):
    v1 = int(a2, 16)
    v14 = v1 ^ 2654435769
    v15 = v1 >> 5
    v19 = v1 << 4
    v20 = v19 & 4198170623
    v22 = v15 >> 23
    v23 = v20 + v22
    v25 = v14 >> 11
    v28 = v25 ** 65537
    v29 = v28 % 4294967293
    return v29, v23

优化一下得到：

def rand0m(n):
    n = int(n, 16)
    x = (((n ^ 2654435769) >> 11) ** 65537) % 4294967293
    y = ((n << 4) & 4198170623) + ((n >> 5) >> 23)
    return x, y

这边都一样，没什么好说的。

check 同理，先是加载密文到 v6。

v6 = PyList_New(8LL);
v9 = __pyx_mstate;
*v6->ob_item = v9[40];
*(v6->ob_item + 1) = v9[43];
*(v6->ob_item + 2) = v9[41];
*(v6->ob_item + 3) = v9[47];
*(v6->ob_item + 4) = v9[39];
*(v6->ob_item + 5) = v9[45];
*(v6->ob_item + 6) = v9[42];
*(v6->ob_item + 7) = v9[46];

也就是这个。

v6 = [304643896, 2563918650, 1244723021, 3773946743, 37360232, 2918417411, 2282784775, 3628702646]

然后对明文进行切片。

v30 = (ob_type == PyFloat_Type
      ? PyFloat_FromDouble(v21, __pyx_mstate, PyLong_Type.ob_base.ob_base.ob_refcnt, __pyx_mstate[34])
      : PyNumber_Multiply(v22, __pyx_mstate[34]));// v30 = v22 * 8
v28 = v30;
v29 = v30;
v24 = __pyx_mstate;
v31 = add(v22, v24[30], ob_refcnt, 0LL);    // v31 = v22 + 1
v33 = v31;
v34 = v31->ob_base.ob_type;
v38 = (v34 == PyFloat_Type
      ? PyFloat_FromDouble(__pyx_mstate, PyLong_Type.ob_base.ob_base.ob_refcnt, __pyx_mstate[34], v32)
      : PyNumber_Multiply(v33, __pyx_mstate[34]));// v38 = v31 * 8
v36 = v38;
v37 = v38;
v39 = *(v2 + 8);
v40 = *(v39 + 112);
v41 = PySlice_New(v28, v36, Py_NoneStruct); // slice(i * 8, (i + 1) * 8)

然后从常量池里找到 rand0m，后续以切片为参数调用 rand0m.rand0m。

v44 = __pyx_mstate[19];                     // "rand0m"
Item_KnownHash = PyDict_GetItem_KnownHash(*__pyx_mstate, v44, v44[1].ob_type);

之后的比较过程就没什么好说的了。

爆破的话思路也是先根据 rand0m(x)[1] 用 c 爆破出参数候选值，再用 python 爆破模幂，毕竟本地没有大数库。

#include <stdint.h>
#include <stdio.h>

uint32_t e[] = {304643896, 1244723021, 37360232, 2282784775};

int main()
{
    printf("[");
    for (int i = 0; i < 4; i++) {
        printf("[");
        for (uint64_t n = 0; n <= 0xffffffff; n++) {
            uint64_t e1 = ((n << 4) & 4198170623) + ((n >> 5) >> 23);
            if (e1 == e[i]) {
                printf("%llu,", n);
            }
        }
        printf("],");
    }
    printf("]");

    return 0;
}

把生成的值填进去即可。

e = [2563918650, 3773946743, 2918417411, 3628702646]
t = []
for i in range(4):
    y = e[i]
    for x in t[i]:
        if pow((x ^ 2654435769) >> 11, 65537, 4294967293) == y:
            print(f'{x:x}')
            break

体感有类型的情况下效率能提高一倍以上，能接近有符号的情况。不过这题还是花了大概两小时左右。

后附题目、idb 和解题脚本，但是没有 challenge.py，因为从回收站翻出来的时候就只剩 rand0m.pyd 了。

rand0m.7z (215.72 KB, 下载次数: 0)

https://azuria.lanzn.com/iumTC2ij1myh 密码:1vq4

Evolt · 发表于 2024-12-19 21:28

大佬受教了，当时作半天没搞出来

zay1983 · 发表于 2024-12-20 07:39

谢谢分享。

princekin · 发表于 2024-12-20 08:29

学习学习

wasm2023 · 发表于 2024-12-20 08:52

太牛了，感谢大佬分享

aosikaiii · 发表于 2024-12-20 10:18

感谢大佬分享

Psc7day · 发表于 2024-12-22 11:09

感谢大佬分享

帐号		自动登录	找回密码
密码			注册[Register]

[CTF] 2024 CISCN x 长城杯初赛 RE rand0m 纯静态wp

2024 CISCN x 长城杯初赛 RE rand0m 纯静态wp

免费评分

[CTF] 2024 CISCN x 长城杯 初赛 RE rand0m 纯静态wp

2024 CISCN x 长城杯 初赛 RE rand0m 纯静态wp

免费评分

[CTF] 2024 CISCN x 长城杯初赛 RE rand0m 纯静态wp

2024 CISCN x 长城杯初赛 RE rand0m 纯静态wp