[原创] KCTF 2023 第十一题 wp - 98k-CTF对抗-看雪-安全社区|安全招聘|kanxue.com

[原创] KCTF 2023 第十一题 wp - 98k

2023-9-27 22:46 9526

[原创] KCTF 2023 第十一题 wp - 98k

GreatIchild 活跃值

2023-9-27 22:46

9526

逆向部分没什么好说的，有个 check 算法，要在 1,000,000,000 到 1<<32 之间找一个数 k ，满足 !check(k) && check(k - 1) ， check 函数大致如下：

def check(value, try_count):
    buf1 = [0] * 10000
    buf2 = [0] * 10000
    buf3 = [0] * 20000
    buf4 = [0] * 20000
    for _ in range(try_count):
        print(_, end=' \r')
        v = [2, 4, 5, 6, 7, 8, 13]
        for i in range(10000):
            _v = v[rand() % len(v)]
            buf1[i] = _v
            if i == 0:
                buf2[i] = rand() % (_v - 1) + 1
            else:
                buf2[i] = rand() % _v
        for i in  range(20000):
            buf3[i] = v[rand() % len(v)]
        i12 = 0
        i34 = 0
        tmpv = 0
        while i12 < 10000 or tmpv > 0:
            if i34 >= 20000:
                # assert False, 1
                return True
            tmpv_bak = tmpv
            if i12 >= 10000:
                tmpv = tmpv // buf3[i34]
                buf4[i34] = tmpv_bak % buf3[i34]
                i34 += 1
            else:
                tmpv = buf1[i12] * tmpv + buf2[i12]
                if tmpv_bak // buf3[i34] * tmpv >= value:
                    tmpv = tmpv_bak // buf3[i34]
                    buf4[i34] = tmpv_bak % buf3[i34]
                    i34 += 1
                else:
                    i12 += 1
        i12 = 10000 - 1
        i34 -= 1
        tmpv = 0
        while i34 >= 0 or tmpv > 0:
            if i12 < 0:
                # assert False, 2
                return True
            tmpv_bak = tmpv
            if i34 < 0:
                tmpv = tmpv // buf1[i12]
                if tmpv_bak % buf1[i12] != buf2[i12]:
                    # assert False, 3
                    return True
                i12 -= 1
            else:
                tmpv = buf3[i34] * tmpv + buf4[i34]
                if tmpv_bak // buf1[i12] * tmpv >= value:
                    tmpv = tmpv_bak // buf1[i12]
                    if tmpv_bak % buf1[i12] != buf2[i12]:
                        # assert False, 4
                        return True
                    i12 -= 1
                else:
                    i34 -= 1
    return False

程序使用了多线程，总共的 try_count 为 10000 。

直接看这算法完全不懂，于是来找规律。先固定 buf1 和 buf3 数组的值，当输入的 value 比较小的时候 (range(1, 512)) 发现返回值非常稳定，也就是 try_count 为 1 都能直接得到稳定结果，于是使用小 value 调整 buf1 buf3 的取值找规律，部分输出如下：

$ python3 ./script.py
[(28, True), (51, False), (107, True), (153, False), 238, True)]
$ python3./script.py
[(54, True), (103, False), (211, True)]
$ python3 ./script.py
[(28, True), (51, False), (54, True), (103, False), (107, True), (153, False), (211, True)]

上面的三次运行结果，是取 value 为 range(1, 256) ， buf3 全为 13 ， buf1 分别为 ① 全 2 ② 全 4 ③ 随机 2 和 4 这三种情况下的输出，输出的格式是返回值在某个值处发生了变化，变为了 True/False ，如第一次的输出含义是在 value = 28 时返回值开始为 True ， value = 51 时返回值开始为 False ，以此类推。这些输出就得到了指定条件下能返回 True/False 的 value 值的区间。并且这个结果是非常稳定的，只需要一次就能得到这个正确的结果。

这三个综合起来就可以看到，第三次返回 False 的 value 区间就是第一次返回 False 的 value 区间与第二次的交集。

如果将 value 的范围改为 range(1, 512) ，设置 buf1 全 2 ， buf3 全 13 ，可以得到如下结果：

1	`[(28,` `True), (51,` `False), (107,` `True), (153,` `False),` `238,` `True), (307,` `False), (421,` `True)]`

可以看到 True/False 的区间长度是二次递增的（相邻 True 区间或者相邻 False 区间的长度差是一个等差数列），总之就是我们可以通过前几个区间值递推到我们想要的区间的 True/False 分布。

所以我们只要找到某组 buf1 和 buf3 的固定取值下 value 在 range(1, 256) 里的 True/False 分布（必须是稳定的），我们就能找到这些取值下 value 在 1,000,000,000 到 1<<32 之间的 True/False 分布，再结合第一条规律，不同 buf1 和 buf3 的取值下得到的返回 False 的取值区间的交就一定包含目标区间，这样就能大大缩小需要暴破的空间。

后面测试发现， buf1 与 buf3 的固定取值存在倍数关系时得到的结果不稳定，所以排除这一部分数据。最后共有 18 组组合，将暴破区间从 3294967296 减少到 87551 。

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

#!/usr/bin/env python3
 
'''
seed = 0
def rand():
    global seed
    seed += 1
    return seed
'''
 
def rand(): # simulate rand (may be any random function)
    pass
 
def check(value, try_count): # check
    pass
 
def check_1(value, buf1_v, buf3_v):
    print(value, end=' \r')
    buf1 = [buf1_v] * 10000
    buf2 = [rand() % (buf1_v - 1) + 1]
    for i in range(1, 10000):
        buf2.append(rand() % buf1_v)
    buf3 = [buf3_v] * 20000
    buf4 = [0] * 20000
    i12 = 0
    i34 = 0
    tmpv = 0
    while i12 < 10000 or tmpv > 0:
        if i34 >= 20000:
            return True
        tmpv_bak = tmpv
        if i12 >= 10000:
            tmpv = tmpv // buf3[i34]
            buf4[i34] = tmpv_bak % buf3[i34]
            i34 += 1
        else:
            tmpv = buf1[i12] * tmpv + buf2[i12]
            if tmpv_bak // buf3[i34] * tmpv >= value:
                tmpv = tmpv_bak // buf3[i34]
                buf4[i34] = tmpv_bak % buf3[i34]
                i34 += 1
            else:
                i12 += 1
    i12 = 10000 - 1
    i34 -= 1
    tmpv = 0
    while i34 >= 0 or tmpv > 0:
        if i12 < 0:
            return True
        tmpv_bak = tmpv
        if i34 < 0:
            tmpv = tmpv // buf1[i12]
            if tmpv_bak % buf1[i12] != buf2[i12]:
                return True
            i12 -= 1
        else:
            tmpv = buf3[i34] * tmpv + buf4[i34]
            if tmpv_bak // buf1[i12] * tmpv >= value:
                tmpv = tmpv_bak // buf1[i12]
                if tmpv_bak % buf1[i12] != buf2[i12]:
                    return True
                i12 -= 1
            else:
                i34 -= 1
    return False
 
 
try_count = 150
 
'''
low = 1000000000
v_low = check(low, try_count)
print(low, v_low)
 
high = 0x100000000
v_high = check(high, try_count)
print(high, v_high)
 
while low < high:
    mid = (low + high) // 2
    v_mid = check(mid, try_count)
    print(mid, v_mid)
    if v_mid == v_low:
        low = mid + 1
        v_low = check(low, try_count)
        print(low, v_low)
    else:
        high = mid - 1
        v_high = check(high, try_count)
        print(high, v_high)
'''
 
def interval_and(l1, l2):
    l = []
    i1 = 0
    i2 = 0
    while i1 < len(l1) and i2 < len(l2):
        l1a, l1b = l1[i1]
        l2a, l2b = l2[i2]
        if l1a >= l2b:
            i2 += 1
            continue
        elif l2a >= l1b:
            i1 += 1
        elif l1b >= l2b:
            l.append((max(l1a, l2a), l2b))
            i2 += 1
            if l1b == l2b:
                i1 += 1
        else:
            l.append((max(l1a, l2a), l1b))
            i1 += 1
    return l
 
def get_f_intervals(t, f, tdiv, fdiv, pub_div):
    assert t < f
    t = t + tdiv
    tdiv += pub_div
    assert t > f
    while t < 1000000000:
        f += fdiv
        fdiv += pub_div
        t += tdiv
        tdiv += pub_div
    fl = []
    while f < 0x100000000:
        fl.append((f, t))
        f += fdiv
        fdiv += pub_div
        t += tdiv
        tdiv += pub_div
    return fl
 
def number_count(l):
    s = 0
    for a, b in l:
        s += b - a
    return s
 
'''
last_r = False
a = []
for i in range(1, 1024):
    r = check_1(i, 2, 13)
    if last_r != r:
        a.append((i, r))
        if len(a) >= 8: break
        last_r = r
        # print(a)
 
print(a)
print(a[2][0] - a[0][0], a[4][0] - a[2][0], a[6][0] - a[4][0])
 
x=a[0][0]
y=a[2][0]
z=a[4][0]
x1=a[1][0]
y1=a[3][0]
print(x,x1,y-x,y1-x1,(z-y)-(y-x))
'''
 
 
s='''
28 51 79 102 52
54 103 157 206 104
67 129 196 258 130
80 155 235 310 156
93 181 274 362 182
106 207 313 414 208
 
16 27 43 54 28
30 55 85 110 56
37 69 106 138 70
44 83 127 166 84
58 111 169 222 112
 
12 19 31 38 20
22 39 61 78 40
32 59 91 118 60
42 79 121 158 80
 
14 23 37 46 24
26 47 73 94 48
50 95 145 190 96
'''
 
fl = [(1000000000, 0x100000000)]
n = number_count(fl)
 
for i in s.strip().split('\n'):
    if not i.strip(): continue
    fl = interval_and(fl, get_f_intervals(*(int(j) for j in i.split(' '))))
    last_n = n
    n = number_count(fl)
    print('{} -> {} (-{}%)'.format(last_n, n, 100 * (last_n - n) / last_n))
 
for i in fl:
    print(i, i[1] - i[0])

筛选后得到的区间：

(1124320915, 1124327425) 6510
(1898762303, 1898787472) 25169
(2133213325, 2133231523) 18198
(2793543721, 2793581395) 37674

这个空间就可以开始暴了，暴的过程中发现第 2 个区间会有一些误报，而其他都没有，猜测是目标区间就在第二个区间里，区间内其他值离目标值比较近，误报的概率就高了，所以直接写程序暴这个区间内的值：

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <assert.h>
#include <sys/types.h>
#include <unistd.h>
 
#define ullong unsigned long long
 
int check(ullong value, int try_count) {
    int buf1[10000];
    int buf2[10000];
    int buf3[20000];
    int buf4[20000];
    // printf("%d, %d, %d, %d\n", buf1[0], buf2[0], buf3[0], buf4[0]);
    unsigned int v[] = {2, 4, 5, 6, 7, 8, 13};
    for (int _ = 0; _ < try_count; _++) {
        for (int i = 0; i < 10000; i++) {
            int _v = v[rand() % 7];
            buf1[i] = _v;
            if (i) {
                buf2[i] = rand() % _v;
            } else {
                buf2[i] = rand() % (_v - 1) + 1;
            }
        }
 
        for (int i = 0; i < 20000; i++) {
            buf3[i] = v[rand() % 7];
        }
        int i12 = 0;
        int i34 = 0;
        ullong tmpv = 0;
        while (i12 < 10000 || tmpv > 0) {
            if (i34 >= 20000) {
                assert(0 || "1");
                return 1;
            }
            ullong tmpv_bak = tmpv;
            if (i12 >= 10000) {
                tmpv = tmpv / buf3[i34];
                buf4[i34] = tmpv_bak % buf3[i34];
                i34 += 1;
            } else {
                tmpv = buf1[i12] * tmpv + buf2[i12];
                if (tmpv_bak / buf3[i34] * tmpv >= value) {
                    tmpv = tmpv_bak / buf3[i34];
                    buf4[i34] = tmpv_bak % buf3[i34];
                    i34 += 1;
                } else {
                    i12 += 1;
                }
            }
        }
        i12 = 10000 - 1;
        i34 -= 1;
        tmpv = 0;
        while (i34 >= 0 || tmpv > 0) {
            if (i12 < 0) {
                assert(0 || "2");
                return 1;
            }
            ullong tmpv_bak = tmpv;
            if (i34 < 0) {
                tmpv = tmpv / buf1[i12];
                if (tmpv_bak % buf1[i12] != buf2[i12]) {
                    return 1;
                }
                i12 -= 1;
            } else {
                tmpv = buf3[i34] * tmpv + buf4[i34];
                if (tmpv_bak / buf1[i12] * tmpv >= value) {
                    tmpv = tmpv_bak / buf1[i12];
                    if (tmpv_bak % buf1[i12] != buf2[i12]) {
                        return 1;
                    }
                    i12 -= 1;
                } else {
                    i34 -= 1;
                }
            }
        }
    }
    return 0;
}
 
int main() {
    setbuf(stdout, NULL);
 
    int try_count = 100;
    srand(time(NULL));
 
    #define PROCESS_COUNT 16
    #define INIT_VALUE (1898762303l)
    #define FINI_VALUE (1898787472l)
    #define TASK_COUNT ((FINI_VALUE - INIT_VALUE) / PROCESS_COUNT)
 
    #define LOG_TOTAL (100)
    #define COUNT_TO_LOG (TASK_COUNT / LOG_TOTAL)
 
    for (int j = 0; j < PROCESS_COUNT; j++) {
        if (!fork()) { // child
            int logged_count = 0;
            int counting = COUNT_TO_LOG;
            printf("process %d started (0x%lx - 0x%lx).\n", j, INIT_VALUE + j * TASK_COUNT, INIT_VALUE + j * TASK_COUNT + TASK_COUNT);
            for (ullong i = INIT_VALUE + j * TASK_COUNT; i < INIT_VALUE + j * TASK_COUNT + TASK_COUNT; i++) {
                if (!check(i, try_count) && !check(i, 10000)) {
                    printf("found: %lld\n", i);
                } else {
                    // printf("\r%lld", i);
                }
                counting--;
                if (counting <= 0) {
                    counting = COUNT_TO_LOG;
                    logged_count += 1;
                    printf("process %d: %d / %d\n", j, logged_count, LOG_TOTAL);
                }
            }
            printf("process %d done.\n", j);
            exit(0);
        }
    }
 
    getchar();
    return 0;
}

跑了可能有半小时，输出里找了下很容易看到有一段连续好几百个值，这就是目标区间。当然里面还有一些误报的值， 2 万多个数误报了 20 多个，但是显然这些值是没法重复稳定通过的，只有这个区间里的值能稳定过 !check 。最后回到问题，满足 !check(k) && check(k - 1) 的值就是这个区间里的最小值 1898766093 。

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课

收藏・0

点赞・2

打赏