[原创]看雪.TSRC 2017CTF秋季赛第五题 CTF2017-brichfire-CTF对抗-看雪-安全社区|安全招聘|kanxue.com

[原创]看雪.TSRC 2017CTF秋季赛第五题 CTF2017-brichfire

2017-11-3 10:40 3844

[原创]看雪.TSRC 2017CTF秋季赛第五题 CTF2017-brichfire

iweizime

2017-11-3 10:40

3844

大整数
进制转换
置换
流程
其他

这题代码比较多，就不贴汇编代码或者伪代码了。主要讲一下涉及到的两个数据结构和思路。

大整数

程序定义了一个大整数结构，并定义了相应的加、减、乘、除、模等运算。给一下这个数据结构。

struct bignum {
    uint32_t    digits[16];
    int         carray;
    int         length;
};

加、减、乘、除、模的相关运算可以自己分析。

进制转换

比赛规则规定逆向的flag只能包含字母和数字，也就是0-9A-Za-z。因此程序把一个只包含字母和数字的字符串当成62进制的整数，转换成整数后用bignum结构保存。转换规则是0-9, A-Z, a-z对应0-9, 10-35, 36-61。例如KanXueCrackMe2017转换成十进制的整数为334476251944397096847543189896。

然后程序再利用字符0-9A-H将整数转换成18进制，转换规则是0-9, A-H对应0-9, 10-17。例如十进制数334476251944397096847543189896转换成18进制为EDAHE450C741GH441E11BH84。

置换

这里再引入一个数据结构。

struct permutation {
    int32_t origin[0x30];
    int32_t perm[0x30];
    int32_t matrix[6][0x30][0x30];
};

这个数据结构很大，然而程序是在栈中分配的。
程序将origin和perm字段初始化为0-0x2f，即

for (int i=0; i < 0x30; ++i) {
    p->origin = i;
    p->perm = i;
}

将6个0x30*0x30的矩阵也初始化，用于置换操作。其中matrix[0]矩阵初始化如下

0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

置换操作的过程就是perm字段的第i个元素是perm字段和某个矩阵第i列点积。所以矩阵0的置换操作用轮换来表示就是

(0 2 4 6)(1 3 5 7)(c 16 18 22)(d 17 19 23)(10 1a 24 e)

可以发现这个置换操作的周期为4，其他置换操作与之类似，其周期也为4。

流程

经过以上分析，就可以还原程序的思路了。
首先程序经过进制转换将KanXueCrackMe2017转换为EDAHE450C741GH441E11BH84。然后取EDAHE450C741GH441E11BH84每一位来进行置换操作，例如第一位E，表示十进制数14。那么就使用14/3矩阵进行14%3 + 1次置换。
将EDAHE450C741GH441E11BH84转换位(d/3, d%3 + 1)的形式为：

(4, 3)(4, 2)(3, 2)(5, 3)(4, 3)(1, 2)(1, 3)(0, 1)(4, 1)(2, 2)(1, 2)(0, 2)
(5, 2)(5, 3)(1, 2)(1, 2)(0, 2)(4, 3)(0, 2)(0, 2)(3, 3)(5, 3)(2, 3)(1, 2)

因为周期为4，所以可以求逆操作，又因为flag的长度限制为12，KanXueCrackMe2017长度为17，所以还要化简。求逆就是反着开始，(1, 2)->(1, 2), (2, 3)->(2, 1), 化简就是(4, 3)(4, 2)->(4, 5)->(4, 1)。求得逆操作为：

(1, 2)(2, 1)(5, 1)(3, 1)(4, 1)(0, 2)(5, 3)(0, 2)(1,2)
(2, 2)(4, 3)(0, 3)(1, 3)(4, 1)(5,1)(3, 2)(4, 3)

将逆操作转换成18进制数为46F9C1H147E25CFAE，再转换为62进制，也就是最终flag为CcLaoE37J45Y。

其他

程序中有一个int 2d，通过异常实现了跳转，要搞清它跳转到哪里。
求flag过程中用到的结构permutation的值是在程序对它初始化后，从内存中dump出来的。
程序中有一个函数应该是和椭圆曲线有关，但是没有影响做题，所以没有仔细研究，太麻烦了，不要被误导。
程序中有很多类似下面的比较奇怪的代码，要正确的理解这种表达的意思。

int aa[32];
int ba[32];
int c, *pa;

pa = aa;
for (int i = 0; i < 32; ++i) {
    c = *(int *)(pa + ba - aa);     // c = ba[i]
    ++pa;
}

[CTF入门培训]顶尖高校博士及硕士团队亲授《30小时教你玩转CTF》，视频+靶场+题目！助力进入CTF世界

收藏・2

点赞・1

打赏

最新回复 (1)
wx_心隐草雪币： 5 活跃值： (10) 能力值： ( LV2，RANK：10 ) 在线值：发帖 0 回帖 6 粉丝 0 关注私信	wx_心隐草 2017-11-3 13:38 2 楼 0 用指针来操作数组，刚开始还真不习惯。矩阵转换没看明白，还需要学习
	游客登录 \| 注册方可回帖　回帖　表情雪币赚取及消费高级回复

iweizime

发帖

回帖

750

RANK

关注

私信

他的文章

在Ubuntu 20.04上调试sudo堆溢出漏洞CVE-2021-3156

[原创]第三题寻踪觅源

[原创]第二题子鼠开天

[原创]看雪CTF.TSRC 2018 团队赛第二题半加器

[原创]看雪.京东 2018CTF 第六题 PWN-noheap

关于我们

联系我们

企业服务

看雪公众号

最新回复 (1)
wx_心隐草雪币： 5 活跃值： (10) 能力值： ( LV2，RANK：10 ) 在线值：发帖 0 回帖 6 粉丝 0 关注私信	wx_心隐草 2017-11-3 13:38 2 楼 0 用指针来操作数组，刚开始还真不习惯。矩阵转换没看明白，还需要学习
	游客登录 \| 注册方可回帖　回帖　表情雪币赚取及消费高级回复