![]()
-
-
[原创]KCTF2022秋季赛第二题分析(4qwerty7)
-
9小时前
151
-
[原创]KCTF2022秋季赛第二题分析(4qwerty7)
简单分析可知此题采用了高精度计算，且高精度数值的结果为：
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 | F = 4
if G % round_id == 1:
G = F >> round_id
F % fit
if G % round_id == 4:
G = F >> round_id
F % fit
if C % round_id == 4:
G % fit
G >>= round_id
G = E | A
if round_id % 2 == 1 and G > F:
F <<= round_id
F % fit
if G % round_id == maxSrcLen:
F = E % fit
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
if fit > 0:
F = 4
if G % round_id == 1:
G = F >> round_id
F % fit
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
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
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冬季班]《安卓高级研修班(网课)》月薪两万班招生中～
文章来源: https://bbs.pediy.com/thread-275219.htm
如有侵权请联系:admin#unsafe.sh