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

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

2023-9-11 23:52 2682

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

GreatIchild 活跃值

2023-9-11 23:52

2682

程序主逻辑没多少，但是加入了大量无关代码，单个函数体积膨胀非常大，这对正常逻辑分析造成了一定阻碍，没办法直接阅读 ida 生成的代码。不过加入的这些逻辑与主要逻辑无关，只要找 F5 中的关键变量（从函数参数或函数返回值入手）的交叉引用，将所有相关的语句手动组合起来即可得到判断逻辑。

大致逻辑恢复如下（后面的注释是该语句在二进制程序中对应的地址）：

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

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int has_debugger() { // 0x402220
    // patch
    return 0;
    // ...
}
 
int check1(char* buf, size_t size) { // 0x455F80
    unsigned int crc = CRC32(buf, size - 4); // 0x457690
    return crc == *(unsigned int*) (buf + size - 4); // 0x457C13
}
 
int check2(void* buf, size_t size, unsigned short** buf1, unsigned short** buf2) {
    if (size >= 0x10) { // 0x45942B
        *buf1 = buf; // 0x45AF4E
        if ((*buf1)[2] && (*buf1)[2] <= size - 16) { // 0x45B836
            *buf2 = (unsigned short *)((unsigned char*) buf + (*buf1)[2] + 8); // 0x45CA22
            if ((*buf2)[2] && (*buf2)[2] <= size - 16 - (*buf1)[2]) { // 0x45D3A3
                return 1;
            } else {
                *buf2 = NULL;
            }
        } else {
            *buf1 = NULL;
        }
    }
    return 0;
}
 
int check_inverse(unsigned long long x, unsigned long long y, unsigned long long z) {
    return x * y % z == 1;
}
 
int check3(unsigned int x, unsigned int y) { // 0x474170
    unsigned long long p = 0x346F8717, a = 32069; // 0x47546A
    if (check_inverse(a, x, p)) { // 0x477A1C
        p = 0x729969FF;
        a = 55057; // 0x478965
        if (check_inverse(a, y, p)) { // 0x47A972
            return 1;
        }
    }
    return 0;
}
 
unsigned int* alloc_map(size_t n) { // 0x4D2250
    return (unsigned int*) malloc(4 * n * n); // 0x4D34CD
}
 
void set_value(unsigned int* map, size_t n, unsigned int y, unsigned int x, unsigned int value) { // 0x4D45A0
    map[n * y + x] = value;
}
 
unsigned int get_value(unsigned int* map, size_t n, unsigned int y, unsigned int x) { // 0x4D6450
    return map[n * y + x];
}
 
void create_map(size_t n, unsigned int** map) { // 0x4D76B0
    if (n % 4) return;
    unsigned int* _map = alloc_map(n); // 0x4D82D0
    int value = 1; // 0x4D8B3F
    for (int y = 0; y < n; y++) {
        for (int x = 0; x < n; x++) {
            set_value(_map, n, y, x, value); // 0x4D956F
            value++; // 0x4D986A
        }
    }
    size_t y1 = 0; // 0x4DA51B
    size_t y2 = n - 1; // 0x4DA9DB
    while (y1 < y2) { // 0x4DB041
        for (int x = 0; x < n; x++) { // 0x4DB3E7
            if (x % 4 == 0 || x % 4 == 3) { // 0x4DB913
                unsigned int a = get_value(_map, n, y1, x); // 0x4DC2A8
                unsigned int b = get_value(_map, n, y2, x); // 0x4DCD5B
                set_value(_map, n, y1, x, b); // 0x4DCD7D
                set_value(_map, n, y2, x, a); // 0x4DD05C
            }
        }
        y1++; // 0x4DDB3A
        y2--; // 0x4DE105
    }
    *map = _map; // 0x4DF1E8
}
 
void shuffle_map(unsigned int* map, size_t n, unsigned int seed) { // 0x4DF410
    srand(seed); // 0x4DF75D
    for (int y1 = 0; y1 < n; y1++) { // 0x4DFF3B
        for (int x1 = 0; x1 < n; x1++) { // 0x4E017C
            unsigned int v1 = get_value(map, n, y1, x1); // 0x4E04A6
            unsigned int y2 = rand() % n; // 0x4E09C4
            unsigned int x2 = rand() % n; // 0x4E0CA2
            unsigned int v2 = get_value(map, n, y2, x2); // 0x4E1197
            set_value(map, n, y1, x1, v2);
            set_value(map, n, y2, x2, v1); // 0x4E12EC
        }
    }
}
 
void trans(unsigned int seed, char* buf, size_t size) { // 0x4E1620
    unsigned int* map;
    size_t n = 16; // 0x4E1B9B
    create_map(n, &map); // 0x4E21C3
    shuffle_map(map, n, seed); // 0x4E27BD
    int x = 0; // 0x4E4442
    int y = 0; // 0x4E4452
    int i = 0; // 0x4E445E
    while (i < size) { // 0x4E4823
        buf[i] ^= get_value(map, n, y, x); // 0x4E492B
        if (i % n == 0) { // 0x4E4BDE
            y++; // 0x4E4F92
            x = 0; // 0x4E5402
        }
        x++; // 0x4E641B
        i++; // 0x4E68C7
    }
}
 
char* alloc_buf() { // 0x423810
    return (char*) malloc(200); //
}
 
unsigned long long get_values1(char** buf, size_t* size) {
    *size = 74;
    char* _buf = (char*) malloc(74);
    char __buf[] = {
        // ...
    };
    memcpy(_buf, __buf, 74);
    *buf = _buf; // 004A79EA;
    return 0xAAC82A5B;
}
 
void buf_set_values(char* buf, unsigned long long value) { // 0x426150
    memset(buf, 0, 200); // ???
    *(unsigned long long*) buf = value;
}
 
int buf_len(char* buf) { // 0x421970
    int i;
    for (i = 199; i >= 0; i--) {
        if (buf[i]) break;
    }
    return i + 1;
}
 
int buf_empty(char* x) {
    for (int i = 0; i < 200; i++) {
        if (x[i]) {
            return 0;
        }
    }
    return 1;
}
 
void buf_add(char* x, char* y, char* z) {
    for (int i = 0; i < 200; i++) {
        z[i] = x[i] + y[i];
    }
}
 
void buf_mul(char *x, char *y, char *z) { // 0x43C130
    memset(z, 0, 200);
    if (buf_empty(x) || buf_empty(y)) { // 0x43DFC5
        return ;
    }
    int x_len = buf_len(x); // 0x43E86F
    int y_len = buf_len(y); // 0x43EDAD
    char* tmp = alloc_buf(); // 0x43F271
    for (int x_index = 0; x_index < x_len; x_index++) { // 0x43F658
        int y_index = 0; // 0x43F8A4
        int value = 0; // 0x43FD65
        memset(tmp, 0, 200);
        while (y_index < y_len) { // 0x440589
            int _value = value + (unsigned char) y[y_index] * (unsigned char) x[x_index]; // 0x440ACE
            tmp[x_index + y_index] = _value; // 0x441393
            value = _value & 0xff00; // 0x4419D8
            value >>= 8; // 0x442168
            ++y_index; // 0x44057D
        }
        if (x_index + y_index < 200) { // 0x442E85
            tmp[x_index + y_index] = value; // 0x44324F
        }
        buf_add(tmp, z, z); // 0x443B53
    }
}
 
void buf_cpy(char* x, char* y) { // 0x429980
    memcpy(x, y, 200);
}
 
void buf_divmod(char* x, char* y, char* z, char* w) { // 0x444F30
    /*
    memset(w, 0, 200);
    if (buf_empty(y)) { // 0x447D10
        return;
    }
    memset(w); // 0x447116
    buf_cpy(w, x); // 0x449797
    v582 = buf_len(w) - buf_len(y); // 0x449A5A
    /**/
}
 
void buf_mod(char* x, char* y, char* z) { // 0x44EA60
    // ...
    buf_divmod(x, y, tmp, z);
}
 
int check_buf(char* x, char* y, char* z) {
    if (buf_len(x) + buf_len(y) > 200) { // 0x4C6123
        return 0;
    }
    char* tmp1 = alloc_buf(); // 0x4C6FF1
    char* tmp2 = alloc_buf(); // 0x4C783E
    buf_mul(x, y, tmp1); // 0x4C9B3F
    buf_mod(tmp1, z, tmp2); // 0x4CA6CB
    // return tmp2 == 1;
    return 1;
}
 
 
int check4(char* buf1, size_t len1, char* buf2, size_t len2) {
    char* dst = alloc_buf(); // 0x461262
    char* tmp = alloc_buf(); // 0x461ACB
    char* out = alloc_buf(); // 0x462284
    char* dst1, dst2;
    size_t size1, size2;
    unsigned long long value1 = get_values1(&dst1, &size1)// 0x462B2D
    buf_set_values(dst, value1); // 0x4632D6
    memcpy(tmp, buf1, len1); // 0x463BD4
    memcpy(out, dst1, size1); // 0x46473E
    if (check_buf(dst, tmp, out)) { // 0x468066
        // 0x46D156
        // get_value2 -> 0x8395475F, buf2, dst2 // 0x4C2285
        // check_buf(dst, tmp, out); // 0x470F73
        return 1;
    }
    return 0;
}
 
int check(char* input) { // sub_47B430
    char* output;
    size_t length;
    if (b64decode(input, &output, &length)) { // 0x47D609
        if (has_debugger() == 1) { // 0x47E402
            if ( (*output & 1) != 0 )
                *output += rand() % 3 + 1;
            else
                *output += rand() % 4 + 4;
        }
        /*
            char a[16] = {
                33, -124, 16, 66, 8, 33, -124, 16,
                66, -56, 81, -121, -61, 0x80, -44, 61
            }
            for (int i = 0; i < (length >> 1); i++) { // 0x47E8A7
                output[i] ^= a[i % 16];
            }
            for (int i = 0; i < length; i++) { // 0x47F146
                output[i] ^= 0x63;
            }
            for (int i = length - 1; i < >= 0; i--) { // 0x47F146
                output[i] ^= 0xa3;
            }
            for (int i = 0; i < length; i++) {
                output[i] ^= 0xa3;
            }
            for (int i = 0; i < length; i++) {
                output[i] ^= 0x63;
            }
            for (int i = 0; i < (length >> 1); i++) { // 0x47FD46
                output[i] ^= a[i % 16];
            }
        /**/
 
        unsigned short* buf1;
        unsigned short* buf2;
        if (check1(output, output_length)) { // 0x480414
            if (check2(output, output_length - 4, &buf1, &buf2)) { // 0x482D0E
                if (check3(*(unsigned int*) buf1, *(unsigned int*) buf2)) { // 0x48564B
                    trans(*(unsigned int*) buf1, (char*)((unsigned char*) buf1 + 8), buf1[2]); // 0x48792E
                    trans(*(unsigned int*) buf2, (char*)((unsigned char*) buf2 + 8), buf2[2]); // 0x488229
                    if (check4((char*)((unsigned char*) buf1 + 8), buf1[2], (char*)((unsigned char*) buf2 + 8), buf2[2])) { // 0x489AFF
                        return 1;
                    }
                }
            }
        }
    }
    return 0;
}

提取出来后发现有一些跟主变量相关的逻辑也是无效逻辑（如重复异或一个值两次），直接忽略这些即可。还有一个函数用于反调试（检测调试器是否存在），直接 patch 为 return 0 。

程序主要逻辑：

将输入 base64 解码；
检查解码后数据的后 4 个字节对应的数值是前面的数据的 CRC32 校验；
解析前面的数据，得到两块数据，其具体结构体形式如下：

struct A {
    int seed; // 0~4
    short length; // 4~6
    // char padding[2]; // 6~8;
    char data[length]; // 8~8+length
};

验证两个 seed 的值，判断的形式是 unsigned __int64 运算中的 seed * y % z == 1 ；
将两块数据中的 data 以 seed 作为随机数种子解密；
验证两段解密后的 data 的值，判断的形式是 char[200] 表示的大数的运算 data * Y % Z == 1 。

4 和 6 中的运算的两组 (y, z) 和 (Y, Z) 都是直接给出来的，就只是个有限域求逆的问题。反向求解输入就行。

先把两组 seed 、解密后的 data 值求出来，再将两者组合得到加密的 data ，再重构结构体、组合得到数据并求 CRC32 附在其后，最后 base64 。

但是此题由于几个地方没完全限制正确导致出现多解。导致多解的原因：

结构体中数据的对其导致多出来 2 字节的填充，这两组 2 字节可以为任意值；可行的解决方案：结构体定义中定义按 1 字节对齐，或者将 length 设置为 int 类型；
大数的结构为 char[200] ，但是实际计算中的 Z 只有 74 字节，也就是解密后的 data 有效字节数为 74 ，那么可以在解密的 data 后添加 0~126 字节的 0 （即高位补 0 ，增加长度但是不改变数值。 126 是因为数据结构 char[200] 是堆上分配的，过长将覆盖后面的数据导致程序崩溃。实际测试最长可增加 129 字节的 0 ）；可行的解决方案：增加对 length 的判断，并且还需要增加一条限制 data < Z 避免出现 data + kZ 的情况；
解析上述第 3 步中的两个数据结构时判断两块数据的长度不大于而不是等于输入的长度，所以这部分输入后面可以有任意长的填充；可行的解决方案：改成等于；
base64 解析时遇到 '=' 直接停止，后面的数据可以为任意值；可行的解决方案：限制输入长度，对第一个 '=' 后面的数据进行有效性判断或者预期输入中直接去掉填充的 '=' 。

题目整体的判断逻辑设计得挺好的，就是逆向的时候看到限制条件太松一定会产生非常多解的，之前的两道逆向题弄出心理阴影了，我都担心最后会出现一个哈希判断。虽然现在还鞭尸不太好，不过还是想多说一下，逆向题里用哈希限制输入的唯一性完全没必要，题目设计时限制条件处理好就不会产生多解。当然也可能会在自己意想不到的地方出现多解，不过公布题解后出题人也能学到一些新的东西，以后的题目中把限制条件做得更精确，大家也可以开心做题。而明明知道限制条件不够强会导致多解的情况下，硬给题目加一个哈希判断就是在耍流氓，加的这个条件达到了出题人限制输入唯一的目的，但是这条件对做题方没有任何帮助，这就是把本来应该由出题人干的活强行塞给做题方来干。当然也不排除某些情况下题目限制条件虽然会导致多解但是没办法再加限制条件了，或者说再加任何条件都会导致题目难度大量下降，如果这时的解不多那就可以加上哈希的条件。当然，我的建议是题目中给出目标哈希值，但是只对其至多两个字节（即 4 个十六进制数值，碰撞概率 1/65536 ）做判断。这样能大概率达到限制解唯一的情况，并且对做题方也很友好。

最后给出逆向脚本以及两组多解：

#!/usr/bin/env python3
 
from Crypto.Util.number import inverse, long_to_bytes
import base64
import zlib
 
# check4
p1 = int.from_bytes(bytes.fromhex('03 8D B6 BB BD 8A DB 73 AC 57 2C 60 51 99 E6 EC AE 56 98 E1 D4 56 BA 9F 90 2B F6 50 9F 1D 23 91 8E 28 AF B9 A4 C5 06 C7 7D AA 28 8E BE 40 12 33 7E 76 17 96 CE 3B 48 2E 83 2E 2C 79 A4 E3 41 0D A3 D1 8E 58 C0 AB D6 B8 C1 D3'), 'little')
x1 = 0xAAC82A5B
p2 = int.from_bytes(bytes.fromhex('05 B3 44 98 B0 EF 11 F7 EB 3B 97 8C A2 FB 6D 6A 59 17 C6 A1 98 8B 9C 21 D4 89 06 EC CF 8D E7 74 30 83 37 88 B4 6C 7A 2E 3D 91 50 5E 25 D1 8F EF 12 78 5B AF 3D BA B8 EC 5F 3D FC 7B 37 5B 2D 72 5C EC 12 2C 59 57 AF 41 B4 B5'), 'little')
x2 = 0x8395475F
 
y1 = inverse(x1, p1)
y2 = inverse(x2, p2)
 
# extra_size1 = 203 - 74
extra_size1 = 0
extra_size2 = 0
buf1 = long_to_bytes(y1)[::-1] + b'\x00' * extra_size1
buf2 = long_to_bytes(y2)[::-1] + b'\x00' * extra_size2
len1 = len(buf1)
len2 = len(buf2)
 
# check3
seed1 = inverse(32069, 0x346F8717)
seed2 = inverse(55057, 0x729969FF)
 
_seed = 1
def srand(seed):
    global _seed
    _seed = seed
 
def rand():
    global _seed
    _seed = 214013 * _seed + 2531011 & 0xffffffff
    return (_seed >> 16) & 0x7fff
 
def trans(seed, buf):
    _map = list(range(1, 257))
    for y in range(8):
        for x in range(16):
            if x % 4 == 0 or x % 4 == 3:
                _map[16 * y + x], _map[16 * (15 - y) + x] = _map[16 * (15 - y) + x], _map[16 * y + x]
    srand(seed)
    for y1 in range(16):
        for x1 in range(16):
            y2 = rand() % 16
            x2 = rand() % 16
            _map[16 * y1 + x1], _map[16 * y2 + x2] = _map[16 * y2 + x2], _map[16 * y1 + x1]
    x = 0
    y = 0
    out = []
    for i in range(len(buf)):
        out.append(buf[i] ^ _map[16 * (y + x // 16) + x % 16] & 0xff)
        if i % 16 == 0:
            y += 1
            x = 0
        x += 1
    return bytes(out)
 
buf1 = trans(seed1, buf1)
buf2 = trans(seed2, buf2)
 
# check2
rand_bytes1 = b'\x00\x00' # 2 random bytes
rand_bytes2 = b'\x00\x00' # 2 random bytes
flag = b''
flag += seed1.to_bytes(4, 'little')
flag += len1.to_bytes(2, 'little') + rand_bytes1
flag += buf1
 
flag += seed2.to_bytes(4, 'little')
flag += len2.to_bytes(2, 'little') + rand_bytes2
flag += buf2
 
# flag += b'A' * 8 # can be any bytes
 
# check1
flag += (zlib.crc32(flag) & 0xffffffff).to_bytes(4, 'little')
 
print(base64.b64encode(flag))
 
 
# solution 1 (standard): KmJTMUoAAAD1UMTRG+iFRaF+30mmANMCEqF3YPgU8FTyUvX6yePJFbEZXZ8tUvO70stWkJgshd+8oMQQITLP8l5HQPPJxxF0gCxZp/r5ja68Up2kckNKAAAAVESbyOlxOm8t5prM6tsrtV9VApTX9NiH1WHIWMEtdKohjkV2bQeZORqMYX9eP7AP1JlenlB3EAchhYJhoiP7R3NzbOYCcnXnqewe7SYM
# solution 2 (extra_size1 = 1): KmJTMUsAAAD1UMTRG+iFRaF+30mmANMCEqF3YPgU8FTyUvX6yePJFbEZXZ8tUvO70stWkJgshd+8oMQQITLP8l5HQPPJxxF0gCxZp/r5ja68UtmdpHJDSgAAAFREm8jpcTpvLeaazOrbK7VfVQKU1/TYh9VhyFjBLXSqIY5Fdm0HmTkajGF/Xj+wD9SZXp5QdxAHIYWCYaIj+0dzc2zmAnJ156nsu9Cu3g==
# solution 3 (rand_bytes1 = b'\x00\x01', rand_bytes2 = b'\x00\x02'): KmJTMUoAAAH1UMTRG+iFRaF+30mmANMCEqF3YPgU8FTyUvX6yePJFbEZXZ8tUvO70stWkJgshd+8oMQQITLP8l5HQPPJxxF0gCxZp/r5ja68Up2kckNKAAACVESbyOlxOm8t5prM6tsrtV9VApTX9NiH1WHIWMEtdKohjkV2bQeZORqMYX9eP7AP1JlenlB3EAchhYJhoiP7R3NzbOYCcnXnqewivEZe