看雪·众安 2021 KCTF 秋季赛 | 第五题设计思路及解析

资讯作者：看雪学院 2021-11-29 18:40:02 阅读：439

看雪·众安 2021 KCTF秋季赛的第五题《拔刀相向》历时4天，已于今天中午12点关闭攻击通道，截止答题。那么目前的比赛情况如何呢？

攻击方排名前10如下：

已开放赛题的5支防守队伍排名如下：

经统计，第五题《拔刀相向》围观人数1094人：

最终无人能攻破该题。是题目难度太高还是思路太过巧妙呢？想必大家都迫切地想知道此题何解吧

接下来一起来看看解析吧～

出题团队简介

第五题《拔刀相向》出题方： 刘大爷粉丝团99号 战队：

赛题设计思路

谨以此题纪念高光荣教授（1945年-2021年9月12日）。

高光荣教授是中国第一位 MIT 计算机博士，也是整个计算机学界中泰斗级的人物，与其导师 Jack Dennis 一同开创了数据流编程模型的先河，在并行计算与计算机系统结构领域产生了深远的影响。

本题目在高光荣教授提出的 Codelets 的细粒度线程执行模型下，采纳了基于共享内存模型的运行时 DARTS 作为框架，试图通过并行多线程调度的方式打断传统逆向工程中所习惯的控制流分析方法。在单核性能停滞不前的背景下，传统的代码混淆往往会带来无法容忍的性能开销，而并行编程范式则可以在混淆数据变换算法的前提下，甚至带来额外的性能提升。

本题算法主要由三部分构成：

自定义的简陋 Hash 算法，用以对输入的用户名进行处理。
一个基于多项式商环的 RSA 算法。因为多项式相较于整数更加易于分解，故而可以还原得到输入。
一个随机生成的 16 轮 Feistel 结构的变换。

这三个部分分别对应密码学中最常见的三种算法：信息摘要，非对称加密，对称加密，旨在模拟实际情况中所用的密码学算法（为了避免侧信道等非预期解法故而避开了标准的 AES 和 RSA 等等）。

题目代码已经上传，如需详细研究可以对照源代码（还有源代码中的解题脚本 .ipynb 文件）一同参看。

主要流程

题目验证流程如图所示，直线箭头标识着主要的 Codelets/ThreadedProcedure 之间的数据依赖。曲线箭头则标识了一些内部的 Codelets 的数据依赖。在 DARTS 运行时下，无数据依赖的 codelets 会被并行调度。高度并行化使得在任意时刻下断点，内存中可能都不会存在一个严格的算法中间状态。比如 Feistel 算法中的不同层级可能会同时执行。blockHash 的结果可能也并未存储在某个特定的位置，而是仅仅存在于其后的 blockAdder 加法器中。

数据结构

本题主要数据都在于 Poly 结构体中：

struct Poly {    PolyBlock blocks[6];    Poly() :blocks() {}    PolyBlock& operator[](int i) {        return blocks[i];    }    void reset(){        for(int i = 0; i < 6; i++){            blocks[i].reset();        }    }};

Poly 是一个最高次数为 23 次的多项式。加上常数项一共有 24 项，从低到高每 3 项为一个 PolyBlock，一共有 6 个 PolyBlock。

PolyBlock 是一个包含了 4 个系数的多项式块，每个系数都是模 61 意义下的。故而可以用 6 个 bit 表示一个系数（61 < 2^6）。四个系数一共 4*6 = 24 个 bit，也就是 3 个 bytes。把多项式块的内部 bits 顺序全部打乱，再异或一个固定的随机 mask，就是 PolyBlock 的混淆后的二进制表示：

struct PolyBlock {    uint8_t ele[3];    PolyBlock() : ele(){}    void reset() {        ele[0] = 0xf7;        ele[1] = 0x31;        ele[2] = 0x89;    }    //省略部分代码    PolyBlock& operator+=(PolyBlock& rhs) {        this->set<3>(((*this).get<3>() + rhs.get<3>()) % 61);        this->set<0>(((*this).get<0>() + rhs.get<0>()) % 61);        this->set<2>(((*this).get<2>() + rhs.get<2>()) % 61);        this->set<1>(((*this).get<1>() + rhs.get<1>()) % 61);        return *this;    }    friend PolyBlock operator+(PolyBlock lhs, PolyBlock& rhs) {        lhs += rhs;        return lhs;    }    //省略部分代码};

本题中大部分数据变换的最小单位都是 PolyBlock。

blockHash

这个是基于 xorshift 结构构造的一个简易的类似于 PRF (pseudo random function) 的作用。算法很简单：

// 输入是长度为 9 的 uint8_t 的数组 data，也就是 3 个 PolyBlock。输出是 1 个 PolyBlock （也就是 3 个 uint8_t）。void blockHasher::fire(){    uint64_t x = *(uint64_t*)hh.data;    x ^= hh.data[8];    x ^= x >> 12;    x ^= x << 25;    x ^= x >> 27;    x *= 0x2545F4914F6CDD1DULL;    *((uint8_t*)result) = x&0xFF;    *((uint8_t*)result+1) = (x >> 8)&0xFF;    *((uint8_t*)result+2) = (x >> 16)&0xFF;    toSignal->decDep();}

这个 PRF 在构造用户名 hash 和 Feistel 对称加密中都有用到。

StrHasher

随手写的一个基于上述 blockHash 的 Hash 算法。没用到什么构造，所以效果很差。因为做出来本题不需要研究这种不可逆的 Hash 算法，所以没太花功夫。具体算法可以自己看看代码，做题的时候只需要在内存里提取 'KCTF' 对应的 Hash 数据即可。

PolyFeistel

一个随机生成的 16 层的 6 路 Feistel 网络，目的是把 blockHash 这种类似于 PRF 的玩意转化为 PRP (pseudo random permutation)（参看 Luby-Rackoff 定理）。

一层随机 Feistel 结构如图所示：（随机生成的结构展示，与实际中具体的数据变换不同）

程序从上一层的多项式中随机选取 3 个 polyBlock 作为 blockHash 的输入，生成的输出与剩下三个 polyBlock 相加（在多项式环中），然后将用来 hash 的 block 和 blockAdder 的输出随机排列成下一层的多项式。

因为 Feistel 结构可逆，所以这一层结构可以逆向回去。

PolyRSA

PolyRSA 是一个在 GF(61) 下模多项式 t^24 + 51*t^21 + 55*t^20 + 2*t^19 + 3*t^18 + 35*t^17 + 13*t^16 + 5*t^15 + 25*t^14 + 40*t^13 + 11*t^12 + 17*t^11 + 48*t^10 + 26*t^9 + 48*t^8 + 54*t^7 + 5*t^6 + 19*t^5 + 28*t^4 + 43*t^2 + t + 38 的商环中进行的 RSA。

首先题目中实现了模上述多项式的乘法，然后通过快速幂算法，计算出 poly 的 2^0 + 2^7 + 2^21 + 2^31 次方。

通过 SageMath 很容易求得上述多项式可以分解为 (t^11 + 19*t^6 + 55*t^5 + 2*t^4 + 7*t^3 + 30*t^2 + 59*t + 30) * (t^13 + 51*t^10 + 55*t^9 + 44*t^8 + 9*t^7 + 33*t^6 + 13*t^5 + 29*t^4 + 29*t^3 + 2*t^2 + 58*t + 46)。所以对应的 RSA 的 phi 为 (61^11-1)*(61^13-1)，按照类似于 RSA 的算法，取逆后即可还原。

多项式的乘法经过了复杂的混淆，（是由 trivial 的 O(n^2) 多项式乘法算法的中间步骤累加而成，生成方法可以看脚本），可能比较难以识别出模多项式。实际上如果通过快速幂算法识别出 RSA 的结构，可以简单通过特殊数据尝试出实际的模多项式。另一种可能的方法是已知多项式最高次幂必为 24，然后猜测分解后两多项式的幂次，从而直接得到 phi（不需要分解）。