首页
论坛
课程
招聘
[原创]看雪 2022·KCTF 秋季赛 > 第二题 盗贼作乱 by 心学
2022-11-19 00:31 6660

[原创]看雪 2022·KCTF 秋季赛 > 第二题 盗贼作乱 by 心学

htg 活跃值
4
2022-11-19 00:31
6660

准备工具:

1、IDA77
2、WinDBG Preview【可以不用】
3、Python

一、分析程序结构

1、直接运行程序,了解程序反馈

1
2
3
4
5
6
7
C:\Users\surface>"C:\Users\surface\OneDrive\Crack\CTF\看雪 2022·KCTF 秋季赛\02\cm2022\cm2022.exe"
Input:0123456789abcdef0123456789abcdef0123456789abcdef0123456789abcdef
Error.
C:\Users\surface>"C:\Users\surface\OneDrive\Crack\CTF\看雪 2022·KCTF 秋季赛\02\cm2022\cm2022.exe"
Input:11111111111111
Error.
C:\Users\surface>

结论:输入错误的序列号,直接返回 Error
提示:先打开CMD窗口,然后将文件拖入窗口运行。

2、IDA反编译程序,浏览整体架构

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
int __cdecl main(int argc, const char **argv, const char **envp)
{
  int v3; // edi
  int v4; // eax
  int v6; // esi
  int v7; // eax
  char inputSN; // [esp+8h] [ebp-40h] BYREF
  char v10[60]; // [esp+9h] [ebp-3Fh] BYREF
  __int16 v11; // [esp+45h] [ebp-3h]
  char v12; // [esp+47h] [ebp-1h]
 
  inputSN = 0;
  memset(v10, 0, sizeof(v10));
  v11 = 0;
  v12 = 0;
  sub_40284A((int)aInput);
  gets(&inputSN);
  v3 = -1;
  v4 = 0;
  if ( !inputSN )
    goto LABEL_20;
  do
  {
    if ( v4 >= 0x40 )
      break;
    if ( v10[v4 - 1] == '-' )
      v3 = v4;
  }
  while ( v10[v4++] );
  if ( v3 > 0
    && (v6 = v4 - v3, v4 - v3 > 0)
    && sub_4014D0(dword_40A940, &inputSN, v3, Base62) > 0// '-'前半部分
    && sub_4014D0(dword_40A964, &v10[v3], v6 - 1, Base62) > 0// '-'后半部分
    && (sub_4014D0(
          dword_40A9D0,
          aIrtzloz6iub,
          strlen(aIrtzloz6iub),
          Base62),                              // 处理固定字符
        sub_401630(
          dword_40A9FC,
          0),                                   // 初始化 为 0
        sub_401630(
          dword_40AA20,
          0),                                   // 初始化 为 0
        cmp(dword_40A940, dword_40A964) < 0)    // 前半部分 < 后半部分
    && cmp(dword_40A940, dword_40A9D0) < 0      // 前半部分 < 内置 8
    && cmp(dword_40A964, dword_40A9D0) < 0 )    // 后半部分 < 内置 8
  {
    v7 = 0;
    while ( 1 )
    {
      dword_40A9F4 = v7 + 1;                    // 处理的标志位?
      sub_401730(dword_40A9FC, dword_40A9FC, dword_40A940);// 累加
      sub_401730(dword_40AA20, dword_40AA20, dword_40A964);// 累加
      sub_4021A0(dword_40A9FC, dword_40A9FC, dword_40A9D0);// 取余
      sub_4021A0(dword_40AA20, dword_40AA20, dword_40A9D0);// 取余
      sub_401630(dword_40A988, 1);              // 初始化 为 1,此处会重新赋值
      sub_401820(dword_40A988, dword_40A9FC, dword_40A988);// 1
      if ( !cmp(dword_40A988, dword_40A940) )   // 判断两个数要相等才行。相等返回0,大于返回1,小于返回-1
      {
        ++dword_40A9F8;
        sub_401CF0(dword_40A988, dword_40A988, dword_40A940);// 乘法?
      }
      sub_401630(dword_40A9AC, 1);
      sub_401730(dword_40A9AC, dword_40AA20, dword_40A9AC);// 1
      if ( !cmp(dword_40A9AC, dword_40A964) )
      {
        ++dword_40A9F8;
        sub_401F30(dword_40A9AC, dword_40A9D0, dword_40A964);// 除法?
      }
      if ( dword_40A9F8 == 0xA )                // 需要命中10次(只要使其等于10即可)才行
        break;
      v7 = dword_40A9F4;
      if ( dword_40A9F4 >= 0x200000 )
        goto LABEL_20;
    }
    sub_40284A((int)aSuccess);
    return 0;
  }
  else
  {
LABEL_20:
    sub_40284A((int)aError);
    return 0;
  }
}
 
程序分为四大块:
一是:获取用户输入
二是:IF条件判断,需满足
三是:while循环,一大堆计算
四是:输出结果
### 3、全局查看结构,锁定成功失败

在IDA里,反编译之后,程序的主函数main结构比较简单,Text或Graph视图都可以清晰的看到 Error 和 Success 信息,能快速定位到程序运行失败或成功的关键判断之处。

1
2
3
4
5
6
7
8
9
    sub_40284A((int)aSuccess);
    return 0;
  }
  else
  {
LABEL_20:
    sub_40284A((int)aError);
    return 0;
  }

从后往前推:
如果要运行到 sub_40284A((int)aSuccess),则必须保证 dword_40A9F8 == 0xA;【作者埋了一个坑】,此时想当然认为 循环要进行十遍(错了)。
关注:全局变量 dword_40A9F8

二、找出约束条件

1、静态代码走查,记录约束条件

1
2
3
4
5
6
7
8
9
do
{
  if ( v4 >= 0x40 )
    break;
  if ( v10[v4 - 1] == '-' )
    v3 = v4;
}
while ( v10[v4++] );
if ( v3 > 0

约束条件1:序列号长度小于等于 0x40
约束条件2:序列号内存在一个 '-' 字符。v3 记录 '-' 的位置

1
2
sub_4014D0(dword_40A940, &inputSN, v3, Base62) > 0
sub_4014D0(dword_40A964, &v10[v3], v6 - 1, Base62) > 0

约束条件3:序列号部分转换满足要求(2处)

1
(sub_4014D0(dword_40A9D0,aIrtzloz6iub,strlen(aIrtzloz6iub),Base62)

约束条件4:内置字符串转换满足要求

1
2
3
cmp(dword_40A940, dword_40A964) < 0
&& cmp(dword_40A940, dword_40A9D0) < 0
&& cmp(dword_40A964, dword_40A9D0) < 0

约束条件5:序列号(2处)及内置字符串相互比较要满足要求

1
if ( dword_40A9F8 == 0xA )

约束条件6:dword_40A9F8 == 0xA

 

总结一下:6个约束条件,在不深入到子函数细节的情况下进行分析。
约束条件1:序列号长度小于等于 0x40
约束条件2:序列号内存在一个 '-' 字符。v3 记录 '-' 的位置
约束条件3:序列号部分转换满足要求(2处)
约束条件4:内置字符串转换满足要求
约束条件5:序列号(2处)及内置字符串相互比较要满足要求
约束条件6:dword_40A9F8 == 0xA

2、数据驱动调试,猜测函数功能

我们遇到了很多函数,目前,还不清楚每个函数的细节,但是对于大佬老说,此时已经猜测是利用高进制进行大整数的运算。接下来我主要从经验值较低的角度来分析函数功能,主要方法是通过参数及变量(内存区域)的变化,来猜测或推测函数的大概功能

2.1 sub_4014D0

1
2
3
sub_4014D0(dword_40A940, &inputSN, v3, Base62)
sub_4014D0(dword_40A964, &v10[v3], v6 - 1, Base62)
sub_4014D0(dword_40A9D0,aIrtzloz6iub,strlen(aIrtzloz6iub),Base62)

输入四个参数,返回结果要大于0
输入的参数:最后一个参数是固定的内置字符串,即Base62;第二个参数是字符串,有的是用户输入的字符串、程序内置字符串;第三个参数是整数;第一个参数是一个全局变量。
现在猜测这个函数应该只对第一个参数全局变量做修改。
现在开始数据驱动测试,我们构造序列号:
IDA调试:
SN:0123456789abcdef-0123456789abcdef
结果:

1
2
3
.data:0040A940 dword_40A940 dd 0Ch, 2C7BD6CEh, 0B7B6B582h, 677E02E5h, 0, 0, 0, 0, 0
.data:0040A964 dword_40A964 dd 0Ch, 2C7BD6CEh, 0B7B6B582h, 677E02E5h, 0, 0, 0, 0, 0
.data:0040A9D0 dword_40A9D0 dd 8, 89E80000h, 8AC72304h, 0

0040A940 和 0040A964 结果一样,这与我们输入的序列号相关,初步判断是用 - 进行了分割,然后分别进行计算。
0040A9D0 与 内置字符串相关 'IRtzloZ6iuB'
但是 这些全局变量值与输入的字符串有什么关联,直接看代码是一种方式,但是通过数据测试也可以才出来。用最小的值依次判断。
SN:0-0
程序非正常退出
在sub_4014D0内return 0 直接返回0,不满足条件,退出了。全局变量没有值,这个子函数不支持0数据转换
SN:1-1

1
2
.data:0040A940 dword_40A940 dd 1, 1, 0, 0, 0, 0, 0, 0, 0
.data:0040A964 dword_40A964 dd 1, 1, 0, 0, 0, 0, 0, 0, 0

那看来输入1,返回1
SN:11-12

1
2
.data:0040A940 dword_40A940 dd 1, 3Fh, 0, 0, 0, 0, 0, 0, 0
.data:0040A964 dword_40A964 dd 1, 7Dh, 0, 0, 0, 0, 0, 0, 0

0x3F = 63 对应 11
0x7D = 125 对应 12
我们与62进制来对照,11(62进制) = 63;21(62进制) = 125
初步猜测该函数是 62进制 的字符串序列与整数的转换,不过字符串是倒序存放的。可以进一步分析

1
.data:0040A9D0 dword_40A9D0 dd 8, 89E80000h, 8AC72304h, 0

'IRtzloZ6iuB' ==》8, 89E80000h, 8AC72304h
第一个 DWORD = 8 是后面的字节序列长度。可以猜测出来。

2.2 sub_401630

1
2
sub_401630(dword_40A9FC,0)                                 
sub_401630(dword_40AA20,0)

可以跟踪函数的运行前后,两个全局变量的变化,基本可以判断这是一个赋值操作,用0来给全局变量赋值,类似于初始化。

2.3 sub_401690

1
sub_401690(resultA *a1, resultA *a2)

用上面的方法,可以判断出这是一个比较方法,其返回值有1、0、-1 分别表示大于、等于、小于
我在这儿构造了一个结构resultA,它是大整数计算的结构,第一个DWORD是大整数的字节长度,之后就是大整数的字节序列。我们可以通过前述的0040A940进行分析,当我们给定更大的值,就可以得出上述结构构造。

2.4 sub_401730

1
signed int __cdecl sub_401730(resultA *dest, resultA *a2, resultA *source)

用上面方法分析,这是一个 加法运算
dest = a2 + source

2.5 sub_4021A0

1
int __cdecl sub_4021A0(resultA *a1, resultA *a2, resultA *baseNum)

这是取模运算,最后一个参数都是固定的,dword_40A9D0 ,存储的是内置字符串的62进制值。

2.6 sub_401630

1
sub_401630(dword_40A988, 1)

这是 赋值操作,给第一个参数赋第二个参数值,即赋值1

2.7 sub_401820

1
2
signed int __cdecl sub_401820(resultA *dest, resultA *a2, resultA *source)
sub_401820(dword_40A988, dword_40A9FC, dword_40A988)

这是 减法操作,实际上 减去了1 (dword_40A988)
dword_40A988 = dword_40A9FC - dword_40A988

2.8 sub_401CF0

1
sub_401CF0(dword_40A988, dword_40A988, dword_40A940);

它的运算比较复杂,如果用参数前后对照,会发现它是一个 乘法运算
dword_40A988 = dword_40A988 * dword_40A940
dword_40A988 在每次循环后都会置初始值1,其不会对其他造成干扰
dword_40A940 是固定值。貌似这个乘法用处不大。

2.9 sub_401F30

1
sub_401F30(dword_40A9AC, dword_40A9D0, dword_40A964);

这是除法运算
dword_40A9AC = dword_40A9D0 / dword_40A964
dword_40A9AC 在每次循环后都会置初始值1,其不会对其他造成干扰
dword_40A9D0 、dword_40A964 是固定值。
这个除法貌似没法用。它没有对我们关注的全局变量进行修改【实际有坑

3、深入挖掘代码,寻找隐藏细节

经过上面分析,基本上对逻辑计算有了一定理解,
dword_40A940:序列号前半部分值 partA
dword_40A964:序列号后半部分值 partB
dword_40A9D0:内置字符串值 interValue
条件判断:
partA < partB
partA < interValue
partB < interValue

 

经过if条件判断之后,开始while循环处理
dword_40A9F8:记录两个 cmp 相等的次数【坑,还有其他地方对其影响】,满足10即可
dword_40A9F4:记录当前循环的次数 cnt

1
2
3
4
dword_40A9FC = dword_40A940 * dword_40A9F4 = partA * cnt mod(interValue)
dword_40AA20 = dword_40A964 * dword_40A9F4 = partB * cnt mod(interValue)
dword_40A988 =  1
dword_40A988 =  dword_40A9FC - dword_40A988 = dword_40A9FC - 1

cmp(dword_40A988, dword_40A940)
比较相等即成功给 dword_40A9F8 加 1
数学表达式就是

1
partA * cnt mod(interValue)  - 1 == partA

一个数乘以一个倍数,减去 1 然后等于自身
这是第一处判断。。。。。。
dword_40A9AC = 1
dword_40A9AC = dword_40AA20 + dword_40A9AC = dword_40AA20 +1
cmp(dword_40A9AC, dword_40A964)
比较相等即成功给 dword_40A9F8 加 1
数学表达式就是

1
partB * cnt mod(interValue)  + 1 == partB

一个数乘以一个倍数,加上 1 然后等于自身
这是第二处判断。。。。。。

 

然后这些需要经过 10次 才能满足要求【】,
这种情况可能吗?cnt 有上限 0x200000; interValue模数已知,要求 partA 和 partB,直觉不可能,如果具有一定的数论知识,联想到 模N求逆,只能有一个结果。
模N 求A 的 逆元B =》 A × B == 1 mod(N),只有在A或B与N互质的情况下才存在,如果 不互质,那么就不可能存在逆元 B。存在的情况下也只有一个结果。
那么,问题如何解决了?这需要更进一步查看、深究代码。
重点关注cmp比较之后的代码,也就是上面分析出来的乘法和除法函数,为什么?一是此段代码执行比较少,应优先判断去排查;二是循环体的外侧代码功能性强,运算的结果都有一定的影响,影响的全局变量值目的性强,且未发现对其他的全局变量进行更改。
关键隐藏之处1
乘法:

1
2
3
4
5
6
7
8
9
10
11
12
13
int __cdecl sub_401CF0(resultA *a1, resultA *a2, resultA *a3)
    sub_401630(dword_40A988, 4);
    sub_4023A0(dword_40A9AC, dword_40A988, 3);
    if ( dword_40A9F8 > 0
      && *(_DWORD *)&dword_40A9D0[0].value[(unsigned __int8)dword_40A9AC[0].value[0]] == (unsigned __int8)dword_40A9AC[0].value[0] )
    {
      sub_401730(dword_40A988, dword_40A988, dword_40A9AC);
      v13 = sub_402360(dword_40A988, dword_40A9F4);
      dword_40A9D0[0].value[(unsigned __int8)dword_40A988[0].value[0]] += 4;
      sub_4023A0(dword_40A988, dword_40A988, v13);
      sub_401820(dword_40A9AC, dword_40A988, dword_40A9AC);
    }
    return v7;
1
2
3
4
5
sub_401630(dword_40A988, 4)==>dword_40A988 = 4
sub_4023A0(dword_40A9AC, dword_40A988, 3) ==>
dword_40A9AC = 4 * 2^3 = 32
dword_40A9AC[0].value[0] 是第一个字节,即上面的赋值 32
dword_40A9D0[0].value[(unsigned __int8)dword_40A9AC[0].value[0]]  ==> dword_40A9D0[0].value[32]

if语句的两个判断:
dword_40A9F8 > 0 显然无问题 4
dword_40A9D0[0].value[32] == 32
这里要满足32,才执行里面的语句,此处分析两个问题:
1、怎么满足条件?
2、满足条件后,执行了啥?有什么用?
第一个问题,进一步查看全局变量的位置
dword_40A9D0[0].value[32] ==>
dword_40A9D0 + 4 + 32 = dword_40A9F4
+4 是略过了第一个双字(字节序列长度)
我们发现,这种操作之后,实际内存位置是 dword_40A9F4
它是什么,我们回看main里面的while循环,他是循环累计次数,即进行到了第几次循环,也就说,我们得循环到第32次(从1开始计数)才能进入,此时要够在序列号,使其满足前述的5个约束条件,特别是两个 cmp 运算,即满足while里的cmp运算。
一个数乘以一个倍数,减去 1 然后等于自身
第二个问题,满足条件了,执行了啥?

1
2
sub_401730(dword_40A988, dword_40A988, dword_40A9AC);
dword_40A9D0[0].value[(unsigned __int8)dword_40A988[0].value[0]] += 4;

dword_40A988 = dword_40A988 + dword_40A9AC = 4+32 = 36
dword_40A988[0].value[0]] = 36
dword_40A9D0[0].value[(unsigned __int8)dword_40A988[0].value[0]] = dword_40A9D0[0].value[4]==>
dword_40A9D0 + 4 + 36 = dword_40A9F8
这是 关键的全局变量,它等于0xA才能输出success。

 

除法方法类似。这两个方法是关键的隐藏之处。
梳理一下思路:
序列号的前后两个部分:
1、执行到32次,满足判断条件,此时 dword_40A9F8 各计入1次
partA × 32 mod(interValue) - 1 == partA
partB × 32 mod(interValue) + 1 == partB

2、进入乘法或除法方法后,dword_40A9F8 各累加4
此时,就可以满足 dword_40A9F8 == 10 == 0xA

三、整理破解思路

1、列出步骤

1.1 构造一个62进制的解码及编码方法

1.2 求出序列号的前后两部分

1.3 输出序列号

2、优化方案

主要是对 求出序列号的前后两部分 进行优化

1
2
3
interValue = 0x8AC7230489E80000 = 10000000000000000000 = 10 ^ 19
partA × 32 mod(10 ^ 19- 1 == partA
partB × 32 mod(10 ^ 19+ 1 == partB

可以通过循环,逐个从1开始计算,找到结果。
有一种快速方法,可以利用求模N的逆来快速得到结果。

1
2
partA * 31    = 1 mod(10 ^ 19)
partB * (-31) = 1 mod(10 ^ 19)

可以利用pow方法求出

1
2
partA = pow(31,-1,10**19)
partB = pow(-31,-1,10**19)

四、编写程序脚本

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
'''
题目:看雪 2022·KCTF 秋季赛  >   第二题 盗贼作乱
链接:https://ctf.pediy.com/game-season_fight-217.htm
作者:htg 心学
时间:2022-11-18
'''
BASE62 = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
interValue = 'IRtzloZ6iuB' #模
 
##62进制字符串转整数:字符串倒序存放
def Str2Int(text):
    base = len(BASE62)
    num = 0
    for i in text[::-1]:
        num = num * base + BASE62.index(i)
    return num
##整数转62进制字符串:字符串倒序存放
def Int2Str(value):
    base = len(BASE62)
    resultStr = ""
    while value > 0:
        tmp = value % base
        value = value // base
        resultStr = resultStr + BASE62[tmp]
    if resultStr == "":
        resultStr = 0
    return resultStr
 
returnNum = Str2Int(interValue)
print("测试:Str2Int('IRtzloZ6iuB') = {0}\t0x{0:X}".format(returnNum))
'''
10**19 == 10000000000000000000 == 0x8AC7230489E80000
N = 0x8AC7230489E80000 = 10**19
【数论知识点】模N求逆运算
求解 X
32 * X - 1 = X mod N  ===》 31 * X = 1 mod N  ===》X 为 31 相对于 模N 的逆。
这个容易想起模逆运算。
X * Y = 1 mod N 代表 X 和 Y 相对于模 N 互逆。当然 X,Y 相对于 模N 互质。
所以可以直接用 pow(31,-1,10**19) 来求 31 的 逆 相对于模10**19
 
求解 Y
32 * Y + 1 = Y mod N  ===》 31 * Y = -1 mod N  ===》-31 * Y = 1 mod N ==》Y 为 -31 相对于 模N 的逆。
所以可以直接用 pow(-31,-1,10**19) 来求 31 的 逆 相对于模10**19
'''
partA = pow(31,-1,10**19)
partB = pow(-31,-1,10**19)
print("(partA,partB) = ({},{})".format(partA,partB))
print("(partA,partB) = ({0},{1})\nSN = {0}-{1}".format(Int2Str(partA),Int2Str(partB)))

[2022冬季班]《安卓高级研修班(网课)》月薪两万班招生中~

最后于 2022-11-19 11:47 被htg编辑 ,原因: 修改部分笔误
上传的附件:
收藏
点赞2
打赏
分享
最新回复 (2)
雪    币: 1237
活跃值: 活跃值 (654)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
yp太阳神 活跃值 2022-11-20 01:01
2
0
学习进步,学习快乐。
游客
登录 | 注册 方可回帖
返回