-
-
看雪 2023 KCTF 年度赛 第五题 争分夺秒 解题过程（模逆元素）
-
发表于: 2023-9-12 00:00
-
静态看，程序主要是大量加花了，
不过经过仔细查看，原有正常指令没有任何变形，还是非常能看的状态。
于是直接带花分析。
分析技巧：
根据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 =
0x3153622a0x65c2e9410x9a3270580xcea1f76fB =
0x4372a49d0xb60c0e9cA =
0x3153622a0x65c2e9410x9a3270580xcea1f76fB =
0x4372a49d0xb60c0e9ca1 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 *
# 在线网站 解出来的x1x1 = 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)# 在线网站 解出来的x2x2 = 6030658962721950361155533835702172940609579189992003760553378343560660612412076910216892955114510943618804706539422649399614037254978869753190882492376528406540173851407196912984
do_x(x2)# 由C代码处理了3轮异或之后的x1x1bef = "F550C4D11BE88545A17EDF49A600D30212A17760F814F054F252F5FAC9E3C915B1195D9F2D52F3BBD2CB5690982C85DFBCA0C4102132CFF25E4740F3C9C71174802C59A7FAF98DAEBC52"
# 由C代码处理了3轮异或之后的x2x2bef = "54449BC8E9713A6F2DE69ACCEADB2BB55F550294D7F4D887D561C858C12D74AA218E45766D0799391A8C617F5E3FB00FD4995E9E5077100721858261A223FB4773736CE6027275E7A9EC"
# 输入字节的hexh = ("""
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)))
# 这个输出的就是flagprint('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 *
# 在线网站 解出来的x1x1 = 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)# 在线网站 解出来的x2x2 = 6030658962721950361155533835702172940609579189992003760553378343560660612412076910216892955114510943618804706539422649399614037254978869753190882492376528406540173851407196912984
do_x(x2)# 由C代码处理了3轮异或之后的x1x1bef = "F550C4D11BE88545A17EDF49A600D30212A17760F814F054F252F5FAC9E3C915B1195D9F2D52F3BBD2CB5690982C85DFBCA0C4102132CFF25E4740F3C9C71174802C59A7FAF98DAEBC52"
# 由C代码处理了3轮异或之后的x2x2bef = "54449BC8E9713A6F2DE69ACCEADB2BB55F550294D7F4D887D561C858C12D74AA218E45766D0799391A8C617F5E3FB00FD4995E9E5077100721858261A223FB4773736CE6027275E7A9EC"
# 输入字节的hexh = ("""
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)))
# 这个输出的就是flagprint('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))
[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课
|
|
|---|---|
