警告
本文最后更新于 2022-03-31，文中内容可能已过时。
给了源代码:
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
| flag = '[test]'
hflag = flag.encode('hex')
iflag = int(hflag[2:], 16)
def polinom(n, m):
i = 0
z = []
s = 0
while n > 0:
if n % 2 != 0:
z.append(2 - (n % 4))
else:
z.append(0)
n = (n - z[i])/2
i = i + 1
z = z[::-1]
l = len(z)
for i in range(0, l):
s += z[i] * m ** (l - 1 - i)
return s
i = 0
r = ''
while i < len(str(iflag)):
d = str(iflag)[i:i+2]
nf = polinom(int(d), 3)
r += str(nf)
i += 2
print(r)
# 242712673639869973827786401934639193473972235217215301
|
可以看出是 10 进制 flag 每两位传入 polinom, 考虑直接打表开爆:
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
| import binascii
from pprint import pprint
def polinom(n, m):
i = 0
z = []
s = 0
while n > 0:
if n % 2 != 0:
z.append(2 - (n % 4)) # odd -> 1 or -1
else:
z.append(0) # even -> 0
n = (n - z[i]) // 2
i = i + 1
z = z[::-1]
l = len(z)
for i in range(0, l):
s += z[i] * m ** (l - 1 - i) # z_{l-1}*m^{l-1} + z_{l-2}*m^{l-2} + ... + z_0
return s
ftable = {i : polinom(i, 3) for i in range(100)}
re_ftable = {v : k for k, v in ftable.items()}
cipher = '242712673639869973827786401934639193473972235217215301'
num = ''
n = 0
while n < len(cipher):
for i in range(4, 0, -1):
t = int(cipher[n : n + i], 10)
try:
lala = str(re_ftable[t])
if len(lala) == 1:
lala = '0' + lala
num += lala
n += i
break
except KeyError:
continue
print(num)
|
注意最后一位可能是 1 个数, 也可能是 2 个数, 那只需要挨个去试一下就好了
题目使用了 cython 中的 cythonize 功能将 python 转译成 c 的实现, 然后再编译出共享目标文件.
具体而言, 将文件拖进 IDA, 通过 Strings Window 可以发现不少位于 rodata 段的 python 字符串, 即 __pyx_string_tab, 并且通过 xref 可以定位到关键函数 _pyx_pymod_exec_test. 里面首先检查了一下 python 版本为 3.6, 大概知道意思就不用扣细节了, 因为有很多不太重要的边界检查之类的操作.
下面是 import 一些模块:
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
| // from Crypto.Util.number import *
v29 = (__int64 *)_Pyx_Import_constprop_24(_pyx_n_s_Crypto_Util_number, v8);
// from math import gcd
v62 = _pyx_n_s_gcd;
v63 = (__int64 *)v29[3];
++*(_QWORD *)_pyx_n_s_gcd;
*v63 = v62;
v8 = (__int64 *)_Pyx_Import_constprop_24(_pyx_n_s_math, v29);
// from flag import FLAG
v29 = (__int64 *)_Pyx_Import_constprop_24(_pyx_n_s_flag, v8);
if ( !v29 ) // 很多这种异常处理，其实可以就不看也没啥关系
{
v59 = 0LL;
v60 = 0LL;
v178 = 0LL;
v176 = 7;
v177 = 2865;
goto LABEL_158;
}
v44 = (*v8)-- == 1;
if ( v44 )
(*(void (__fastcall **)(__int64 *))(v8[1] + 48))(v8);
v67 = _Pyx_ImportFrom(v29, _pyx_n_s_FLAG);
|
下面的 _pyx_d 是一个全局字典, 可以通过它去索引一般的 PyObject:
1
| PyDict_SetItem(_pyx_d, _pyx_n_s_gcd, v64)
|
然后设置了两个 CyFunction 分别是 keygen 和 encrypt:
1
2
3
4
5
6
7
8
9
10
11
12
13
| v68 = _Pyx_CyFunction_New_constprop_22(
&_pyx_mdef_4test_1keygen,
_pyx_n_s_keygen,
_pyx_n_s_test,
_pyx_d,
_pyx_codeobj__3);
v69 = _Pyx_CyFunction_New_constprop_22(
&_pyx_mdef_4test_3encrypt,
_pyx_n_s_encrypt,
_pyx_n_s_test,
_pyx_d,
_pyx_codeobj__5);
|
然后是设置一些变量的值:
1
2
3
4
5
6
7
8
| // nbit = 1024 dbit = 256
v29 = (__int64 *)_pyx_int_1024;
v8 = (__int64 *)_pyx_int_256;
v70 = _pyx_n_s_nbit;
v71 = _pyx_d;
++*(_QWORD *)_pyx_int_1024;
++*v8;
if ( (int)PyDict_SetItem(v71, v70, v29) < 0 )
|
下面的内容其实也大同小异, 直接给出大概的翻译结果:
1
2
3
4
5
6
7
8
9
| e, n1, n2 = keygen(dbit, nbit)
FLAG = long(FLAG.encode("utf-8").hex(), 16)
c1 = encrypt(FLAG, (e, n1))
c2 = encrypt(FLAG, (e, n2))
print(f'e = {e}')
print(f'n1 = {n1}')
print(f'n2 = {n2}')
print(f'enc1 = {c1}')
print(f'enc2 = {c2}')
|
参数是两个:
1
2
| v22 = _PyDict_GetItem_KnownHash(a3, _pyx_n_s_msg, *(_QWORD *)(_pyx_n_s_msg + 24));
v23 = (_QWORD *)_PyDict_GetItem_KnownHash(a3, _pyx_n_s_pubkey, *(_QWORD *)(_pyx_n_s_pubkey + 24));
|
其中 pubkey 是一个二元组，然后关键在于:
1
| v14 = (_QWORD *)PyNumber_Power(v8, v11, v12);
|
大概能看到是一个比较常规的 rsa 加密过程, 所以:
1
2
| def encrypt(msg, pubkey : tuple):
return pow(msg, pubkey[0], pubkey[1])
|
同样是两个参数 dbit 和 nbit, 分析流程和上述大概相同, 就是长了很多, 并且多次用到了前一千行处赋值的变量, 尽量多给变量重命名可以提升一点点效率 XD:
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
| def keygen(nbit, dbit):
if dbit * 2 < nbit:
while True:
p = getRandomNBitInteger(dbit)
q = getRandomNBitInteger(nbit // 2 - dbit)
if isPrime(q * p + 1):
break
while True:
p2 = getRandomNBitInteger(dbit)
q2 = getRandomNBitInteger(nbit // 2 - dbit)
if isPrime(p * q2 + 1) and isPrime (p2 * q2 + 1):
break
while True:
while True:
p3 = getRandomNBitInteger(dbit)
if gcd(p * q * p2 * q2, p3) == 1:
break
u = p * q
v = p2 * q2
if not isPrime(((inverse(u * v, p3) * p3 - 1) // (u * v)) * q + 1):
continue
return p3, (p * q + 1) * (p2 * q2, 1), (p * q2 + 1) * (((inverse(u * v, p3) * p3 - 1) // (u * v)) * q + 1)
|
要求输入一个 public key 和一个 serial key, 关键明显在于 verify_serial 中, 我们期望它返回 1.
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
| while ( 1 )
{
v15 = std::string::find(a2, v17, 0LL); // find "-" in serial key
if ( v15 == -1 )
break;
++v13;
if ( v15 != 3 )
{
v18 = 0;
v12 = 1;
goto LABEL_12;
}
std::string::substr(v11, a2, 0LL, 3LL);
std::string::operator=(v14, v11);
std::string::~string(v11);
std::string::basic_string(subStr, v14);
v2 = idx++;
v8 = (char *)std::string::at(a1, v2);
v7 = !verify_char((__int64)subStr, *v8);
std::string::~string(subStr);
if ( v7 )
{
v18 = 0;
v12 = 1;
goto LABEL_12;
}
v6 = v15;
v3 = std::string::length(v17);
std::string::erase(a2, 0LL, v3 + v6);
}
|
一个主循环, 大意是 serial key 是被 - 分割开的, 我们将每组 split 后的结果连同 public key 的一个字符传入 verify_char 函数.
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
| _BOOL8 __fastcall verify_char(__int64 a1, char a2)
{
const char *v2; // rax
int v3; // eax
unsigned __int64 v5; // [rsp+0h] [rbp-20h]
unsigned __int64 v6; // [rsp+8h] [rbp-18h]
signed __int64 v7; // [rsp+10h] [rbp-10h]
v2 = (const char *)std::string::c_str(a1);
v7 = strtol(v2, 0LL, 16);
v6 = fib(v7); // fib_{n+1} / 0x64
v5 = v6;
do
{
do
--v5;
while ( !check_arm(v5) );
}
while ( (unsigned int)notused(v5) || v5 > 0x10E47F4C575565LL );
// v5 cannot be reused
// v5 <= 0x10E47F4C575565
if ( v7 < 100 )
return 0;
if ( !(unsigned int)isprint(a2) ) // printable
return 0;
v3 = UN++;
used[v3] = v5;
return v5 && v6 && v5 != v6 && (v6 - v5) % 0x64 == a2;
}
|
约束大概是这么几条:
- v5 必须是
countSetBits 之后返回奇数 - v5 不能重复
- v5 必须小于等于 0x10E47F4C575565
- v2 必须是 printable 字符
- 然后 fib(x) - v5 % 0x64 == a2
keygen 也不是特别难写, 枚举一下就好了. 虽然远程环境连不上了不知道对不对:
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
| #include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
__uint128_t fib(__uint128_t n) {
__uint128_t v5[0x1000] = {0};
v5[0] = 0;
v5[1] = 1;
for (int i = 2; i <= n; i++) {
v5[i] = v5[i - 1] + v5[i - 2];
}
return v5[n] / 0x64;
}
int64_t countSetBits(int64_t x) {
uint32_t v2;
v2 = 0;
while ( x ) {
x &= x - 1;
++v2;
}
return v2;
}
bool check_arm(uint64_t v5) {
return (countSetBits(v5) & 1) == 1;
}
void filter(int64_t *v5) {
do {
--*v5;
} while(!check_arm(*v5));
return ;
}
int main() {
int64_t v5 = 0x10E47F4C575565;
int serial_key[100];
char public_key[20];
for (int i = 0; i < 20; i++) {
filter(&v5);
for (int j = 100; j < 114514; j++) {
int64_t maybe = (fib(j) - v5) % 0x64;
if (maybe > 0x20) {
serial_key[i] = j;
public_key[i] = maybe;
break;
}
}
}
printf("public key: ");
for (int i = 0; i < 20; i++) {
printf("%c", public_key[i]);
}
printf("\n");
printf("serial key: ");
for (int i = 0; i < 19; i++) {
printf("%03x-", serial_key[i]);
}
printf("bss\n");
return 0;
}
|