-
-
[原创][原创]KCTF 2023 第二题 CN星际基地 98k writeup
-
发表于: 2023-9-4 00:34 8266
-
逆向部分,要求输入:
判断长度为 156 :
每隔 39 个字符取一个字符出来,得到长度为 4 的字串,并转成 10 进制数(共39次循环):
如果这个串不包含 '2' ,就转成 2 进制数值,判断这个值不能为 15 :
如果包含 '2' ,则不能四个全为 '2' :
转成的 10 进制值必须比之前的最大值大( max_value 初值为 0 ,则不能为全 '0' )
上面的长度为 4 的字串的 39 轮循环过了之后进入赋值环节, 遇到 '0' 赋值 0 ,遇到 '1' 赋值 1 ,遇到 '2' 赋值 -1 ,否则失败
之后进入 39 轮循环,每轮循环中判断上面得到的每 39 个值相加为 0 ,共 4 组 ( 39 轮循环就是多余的,一次判断就够了);另外还会对每轮中的 1 和 -1 检测,为循环轮数时对应的变量加一次,最终要求 39 轮每轮都有一个值和某种计算得到的值相匹配,并且这个 index 与轮数相同。
然后后面是 md5 检测,输入的 md5 必须是 aac82b7ad77ab00dcef90ac079c9490d 。
39 轮完成后,就会输出 success 。
上面的约束部分抄写出来:
其中第 4 点是那堆复杂的运算比较,每轮需要有对应的,结果化简之后发现是一个恒成立的条件,所以转给队友求解的时候就忽略了这一点了。
逆向到这里就完了,根据上面的部分总结出来限制条件:
除了 md5 ,前面的部分很容易构造,而且解空间非常大,这里给出想到的解空间:
39 个向量,和为零向量,那就可以构造其中三个向量和为 0 ,剩下的取 18 组和为 0 的向量对。
前三个可以取上面的 ('0012', '0120', '0201')
, 或者将 12 替换得到的 ('0021', '0210', '0102')
后面的 18 组和为 0 的向量对, 0 开头的总共有 26 个向量(除去 0000 )也就是 13 对,再减去上面已经用过的 3 对就剩下 10 对可用的; 1 和 2 开头的互相成对,共 26 对(除去全 1 和全 2 ),也就是说上面分析的可行解应该是 2 * C(18, 36)
。而且注意,这还只是可行解的下界,实际的解空间还要更大。很容易验证这部分的分析是否正确,上面贴出来的代码每次运行都会随机生成一组数据并且输出相对应的 crackme 的输入,将 crackme 的 md5 判断部分 patch 掉后运行,输入这里代码得到的随机输出即可得到 success 。
那么 2 * C(18, 36)
有多大呢?
输出:
也就 181 亿,在我上个月刚配的新机上跑的只需要 2 个甚至 3 个小时就能跑完啦!而且这还不是全部解空间,甚至这还只是求一个固定串的 md5 还没加入各种 crackme 相关的逻辑。所以这个逆向附件是完全不符合出题要求的(当然也可能是出题人逻辑写错了,那段重要的逻辑错误写成了一个恒成立的条件)。
后来晚上给出了提示:
1、列向量组里不存在相反值,如 [1,-1,1,0]
与 [-1,1,-1,0]
不能同时存在
2、每个行向量里的 0 的数量 占 1/3
这在逆向附件里是完全体现不出来的,逆向题目在赛程中加条件约束还是第一次见。
不过正好,加了这些约束之后题目就能解了。
重新整理上述逆向出来的逻辑和提示,输入长度是 156 ,字符集在 {0,1,2} 之中,总搜索空间是 3156 ,将字符串排列如下:
M=x1x40x79x118x2x41x80x119⋯⋯⋯⋯x39x78x117x156={c1,c2,⋯,c39}={r1,r2,r3,r4}
其中 {c1,c2,⋯,c39} 和 {r1,r2,r3,r4} 分别是矩阵 M 的列向量与行向量,满足:
在对上述条件分析后发现,列向量满足下面条件:
这样列向量的穷举空间就是 239 ,直接爆破是不可行的,采取中间相遇攻击的思路进行穷举。
分析候选的 39 组列向量组(每组中两个向量,且互为相反向量),由于在 Z3 上 0 相反数是 0,1 、2 互为相反数,这个时候我们考虑这些列向量的第一维度,有 13 组每个都是以 0 开头的(list0):
剩下 26 组则每组中存在 1,2开头的向量各一个(list12):
既然 39 组列向量中每组都要选一个出来,那么必然有 0 的个数为 1/3 ,这就是约束 5 ,因此约束 5 是可以不用给的,可以直接从分析推导出。
这样我们就可以根据约束 3 进行中间相遇攻击了(搜索所有可能解):
上述中间相遇在 i7-13700K 单核上使用 sage 搜索完整个空间不到 30 min,第一步 5 min 左右打表,第二步得到结果几乎是秒出。
一个完整跑完的 log 记录 :
v5 = sub_140002F10(std::cout,
"请输入序列号,按回车键结束。"
);
v6 = std::ostream::operator<<(v5, sub_1400030E0);
sub_140002F10(v6,
"Serial:\t\t"
);
input.size = 0i64;
input.cap = 15i64;
input.data.sstr[0] = 0;
std::string::ctor(&input, empty, 0i64);
LOBYTE(v7) = 10;
v8 = std::ios::widen((
char
*)&std::cin + *(
int
*)(std::cin + 4i64), v7);
sub_1400032F0(std::cin, &input, v8);
v5 = sub_140002F10(std::cout,
"请输入序列号,按回车键结束。"
);
v6 = std::ostream::operator<<(v5, sub_1400030E0);
sub_140002F10(v6,
"Serial:\t\t"
);
input.size = 0i64;
input.cap = 15i64;
input.data.sstr[0] = 0;
std::string::ctor(&input, empty, 0i64);
LOBYTE(v7) = 10;
v8 = std::ios::widen((
char
*)&std::cin + *(
int
*)(std::cin + 4i64), v7);
sub_1400032F0(std::cin, &input, v8);
_input.size = v10;
if
( v10 != 156 )
{
fail1:
v105 = sub_140002F10(std::cout,
"fail"
);
std::ostream::operator<<(v105, sub_1400030E0);
goto
LABEL_228;
}
_input.size = v10;
if
( v10 != 156 )
{
fail1:
v105 = sub_140002F10(std::cout,
"fail"
);
std::ostream::operator<<(v105, sub_1400030E0);
goto
LABEL_228;
}
substr.size = 0i64;
substr.cap = 15i64;
substr.data.sstr[0] = 0;
std::string::ctor(&substr, empty, 0i64);
v16 = 0i64;
do
{
_input_data = (
char
*)&_input;
if
( _input.cap >= 0x10 )
_input_data = _input.data.lstr;
v18 = _input_data[_i + v16];
v19 = substr.size;
if
( substr.size >= substr.cap )
{
sub_140003120(&substr);
}
else
{
++substr.size;
v20 = (
char
*)&substr;
if
( substr.cap >= 0x10 )
v20 = substr.data.lstr;
v20[v19] = v18;
v20[v19 + 1] = 0;
}
v16 += 39i64;
}
while
( v16 < 156 );
v21 =
errno
();
v22 = v21;
v23 = (
char
*)&substr;
if
( substr.cap >= 0x10 )
v23 = substr.data.lstr;
*v21 = 0;
to_int_10 =
strtol
(v23, &EndPtr, 10);
substr.size = 0i64;
substr.cap = 15i64;
substr.data.sstr[0] = 0;
std::string::ctor(&substr, empty, 0i64);
v16 = 0i64;
do
{
_input_data = (
char
*)&_input;
if
( _input.cap >= 0x10 )
_input_data = _input.data.lstr;
v18 = _input_data[_i + v16];
v19 = substr.size;
if
( substr.size >= substr.cap )
{
sub_140003120(&substr);
}
else
{
++substr.size;
v20 = (
char
*)&substr;
if
( substr.cap >= 0x10 )
v20 = substr.data.lstr;
v20[v19] = v18;
v20[v19 + 1] = 0;
}
v16 += 39i64;
}
while
( v16 < 156 );
v21 =
errno
();
v22 = v21;
v23 = (
char
*)&substr;
if
( substr.cap >= 0x10 )
v23 = substr.data.lstr;
*v21 = 0;
to_int_10 =
strtol
(v23, &EndPtr, 10);
if
( !substr.size || (v28 =
memchr
(v25,
'2'
, substr.size)) == 0i64 || v28 - v25 == -1 )
{
v29 =
errno
();
v30 = v29;
v31 = (
char
*)&substr;
if
( substr.cap >= 0x10 )
v31 = substr.data.lstr;
*v29 = 0;
to_int_2 =
strtol
(v31, &v143, 2);
if
( v31 == v143 )
{
std::_Xinvalid_argument(
"invalid stoi argument"
);
__debugbreak();
}
if
( *v30 == ERANGE )
{
std::_Xout_of_range(
"stoi argument out of range"
);
__debugbreak();
}
if
( to_int_2 == 15 )
{
v123 = sub_140002F10(std::cout,
"Fail"
);
std::ostream::operator<<(v123, sub_1400030E0);
goto
LABEL_223;
}
v27 = substr.cap;
v26 = substr.data.lstr;
}
if
( !substr.size || (v28 =
memchr
(v25,
'2'
, substr.size)) == 0i64 || v28 - v25 == -1 )
{
v29 =
errno
();
v30 = v29;
v31 = (
char
*)&substr;
if
( substr.cap >= 0x10 )
v31 = substr.data.lstr;
*v29 = 0;
to_int_2 =
strtol
(v31, &v143, 2);
if
( v31 == v143 )
{
std::_Xinvalid_argument(
"invalid stoi argument"
);
__debugbreak();
}
if
( *v30 == ERANGE )
{
std::_Xout_of_range(
"stoi argument out of range"
);
__debugbreak();
}
if
( to_int_2 == 15 )
{
v123 = sub_140002F10(std::cout,
"Fail"
);
std::ostream::operator<<(v123, sub_1400030E0);
goto
LABEL_223;
}
v27 = substr.cap;
v26 = substr.data.lstr;
}
do
{
v45 = (
int
)v44;
if
( wsubstr[v45] ==
'2'
)
{
if
( !has_2 )
{
has_2 = 1;
if
( ((1 - *((_DWORD *)wsubstr - 2)) | (*((_DWORD *)wsubstr - 3) - (
int
)v43)) < 0 )
{
sub_140002D70(&v145, (unsigned
int
)v43);
wsubstr = v145;
}
}
wsubstr[v45] =
'1'
;
++v41;
}
v44 = (v45 * 2 + 2) >> 1;
}
while
( (
int
)v44 < (
int
)v43 );
if
( has_2 )
{
if
( (
int
)v43 > *((_DWORD *)wsubstr - 3) )
sub_1400012C0(E_INVALIDARG);
*((_DWORD *)wsubstr - 4) = v43;
wsubstr[v43] = 0;
}
if
( v41 == 4 )
{
v60 = sub_140002F10(std::cout,
"Fail"
);
std::ostream::operator<<(v60, sub_1400030E0);
goto
LABEL_220;
}
do
{
v45 = (
int
)v44;
if
( wsubstr[v45] ==
'2'
)
{
if
( !has_2 )
{
has_2 = 1;
if
( ((1 - *((_DWORD *)wsubstr - 2)) | (*((_DWORD *)wsubstr - 3) - (
int
)v43)) < 0 )
{
sub_140002D70(&v145, (unsigned
int
)v43);
wsubstr = v145;
}
}
wsubstr[v45] =
'1'
;
++v41;
}
v44 = (v45 * 2 + 2) >> 1;
}
while
( (
int
)v44 < (
int
)v43 );
if
( has_2 )
{
if
( (
int
)v43 > *((_DWORD *)wsubstr - 3) )
sub_1400012C0(E_INVALIDARG);
*((_DWORD *)wsubstr - 4) = v43;
wsubstr[v43] = 0;
}
if
( v41 == 4 )
{
v60 = sub_140002F10(std::cout,
"Fail"
);
std::ostream::operator<<(v60, sub_1400030E0);
goto
LABEL_220;
}
if
( to_int_10 <= max_value )
break
;
// goto fail
max_value = to_int_10;
if
( to_int_10 <= max_value )
break
;
// goto fail
max_value = to_int_10;
if
( ++_i >= 39 )
{
v55 = 0;
if
( _input.size )
{
v56 = 0i64;
do
{
_y = v55 / 39;
_x = v55 % 39;
v59 = (
char
*)&_input;
if
( _input.cap >= 0x10 )
v59 = _input.data.lstr;
switch
( v59[v56] )
{
case
'0'
:
map[_y][_x] = 0;
break
;
case
'1'
:
map[_y][_x] = 1;
break
;
case
'2'
:
map[_y][_x] = -1;
break
;
default
:
goto
fail1;
}
++v55;
++v56;
}
while
( v55 < _input.size );
}
// ...
}
if
( ++_i >= 39 )
{
v55 = 0;
if
( _input.size )
{
v56 = 0i64;
do
{
_y = v55 / 39;
_x = v55 % 39;
v59 = (
char
*)&_input;
if
( _input.cap >= 0x10 )
v59 = _input.data.lstr;
switch
( v59[v56] )
{
case
'0'
:
map[_y][_x] = 0;
break
;
case
'1'
:
map[_y][_x] = 1;
break
;
case
'2'
:
map[_y][_x] = -1;
break
;
default
:
goto
fail1;
}
++v55;
++v56;
}
while
( v55 < _input.size );
}
// ...
}
_index = 1;
LABEL_115:
y = 0i64;
while
( 1 )
{
count_success_2 = 0;
count_success_1 = 0;
sum = 0;
line_y = map[y];
_13i_add_2 = 2;
_13i_add_3 = 3i64;
do
{
value = line_y[_13i_add_3 - 3];
if
( value == -1 )
{
count_success_2 += _13i_add_2 - 1 == _index;
}
else
if
( value == 1 )
{
count_success_1 += _13i_add_2 - 1 == _index;
}
sum += value;
value = line_y[_13i_add_3 - 2];
if
( value == -1 )
{
count_success_2 += _13i_add_2 == _index;
}
else
if
( value == 1 )
{
count_success_1 += _13i_add_2 == _index;
}
sum += value;
// ...
value = line_y[_13i_add_3 + 9];
if
( value == -1 )
{
count_success_2 += _13i_add_2 + 11 == _index;
}
else
if
( value == 1 )
{
count_success_1 += _13i_add_2 + 11 == _index;
}
sum += value;
_13i_add_2 += 13;
_13i_add_3 += 13i64;
}
while
( _13i_add_3 < 42 );
if
( count_success_2 == count_success_1 )
{
*cmp[y] = 0;
}
else
{
v94 = -1;
if
( count_success_2 < count_success_1 )
v94 = 1;
*cmp[y] = v94;
}
if
( sum )
goto
fail1;
if
( ++y >= 4 )
{
index = 0;
column = 0i64;
map1 = map[1];
map0_sub_map1 = (
char
*)((
char
*)*map - (
char
*)map1);
map2_sub_map1 = (
char
*)((
char
*)map[2] - (
char
*)map1);
map3_sub_map1 = (
char
*)((
char
*)map[3] - (
char
*)map1);
while
( 1 )
{
v97 = **cmp;
v102 = (v97 == *(_DWORD *)&map0_sub_map1[(_QWORD)map1]) + 1;
if
( *cmp[1] != *map1 )
v102 = v97 == *(_DWORD *)&map0_sub_map1[(_QWORD)map1];
v103 = v102 + 1;
if
( *cmp[2] != *(_DWORD *)&map2_sub_map1[(_QWORD)map1] )
v103 = v102;
++index;
v104 = v103 + 1;
if
( *cmp[3] != *(_DWORD *)&map3_sub_map1[(_QWORD)map1] )
v104 = v103;
if
( v104 == 4 )
break
;
++column;
++map1;
if
( column >= 39 )
goto
fail1;
}
if
( index != _index )
goto
fail1;
// ...
_index = 1;
LABEL_115:
y = 0i64;
while
( 1 )
{
count_success_2 = 0;
count_success_1 = 0;
sum = 0;
line_y = map[y];
_13i_add_2 = 2;
_13i_add_3 = 3i64;
do
{
value = line_y[_13i_add_3 - 3];
if
( value == -1 )
{
count_success_2 += _13i_add_2 - 1 == _index;
}
else
if
( value == 1 )
{
count_success_1 += _13i_add_2 - 1 == _index;
}
sum += value;
value = line_y[_13i_add_3 - 2];
if
( value == -1 )
{
count_success_2 += _13i_add_2 == _index;
}
else
if
( value == 1 )
{
count_success_1 += _13i_add_2 == _index;
}
sum += value;
// ...
value = line_y[_13i_add_3 + 9];
if
( value == -1 )
{
count_success_2 += _13i_add_2 + 11 == _index;
}
else
if
( value == 1 )
{
count_success_1 += _13i_add_2 + 11 == _index;
}
sum += value;
_13i_add_2 += 13;
_13i_add_3 += 13i64;
}
while
( _13i_add_3 < 42 );
if
( count_success_2 == count_success_1 )
{
*cmp[y] = 0;
}
else
{
v94 = -1;
if
( count_success_2 < count_success_1 )
v94 = 1;
*cmp[y] = v94;
}
if
( sum )
goto
fail1;
if
( ++y >= 4 )
{
index = 0;
column = 0i64;
map1 = map[1];
[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入!