看雪.纽盾 KCTF 2019 Q2 | 第七题点评及解题思路
时光匆匆，不知不觉间已经迈入了七月，我们一路相伴，经过KCTF精彩激烈的比拼，之后又对赛题依次进行了详细的点评和思路分析，不知道看过题目解析的你有没有感到豁然开朗呢？
今天解析的这道题就厉害了，截至比赛结束时无人攻破。废话不多说，下面就让我们来看下第七题，一起斗智斗勇，看看如何去化解部落冲突！
题目简介
题目背景：
经过几天几夜的奋战，双眼已经开始不听使唤，不停的往下掉。终于，世界变成一片黑暗，思想变得虚无。待双眼睁开，白光闪进双眼，只见一个和你相同模样的人正在你的面前仔细端详着你。
“你是谁？”
“我是你”
空气中开始回荡起一阵阴森诡异的笑声……有一个守护宝石的部落出现在你面前，首领长老叫司看。那个和你长得一样的，是部落里的一位勇士，名叫狂场，勇猛善战。他身后站着一个女巫，斜挎着一个兽皮袋，名叫暴风雪，擅长设置机关和控制天气。
在这个自由的世界里，部落之间经常发生冲突。冲突来临时，他们各有分工。狂场是场上队长，带领着勇士们冲锋陷阵。暴风雪会在开仗之前，先在战场上布下机关，并且在战争过程中通过控制天气来引导狂场正确走位。
如果走位正确，就能毫发无伤；如果走位错误，肯定要被射成刺猬。但是，暴风雪自身很脆弱，一旦被敌人发现就非常危险。所以她通常隐匿在战场的某个角落。而司看的任务就是：监督狂场严格听从天气的指示，禁止狂场回头看暴风雪，以免暴露她隐藏的位置。
狂场已经等了你很久了。能否拿到宝石，就看你的走位了。
本题共有1840人围观，截至比赛结束没有人能攻破此题。是第二赛段难度最高的一道题。
看雪评委crownless点评
“部落冲突”这道题模拟了一个正版软件，假设攻击方花钱购买了这个软件，并获得了一个正确序列号，然后这个攻击者想求出另外一个用户的正确序列号。分析向量表和散列值的叠加结果的随机性，是此题的解题线索。
出题团队简介
本题出题战队 中娅之戒 ：
再拜各位大佬！
本次2019KCTF Q2的中娅之戒由三名队员组成：
Venessa：仍旧被玄学击垮的密码学方向在读研(小)究(姑)生(娘)
loom：我只是一只小猫咪，我不应该为生活发愁.jpg
上海刘一刀：科锐31期4阶段学员，战队里话最多且技术最辣鸡的弟弟，写壳比较像cxk
//这里还有一些奇奇怪怪的资料↓
//http://www.51asm.com/zuixindongtai/xueyuandongtai/2019/0702/247.html
设计思路
“部落冲突”是一个模拟实战环境的CM。
模拟场景：攻击者得到了一组授权后，通过观察分析，使用相关技术推算得到另一组授权。
“部落冲突”是“七十二疑冢”的升级作品。
“七十二疑冢”考验的是攻击方的CRC算法能力。它选用了CRC校验作为基本运算，而CRC函数（在多项式意义下）是线性运算的，从而使得“七十二疑冢”能被高效破解。
为了进一步提高难度，“部落冲突”采用了哈希函数作为作为基本运算，而序列号就是依次序改变哈希函数种子的下标。算法如下：
上一轮种子经过哈希函数生成的散列值（256bit），叠加上由序列号指定的常向量（给定256个向量，每个向量256bit）计算出本轮迭代值，作为下一轮哈希的种子。
按照这样的规则迭代下去，直至穷尽序列号。如果最终计算结果得到全0序列（256bit），即为破解成功。或者说，要想正面攻克部落冲突本质上就是一个寻找弱碰撞的过程，其穷举难度很大。
如果把破解思路安排在hash碰撞上，太没意思，而且也是违规的。
作者安排的正确解法是什么呢？
“部落冲突”模拟了一个正版软件。
假设攻击方花钱购买了这个软件，并获得了一个（以狂场为用户名的）正确序列号，然后这个攻击者想求出另外一个用户（用户名为“你”）的正确序列号。
上述计算过程被包装成一个名为“部落冲突”的游戏。
要求解的序列号就是“你”的走位，只有成功躲开所有射击（中0箭）才能活着走出战阵（破解成功）。
而“你”不是唯一的玩家。游戏中已经有一名叫做“狂场”的通关玩家，并且题干中已经显式给出了他的走位（已知一组正确序列号）。
通过分析“狂场”的走位，发现其中暗藏的规律，应当可以得到解题思路。
分析过程如下：
1）观察狂场的走位，序列号本身并无特殊规律 --> 解题线索蕴藏于走位过程中。
2）游戏的流程是单向进行的，每一轮迭代值由哈希算法迭代生成，不可逆推或跳过 --> 必须一步一步跟踪迭代结果。
3）脱壳后最先可以看到256*256bit的向量表，看起来数据随机毫无规律（但作者是有机会在其中精心构造数据的） --> 作为用来叠加到散列值的向量，不太可能单独成为解题线索，所以攻击者不能抛开哈希函数和散列值单独分析向量表。
4）哈希函数得到怎样的散列值，对于出题者来说也是难以控制（预测或构造）的，同时哈希函数因其特性可以作为伪随机数生成器（或伪随机数生成器的一部分） --> 散列值应当依概率满足伪随机序列的特点，因此也不能作为作者预埋解题线索的地方。
5）结合3）4）分析，尽管向量表和散列值都看似随机，但根据计算流程，二者的叠加结果才是真正值得分析的，作者预留的解题线索只能在这个地方。
6）如果此题的计算过程真的都是随机的，那么作者也难设计有效解法 --> 作者预埋的解题线索必然是“不随机”的。
所以，分析向量表和散列值的叠加结果的随机性，是此题的解题线索。
据此分析“狂场”的走位，使用经典的随机性检测方法*分别对迭代值进行随机性检测，会发现：每3步会出现一个“游程分布*”严重不随机的迭代值。
本题的随机性检测方法，基于 国家密码管理局发布的《GM/T 0005-2012 随机性检测规范》。
具体算法如下：
其中：
n为待检测序列长度（此题中n=256）
igamc为不完全伽马函数（Incomplete Gamma Function）
本题中“狂场”的走位先后经过的迭代值及其游程分布检测P-value值如下：
第0步，初始种子，若以%s输出为“狂场”的汉字，即玩家用户名；
第19步，迭代值为全0序列（中0箭，中箭支数其实就是256bit序列中有多少个1），为此题目标；
第3、6、9、12、15、18步（即每隔3步）所处迭代值及其游程分布检测P-value值如下：
{ 0xAA, 0xD2, 0x6B, 0x41, 0x6E, 0x1D, 0x54, 0x9F, 0xAB, 0x7D, 0xE9, 0x7A, 0x95, 0x6B, 0x4D, 0xD5, 0x55, 0x28, 0xDD, 0xDF, 0x95, 0x06, 0xAF, 0x6A, 0xAB, 0xAA, 0xAA, 0xD5, 0xC0, 0xA6, 0xD9, 0x8D },// 0.0000000000005602
{ 0x55, 0xA6, 0xE8, 0xAD, 0x42, 0xCA, 0xFA, 0xAF, 0xAC, 0x34, 0x32, 0xAA, 0x0D, 0x5F, 0x6C, 0x92, 0x95, 0xDD, 0x6A, 0xFD, 0xA7, 0xDA, 0xAB, 0x4A, 0xBB, 0x6B, 0x68, 0xFD, 0xAA, 0xB5, 0xA1, 0x7A },// 0.0000000000002456
{ 0x57, 0x2E, 0xB6, 0xD5, 0x35, 0xA2, 0xB5, 0x1F, 0x8A, 0xAA, 0xEA, 0x15, 0x5F, 0x50, 0x24, 0x2B, 0x57, 0xF5, 0x5A, 0xAF, 0xFD, 0x45, 0x55, 0xDB, 0x35, 0xFF, 0x6E, 0x25, 0xA8, 0x95, 0xAA, 0xA5 },// 0.0000000000000025
{ 0xAA, 0xD5, 0x67, 0xDA, 0x92, 0xCC, 0xB4, 0x24, 0xA1, 0x51, 0x6A, 0x36, 0x4A, 0x15, 0x35, 0x54, 0xA1, 0xB5, 0x2B, 0xEB, 0x25, 0xF7, 0xAE, 0xA6, 0xD5, 0x5F, 0x29, 0x3A, 0xA2, 0xAE, 0xAA, 0x22 },// 0.0000000000005478
{ 0x2A, 0xD0, 0xA5, 0x56, 0x49, 0x94, 0x42, 0x5E, 0x52, 0x12, 0xAB, 0x81, 0x15, 0x20, 0xB2, 0x56, 0x50, 0x2F, 0x5A, 0xEA, 0x95, 0xCE, 0xBC, 0xAA, 0x92, 0x15, 0x52, 0x55, 0xA0, 0x4E, 0x75, 0x4A },// 0.0000000000003175
{ 0x52, 0xAB, 0xA0, 0x8D, 0x54, 0xAA, 0xA2, 0xBA, 0x16, 0x88, 0x90, 0x67, 0x12, 0x89, 0x3A, 0x8B, 0xFA, 0xAA, 0xA9, 0x55, 0x15, 0x11, 0x6E, 0x8E, 0x2B, 0xA0, 0xD9, 0x51, 0x71, 0x52, 0x2B, 0xC0 },// 0.0000000000005624可以观察到P-value值均小于10^(-12)
在得知了“游程分布不随机”这个线索之后，可以求解本题：
1）以“你”为初始种子出发
2）以3步为深度限制，遍历所有组合（共256*256*256=2^24=16777216种）
3）对于每种组合得到的散列值，用相同量级检测其游程分布P-value值
4）记录这些随机性严重异常的组合，并以其迭代结果为种子
5）重复步骤2）3）4），就能在5分钟之内找出“你”的完整序列号：3C97E45B5E8DB16C9BD0DF4A00EAED0D8CA413ADCFD68E2EC7923EE2620B62A191135E25C0A6F2B4
附“你”的正确走位各步迭代值的P-value：
附：
1、随机性检测方法：
参见https://baike.baidu.com/item/随机性/10578688
2、游程分布检测（runs distribution test）：
根据国家密码管理局发布的《GM/T 0005-2012 随机性检测规范》，游程分布检测是：一种统计检测项目，用于检测待检序列中相同长度游程（指序列中由连续的“0”或“1”组成的子序列，并且该子序列的前导与后继元素都与其本身元素不同）的数目是否接近一致。
▲
END
精彩回顾：
1、【英雄榜单】看雪.纽盾 KCTF 晋级赛Q2 排行榜出炉！
2、看雪.纽盾 KCTF 2019 Q2 | 第一题点评及解题思路
3、看雪.纽盾 KCTF 2019 Q2 | 第二题点评及解题思路
4、看雪.纽盾 KCTF 2019 Q2 | 第三题点评及解题思路
5、看雪.纽盾 KCTF 2019 Q2 | 第四题点评及解题思路
6、看雪.纽盾 KCTF 2019 Q2 | 第五题点评及解题思路
7、看雪.纽盾 KCTF 2019 Q2 | 第六题点评及解题思路
主办方
看雪学院（www.kanxue.com）是一个专注于PC、移动、智能设备安全研究及逆向工程的开发者社区！创建于2000年，历经19年的发展，受到业内的广泛认同，在行业中树立了令人尊敬的专业形象。平台为会员提供安全知识的在线课程教学，同时为企业提供智能设备安全相关产品和服务。
合作伙伴
上海纽盾科技股份有限公司（www.newdon.net）成立于2009年，是一家以“网络安全”为主轴，以“科技源自生活，纽盾服务社会”为核心经营理念，以网络安全产品的研发、生产、销售、售后服务与相关安全服务为一体的专业安全公司，致力于为数字化时代背景下的用户提供安全产品、安全服务以及等级保护等安全解决方案。
10大议题正式公布！第三届看雪安全开发者峰会重磅来袭！
小手一戳，了解更多