首页
论坛
课程
招聘
[原创]2021 KCTF 秋季赛 第十一题 图穷匕见 writeup (比赛结束后开放)
2021-12-14 20:06 14828

[原创]2021 KCTF 秋季赛 第十一题 图穷匕见 writeup (比赛结束后开放)

2021-12-14 20:06
14828

2021 KCTF 秋季赛 第十一题 图穷匕见 设计思路

在我的大学时光,我结交了很多朋友。半盲道人作为我的良师益友,原本这次参赛想趁比赛结束膜一膜半盲道人,没想到比赛中最为对手同台竞技了。怀念大学时光,跟着校友们学习了很多知识。这里主要感谢学习逆向以来的良师益友们。鸣谢 @半盲道人 @负一的平方根 @ThinerDAS @roadicing

题目设计思路

所以我思考怎么提升逆向的乐趣呢?于是诞生这个比赛题目。

 

很多人都从教师或者技术专家的授课中得知些大名鼎鼎的加密算法,加密算法的核心逻辑是怎么在随机和不随机中找到一个较好的平衡点。对于SN程序来说,序列号就是加密算法中的明文或者密钥。

 

一般而言,设计一个SN算法,单序列号主要使用加密算法进行魔改,多序列号主要使用签名函数进行魔改。当然,很多有乐趣的题目使用各式各样的数学问题来设计校验过程。

 

Feistal 结构大家肯定不陌生,其中的灵魂设计在于那个不可逆的F函数,这个题目的灵感就来源于这个F函数。如果这个F函数是一个线性的函数,则会对密码学算法产生破坏性的影响。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def pure_block_cipher_encrypt(p: list, k: list, round_n: int, constant_c: list):
    assert len(p) == 2
    assert len(k) == 2
    pl = p[0]
    pr = p[1]
    tmpl = pl
    tmpr = pr
    for i in range(round_n):
        tmpl, tmpr = pure_block_cipher_enc_round(tmpl, tmpr, k[i % 2], constant_c[i])
    return tmpl, tmpr
 
def pure_block_cipher_enc_round(xl, xr, ki, ci):
    yl = xr
    yr = xl + (xr + ki + ci)^3
    return (yl, yr)

程序中为了限制多解,使用了魔改的md5校验答案,当然,我在设计题目的时候,你对程序进行分析不会产生多解。程序还用了aes的sbox来混淆视听,加个了没加一样,其实是用来干扰基于特征的分析插件。

 

以上的代码都是sagemath的代码。其中“^”符号是指数幂运算的符号,不是 xor 。

 

总是说线性的东西是脆弱的,如果一个加密算法,无论它应用在什么上,hash、加密,如果只有线性的运算,没有非线性的运算,最终它的明文密文会在某个代数结构上构成一组线性方程。

 

本题实现了在 Galois Fields 上的多项式环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
equations.append(x1+pr_list[0])
equations.append(x2+pl_list[0]+(k_list[0] + pr_list[0] + constant_c[0])^3)
 
for i in range(1, round_n):
    this_round_vars = x_list[i*2-2:i*2+2]
    # print(this_round_vars)
    equations.append(this_round_vars[1] + this_round_vars[2])
    equations.append(this_round_vars[3] + this_round_vars[0] + (k_list[i % 2] + constant_c[i] + this_round_vars[1])^3)
equations.append(x_list[-2]+cl_list[0])
equations.append(x_list[-1]+cr_list[0])
equations.append(y1+pr_list[1])
equations.append(y2+pl_list[1]+(k_list[0] + pr_list[1] + constant_c[0])^3)
 
for i in range(1, round_n):
    this_round_vars = y_list[i*2-2:i*2+2]
    # print(this_round_vars)
    equations.append(this_round_vars[1] + this_round_vars[2])
    equations.append(this_round_vars[3] + this_round_vars[0] + (k_list[i % 2] + constant_c[i] + this_round_vars[1])^3)
equations.append(y_list[-2]+cl_list[1])
equations.append(y_list[-1]+cr_list[1])

本算法是5轮的 Feistal 结构,所以我们定义好中间过程的变量,将它们使用等式链接起来。这些等式在是原先多项式环的子集,满足原来的加法,自成一群。且该子环内所有元素与原环之元素相乘的结果均在其内。所以可以构建理想。

 

Gröbner basis可以求理想从任意一个多项式理想的一组给定生成元,计算另一组性质良好的生成元。常常用来求解多项式方程。
所以我们在这个理想上求Gröbner basis,即可算出密钥。算出密钥后,题目的难点就解决了,剩下的就是满足输入规则即可。

 

详细的wp请参考,ipynb文件。


【看雪培训】目录重大更新!《安卓高级研修班》2022年春季班开始招生!

上传的附件:
收藏
点赞0
打赏
分享
最新回复 (0)
游客
登录 | 注册 方可回帖
返回