看雪CTF.TSRC 2018 团队赛 第七题 『魔法森林』 解题思路
有一片魔法森林，森林里的每一颗树都不一样；每一颗树与别的树之间都有一扇魔法门，穿过一扇门就会到达另一颗树；魔法门是双面的，顺时针穿过和逆时针穿过，会到达两个不同的目的地；只有按照正确的路线穿过这些魔法门才能走出这片魔法森林。
森林里有一只独角兽 她有两件法宝：天书 和 金蛋；
天书里记录着《魔法森林》设计思路，能帮你找到出路，但是，能开启天书的就只有那枚金蛋；
可惜的是，独角兽弄丢了那枚金蛋，你只有找到金蛋，交给独角兽，她才能带你走出这片魔法森林......
第七题《魔法森林》在今天（12月15日）中午12：00 攻击结束，意味着本次KFCT已经走完了前半阶段。
魔法森林充满魔幻让人眩晕，以至于本题在48小时内只有一个团队将其攻破，闯出森林的团团迷雾！
他就是中午放题搬砖狗哭哭！ 以 165202s（约45.8小时）冲出森林迷雾！
最新赛况战况一览
攻击方在第七题之后的最新排名情况如下：（Top 10）
本题结束后，攻击方Top 10 排名无异。
中午放题搬砖狗哭哭 在接下来的比赛中，还能稳坐第一吗？
又会再次出现排名大调整的景象么？
crownless：
魔法森林这道题的设计遵循了“安全 普适 高效 最简”的原则，而且准备了一份“剧情介绍”来增加题目的趣味性。原理上，此题涉及了群论的相关知识，具有一定的难度。
出题团队： GRAFFINDOR
由看雪论坛 Chikey 原创
大家好！我们又见面了！这一次，我奉上的作品是：密室逃脱系列之二——魔法森林 。
既然说是系列，显然与前一作品是有关系的。我们先来理一下它们之间的关联和区别：
（1）首先，它们的设计目标是一致的，都是为了验证我的执念到底是否可行（在上一期有提到过 这里不再赘述）；
（2）它们都遵循着相同的设计原则：安全、普适、高效、最简。所谓安全， 指的是希望能在看雪CTF中存活，攻击方不禁手，不假设攻击者有知识盲区；所谓普适，指保护方法不限定硬件平台，不限定操作系统，不限定编程语言（但在实际比赛中 我只能选择一种来实现；所谓高效，指不使用攻击难度与防御代价呈线性关系的防护手段（期望是指数关系）；所谓最简，指不做锦上添花的事情，每个操作和每个数据都有存在的必要性， 一旦去掉某个保护都会对安全性形成致命威胁 ；
（3）趣味性，虽然这不是比赛必须的，但是我每次都准备了一份“剧情介绍”希望参与者有个更好的心情来干这道题（不是我看不起对手故意放水）。
从设计上讲，这两次的作品都使用了“主盾”+“副盾”的结构。主盾的作用是抵抗最核心的攻击，而副盾的作用可以理解为是主盾的放大器。类似结构在对称密码算法设计中已经得到了充分的验证，可以认为是一种最优结构。然而，魔法森林并非密室逃脱的简单升级，这两件作品在使用主副盾结构时是有本质区别的：
（1）鉴于密室逃脱在副盾上出现了2处严重bug，导致不到6小时就被攻破 。这次的魔法森林更换了副盾（天书，也就是本文），避免了上次的缺陷；
（2）迄今为止，密室逃脱的主盾还没有被发现受到了有效的攻击（可能是因为副盾出现了严重bug导致防御系统崩溃 所以就没人搞主盾了），但是我自己发现了主盾上的一个缺陷(leakage) 于是这次的魔法森林升级了主盾（魔法门）。形象地说，从橡木盾升级为铜盾，一次铸造成型。更小，更重，没有拼接痕迹。 但和上次的橡木盾一样，都刷了防水层，能够抵抗攻击者对主盾的直接侵蚀 ；
（3）增加了第三面护盾——隐身盾（金蛋）。它的作用是保护副盾，它能让副盾隐身，如果攻击者找不到副盾，那么主盾将免受攻击（严格意义上讲，它违背了最简原则，因为即使没有它，本题也应该安全，所以此盾的难度故意设得很低，大致相当于签到题，但却增加了“蛋生鸡，鸡生蛋”的乐趣话题）。
如果你是在比赛期间看到了此文，那么恭喜你，你已经找到了副盾，但是， 找到了副盾，并不等于攻破了此题，真正的挑战，才刚开始~！
Good Luck!
本题解析由看雪论坛 Riatre 原创。
观察
题目（又³）给出了一个 32 位控制台应用程序，无任何保护。
从读取输入的方式来看，非常的看场雪了。
分析
程序明面上的逻辑比较简单，可参考如下代码。
// 0042E924 kForestEntry
// 00431058 kForestExit
// 0042E914 kLastKey
// 0041EB10 kQGBinOpTable
// 0041E710 kCRC32Table
unsigned char *g_control_dword;
char g_hexserial[36];
unsigned char g_serial[16];
// 00401040
void FillTable(unsigned char *input, unsigned int seed, unsigned char *output) {
unsigned char seed_u8[4];
*(unsigned int*)(seed_u8) = seed;
int sum = 0;
for (int i = 0; i < 1958; i++) {
sum = (sum + seed_u8[i & 3]) % 65025;
output[i] = input[i] ^ kQGBinOpTableFlat[sum];
}
}
// inline @ 0040112F, 00401172
unsigned int CRC32(void* _data, int len) {
unsigned char* data = (unsigned char*)_data;
unsigned int crc = 0x5A1C600E;
for (int i = 0; i < len; i++) {
crc = kCRC32Table[(unsigned char)(crc ^ data[i])] ^ (crc >> 8);
}
return crc;
}
// 004010D0
void GenerateControlDword() {
unsigned char* buf0 = (unsigned char *)malloc(0x7A6u);
unsigned char* buf1 = (unsigned char *)malloc(0x7A6u);
g_control_dword = buf1;
if ( !buf0 || !buf1 ) {
printf("\nWrong");
return;
}
memset(buf0, 0, 0x7A6u);
memset(buf1, 0, 0x7A6u);
unsigned int inp_crc = CRC32(g_hexserial, strlen(g_hexserial));
FillTable(kTableInput, inp_crc | 0xA4A4A4A4, buf0);
FillTable(buf0, CRC32(buf0, 0x7A6), buf1);
free(buf0);
}
// 004011E0
void CheckSerialNumber() {
unsigned char buffie[432];
GenerateControlDword();
memset(buffie, 0, sizeof(buffie));
memcpy(buffie, kForestEntry, 16);
for (int block = 1; block < 27; block++) {
unsigned char* cur_block = buffie + block * 16;
unsigned char* last_block = cur_block - 16;
for (int i = 0; i < 16; i++) {
unsigned int i0 = g_control_dword[(block * 16 - 16 + i) * 4];
unsigned int i1 = g_control_dword[(block * 16 - 16 + i) * 4 + 1];
unsigned int i2 = g_control_dword[(block * 16 - 16 + i) * 4 + 2];
unsigned int i3 = g_control_dword[(block * 16 - 16 + i) * 4 + 3];
unsigned int as_be_dword = i3 + ((i2 + ((i1 + (i0 << 8)) << 8)) << 8);
unsigned char cur_byte = last_block[0];
for (int j = 1; j < 16; j++) {
if ( as_be_dword & 1 ) {
cur_byte = kQGBinOpTable[last_block[j]][cur_byte];
} else {
cur_byte = kQGBinOpTable[cur_byte][last_block[j]];
}
as_be_dword >>= 1;
}
for (int j = 0; j < 16; j++) {
if ( as_be_dword & 1 ) {
cur_byte = kQGBinOpTable[g_serial[j]][cur_byte];
} else {
cur_byte = kQGBinOpTable[cur_byte][g_serial[j]];
}
as_be_dword >>= 1;
}
cur_block[i] = cur_byte;
}
}
if (memcmp(kForestExit, buffie + 416, 16) != 0) {
printf("\nError! SerialNo!\n\n");
} else {
for (int i = 0; i < 16; i++) {
buffie[208 + i] ^= kLastKey[i];
}
buffie[224] = 0;
printf("\n%s\n", &buffie[208]);
}
free(g_control_dword);
g_control_dword = 0;
}
// 00401490
int ReadSerialNumber() {
char buf[36];
printf("\nPlease input your serial:");
scanf("%33s", g_hexserial);
for (int i = 0; i < 16; i++) {
int res = 0;
if (g_hexserial[i * 2] <= 57) {
res += (g_hexserial[i * 2] - 48) * 16;
} else {
res += (g_hexserial[i * 2] - 55) * 16;
}
if (g_hexserial[i * 2 + 1] <= 57) {
res += g_hexserial[i * 2 + 1] - 48;
} else {
res += g_hexserial[i * 2 + 1] - 55;
}
g_serial[i] = res;
}
sprintf(
buf,
"%02X%02X%02X%02X%02X%02X%02X%02X%02X%02X%02X%02X%02X%02X%02X%02X",
g_serial[0], g_serial[1], g_serial[2], g_serial[3],
g_serial[4], g_serial[5], g_serial[6], g_serial[7],
g_serial[8], g_serial[9], g_serial[10], g_serial[11],
g_serial[12], g_serial[13], g_serial[14], g_serial[15]);
return strcmp(g_hexserial, buf) != 0;
}
// 004015E0
int main(int argc, const char **argv) {
if ( ReadSerialNumber() ) {
printf("\nWrong Input!");
system("PAUSE");
return -1;
} else {
CheckSerialNumber();
getchar();
getchar();
return 0;
}
return 0;
}<!-- TODO(riatre): 这段扩写一下讲清楚一点，顺便描述一下输入是怎么构造出来的 -->
后面的计算是在 hexdecode 过的输入上做的，而后面的计算过程又受一个用 hexdecode 之前的输入上算出来的某种 CRC or 上 0xA4A4A4A4 生成的 table （后文称作 ControlDword）有关。这大概就是描述中的“鸡生蛋，蛋生鸡”的部分吧。简单观察后面的计算，不妨设其在 ControlDword 确定的情况下解唯一。这里可以控制用来造出这个行为的变量看起来只有 kTableInput。看起来作者是先确定了 ControlDword 和后面的解之后再构造的前面的部分。根据之前接触到的“看场雪”所出的题目来看，作者是个十分喜欢自hi的人，不妨认为 ControlDword 就是描述中提到的“天书”，并且其至少包含一段有意义的文本。
注意到 0xA4A4A4A4 包含 12 位，因此实际有效的输入只有 20 bit，不妨直接枚举一遍，按照原程序中的 GenerateControlDword 的逻辑算出输出，然后找里面有 “森林” 两个字的。结果可以得到如下文本（GBK 编码，共 1958 字节）：
看雪CTF从入门到存活（二）主盾与副盾
大家好! 我们又见面了! 这一次 我奉上的作品是:密室逃脱系列之二----魔法森林
既然说是系列 显然与前一作品是有关系的 我们先来理一下它们之间的关联和区别
（1）首先 它们的设计目标是一致的 都是为了验证我的执念到底是否可行（在上一期有提到过 这里不再赘述）
（2）它们都遵循着相同的设计原则：安全 普适 高效 最简
所谓安全 指的是希望能在看雪CTF中存活?攻击方不禁手 不假设攻击者有知识盲区
所谓普适 指保护方法不限定硬件平台 不限定操作系统 不限定编程语言（但在实际比赛中 我只能选择一种来实现）
所谓高效 指不使用攻击难度与防御代价呈线性关系的防护手段（期望是指数关系）
所谓最简 指不做锦上添花的事情 每个操作和每个数据都有存在的必要性 一旦去掉某个保护都会对安全性形成致命威胁
（3）趣味性 虽然这不是比赛必须的 但是我每次都准备了一份‘剧情介绍’ 希望参与者有个更好的心情来干这道题（不是我看不起对手故意放水）
从设计上讲 这两次的作品 都使用了‘主盾’+‘副盾’的结构
主盾的作用是抵抗最核心的攻击 而副盾的作用可以理解为是主盾的放大器
类似结构在对称密码算法设计中 已经得到了充分的验证 可以认为是一种最优结构
然而 魔法森林并非密室逃脱的简单升级
这两件作品在使用主副盾结构时 是有本质区别的
（1）鉴于密室逃脱在副盾上出现了2处严重bug 导致不到6小时就被攻破 这次的魔法森林更换了副盾（天书，也就是本文） 避免了上次的缺陷
（2）迄今为止 密室逃脱的主盾还没有被发现受到了有效的攻击（可能是因为副盾出现了严重bug导致防御系统崩溃 所以就没人搞主盾了）但是我自己发现了主盾上的一个缺陷(leakage) 于是这次的魔法森林升级了主盾（魔法门）
形象地说 从橡木盾升级为铜盾 一次铸造成型 更小 更重 没有拼接痕迹 但和上次的橡木盾一样 都刷了防水层 能够抵抗攻击者对主盾的直接侵蚀
（3）增加了第三面护盾——隐身盾（金蛋） 它的作用是保护副盾 它能让副盾隐身 如果攻击者找不到副盾 那么主盾将免受攻击（严格意义上讲 它违背了最简原则 因为即使没有它 本题也应该安全 所以此盾的难度故意设得很低 大致相当于签到题 但却增加了“蛋生鸡，鸡生蛋”的乐趣话题）如果你是在比赛期间看到了此文 那么恭喜你 你已经找到了副盾
但是 找到了副盾 并不等于攻破了此题
真正的挑战 才刚开始
Good Luck!
不妨认为现在 ControlDword 已经确定了，接下来只要看后面的计算即可。
后面的计算只包含一种操作，即查一张
255 x 255 的表，看起来是把某个原群 (Q, •) 的二元运算 •
的结果打成了表而不是直接写出运算过程，以此来对程序进行混淆。（这也是一种通用方法。TODO：粘几个link过来）注意到 ControlDword 用来控制运算的左右顺序，所以多半这个二元运算不是可交换的，验证一下可以发现确实如此。同时注意到这张表是一个 Latin square，因此它是一个拟群。简单验证一下其他容易发现的性质可以发现结合律也不满足，但存在恰好一个幂等元素 89。
注意到后面一通运算的输入和输出都是可见字符串，我们只能控制中间混合进去的 serial，这个拟群一定是通过某种形式构造的，具有某种性质，否则很难实现以上这一点。
<!-- TODO(riatre): 补充更多细节 -->
显然，本题的秘密就藏在这个拟群的构造方式上了。观察 a•b/a 的结果（这里中间当然有一番各种尝试）：
[[0, 210, 209, 1, 2, 208, ...],
[210, 1, 208, 82, 127, 80, ...],
[209, 208, 2, 80, 130, 127, ...],
[1, 82, 80, 3, 5, 86, ...],
[2, 127, 130, 5, 4, 133, ...],
[208, 80, 127, 86, 133, 5, ...],
...]这提示了我们这个拟群可能是 medial 的。验证一下发现确实如此。阅读一会儿各种 pdf，发现有一个叫 Bruck-Murdoch-Toyoda theorem 的东西，接下来就是体力活了。（TODO：描述一下体力活是怎么做的）
经过一番体力活之后，我们可以得到程序里的 kBinOpTable 的其中一种可能的构造是下面这个玩意：
const int his2our[255] = {1, 182, 30, 108, 59, 211, 242, 34, 16, 240, 130, 137, 35, 168, 88, 215, 117, 197, 24, 166, 228, 56, 64, 63, 91, 216, 45, 94, 159, 14, 100, 141, 129, 43, 21, 123, 118, 205, 188, 92, 210, 154, 120, 237, 74, 245, 235, 244, 116, 17, 146, 142, 53, 226, 37, 20, 93, 85, 41, 195, 126, 26, 2, 67, 31, 55, 209, 224, 4, 202, 155, 49, 254, 44, 122, 131, 70, 114, 77, 18, 69, 136, 145, 80, 175, 46, 32, 163, 66, 0, 25, 171, 86, 161, 82, 170, 157, 42, 158, 198, 50, 72, 110, 68, 217, 234, 214, 152, 179, 218, 147, 201, 9, 19, 241, 11, 22, 222, 103, 121, 10, 52, 239, 207, 149, 183, 164, 248, 193, 212, 172, 236, 23, 135, 178, 150, 189, 185, 39, 128, 13, 81, 169, 230, 173, 180, 38, 225, 15, 48, 102, 57, 132, 251, 134, 40, 107, 3, 51, 199, 27, 250, 186, 62, 187, 71, 65, 6, 139, 101, 5, 227, 153, 213, 79, 89, 176, 247, 112, 181, 125, 206, 208, 97, 252, 12, 246, 87, 243, 8, 113, 96, 177, 83, 60, 223, 238, 84, 58, 124, 184, 231, 232, 253, 221, 36, 33, 249, 106, 143, 219, 160, 156, 140, 99, 78, 229, 105, 28, 144, 151, 73, 196, 127, 111, 190, 220, 200, 76, 167, 115, 192, 7, 203, 95, 148, 54, 29, 194, 47, 138, 191, 98, 233, 174, 165, 119, 133, 61, 75, 104, 109, 162, 90, 204};
int our2his[255]; // inverse map of his2our
int BinOp(int a, int b) {
return our2his[(241 * his2our[a] + 227 * his2our[b]) % 255];
}注意到映射的过程可以拿出来放到输入和输出的时候做，也就是说映射到 Z_{255} 上之后这个运算是线性的，所以可以直接解。
解决
Sage 代码。
import struct
import copy
control_dwords = []
with open('tianshu.txt') as fp:
data = fp.read()
for i in xrange(0, len(data) // 4 * 4, 4):
control_dwords.append(struct.unpack('>I', data[i:i+4])[0])
k0, k1, his2our = eval("(241, 227, [1, 182, 30, 108, 59, 211, 242, 34, 16, 240, 130, 137, 35, 168, 88, 215, 117, 197, 24, 166, 228, 56, 64, 63, 91, 216, 45, 94, 159, 14, 100, 141, 129, 43, 21, 123, 118, 205, 188, 92, 210, 154, 120, 237, 74, 245, 235, 244, 116, 17, 146, 142, 53, 226, 37, 20, 93, 85, 41, 195, 126, 26, 2, 67, 31, 55, 209, 224, 4, 202, 155, 49, 254, 44, 122, 131, 70, 114, 77, 18, 69, 136, 145, 80, 175, 46, 32, 163, 66, 0, 25, 171, 86, 161, 82, 170, 157, 42, 158, 198, 50, 72, 110, 68, 217, 234, 214, 152, 179, 218, 147, 201, 9, 19, 241, 11, 22, 222, 103, 121, 10, 52, 239, 207, 149, 183, 164, 248, 193, 212, 172, 236, 23, 135, 178, 150, 189, 185, 39, 128, 13, 81, 169, 230, 173, 180, 38, 225, 15, 48, 102, 57, 132, 251, 134, 40, 107, 3, 51, 199, 27, 250, 186, 62, 187, 71, 65, 6, 139, 101, 5, 227, 153, 213, 79, 89, 176, 247, 112, 181, 125, 206, 208, 97, 252, 12, 246, 87, 243, 8, 113, 96, 177, 83, 60, 223, 238, 84, 58, 124, 184, 231, 232, 253, 221, 36, 33, 249, 106, 143, 219, 160, 156, 140, 99, 78, 229, 105, 28, 144, 151, 73, 196, 127, 111, 190, 220, 200, 76, 167, 115, 192, 7, 203, 95, 148, 54, 29, 194, 47, 138, 191, 98, 233, 174, 165, 119, 133, 61, 75, 104, 109, 162, 90, 204])")
our2his = [None] * 255
for i in xrange(255):
our2his[his2our[i]] = i
kForestEntry = '\xd5\xe2\xca\xc7\xc4\xa7\xb7\xa8\xc9\xad\xc1\xd6\xc8\xeb\xbf\xda'
kForestExit = '\xc9\xad\xc1\xd6\xb5\xc4\xb3\xf6\xbf\xda\xd4\xda\xd5\xe2\xc0\xef'
kForestEntry = map(ord, kForestEntry)
kForestExit = map(ord, kForestExit)
def permute(data):
return map(lambda x: his2our[x], data)
def inverse_permute(data):
return map(lambda x: our2his[x], data)
kForestEntry = permute(kForestEntry)
kForestExit = permute(kForestExit)
class Expr(object):
def __init__(self, var=None):
self.coeff = [0] * 16
self.const = 0
if var is not None:
self.coeff[var] = 1
def fma(self, k, a):
result = copy.deepcopy(self)
if isinstance(a, int):
result.const = (result.const + k * a) % 255
else:
assert isinstance(a, Expr), type(a)
for i in xrange(16):
result.coeff[i] = (result.coeff[i] + k * a.coeff[i]) % 255
result.const = (result.const + k * a.const) % 255
return result
def qg_op(a, b):
return Expr().fma(k0, a).fma(k1, b)
buffie = [None] * 432
buffie[:16] = kForestEntry
serial = [Expr(i) for i in xrange(16)]
def op(a, b, ctrl):
if ctrl & 1:
a, b = b, a
return qg_op(a, b)
for blkno in xrange(1, 27):
last_block = buffie[blkno * 16 - 16:blkno * 16]
for i in xrange(16):
as_be_dword = control_dwords[blkno * 16 - 16 + i]
cur_byte = last_block[0]
for j in xrange(1, 16):
cur_byte = op(cur_byte, last_block[j], as_be_dword)
as_be_dword >>= 1
for j in xrange(16):
cur_byte = op(cur_byte, serial[j], as_be_dword)
as_be_dword >>= 1
buffie[blkno * 16 + i] = cur_byte
mat = []
rhs = []
for i in xrange(16):
vec = map(lambda x: Mod(x, 255), buffie[416 + i].coeff)
val = Mod((kForestExit[i] - buffie[416+i].const) % 255, 255)
# print vec, val
mat.append(vec)
rhs.append(val)
mat = matrix(mat)
rhs = vector(rhs)
solution = mat.solve_right(rhs)
print ''.join(map(chr, inverse_permute(solution))).encode('hex').upper()运行即可得到答案 64AD6A44B63F9EA5630D4E13335D54A6，验证可以发现 CRC 也符合，运行一下会发现程序输出了 “恭喜你走出森林了”。
第八题【二向箔】正在火热进行中
第8题/共15题
《二向箔》将于12月17日中午12:00结束
赶紧参与进来吧~！
热门图书推荐：
合作伙伴
腾讯安全应急响应中心
TSRC，腾讯安全的先头兵，肩负腾讯公司安全漏洞、黑客入侵的发现和处理工作。这是个没有硝烟的战场，我们与两万多名安全专家并肩而行，捍卫全球亿万用户的信息、财产安全。一直以来，我们怀揣感恩之心，努力构建开放的TSRC交流平台，回馈安全社区。未来，我们将继续携手安全行业精英，探索互联网安全新方向，建设互联网生态安全，共铸“互联网+”新时代。
- End -
公众号ID：ikanxue
官方微博：看雪安全
商务合作：wsc@kanxue.com