看雪 2023 KCTF 年度赛第五题争分夺秒解题过程（模逆元素）

2023-9-12 00:00 7612

看雪 2023 KCTF 年度赛第五题争分夺秒解题过程（模逆元素）

moyiah

2023-9-12 00:00

7612

一、静态分析

静态看，程序主要是大量加花了，
不过经过仔细查看，原有正常指令没有任何变形，还是非常能看的状态。
于是直接带花分析。

分析技巧：

基本只通过交叉引用来移动位置，而不通过上下滑动。
查看所有参数与return的交叉引用，基本上相当于去花了。
只是代码片段有所分散。
结合动态调试，重点关注call前后的入参、出参变化。

二、整体流程

根据ReadMe.txt与main函数可知，程序通过argv[1]取得序列号输入。

base64解码argv[1]字符串得到字节
计算除最后4个字节以外的前面字节的crc32，并需要等于最后4个字节。
即，最后4个字节是前面字节的crc32。
然后按特定位置、特定长度取了2个4字节整数，用不同的常量，调用了同一个检查函数，实际是某种方程，具体见后面“小整数方程”。
小整数方程过去之后，发现疑似大整数加法、大整数乘法（0043C130）函数。
对疑似乘法做日志断点，输出乘法调用前后的参数值。
基本认定这一步是小整数那一步的放到大整数了。
大整数方程通过找到在线网站求出解。
解完大整数，处理完几轮异或即可得出flag。

三、调试器检测暗坑

出现有几处如下代码，可能是暗坑。
inside_dbg（ea=0x402220）里面有两个函数做调试器检测。
不管三七二十一，直接静态patch掉调试器判断，
使得inside_dbg始终返回0。

if ( inside_dbg() )
{
  if ( (*Block & 1) != 0 )
    *Block += rand() % 3 + 1;
  else
    *Block += rand() % 4 + 4;
}

四、小整数方程

第一组小整数方程 32bit整数

n = 0x346F8717i64;
a = 0x7D45i64;
求解x使得 a*x % n = 1;

与

a = 0xD711i64;
n = 0x729969FFi64;
求解x使得 a*x % n = 1;

直接for循环枚举出结果
并且有意确认了这里是否会出现多个解

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

默认取最小整数解，继续向下动静结合分析。

五、日志断点

关键日志断点，
主要关注BN_mul与BEF MID AFT 3轮异或处理。

如下：

六、大整数方程

搜索得到一个可用的在线求解网站：https://www.dcode.fr/modular-inverse。

x1求解：

a1 2865244763
n1 13407712312341506807290785620513810006013432881349817380059896195876647865383040511615194818142561216049323742693301651262826523009904773019126031607880381917510353811872243158275
 
求解x使得 a1 * x % n1 = 1

x2求解：

a2 = 2207598431
n2 = 11504884415388796500219489938877037570907236266221216736789242959943502559932358261444533399595441834388023078747736743001176901105009843107005500447845023069935116586106537423621
求解x使得 a2 * x % n2 = 1

七、Python Keygen

求解到大整数方程的解之后，通过python脚本处理好前期步骤。
代码如下，以下脚本python3可以直接运行，输出flag。
不过，编写过程需要与后面辅助异或的C代码交替配合。

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)

脚本输出flag为引号内base64字符串：

1	`b64 b'KmJTMUoAAAD1UMTRG+iFRaF+30mmANMCEqF3YPgU8FTyUvX6yePJFbEZXZ8tUvO70stWkJgshd+8oMQQITLP8l5HQPPJxxF0gCxZp/r5ja68Up2kckNKAAAAVESbyOlxOm8t5prM6tsrtV9VApTX9NiH1WHIWMEtdKohjkV2bQeZORqMYX9eP7AP1JlenlB3EAchhYJhoiP7R3NzbOYCcnXnqewe7SYM'`

修改程序命令行，进行验证，程序提示OK。
提交到网站，显示答对。

八、大整数求解之后的异或处理

由C代码辅助实现。

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

#include <stdlib.h>
#include <stdio.h>
 
int main()
{
    // true: 处理x1    false: 处理x2
    bool x = false;
 
    unsigned char xbs2[] = { 
        // x1的大整数字节数组 由python脚本打印出
        //0x9, 0x57, 0x68, 0x6C, 0x8A, 0x1, 0xD9, 0x76, 0x34, 0x9B, 0x1C, 0x99, 0x58, 0x3E, 0xDC, 0x6C, 0x94, 0x8A, 0x41, 0xD2, 0xC2, 0x21, 0xA8, 0x48, 0x9A, 0x60, 0xFB, 0x3B, 0xAF, 0x96, 0x6C, 0x5A, 0x8A, 0x53, 0x74, 0xCB, 0x9C, 0xEB, 0x99, 0x61, 0x1C, 0x68, 0xE1, 0x3B, 0x8E, 0xB0, 0xA8, 0xAD, 0x8, 0x1A, 0x0, 0xBF, 0xFD, 0x16, 0xDE, 0xC3, 0xFF, 0x37, 0xF3, 0xD3, 0xA0, 0x61, 0x1C, 0x24, 0xBC, 0x76, 0x36, 0x49, 0x91, 0xE1, 0x90, 0xF7, 0xDE, 0x6D
     
        // x2的大整数字节数组 由python脚本打印出
        0x58, 0x7D, 0x5C, 0x2, 0x4B, 0x3A, 0x90, 0x1E, 0xE0, 0xD8, 0x20, 0x2F, 0xF5, 0x7, 0x2, 0x24, 0x62, 0x36, 0x83, 0x4B, 0xF9, 0x9B, 0x25, 0xA2, 0xBD, 0x85, 0xB5, 0xEA, 0xE7, 0x96, 0x7, 0xD3, 0x7E, 0xFB, 0x13, 0x94, 0x80, 0xC2, 0x14, 0xF0, 0x91, 0x20, 0x72, 0xD9, 0x9D, 0x32, 0x5A, 0x64, 0xC5, 0xEF, 0xC, 0xD, 0x27, 0x7C, 0x75, 0x59, 0x94, 0xA, 0xBE, 0xD, 0x3B, 0x72, 0xF2, 0x1B, 0x4B, 0x15, 0xC9, 0x41, 0x8A, 0x9B, 0xD8, 0x1, 0x3F, 0x5F
    };
    printf("\nAFT ");
    for (int i = 0; i < sizeof(xbs2); ++i)
    {
        printf("%02X", xbs2[i]);
    }
    printf("\n    ");
    if (x)
    {
        unsigned char xork2[16];
        int ind2;
        int xlen;
 
        xlen = 0;
        xork2[0] = 0x21;
        xork2[1] = -124;
        xork2[2] = 16;
        xork2[3] = 66;
        xork2[4] = 8;
        xork2[5] = 33;
        xork2[6] = -124;
        xork2[7] = 16;
        xork2[8] = 66;
        xork2[9] = -56;
        xork2[10] = 81;
        xork2[11] = -121;
        xork2[12] = -61;
        xork2[13] = 0x80;
        xork2[14] = -44;
        xork2[15] = 61;
        xlen = sizeof xbs2 / 2;
        for (ind2 = 0; ind2 < xlen; ++ind2)
        {
            printf("%02X", xork2[ind2 % 0x10u]);
 
            xbs2[ind2] ^= xork2[ind2 % 0x10u];
        }
    }
    printf("\n");
 
    for (int i = 0; i < sizeof(xbs2); ++i)
    {
        printf("%02X", xbs2[i]);
    }
    printf("\n");
 
    printf("\nMID ");
    unsigned char xormid[] = {
    // x1的xor key 由日志断点MID 输出后提取出字节
    //0xFC , 0x7 , 0xAC , 0xBD , 0x91 , 0xE9 , 0x5C , 0x33 , 0x95 , 0xE5 , 0xC3 , 0xD0 , 0xFE , 0x3E , 0xF , 0x6E , 0x86 , 0x2B , 0x36 , 0xB2 , 0x3A , 0x35 , 0x58 , 0x1C , 0x68 , 0x32 , 0xE , 0xC1 , 0x66 , 0x75 , 0xA5 , 0x4F , 0x3B , 0x4A , 0x29 , 0x54 , 0xB1 , 0xB9 , 0x6A , 0xDA , 0xCE , 0xA3 , 0xB7 , 0xAB , 0x16 , 0x9C , 0x2D , 0x72 , 0xB4 , 0xBA , 0xC4 , 0xAF , 0xDC , 0x24 , 0x11 , 0x31 , 0xA1 , 0x70 , 0xB3 , 0x20 , 0x69 , 0xA6 , 0xD , 0x50 , 0x3C , 0x5A , 0x6F , 0xEE , 0x6B , 0x18 , 0x1D , 0x59 , 0x62 , 0x3F
     
    // x2的xor key 由日志断点MID 输出后提取出字节
     0xC , 0x39 , 0xC7 , 0xCA , 0xA2 , 0x4B , 0xAA , 0x71 , 0xCD , 0x3E , 0xBA , 0xE3 , 0x1F , 0xDC , 0x29 , 0x91 , 0x3D , 0x63 , 0x81 , 0xDF , 0x2E , 0x6F , 0xFD , 0x25 , 0x68 , 0xE4 , 0x7D , 0xB2 , 0x26 , 0xBB , 0x73 , 0x79 , 0x5F , 0x75 , 0x56 , 0xE2 , 0xED , 0xC5 , 0x8D , 0xC9 , 0x8B , 0xAC , 0x13 , 0xA6 , 0xC3 , 0xD , 0xEA , 0x6B , 0x11 , 0x76 , 0x52 , 0x93 , 0x77 , 0xB , 0x65 , 0x5E , 0xB5 , 0x8F , 0x3C , 0x6C , 0x99 , 0x51 , 0x9 , 0x5C , 0x38 , 0x66 , 0xA5 , 0xA7 , 0x88 , 0xE9 , 0xAD , 0xE6 , 0x96 , 0xB3
    };
    for (int i = 0; i < sizeof(xbs2); ++i)
    {
        xbs2[i] ^= xormid[i];
        printf("%02X", xormid[i]);
    }
 
    printf("\n    ");
 
    for (int i = 0; i < sizeof(xbs2); ++i)
    {
        printf("%02X", xbs2[i]);
    }
    printf("\n");
 
    if (x)
    {
        printf("\n\nBEF ");
        int ixlen1;
        unsigned char xork1[16];
        int ind1;
 
        ixlen1 = 0;
        xork1[0] = 33;
        xork1[1] = -124;
        xork1[2] = 16;
        xork1[3] = 66;
        xork1[4] = 8;
        xork1[5] = 33;
        xork1[6] = -124;
        xork1[7] = 16;
        xork1[8] = 66;
        xork1[9] = -56;
        xork1[10] = 81;
        xork1[11] = -121;
        xork1[12] = -61;
        xork1[13] = 0x80;
        xork1[14] = -44;
        xork1[15] = 61;
        ixlen1 = sizeof(xbs2) / 2;
        for (ind1 = 0; ind1 < ixlen1; ++ind1)
        {
            printf("%02X", xork1[ind1 % 0x10u]);
 
            xbs2[ind1] ^= xork1[ind1 % 0x10u];
        }
        printf("\n    ");
        for (int i = 0; i < sizeof(xbs2); ++i)
        {
            printf("%02X", xbs2[i]);
        }
    }
    return 0;
}