“部落冲突”破解思路

------------------------------

“部落冲突”是一个模拟实战环境的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 随机性检测规范》

具体算法如下：

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课