看雪CTF.TSRC 2018 团队赛 第七题 『魔法森林』 解题思路

发布日期:2021-11-01 11:07    点击次数:64

有一片神奇的森林,森林里的每棵树都不一样。每棵树和其他树之间都有一扇神奇的门,你会通过一扇门到达另一棵树。魔门是双面的,顺时针和逆时针经过会到达两个不同的目的地;只有沿着正确的路线穿过这些魔门,我们才能走出这片神奇的森林。

森林里有一只独角兽。她有两件法宝:天书和金蛋。

魔法森林的设计思路记录在天书里,可以帮你找到出路,但只有金蛋才能打开天书;

不幸的是,独角兽失去了金蛋。只有当你找到金蛋并把它交给独角兽时,她才能带你走出这片神奇的森林...。

【/br/】第七个问题“魔法森林”,今天(12月15日)中午12: 00结束,这意味着本次KFCT已经走过了上半场阶段。

魔法森林充满了魔力,让人头晕目眩,以至于48小时内只有一支队伍能够突破,冲破森林的浓雾!

他中午刚提问题搬砖头,狗就哭了!165202s(约45.8小时)走出森林迷雾!

最新事件列表。

第七个问题后攻击者的最新排名如下:(前十名)。

这个话题讲完后,攻击者的Top 10排名是一样的。

中午,提出问题,搬砖。狗哭啊哭。他们还能在下一场比赛中坐第一吗?

排名会不会再次大幅调整?

第七题 点评

无冠:魔法森林的设计遵循“安全、通用、高效、简洁”的原则,并准备了“故事介绍”,增加话题的趣味性。这个题目原则上涉及群论的相关知识,有一定难度。开始第七个问题的团队简介。

写作团队:涂鸦。

团队成员:leafpad是一名新生,喜欢数学,正在柯睿努力学习。队长:少女,一个佛教节目,崇拜每一个人,进入去看雪坛...看战争的时候,我觉得生活很艰难...

大家好!我们又见面了!这一次,我的作品是:第二部逃离密室系列——魔法森林。

既然是系列,显然和之前的作品有关。我们先梳理一下它们之间的联系和区别:

(1)首先他们的设计目标是一致的,都是为了验证我的执念是否可行而设计的(上一期提到过,这里不再赘述);

(2)它们都遵循相同的设计原则:安全、通用、高效和简单。所谓安全是指攻击者忍不住想在雪地里生存观察CTF,而不假设攻击者有知识盲点;所谓普适性,就是保护方法不限制硬件平台、操作系统或编程语言(但我在实际比赛中只能选择一个来实现;所谓高效率,是指不使用攻击难度与防御成本成线性关系的防护手段(期望值为指数级);所谓极简主义,就是不做锦上添花的事情,每一个操作,每一个数据都是必须的,一旦去掉了一定的保护,就会对安全造成致命的威胁。

(3)有意思,虽然这不是比赛所必须的,但我总是准备一个“故事介绍”,希望参与者能有更好的心情来做这个任务(并不是说我看不起对手刻意放水)。

从设计上看,两部作品都采用了“主盾”+“副盾”的结构。主盾的作用是抵御核心攻击,而辅助盾的作用可以理解为主盾的放大器。相似结构在对称密码算法设计中得到了充分验证,可以认为是一种最优结构。然而,魔法森林并不是一个简单的密室逃脱升级。使用主、副盾构结构时,两者有本质区别:

(1)鉴于密室逃脱时辅助盾上有两个严重的bug,不到6小时就被攻破。这个魔法森林取代了辅助护盾(天书,也就是这篇文章),避免了上次的缺陷;

(2)到目前为止,从秘室逃出来的主护盾还没有发现受到有效攻击(可能是因为辅助护盾有严重bug导致防御系统崩溃),但是我发现主护盾有瑕疵(泄漏),所以这个魔法森林升级了主护盾(魔门)。形象地说,是从橡木盾升级为铜盾,铸造一次。更小,更重,没有缝合痕迹。但是和最后一个橡木盾一样,上面涂有防水层,可以抵御攻击者对主盾的直接侵蚀。

(3)增加了第三个护盾——隐身护盾(金蛋)。它的作用是保护辅助盾,可以让辅助盾隐形。如果攻击者找不到辅助护盾,那么主护盾就会受到保护而不被攻击(严格来说,这违反了极简主义原则,因为即使没有它,主体也应该是安全的,所以这个护盾的难度被刻意设置得很低,大致相当于签到问题,但是增加了“下蛋生鸡生蛋”这个有趣的话题)。如果你在比赛中阅读了这篇文章,恭喜你,你找到了辅助护盾。然而,找到辅助护盾并不意味着打破问题。真正的挑战才刚刚开始~!祝你好运!

第七题 魔法森林 解题思路[/s2/]

这个话题的分析最初是由看雪论坛Riatre创建的。

观察标题(再次)给出了没有任何保护的32位控制台应用程序。从读取输入的方式来看,非常下雪。分析程序光明面的逻辑相对简单。请参考以下代码。

#include #include #include #include // 0042E924 kForestEntry// 00431058 kForestExit// 0042E914 kLastKey// 0041EB10 kQGBinOpTable// 0041E710 kCRC32Table#include "const_value.inc"unsigned char *g_control_dword;char g_hexserial在使用主副盾的结构时,这两个作品有本质的区别。;unsigned char g_serial[16];// 00401040void 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 > 8);}返回crc}//004010d 0void generatecontorldword(){无符号char* buf0 =(无符号char *)malloc(0x7a 6u);无符号char* buf1 =(无符号char *)malloc(0x7a 6u);g _ control _ dword = buf 1;if(!buf0 ||!buf 1){printf(" nWrong ");返回;}memset(buf0,0,0x7a 6u);memset(buf1,0,0x7a 6u);无符号int inp_crc = CRC32(g_hexserial,strlen(g _ hex serial));FillTable(kTableInput,inp _ crc | 0xA4A4A4A4,buf 0);FillTable(buf0,CRC32(buf0,0x7A6),buf 1);free(buf 0);}//004011 E0void check serial number(){无符号char buffe[432];GenerateControlDword();memset(buffie,0,sizeof(buffie));memcpy(buffie,kForestEntry,16);【/h/】( int block = 1;block > = 1;}cur _ block[I]= cur _ byte;}}if(memcmp(kForestExit,buffie + 416,16)!= 0){printf(" n RoR!序列号!nn ");} else {for(int I = 0;i 请注意,0xA4A4A4A4包含12位,因此实际有效输入仅为20位。请直接枚举,根据原程序中GenerateControlDword的逻辑计算输出,然后找到里面有“forest”这个词的。结果可获得以下文本(GBK码,共1958字节):

参见雪CTF从入门到生存(2)主盾和辅助盾。

大家好!我们又见面了!这一次,我的作品是:密室逃脱系列第二部——魔法森林。

既然系列明显和之前的作品有关,那我们就先梳理一下它们之间的联系和区别。

(1)首先,他们的设计目标是一致的,验证我的执念是否可行(上一期提到过,这里不再赘述)。

(2)它们都遵循着同样的设计原则:安全、通用、高效、简洁所谓安全是指在看CTF的雪中生存的希望?攻击者不能不假设攻击者有知识盲点。所谓的通用保护方法,并不局限于硬件平台、操作系统或编程语言(但我在实际比赛中只能选择一种来实现)。

所谓高效就是不使用攻击难度和防御成本成线性关系的防护手段(期望值是指数级的)所谓极简就是不做锦上添花的事情,每一个操作,每一个数据都是必须的。一旦某项保护被解除,就会对安全构成致命威胁。

(3)有意思虽然这不是比赛必须的,但我每次都准备了一个‘故事介绍’,希望参与者能有更好的心情来做这道题(并不是看不起对手故意放水)从设计上看,两部作品都采用了‘主盾’+‘辅助盾’的结构主盾的作用是抵御核心攻击。Br/]类似的结构在对称密码算法的设计中得到了充分的验证,可以认为是一种最优结构。然而,魔法森林并不是密室逃脱的简单升级。

[36]

(1)鉴于密室逃脱时辅助盾上有两个严重的bug,不到6小时就被攻破。这个魔法森林取代了辅助护盾(天书,也就是这篇文章),避免了最后一个缺陷。

(2)到目前为止,从秘室逃出来的主护盾还没有发现受到有效攻击(可能是因为辅助护盾有严重bug导致防御系统崩溃,所以没有人从事主护盾),但是我发现主护盾上有瑕疵(泄漏),所以这次魔法森林升级了主护盾(魔门)。

形象地说,从橡木盾升级为铜盾,一次铸造更小更重,没有拼接痕迹,但和最后一个橡木盾一样,涂有防水层,可以抵御攻击者对主盾的直接侵蚀。

(3)增加第三个护盾——隐身护盾(金蛋)。它的作用是保护辅助盾。它可以让辅助护盾隐形。如果攻击者找不到辅助护盾,主护盾会受到保护而不被攻击(严格来说,这违反了极简主义原则,因为主体即使没有它也应该是安全的,所以这个护盾的难度被刻意设置得很低,大致相当于签到问题,但增加了“下蛋生鸡,下蛋生鸡”这个有趣的话题)。

但是找到辅助护盾并不意味着破解问题。

真正的挑战才刚刚开始。

祝你好运!我们假设现在已经确定了ControlDword,那么就看下面的计算。

下面的计算只包括一个操作,就是查一个255×255的表,看起来是把一个原始组(q)的二进制运算的结果打成一个表,而不是直接写出运算过程,从而混淆程序。(这也是一般的方法。TODO:贴几个链接)注意ControlDword是用来控制操作的左右顺序的,所以这个二进制操作大部分是不可交换的。经过验证,可以发现这是真的。同时注意这张表是拉丁方,所以是准群。通过简单地验证其他容易找到的性质,我们可以发现关联定律并不满足,但是只有一个幂等元素89。注意下一个操作的输入和输出都是可见的字符串,所以我们只能控制中间的串行混合。这个伪群必须以某种形式构造并具有某种性质,否则很难达到上述目的。观察AB/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, ...],...]

这表明我们的准群可能是中间的。验证它是真实的。看了一会儿各种pdf,找到了一个叫布鲁克-默多克-丰田章男主题的东西,下一步就是体力劳动了。(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 his2ourint BinOp(int a, int b) {return our2his[(241 * his2our[a] + 227 * his2our[b]) % 255];}

注意映射过程是可以取出来放入输入输出的,也就是说映射到Z_{255}之后,运算是线性的,所以可以直接求解。求解。

Sage 代码。import structimport copycontrol_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] * 255for i in xrange(255):our2his[his2our[i]] = ikForestEntry = 'xd5xe2xcaxc7xc4xa7xb7xa8xc9xadxc1xd6xc8xebxbfxda'kForestExit = 'xc9xadxc1xd6xb5xc4xb3xf6xbfxdaxd4xdaxd5xe2xc0xef'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] * 16self.const = 0if var is not None:self.coeff[var] = 1def fma(self, k, a):result = copy.deepcopy(self)if isinstance(a, int):result.const = (result.const + k * a) % 255else:assert isinstance(a, Expr), type(a)for i in xrange(16):result.coeff[i] = (result.coeff[i] + k * a.coeff[i]) % 255result.const = (result.const + k * a.const) % 255return resultdef qg_op(a, b):return Expr().fma(k0, a).fma(k1, b)buffie = [None] * 432buffie[:16] = kForestEntryserial = [Expr(i) for i in xrange(16)]def op(a, b, ctrl):if ctrl & 1:a, b = b, areturn 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 >>= 1for j in xrange(16):cur_byte = op(cur_byte, serial[j], as_be_dword)as_be_dword >>= 1buffie[blkno * 16 + i] = cur_bytemat = []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, valmat.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()

运行后,可以得到答案64 ad 6a 44 b 63 F9 ea 5630d 4 e 1335d 54 a 6。经过验证,可以发现CRC是符合的。运行后,你会发现程序输出“恭喜你走出森林”。合作伙伴

腾讯安全应急中心腾讯安全先锋TSRC负责发现和处理腾讯安全漏洞和黑客攻击。这是一个没有硝烟的战场,我们与2万多名安全专家并肩同行,共同捍卫全球数亿用户的信息和财产安全。一直以来,我们怀着感恩的心,努力打造一个开放的TSRC交流平台,回馈平安社区。未来,我们将继续携手安全行业精英,探索互联网安全新方向,构建互联网安全生态,开创“互联网+”新时代。

Http://weixin.qq.com/r/H3VudjvE02asrX8V9yAN(二维码自动识别)

请注意:从薛雪学院转学。

看雪CTF。TSRC 2018团体赛解题思路总结:。

看雪CTF。TSRC 2018年团体赛,第一题,“世纪初”。

看雪CTF。TSRC 2018年团体赛,第二题“半加法器”。

看到薛。TSRC 2018团体赛的第三题“七十二疑”。

看雪CTF。TSRC 2018年团体赛第四题,“盗梦空房”。

看到薛。TSRC 2018年团体赛,第五题《交响乐》。

看看雪CTF。TSRC 2018年团体赛,第六题,“追兵也在”,解决问题。

看看雪CTF。TSRC 2018年团体赛,第七题,“魔法森林”。

看看雪CTF。TSRC 2018年团体赛,第八题,“双向陪衬”。

看看雪CTF。TSRC 2018年团体赛,第九题《谍战》。

看到薛。TSRC 2018年团体赛,第十题,“侠义双雄”。