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

Original 2021 KCTF 看雪学苑 2022-07-01

收录于合集 #2021 KCTF设计思路 10个

今天中午12点整，第十一题《图穷匕见》截止答题！这也意味着看雪·众安2021 KCTF秋季赛到此圆满结束了～

本题仅有2支战队成功破解，分别是【辣鸡战队】和【中娅之戒】。

恭喜辣鸡战队用时170067秒拿下“一血”，接下来和我一起来看看该赛题的设计思路和相关解析吧~

出题团队简介

第十一题《图穷匕见》出题方：【98k】战队。

赛题设计思路

怎么提升逆向的乐趣呢？于是诞生了这个比赛题目。
很多人都从教师或者技术专家的授课中得知些大名鼎鼎的加密算法，加密算法的核心逻辑是怎么在随机和不随机中找到一个较好的平衡点。对于SN程序来说，序列号就是加密算法中的明文或者密钥。一般而言，设计一个SN算法，单序列号主要使用加密算法进行魔改，多序列号主要使用签名函数进行魔改。当然，很多有乐趣的题目使用各式各样的数学问题来设计校验过程。 Feistal 结构大家肯定不陌生，其中的灵魂设计在于那个不可逆的F函数，这个题目的灵感就来源于这个F函数。如果这个F函数是一个线性的函数，则会对密码学算法产生破坏性的影响。

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 上的多项式环。

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，即可算出密钥。算出密钥后，题目的难点就解决了，剩下的就是满足输入规则即可。

赛题解析

本赛题解析由看雪论坛xym给出：

题目非常小巧，IDA打开后所有算法也清晰可见。相比第十题各种逆向方法百花齐放，这题简单到可以把F5后的结果直接复制出来使用。

题目逻辑也很清晰：将输入经过一轮s盒转换后当成密钥，分别对两组明文进行加密，如果与指定的两组密文相同，则将输入经过hash比较无误后输出"Correct!"。整体就是已知两对明密文和加密算法，求密钥的操作。

加密函数sub_140002970也不复杂，梳理一下就是一个Feistal结构的加密，据此容易构造出解密方法。加密轮数只有5轮，定义域在GF(2^64)上。

void sub_140002970(UINT64 *Plaintext, UINT64 *key, int len, UINT64 *const0, UINT64 *Ciphertext){ UINT64 v8; // rax UINT64 v9; // rax UINT64 v10; // rax UINT64 v14; // [rsp+40h] [rbp-38h] UINT64 v17; // [rsp+58h] [rbp-20h] UINT64 v18; // [rsp+60h] [rbp-18h] v17 = Plaintext[0]; v18 = Plaintext[1]; for (int i = 0; i < len; ++i) { v8 = v18 ^ key[i % 2] ^ const0[i]; v9 = sub_1400028C0(v8, v8); v10 = sub_1400028C0(v9, v8); v14 = v17 ^ v10; v17 = v18; v18 = v14; } Ciphertext[0] = v17; Ciphertext[1] = v18;}

其中只有一个sub_1400028C0子函数比较特殊。而这个函数粗一看可能比较奇怪，仔细研究后发现就是一个基于0x247F43CB7的乘法。

UINT64 sub_1400028C0(UINT64 a1, UINT64 a2){ UINT64 v3; v3 = 0; while (a2) { if ((a2 & 1) != 0) v3 = v3 ^ a1; a2 >>= 1; if (a1 & 0x8000000000000000) a1 = (2 * a1) ^ 0x247F43CB7; else a1 *= 2; } return v3;}

把异或看成是加法的话，sub_1400028C0函数完全满足乘法三大定律。即

sub_1400028C0(a, b) == sub_1400028C0(b, a)sub_1400028C0(sub_1400028C0(a, b), c) == sub_1400028C0(a, sub_1400028C0(b, c))sub_1400028C0(a xor b, c) == sub_1400028C0(a, c) xor sub_1400028C0(b, c))

因此可以进一步把加密过程的每一轮都化简为如下形式：

v14 = (P1 + KEY0 + const0) ^ 3 + P0;P0 = P1;P1 = v14;...

如果把加密过程的每一轮都表示成如上形式后，可以发现密文在理论上可以表示为明文的表达式，而且里面只有KEY0和KEY1两个未知变元，因此利用两组明密文列出的两个方程在理论上可以求解得到秘钥。

使用sagemath实现题目的过程，如下：

def enc(pt, key): pt0, pt1 = pt key0, key1 = key var('x') var('a')

  K.<a> = GF(2^64, name='a',modulus = 1 +x^1 +x^2 +x^4 +x^5 +x^7 +x^10 +x^11 +x^12 +x^13 +x^18 +x^20 +x^21 +x^22 +x^23 +x^24 +x^25 +x^26 +x^30 +x^33 + x^64)

c0=0x20F4641148FA59A5 c1=0x96950F0D368EB90D c2=0x7467551A8419E0B5 c3=0x01A61218FE968D86 c4=0x192DB7EB78969270 cntList=[] cntList.append(K.fetch_int(c0)) cntList.append(K.fetch_int(c1)) cntList.append(K.fetch_int(c2)) cntList.append(K.fetch_int(c3)) cntList.append(K.fetch_int(c4)) Left = K.fetch_int(pt0) Right = K.fetch_int(pt1) keyList=[] keyList.append(K.fetch_int(key0)) keyList.append(K.fetch_int(key1)) for i in range(5): tmp = Right+keyList[i%2]+cntList[i] tmp = tmp^3 tmp = tmp + Left Left = Right Right = tmp return [hex(Left.integer_representation()),hex(Right.integer_representation())]pt=[0x73C51960EF361B30, 0xFBD5C824382C435D]key = [0xb118c960bcb118c9, 0xb118c960bcb118c9]enc(pt,key)

直接构造方程的思路比较简单，但是方程次数指数级增长导致难以求解。考虑到尽量降低方程次数，编写相应的解密函数，采用中间相遇攻击方法，利用在不同轮数中的相遇情况，可以列出6个方程，然后使用Groebner基方法即可求解出方程组的解。

具体过程如下：

#下面代码可以直接在sage中运行 #1. 构造数域

K.<x> = GF(2^64, name='x',modulus = 1 +x^1 +x^2 +x^4 +x^5 +x^7 +x^10 +x^11 +x^12 +x^13 +x^18 +x^20 +x^21 +x^22 +x^23 +x^24 +x^25 +x^26 +x^30 +x^33 + x^64)

#2. 方程的构造#首先形式化计算出表示方法P0=var('P0')P1=var('P1')M0=var('M0')M1=var('M1')y = var('y')z = var('z')c0 = var('c0')c1 = var('c1')c2 = var('c2')c3 = var('c3')c4 = var('c4')R.<P0,P1,y,z,c0,c1,c2,c3,c4,M0,M1>=GF(2)[]#正向加密过程形式化计算v17 = P0v18 = P1 v8 = v18 + y + c0v10 = v8 * v8 * v8v14 = v17 + v10v17 = v18v18 = v14 eq_forward_1 = v18 v8 = v18 + z + c1v10 = v8 * v8 * v8v14 = v17 + v10v17 = v18v18 = v14 eq_forward_2 = v18 v8 = v18 + y + c2v10 = v8 * v8 * v8v14 = v17 + v10v17 = v18v18 = v14 eq_forward_3 = v18#逆向解密过程形式化计算v17 = M1v18 = M0 v8 = v18 + y + c4v10 = v8 * v8 * v8v14 = v17 + v10v17 = v18v18 = v14 eq_backward_1 = v18 v8 = v18 + z + c3v10 = v8 * v8 * v8v14 = v17 + v10v17 = v18v18 = v14 eq_backward_2 = v18 v8 = v18 + y + c2v10 = v8 * v8 * v8v14 = v17 + v10v17 = v18v18 = v14 eq_backward_3 = v18 #其次带入实际数据 ct0 = 0x55250D8CEEDFFB35ct1 = 0xDBAFC899D2AAD5ECct2 = 0xD30CE81D5CFD183Ect3 = 0x3C205341A484C650pt0 = 0x73C51960EF361B30pt1 = 0xFBD5C824382C435Dpt2 = 0x79EEBA9CCF47A451pt3 = 0x55B4D0E1061D12D0cnt0 = 0x20F4641148FA59A5cnt1 = 0x96950F0D368EB90Dcnt2 = 0x7467551A8419E0B5cnt3 = 0x01A61218FE968D86cnt4 = 0x192DB7EB78969270 y,z=K['y,z'].gens() #利用第1组明密文对列3个方程eq1 = \eq_forward_1(P0=K.fetch_int(pt0),P1=K.fetch_int(pt1),c0=K.fetch_int(cnt0),\c1=K.fetch_int(cnt1),c2=K.fetch_int(cnt2),c3=K.fetch_int(cnt3),c4=K.fetch_int(cnt4))\-eq_backward_3(M0=K.fetch_int(ct0),M1=K.fetch_int(ct1),c0=K.fetch_int(cnt0),\c1=K.fetch_int(cnt1),c2=K.fetch_int(cnt2),c3=K.fetch_int(cnt3),c4=K.fetch_int(cnt4)) eq2 = \eq_forward_2(P0=K.fetch_int(pt0),P1=K.fetch_int(pt1),c0=K.fetch_int(cnt0),\c1=K.fetch_int(cnt1),c2=K.fetch_int(cnt2),c3=K.fetch_int(cnt3),c4=K.fetch_int(cnt4))\-eq_backward_2(M0=K.fetch_int(ct0),M1=K.fetch_int(ct1),c0=K.fetch_int(cnt0),\c1=K.fetch_int(cnt1),c2=K.fetch_int(cnt2),c3=K.fetch_int(cnt3),c4=K.fetch_int(cnt4)) eq3 = \eq_forward_3(P0=K.fetch_int(pt0),P1=K.fetch_int(pt1),c0=K.fetch_int(cnt0),\c1=K.fetch_int(cnt1),c2=K.fetch_int(cnt2),c3=K.fetch_int(cnt3),c4=K.fetch_int(cnt4))\-eq_backward_1(M0=K.fetch_int(ct0),M1=K.fetch_int(ct1),c0=K.fetch_int(cnt0),\c1=K.fetch_int(cnt1),c2=K.fetch_int(cnt2),c3=K.fetch_int(cnt3),c4=K.fetch_int(cnt4)) #利用第2组明密文对列3个方程eq4 = \eq_forward_1(P0=K.fetch_int(pt2),P1=K.fetch_int(pt3),c0=K.fetch_int(cnt0),\c1=K.fetch_int(cnt1),c2=K.fetch_int(cnt2),c3=K.fetch_int(cnt3),c4=K.fetch_int(cnt4))\-eq_backward_3(M0=K.fetch_int(ct2),M1=K.fetch_int(ct3),c0=K.fetch_int(cnt0),\c1=K.fetch_int(cnt1),c2=K.fetch_int(cnt2),c3=K.fetch_int(cnt3),c4=K.fetch_int(cnt4)) eq5 = \eq_forward_2(P0=K.fetch_int(pt2),P1=K.fetch_int(pt3),c0=K.fetch_int(cnt0),\c1=K.fetch_int(cnt1),c2=K.fetch_int(cnt2),c3=K.fetch_int(cnt3),c4=K.fetch_int(cnt4))\-eq_backward_2(M0=K.fetch_int(ct2),M1=K.fetch_int(ct3),c0=K.fetch_int(cnt0),\c1=K.fetch_int(cnt1),c2=K.fetch_int(cnt2),c3=K.fetch_int(cnt3),c4=K.fetch_int(cnt4)) eq6 = \eq_forward_3(P0=K.fetch_int(pt2),P1=K.fetch_int(pt3),c0=K.fetch_int(cnt0),\c1=K.fetch_int(cnt1),c2=K.fetch_int(cnt2),c3=K.fetch_int(cnt3),c4=K.fetch_int(cnt4))\-eq_backward_1(M0=K.fetch_int(ct2),M1=K.fetch_int(ct3),c0=K.fetch_int(cnt0),\c1=K.fetch_int(cnt1),c2=K.fetch_int(cnt2),c3=K.fetch_int(cnt3),c4=K.fetch_int(cnt4)) #至此列出6个方程。 #3.利用sagemath自带的Groebner基解方程I=ideal(eq1,eq2,eq3,eq4,eq5,eq6)B=I.groebner_basis()key0 = hex(B[0].coefficients()[1].integer_representation())key1 = hex(B[1].coefficients()[1].integer_representation())print(key0,key1)

由于上述方程只有唯一解0xf39a46cc6199261d, 0xbdeded27481af0e0，所以该解经过s盒的逆变换后变化得到的字符串de23f9d82798377ea01743d43d5353cd直接通过了后面部分的HASH校验。

注意：【最受欢迎战队奖】投票进行中！欢迎大家前来投上你宝贵的一票～

长按二维码立即投票！

【最受欢迎战队奖】

评选对象：

2021 KCTF秋季赛参赛战队（包含防守方所有战队+攻击方前20名战队）

评选方式：

登陆看雪账号，在本帖为喜欢的战队投票，每个账号可投1票。

投票时间：

12月15日 14:00 ～12月22日 14：00

奖励：

最受欢迎战队奖，得票第一名：可获得「HUAWEI WATCH GT2 华为手表」