首页
社区
课程
招聘
问答 CTF 排行榜 知识库 工具下载 看雪峰会 看雪商城 证书查询
  1. 看雪社区
  2. CTF对抗
    3. 发新帖
[原创]看雪 2022·KCTF 秋季赛 > 第二题 盗贼作乱 by 心学
2022-11-19 00:31 12633

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

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

准备工具：

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)))

[培训]二进制漏洞攻防（第3期）；满10人开班；模糊测试与工具使用二次开发；网络协议漏洞挖掘；Linux内核漏洞挖掘与利用；AOSP漏洞挖掘与利用；代码审计。

最后于 2022-11-19 11:47 被htg编辑 ，原因： 修改部分笔误
上传的附件：
收藏
点赞・5
打赏
分享
最新回复 (2)
yp太阳神
雪    币： 3301
活跃值： (5013)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
yp太阳神 2022-11-20 01:01
2 楼
0
学习进步，学习快乐。
游客
登录 | 注册 方可回帖
　回帖　 表情 雪币赚取及消费
高级回复
返回