-
-
看雪 2023 KCTF 年度赛 第五题 争分夺秒 解题过程(模逆元素)
-
发表于: 2023-9-12 00:00 8670
-
静态看,程序主要是大量加花了,
不过经过仔细查看,原有正常指令没有任何变形,还是非常能看的状态。
于是直接带花分析。
分析技巧:
根据ReadMe.txt与main函数可知,程序通过argv[1]取得序列号输入。
出现有几处如下代码,可能是暗坑。
inside_dbg(ea=0x402220)里面有两个函数做调试器检测。
不管三七二十一,直接静态patch掉调试器判断,
使得inside_dbg始终返回0。
第一组小整数方程 32bit整数
与
直接for循环枚举出结果
并且有意确认了这里是否会出现多个解
很快出结果:
默认取最小整数解,继续向下动静结合分析。
关键日志断点,
主要关注BN_mul与BEF MID AFT 3轮异或处理。
如下:
搜索得到一个可用的在线求解网站:https://www.dcode.fr/modular-inverse。
x1求解:
x2求解:
求解到大整数方程的解之后,通过python脚本处理好前期步骤。
代码如下,以下脚本python3可以直接运行,输出flag。
不过,编写过程需要与后面辅助异或的C代码交替配合。
脚本输出flag为引号内base64字符串:
修改程序命令行,进行验证,程序提示OK。
提交到网站,显示答对。
由C代码辅助实现。
题目作者非常仁慈,用了一对小整数方程来引导做题。
终于不至于“打算来完完题,结果被题玩了”。
if
( inside_dbg() )
{
if
( (
*
Block &
1
) !
=
0
)
*
Block
+
=
rand()
%
3
+
1
;
else
*
Block
+
=
rand()
%
4
+
4
;
}
if
( inside_dbg() )
{
if
( (
*
Block &
1
) !
=
0
)
*
Block
+
=
rand()
%
3
+
1
;
else
*
Block
+
=
rand()
%
4
+
4
;
}
n
=
0x346F8717i64
;
a
=
0x7D45i64
;
求解x使得 a
*
x
%
n
=
1
;
n
=
0x346F8717i64
;
a
=
0x7D45i64
;
求解x使得 a
*
x
%
n
=
1
;
a
=
0xD711i64
;
n
=
0x729969FFi64
;
求解x使得 a
*
x
%
n
=
1
;
a
=
0xD711i64
;
n
=
0x729969FFi64
;
求解x使得 a
*
x
%
n
=
1
;
printf(
"A = \n"
);
unsigned
long
long
n
=
0x346F8717i64
;
unsigned
long
long
a
=
0x7D45i64
;
for
(unsigned
int
i
=
0
; i <
-
1
;
+
+
i)
{
unsigned
long
long
x
=
i;
if
(a
*
x
%
n
=
=
1
)
{
printf(
"0x%x\n"
, i);
}
}
printf(
"\nB = \n"
);
a
=
0xD711i64
;
n
=
0x729969FFi64
;
for
(unsigned
int
i
=
0
; i <
-
1
;
+
+
i)
{
unsigned
long
long
x
=
i;
if
(a
*
x
%
n
=
=
1
)
{
printf(
"0x%x\n"
, i);
}
}
printf(
"A = \n"
);
unsigned
long
long
n
=
0x346F8717i64
;
unsigned
long
long
a
=
0x7D45i64
;
for
(unsigned
int
i
=
0
; i <
-
1
;
+
+
i)
{
unsigned
long
long
x
=
i;
if
(a
*
x
%
n
=
=
1
)
{
printf(
"0x%x\n"
, i);
}
}
printf(
"\nB = \n"
);
a
=
0xD711i64
;
n
=
0x729969FFi64
;
for
(unsigned
int
i
=
0
; i <
-
1
;
+
+
i)
{
unsigned
long
long
x
=
i;
if
(a
*
x
%
n
=
=
1
)
{
printf(
"0x%x\n"
, i);
}
}
A
=
0x3153622a
0x65c2e941
0x9a327058
0xcea1f76f
B
=
0x4372a49d
0xb60c0e9c
A
=
0x3153622a
0x65c2e941
0x9a327058
0xcea1f76f
B
=
0x4372a49d
0xb60c0e9c
a1
2865244763
n1
13407712312341506807290785620513810006013432881349817380059896195876647865383040511615194818142561216049323742693301651262826523009904773019126031607880381917510353811872243158275
求解x使得 a1
*
x
%
n1
=
1
a1
2865244763
n1
13407712312341506807290785620513810006013432881349817380059896195876647865383040511615194818142561216049323742693301651262826523009904773019126031607880381917510353811872243158275
求解x使得 a1
*
x
%
n1
=
1
a2
=
2207598431
n2
=
11504884415388796500219489938877037570907236266221216736789242959943502559932358261444533399595441834388023078747736743001176901105009843107005500447845023069935116586106537423621
求解x使得 a2
*
x
%
n2
=
1
a2
=
2207598431
n2
=
11504884415388796500219489938877037570907236266221216736789242959943502559932358261444533399595441834388023078747736743001176901105009843107005500447845023069935116586106537423621
求解x使得 a2
*
x
%
n2
=
1
from
binascii
import
*
from
base64
import
*
import
zlib
from
struct
import
*
# 在线网站 解出来的x1
x1
=
6956654053800499230326290699174323596088081767147313465648406350971187122655244055152548005625866216241904992654364553316321828514212984633351921722043990261110066970542167578377
# 把在线网站求解出来的大整数 打印成C语言字节数组 然后复制到C代码中,做异或处理
def
do_x(x1):
print
(
'='
*
32
)
hx1
=
hex
(x1)
print
(hx1)
x1bs
=
bytes(
reversed
(unhexlify(hx1.lstrip(
'0x'
))))
print
(
'x1 c arr'
,
', '
.join(
'0x{:X}'
.
format
(b)
for
b
in
x1bs))
print
(
'x1 len'
,
len
(x1bs))
print
(
'x1'
, hexlify(x1bs))
print
(
'='
*
32
)
do_x(x1)
# 在线网站 解出来的x2
x2
=
6030658962721950361155533835702172940609579189992003760553378343560660612412076910216892955114510943618804706539422649399614037254978869753190882492376528406540173851407196912984
do_x(x2)
# 由C代码处理了3轮异或之后的x1
x1bef
=
"F550C4D11BE88545A17EDF49A600D30212A17760F814F054F252F5FAC9E3C915B1195D9F2D52F3BBD2CB5690982C85DFBCA0C4102132CFF25E4740F3C9C71174802C59A7FAF98DAEBC52"
# 由C代码处理了3轮异或之后的x2
x2bef
=
"54449BC8E9713A6F2DE69ACCEADB2BB55F550294D7F4D887D561C858C12D74AA218E45766D0799391A8C617F5E3FB00FD4995E9E5077100721858261A223FB4773736CE6027275E7A9EC"
# 输入字节的hex
h
=
(
"""
2a 62 53 31 """
+
'{:X}'
.
format
(
74
)
+
"""00 00 00"""
+
x1bef
+
"""
9d a4 72 43 """
+
'{:X}'
.
format
(
74
)
+
""" 00 00 00 """
+
x2bef
+
"""
"""
)
print
(
'h'
, h)
h
=
h.replace(
'\n'
, '
').replace('
', '
').replace('
_
', '
')
bs
=
unhexlify(h)
b64
=
b64encode(bs
+
pack(
'<I'
, zlib.crc32(bs)))
# 这个输出的就是flag
print
(
'b64'
, b64, end
=
'\n\n'
);
# 把日志断点输出大整数hex转成大整数
def
to_bn(s):
return
int
(hexlify(bytes(
reversed
(unhexlify(s)))),
16
)
a
=
to_bn(
'5B2AC8AA000000000000000000000000'
)
x
=
to_bn(
'CF43F9DBE60000000000000000000000'
)
p
=
to_bn(
'95107386EB9395029A00000000000000'
)
# 验证代码:确认一下那个函数是大整数乘法
print
(
'{:X}'
.
format
(a))
print
(
'{:X}'
.
format
(x))
print
(
'{:X}'
.
format
(p))
print
(a
*
x
=
=
p)
p
=
to_bn(
'95107386EB9395029A00000000000000'
)
n
=
to_bn(
'038DB6BBBD8ADB73AC572C605199E6ECAE5698E1D456BA9F902BF6509F1D23918E28AFB9A4C506C77DAA288EBE4012337E761796CE3B482E832E2C79A4E3410DA3D18E58C0ABD6B8C1D3'
)
m
=
p
%
n
print
(
'{:X}'
.
format
(m))
# 把第一个大整数方程的a跟n 打印成10进制整数,然后手工复制到网站上 求解
print
(
'a1'
, a)
print
(
'n1'
, n)
n
=
to_bn(
'05B34498B0EF11F7EB3B978CA2FB6D6A5917C6A1988B9C21D48906ECCF8DE77430833788B46C7A2E3D91505E25D18FEF12785BAF3DBAB8EC5F3DFC7B375B2D725CEC122C5957AF41B4B5'
)
a
=
to_bn(
'5F479583000000000000000000000000'
)
# 把第二个大整数方程的a跟n 打印成10进制整数,然后手工复制到网站上 求解
print
(
'a2'
, a)
print
(
'n2'
, n)
from
binascii
import
*
from
base64
import
*
import
zlib
from
struct
import
*
# 在线网站 解出来的x1
x1
=
6956654053800499230326290699174323596088081767147313465648406350971187122655244055152548005625866216241904992654364553316321828514212984633351921722043990261110066970542167578377
# 把在线网站求解出来的大整数 打印成C语言字节数组 然后复制到C代码中,做异或处理
def
do_x(x1):
print
(
'='
*
32
)
hx1
=
hex
(x1)
print
(hx1)
x1bs
=
bytes(
reversed
(unhexlify(hx1.lstrip(
'0x'
))))
print
(
'x1 c arr'
,
', '
.join(
'0x{:X}'
.
format
(b)
for
b
in
x1bs))
print
(
'x1 len'
,
len
(x1bs))
print
(
'x1'
, hexlify(x1bs))
print
(
'='
*
32
)
do_x(x1)
# 在线网站 解出来的x2
x2
=
6030658962721950361155533835702172940609579189992003760553378343560660612412076910216892955114510943618804706539422649399614037254978869753190882492376528406540173851407196912984
do_x(x2)
# 由C代码处理了3轮异或之后的x1
x1bef
=
"F550C4D11BE88545A17EDF49A600D30212A17760F814F054F252F5FAC9E3C915B1195D9F2D52F3BBD2CB5690982C85DFBCA0C4102132CFF25E4740F3C9C71174802C59A7FAF98DAEBC52"
# 由C代码处理了3轮异或之后的x2
x2bef
=
"54449BC8E9713A6F2DE69ACCEADB2BB55F550294D7F4D887D561C858C12D74AA218E45766D0799391A8C617F5E3FB00FD4995E9E5077100721858261A223FB4773736CE6027275E7A9EC"
# 输入字节的hex
h
=
(
"""
2a 62 53 31 """
+
'{:X}'
.
format
(
74
)
+
"""00 00 00"""
+
x1bef
+
"""
9d a4 72 43 """
+
'{:X}'
.
format
(
74
)
+
""" 00 00 00 """
+
x2bef
+
"""
"""
)
print
(
'h'
, h)
h
=
h.replace(
'\n'
, '
').replace('
', '
').replace('
_
', '
')
bs
=
unhexlify(h)
b64
=
b64encode(bs
+
pack(
'<I'
, zlib.crc32(bs)))
# 这个输出的就是flag
print
(
'b64'
, b64, end
=
'\n\n'
);
# 把日志断点输出大整数hex转成大整数
def
to_bn(s):
return
int
(hexlify(bytes(
reversed
(unhexlify(s)))),
16
)
a
=
to_bn(
'5B2AC8AA000000000000000000000000'
)
x
=
to_bn(
'CF43F9DBE60000000000000000000000'
)
p
=
to_bn(
'95107386EB9395029A00000000000000'
)
# 验证代码:确认一下那个函数是大整数乘法
print
(
'{:X}'
.
format
(a))
print
(
'{:X}'
.
format
(x))
print
(
'{:X}'
.
format
(p))
print
(a
*
x
=
=
p)
p
=
to_bn(
'95107386EB9395029A00000000000000'
)
n
=
to_bn(
'038DB6BBBD8ADB73AC572C605199E6ECAE5698E1D456BA9F902BF6509F1D23918E28AFB9A4C506C77DAA288EBE4012337E761796CE3B482E832E2C79A4E3410DA3D18E58C0ABD6B8C1D3'
)
m
=
p
%
n
print
(
'{:X}'
.
format
(m))
[招生]科锐逆向工程师培训(2024年11月15日实地,远程教学同时开班, 第51期)
赞赏
他的文章
看原图
赞赏
雪币:
留言: