-
-
[推荐]看雪·安恒 2020 KCTF 春季赛 | 第六题设计思路及解析
-
2020-5-6 18:11
-
赛题点评
出题团队简介
设计思路
1、设计说明
a.把浮点运算的舍入模式ROUND_NEAREST修改为ROUND_UP，使得误差积累到一定程度会产生不同的运算结果；
b.做了一个简单的宏把浮点数存储前做些移位交换，读出后再还原，这个也不算是障碍，ida下F5后会一览无余，虽然把整个表的257项都计算了，实际每个字符只用到其中一项；
c.频度自适应略作修改，每轮权重因子定长+1
2、解题思路
0000000140002ED1 push rax 0000000140002ED2 stmxcsr dword ptr [rsp] 0000000140002ED6 pop rax 0000000140002ED7 and ah, 0DFh 0000000140002EDA or ah, 40h 0000000140002EDD push rax 0000000140002EDE ldmxcsr dword ptr [rsp] 0000000140002EE2 pop rax 查询SSE指令集得知，这是把浮点运算的默认舍入模式ROUND_NEAREST修改为ROUND_UP
#include <float.h> _set_controlfp(RC_UP,MCW_RC);
解析过程
1、分析
程序逻辑比较简单，拿 IDA 简单看看，可以看出程序的结构是将输入编码了 16 轮，与固定的输出比较。
编码过程中大量用了浮点数。将 F5 出来的验证代码直接复制出来，胡乱改一改，可以整理出还算漂亮的形式：
double XJBShuffleBit1(double x) {
auto v = bit_cast<_QWORD>(x);
v = ((v & 0x7FFFFFFC00ll | ((LOBYTE(v) & 7 | ((v & 0xFFFFFFFFFFFFFFF8ull) << 30)) << 6)) << 18) | ((v & 0x10000000000000ll | (((v >> 1) ^ (v ^ (v >> 1)) & 0xFFF8000000000ull) >> 14)) >> 25);
return bit_cast<double>(v);
}
double XJBShuffleBit2(double x) {
auto v = bit_cast<_QWORD>(x);
v = ((v & 0x8000000 | ((v & 0x1FFF | (2 * (v & 0xFFFFFFFFFFFFE000ull))) << 14)) << 25) | ((v & 0x1FFFFFFF0000000ll | (((v >> 30) ^ ((unsigned int)v ^ (unsigned int)(v >> 30)) & 0x7000000) >> 6)) >> 18);
return bit_cast<double>(v);
}
bool Check(unsigned char hexdecoded[32]) {
int prob[257]; // [rsp+60h] [rbp-A0h]
double ep[257]; // [rsp+470h] [rbp+370h]
unsigned char bits[1024]; // [rsp+1040h] [rbp+F40h]
unsigned char output[8192]; // [rsp+1440h] [rbp+1340h]
unsigned char input[8192]; // [rsp+3440h] [rbp+3340h]
memset(input, 0, sizeof(input));
memset(output, 0, sizeof(output));
memcpy(input, hexdecoded, 32);
int input_len = 32;
int output_len = 0;
auto Emit = [&](int byteidx, int bitcnt = 8) {
char packed = 0;
for (int bi = 0; bi < bitcnt; bi++) {
packed |= bits[8 * byteidx + bi] << (7 - bi);
}
output[output_len++] = packed;
};
for (int round = 0; round < 16; round++) {
double lower = 0.0;
double upper = 1.0;
memset(bits, 0, sizeof(bits));
memset(ep, 0, sizeof(ep));
int total_bits = 0;
// First 2 bytes: input_len
*(unsigned short *)output = input_len;
output_len = 2;
for (int i = 0; i < 257; i++) {
prob[i] = i;
}
unsigned int output_byte_cnt = 0;
for (int idx = 0; idx < input_len + 5; idx++) {
unsigned char tch = (idx < input_len) ? input[idx] : (idx & 1);
double unit = (upper - lower) / (double)prob[256];
for (int i = 0; i < 257; i++) {
ep[i] = XJBShuffleBit1((double)prob[i] * unit + lower);
}
lower = XJBShuffleBit2(ep[tch]);
upper = XJBShuffleBit2(ep[tch + 1]);
double dlower = lower * 2.0;
double dupper = upper * 2.0;
while ((int)dlower == (int)dupper) {
assert(!isnan(dlower) && !isnan(dupper));
bits[total_bits++] = (int)dlower;
upper = dupper - (int)dupper;
lower = dlower - (int)dlower;
dupper = upper * 2.0;
dlower = lower * 2.0;
}
output_byte_cnt = total_bits / 8;
total_bits %= 8;
for (int t = 0; t < output_byte_cnt; t++) {
Emit(t);
}
memmove(bits, &bits[8 * output_byte_cnt], total_bits);
for (int j = tch + 1; j < 257; ++j) {
prob[j] += tch % (round + 16) + round + 16;
}
}
if (total_bits) {
Emit(output_byte_cnt, total_bits);
}
memmove(input, output, output_len);
input_len = output_len;
}
return output_len == 906 && memcmp(output, answer_bin, 906) == 0;
}可以看出在浮点数运算中穿插的 XJBShuffleBit1 和 XJBShuffleBit2 互为逆运算，可以去掉。剩下的部分看起来就是一个用浮点数做的算术编码。
用浮点数做的算术编码一定存在精度问题，整理出程序之后我们首先来尝试把两边的输出对上。
随便输入一个数据（比如 0000000000000000000000000000000000000000000000000000000000000000），可以发现上面贴的代码和原始程序的输出并不相符。
打印 lower、upper、unit 并在调试器里观察对应的值，发现大约第三轮左右开始出现了最低位差 1 的情况。
遇到这种东西第一反应自然是 rounding 参数不同。
x86 CPU 有两个地方可以控制 rounding mode，一个是 FPU ControlWord，还有一个是 MXCSR。
该程序里 x87 指令和 SIMD 指令似乎都有用到（没仔细看），我们把这两个值从调试器里抄出来在自己的程序里设置上：
void InitializeCPUState() {
fpu_control_t fpu_cw;
_FPU_GETCW(fpu_cw);
fprintf(stderr, "old fpu_cw = %#x\n", fpu_cw);
fpu_cw = 0x27F;
_FPU_SETCW(fpu_cw);
fprintf(stderr, "new fpu_cw = %#x\n", fpu_cw);
fprintf(stderr, "old MXCSR = %#x\n", _mm_getcsr());
_mm_setcsr(0x5FA0);
fprintf(stderr, "new MXCSR = %#x\n", _mm_getcsr());
}设置完后会发现编码结果已经可以对上了。
2 、求解
写一个算术编码的解码程序即可。注意不要改变上述的任何计算的形式以免引入数值精度问题。考虑到数据不大，可以写的暴力一点。详细见附件。（https://bbs.pediy.com/thread-259160.htm）
运行即可得到答案504964774D526B756F467A705C4D654B7645587746634A7A75505F757A75776C。
[培训]二进制漏洞攻防（第3期）；满10人开班；模糊测试与工具使用二次开发；网络协议漏洞挖掘；Linux内核漏洞挖掘与利用；AOSP漏洞挖掘与利用；代码审计。
|
|
|---|---|
