首页
论坛
课程
招聘
[原创]KCTF2022秋季赛第二题分析(4qwerty7)
2022-11-18 05:54 4401

[原创]KCTF2022秋季赛第二题分析(4qwerty7)

2022-11-18 05:54
4401

简单分析可知此题采用了高精度计算,且高精度数值的结果为:

1
2
3
4
5
6
7
00000000 Number          struc ; (sizeof=0x24, mappedto_20)
00000000                                         ; XREF: .data:numA/r
00000000                                         ; .data:numB/r ...
00000000 len             dd ?
00000004 data            db 32 dup(?)            ; XREF: num_mul_s+1AF/r
00000004                                         ; num_mul_s+1B9/r ...
00000024 Number          ends

IDA 阅读反编译结果可知,其函数列表_main之前的函数分别为(其中s代码有额外代码):

 

parse_number
init_number_by_int
copy_num
num_cmp_s
num_add_s
num_sub_s
num_and_s
num_or_s
num_xor_s
num_mul_s
num_div_s
num_mod_s
number_mod
num_lshift
num_rshift

 

于是 Python 还原主程序代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def check(A, B, C):
    fit = 0
    D = E = 0
    round_id = 0
    while True:
        round_id += 1
        D += A
        E += B
        D %= C
        E %= C
        F = D - 1
        if F == A:
            fit += 1
            F *= A
        G = E + 1
        if G == B:
            fit += 1
            G = C / B
        if fit == 10:
            return True
        if round_id >= 0x200000
            return False

这段代码fit显然很难大于2,考虑看高精度里夹杂的代码,这些代码翻译如下:

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
# logic in cmp
F = 4
if  G % round_id == 1:
    G = F >> round_id
    F % fit
 
# logic in add T
if  G % round_id == 4:
    G = F >> round_id
    F % fit
 
# logic in sub T
if  C % round_id == 4:
    G % fit
    G >>= round_id
 
# logic in and
G = E | A
if round_id % 2 == 1 and G > F:
    F <<= round_id
    F % fit
if G % round_id == maxSrcLen:
    F = E % fit
 
# logic in or
F = D ^ A
if round_id % 2 == 0 and G == F:
    G = F % round_id
    F >>= fit
    G &= C
if fit > 0 and F == G:
    F >>= round_id
    F % fit
    F <<= round_id
 
# logic in xor
if fit > 0:
    F = 4
    if G % round_id == 1:
        G = F >> round_id
        F % fit
 
# logic in mul
F = 4
G = F << 3
if fit > 0 and C[G[0]]==G[0]:
    F += G
    C[F[0]] += 4
    F <<= F % round_id
    G = F - G
 
# logic in div
F = 4
G = F << 3 # 32
if fit > 0 and C[G[0]]==G[0]: # round_id==32
    F += G # 32+4
    C[F[0]] += 4 # fit += 4
    F <<= F % round_id
    G = F - G
 
# logic in mod
F = D & E
if F > G and fit > 0:
    F >>= round_id
    G = A + B
    F -= G

注意到 F 和 G 在主程序中被读前都会跟着被写,因此上述代码中对 F、G 的都写都是无用的(唯一可能有影响的是加法,但是由于 G % round_id == 4 导致条件恒不成立(此时G==1))。

 

注意到匹配才会触发的乘除法中的特殊逻辑,容易发现C[G[0]]与C[F[0]]都是越界访问,实际访问的是 round_id 和 fit,因此只要让原本两个 fit += 1 的条件在 round_id == 32 的时候触发就能满足全部条件。

 

为此,编写如下程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
alphabet = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'
def parse_num(x):
    ans = 0
    for v in x[::-1]:
        ans *= len(alphabet)
        ans += alphabet.index(v)
    return ans
 
def to_str(x):
    s = ''
    while x > 0:
        s += alphabet[x % len(alphabet)]
        x //= len(alphabet)
    return s
 
from gmpy2 import *
C = parse_num('IRtzloZ6iuB')
A = int(invert(31, C))
B = A*(C-1)%C
 
assert A < B < C
 
print(to_str(A) + '-' + to_str(B))

输出 ZSxZerX4xb4-jyvP7x12lI7 验证发现正确。


[2022冬季班]《安卓高级研修班(网课)》月薪两万班招生中~

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