Chal rsa-factory

字数统计: 2k字   |   阅读时长≈ 9分

一道cython配合觅马学rsa攻击的题目。由于本人稀烂的密码学能力，所以本篇主要分析cython逻辑。

rsa-factory

提供文件

  1. greet.o文件，似乎是未连接到库和重定位，从而生成.so文件的半成品。无法用来调试（虽然我还没研究cython怎么调试）
  2. out.txt文件，给了rsa相关数据。与本博客的目标无关。
1
2
3
4
5
6
7
# out.txt
e = 64991215158963691560526666468141959384959109359439137131747651162956455586271
n1 = 29993503600164729015956324786706888442519396064191560750084140480290745819535179693348191507149250430395035552797283845777601934626280373409219187420866944308214314519319036917673538094015208260669572499228580056077786705598288026374871729383433345507107962917127650202187058774356364876840623349671218708163
n2 = 22111930331381204542945530852361998548318442407872218298358617096708819116917760050316820810420025909178795848107273937553163317177369208499520284574181398183015911140668391445813446367863710044212006290553153052918732733827420444142923043854261762712224865735741111776384712426729456003107915641158324427237
enc1 = 5734479269568428799754263829957380996168467091071186499560002255391225964390802296056440018922131498808809631799051595890069085606010803104164806662687146720687788026847911647036207771907631955479366662789973591244769696134468514079840335501351730204203353632991649784558594004181235638708670967712800524633
enc2 = 2362618611696658863938958429674618535671832342024171207784704801010887172339238339378660582011609537496581126507952922081766648758361491670598981875420705502658641664419829335179411621872684197316613144999495536326791046211596882050099351426090501042665486716774582833785205621814522795611943989934392618493

定位

扔到IDA7.6分析

此二进制文件由于没有生成正式.so文件，没有进行过strip操作，所以保留了符号表。很大的帮助。

一开始自动进入main函数。没有用的。

在函数窗口中找到__pyx_pymod_exec_test函数。此函数代表了原Python文件的主逻辑。

恢复代码

分析起来一步一步的真的很烦，讲解起来更麻烦。直接写点总结性经验吧。

下面先贴一下我翻译后的脚本。和源码已经很接近了，不过双while循环上面还是用了goto伪代码。

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
61
62
63
64
65
66
from typing import Tuple
from Crypto.Util.number import *
from math import gcd
from flag import FLAG

def getRandomNBitInteger(a):
    pass

def isPrime(a):
    pass

def inverse(a):
    pass


def keygen(dbit, nbit):
    while True:
        if 2 * dbit < nbit :
            p = getRandomNBitInteger(dbit)
            q = getRandomNBitInteger((nbit // 2) - dbit)
            if isPrime(p * q + 1):
                break
            # do - while

    while True:
        p2 = getRandomNBitInteger(dbit)
        q2 = getRandomNBitInteger(nbit // 2 - dbit)
        if isPrime(p * q2 + 1) and isPrime(p2 * q2 + 1):
            break

    while True:
        p3 = getRandomNBitInteger(dbit)
        if gcd(p*q*p2*q2, p3) == 1:
            break
        else: 
            LABEL0:
            continue

    u = (p * q + 1) - 1
    v = (p2 * q2 + 1) - 1

    if isPrime(((p3 * inverse(p3 , u * v) - 1) // (u * v)) * q + 1):
        return  p3, (p * q + 1) * (p2 * q2, 1), (p * q2 + 1) * (((inverse(u * v, p3) * p3 - 1) // (u * v)) * q + 1)
    else:
        goto LABEL0
       

def encrypt(msg, pubkey:Tuple):
    return pow(msg, pubkey[0], pubkey[1])

nbit = 1024
dbit = 256

e, n1, n2 = keygen((dbit, "?"))

FLAG = int(FLAG.encode("utf-8").hex(), 16)

c1 = encrypt(FLAG, (e, n1))
c2 = encrypt(FLAG, (e, n2))

print("e = ", e)
print("n1 = ", n1)
print("n2 = ", n2)
print("enc1 = ", c1)
print("enc2 = ", c2)

上面的goto伪代码其实是：

1
2
3
4
5
6
while True:
	while True:
		pass
	if ...:
		return

即实际上外面还有个while，一共两个。

IDA伪代码里面反编译出来，在开头似乎有个while(2)，这个2可能代表了其前驱有2个基本块，再加上IDA里面的goto语句，暗示了实际上就是个双while循环。

难点实际在keygen()函数中。主函数中关于模块导入，函数定义等都是很鲜明的。以前博客也讲过很多次。

经验总结

如何定位__pyx_pymod_exec函数

此文件似乎是个可执行文件，带有main函数。但是没什么用。

正确的方法是：

打开导出界面，找到PyInit_test函数

函数逻辑很小，就这点。

1
2
3
4
__int64 PyInit_test()
{
  return PyModuleDef_Init(&_pyx_moduledef);
}

在_pyx_moduledef下找到__pyx_moduledef_slots

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
.data:000000000020ED60 __pyx_moduledef dq 1                    ; DATA XREF: PyInit_test↑o
.data:000000000020ED68                 dq 0
.data:000000000020ED70                 dq 0
.data:000000000020ED78                 dq 0
.data:000000000020ED80                 dq 0
.data:000000000020ED88                 dq offset aTest         ; "test"
.data:000000000020ED90                 align 20h
.data:000000000020EDA0                 dq offset __pyx_methods
.data:000000000020EDA8                 dq offset __pyx_moduledef_slots
.data:000000000020EDB0                 dq 0
.data:000000000020EDB8                 dq 0
.data:000000000020EDC0                 dq 0
.data:000000000020EDC8                 dq 0
.data:000000000020EDD0                 dq 0
.data:000000000020EDD8                 dq 0

默认找到第二个地址指针即可。

找到__pyx_pymod_exec函数指针

1
2
3
4
5
6
7
8
.data:000000000020EDE0 __pyx_moduledef_slots dq 1              ; DATA XREF: .data:000000000020EDA8↑o
.data:000000000020EDE8                 dq offset __pyx_pymod_create
.data:000000000020EDF0                 dq 2
.data:000000000020EDF8                 dq offset __pyx_pymod_exec_test
.data:000000000020EE00                 dq 0
.data:000000000020EE08                 dq 0
.data:000000000020EE10                 dq 0
.data:000000000020EE18                 dq 0

第二个函数就是。

解决PyTuple_New()函数传参判定出问题

修改PyTuple_New()的函数原型为

1
_QWORD *PyTuple_New(_QWORD, ...)

即可。第一个参数是元组的容量。后面三个点代表有可能会传入多余的PyObject*作为初始化。

向PyTupleObject传入数据

如上，若PyTuple_New是只传入了初始化容量，那么后面还需要程序再次传入参数才行。

给一个2参数的元组：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
v82 = PyTuple_New((int)v78 + 2);	// 一个参数，作为容量
v23 = (__int64)v82;
if ( !v82 )
{
  v17 = 0LL;
  v14 = 0LL;
  v18 = 0LL;
  v15 = 0LL;
  v13 = 1880;
  goto LABEL_415;
}
if ( judge )
  v82[3] = judge;
v83 = v82;
++*(_QWORD *)v94;
v84 = &v82[v78];
v84[3] = v94;	// tuple[0]
++*w;
v84[4] = w;  	// tuple[1]

只要看到取值从[3]开始的，就是传参了。[3]对应元组第一个参数，往后类推。

确定函数调用

全都内联了，又臭又长。

这么长，全是PyObject_Call的内联形式。

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
  if ( (_UNKNOWN *)v9[1] == &PyMethod_Type )	// 是method函数
  {
    judge = (_QWORD *)v9[3];
    if ( judge )
    {
      v79 = (_QWORD *)v9[2];
      ++*judge;
      ++*v79;
      v11 = (*v9)-- == 1LL;
      if ( v11 )
        qword_20FAB0(v9);
      v9 = v79;
      v78 = 1LL;
    }
  }
  v80 = (void *)v9[1];
  v81 = (int)v78 + 2;
  if ( v80 == &PyFunction_Type )	// 是一般函数
  {
    nbit = judge;
    dbit = v94;
    v158 = w;
    v15 = (__int64 *)_Pyx_PyFunction_FastCallDict_constprop_29(v9, &dbit - v78, v81);
    if ( !v15 )
    {
      v17 = 0LL;
      v14 = 0LL;
      v23 = 0LL;
      v18 = 0LL;
      v13 = 1866;
      goto LABEL_415;
    }
    goto LABEL_278;
  }
  if ( v80 != &PyCFunction_Type || (*(_DWORD *)(v9[2] + 16LL) & 0xFFFFFF8D) != 128 )
  {
    v82 = PyTuple_New((int)v78 + 2);
    v23 = (__int64)v82;
    if ( !v82 )
    {
      v17 = 0LL;
      v14 = 0LL;
      v18 = 0LL;
      v15 = 0LL;
      v13 = 1880;
      goto LABEL_415;
    }
    if ( judge )
      v82[3] = judge;
    v83 = v82;
    ++*(_QWORD *)v94;
    v84 = &v82[v78];
    v84[3] = v94;
    ++*w;
    v84[4] = w;                                 // inverse(p3 , u * v)
    judge = (_QWORD *)_Pyx_PyObject_Call_constprop_30(v9, v83);
    if ( judge )	// call 1个参数，但是这个参数是个2数据元组。
    {
      v11 = (*(_QWORD *)v23)-- == 1LL;
      if ( v11 )
        (*(void (__fastcall **)(__int64))(*(_QWORD *)(v23 + 8) + 48LL))(v23);
      goto LABEL_280;
    }
    v17 = 0LL;
    v14 = 0LL;
    v18 = 0LL;
    v15 = 0LL;
    v13 = 1891;
LABEL_415:
    v16 = 24LL;
not:
    if ( v9 )
    {
      v11 = (*v9)-- == 1LL;
      if ( v11 )
      {
        v151 = v16;
        (*(void (__fastcall **)(_QWORD *))(v9[1] + 48LL))(v9);
        v16 = v151;
        v18 = 0LL;
        v17 = 0LL;
      }
    }
    goto LABEL_432;
  }

  nbit = judge;
  dbit = v94;
  v158 = w;				// FastCall
  v15 = (__int64 *)_Pyx_PyCFunction_FastCall(v9, &dbit - v78, v81);
  if ( !v15 )
  {
    v17 = 0LL;
    v14 = 0LL;
    v23 = 0LL;
    v18 = 0LL;
    v13 = 1874;
    goto LABEL_415;
  }

关于如何确定调用函数时的传参：

  1. 首先第一个参数通常都是函数指针，交叉引用在上方找到此函数指针，点进去看看这个函数要什么参数。
  2. 找(_QWORD *)_Pyx_PyObject_Call_constprop_30(v9, v83);这类传入一个元组参数的调用函数，然后通过上面确定元组元素的方法来确定。

学会运用交叉引用确定变量

Cython代码又臭又长，有的变量隔了五六百行才被调用，所以需要学会交叉引用。

在伪代码上交叉引用：按行排序从上到下，寻找距离本行较近，且是数据写入w的行，且不能处在错误处理行中。

错误处理：

1
2
3
4
5
6
7
8
9
10
v15 = (__int64 *)_Pyx_PyCFunction_FastCall(v9, &dbit - v78, v81);
if ( !v15 )
{
  v17 = 0LL;
  v14 = 0LL;
  v23 = 0LL;
  v18 = 0LL;
  v13 = 1874;
  goto LABEL_415;
}

有时由于反汇编生成goto语句，所以可能出现向上跳转。从而按行排序没法找到正确赋值语句。所以还需要从汇编上看。

从汇编CFG上交叉引用：

比如查：

1
v14 = (_QWORD *)PyNumber_FloorDivide(v9, w);

汇编：

1
2
3
mov     rsi, [rsp+0D8h+var_C8]
mov     rdi, r13
call    _PyNumber_FloorDivide

则交叉引用[rsp+0D8h+var_C8]，寻找w写入且距离最近的代码，即可（）。

都不行，就看CFG，看前驱块有没有赋值。

比如往上翻翻找到

1
2
3
4
5
6
7
8
mov     rsi, cs:__pyx_int_1
mov     rdi, rax
mov     [rsp+0D8h+var_C0], rax
call    __Pyx_PyInt_SubtractObjC_isra_9_constprop_33
test    rax, rax
mov     r13, rax
mov     r10, [rsp+0D8h+var_C0]
jz      loc_AC71

即可确定。

删除冗余代码

IDA里面不给删代码，但是自己可以复制一下伪代码，贴到某个.cpp文件，用VS Code打开，然后慢慢删去一些无用代码。比如错误处理，一些函数指针调用等。

比如

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
else
{
  v11 = (*v9)-- == 1LL;
  if ( v11 )
    (*(void (__fastcall **)(_QWORD *))(v9[1] + 48LL))(v9);
  if ( !v75 )
  {
    v138 = w;
    goto LABEL_309;
  }
  v15 = (__int64 *)PyNumber_Multiply(v134, v130);// (p*q+1)*(p2*q2+1)
  if ( !v15 )
  {
    v128 = v14;
    v17 = 0LL;
    v18 = 0LL;
    v129 = v71;
    v14 = 0LL;
    v115 = judge;
    v13 = 1967;
    v16 = 28LL;
    goto LABEL_438;
  }

其中

1
2
3
v11 = (*v9)-- == 1LL;
if ( v11 )
  (*(void (__fastcall **)(_QWORD *))(v9[1] + 48LL))(v9);
1
2
3
4
5
6
7
8
9
10
11
12
if ( !v15 )
{
  v128 = v14;
  v17 = 0LL;
  v18 = 0LL;
  v129 = v71;
  v14 = 0LL;
  v115 = judge;
  v13 = 1967;
  v16 = 28LL;
  goto LABEL_438;
}

都是没用的。

确定传参

在exec函数中使用PyCFunction_New声明的函数没法确定传参。

但是点进函数进去，看开头：

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
_QWORD *__fastcall _pyx_pw_4test_1keygen(__int64 a1, _QWORD *a2, __int64 a3)
{ // ......
{
LABEL_14:
        if ( v6 > 0 && (int)_Pyx_ParseOptionalKeywords_constprop_27(a3, _pyx_pyargnames_14180, &nbit, v3, "keygen") < 0 )
        {
          v7 = 1390LL;
          goto LABEL_488;
        }
        goto LABEL_19;
      }
LABEL_12:
      --v6;
      dbit = _PyDict_GetItem_KnownHash(a3, _pyx_n_s_dbit, *(_QWORD *)(_pyx_n_s_dbit + 24));
      if ( !dbit )
      {
        _Pyx_RaiseArgtupleInvalid_constprop_31("keygen", 1LL);
        v7 = 1386LL;
LABEL_488:
        v91 = 0LL;
        _Pyx_AddTraceback(&unk_BB9C, v7, 9LL, "test.py");
        return v91;
      }
      goto LABEL_14;
    }
    v6 = v5 - 1;
    nbit = (_QWORD *)_PyDict_GetItem_KnownHash(a3, _pyx_n_s_nbit, *(_QWORD *)(_pyx_n_s_nbit + 24));
    if ( nbit )
      goto LABEL_12;
LABEL_487:
    _Pyx_RaiseArgtupleInvalid_constprop_31("keygen", a2[2]);
    v7 = 1403LL;
    goto LABEL_488;
  }

其中PyDict_GetItem_KnownHash可以作为传参确定点。从a3取值。

后话

是空白在0x401知识星球上发的题目。已经有wp了。本题据说是有密码大手子找到原题脚本了。否则像我这样慢慢恢复真的很麻烦。

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia-plus根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

A junior undergraduate
studying in the college of cyber science and engineering
in Sichuan University
in Sichuan , China.
Pronouns:He/him.
A core member of 0x401 CTF team
majorly focus on Reverse Engineering chanllenges.