首页
社区
课程
招聘
看雪 2023 KCTF 年度赛 第五题 争分夺秒 解题过程(模逆元素)
发表于: 2023-9-12 00:00 8670

看雪 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期)

收藏
免费 1
支持
分享
最新回复 (0)
游客
登录 | 注册 方可回帖
返回
//