点击蓝字
关注我们
日期：2025年2月18日
作者：jgk01
介绍：山东数据安全技能兴鲁比赛中一道零解题，赛后复盘。
0x00 前言
山东数据安全技能兴鲁比赛中一道零解题，初赛的时候时间太短，就做了第一个题，第二个题没时间看，后面研究了一下发现没有想象中呢么难，之前对于NFSR的题目没太多接触，趁这个题目记录学习一下。
0x01 题目
题目脚本如下：
from Crypto.Cipher import AESfrom Crypto.Util.number import *from Crypto.Util.Padding import padfrom hashlib import sha512from secret import flagmask1 = 211151158277430590850506190902325379931mask2 = 314024231732616562506949148198103849397mask3 = 175840838278158851471916948124781906887mask4 = 270726596087586267913580004170375666103deflfsr(R, mask):R_bin = [int(b) for b inbin(R)[2:].zfill(128)]mask_bin = [int(b) for b inbin(mask)[2:].zfill(128)]s = sum([R_bin[i] * mask_bin[i] for i inrange(128)]) & 1R_bin =展开收缩+ R_bin[:-1]return (int("".join(map(str, R_bin)), 2), s)defff(x0, x1, x2, x3):return (int(sha512(long_to_bytes(x0 * x2 + x0 + x1**4 + x3**5 + x0 * x1 * x2 * x3 + (x1 * x3) ** 4)).hexdigest(), 16) & 1)defround(R, R1_mask, R2_mask, R3_mask, R4_mask):out = 0R1_NEW, _ = lfsr(R, R1_mask)R2_NEW, _ = lfsr(R, R2_mask)R3_NEW, _ = lfsr(R, R3_mask)R4_NEW, _ = lfsr(R, R4_mask)for _ inrange(256):R1_NEW, x1 = lfsr(R1_NEW, R1_mask)R2_NEW, x2 = lfsr(R2_NEW, R2_mask)R3_NEW, x3 = lfsr(R3_NEW, R3_mask)R4_NEW, x4 = lfsr(R4_NEW, R4_mask)out = (out << 1) + ff(x1, x2, x3, x4)return outkey = getRandomNBitInteger(128)out = round(key, mask1, mask2, mask3, mask4)cipher = AES.new(long_to_bytes(key), mode=AES.MODE_ECB)print(out)print(cipher.encrypt(pad(flag, 16)))# 68014145798558789680147296296059748493170180017159509061459191404846898978879# b'x9cxafx89x98x90<xdfxe8xefxd7x06x9cxf1xb0x1c3xccx12xabxdcx0exfa/x1bx95xe8xd6xa9axe6x86"x18x86q|xfaxa6xf9xedxe7x80Gx16ax18x04xcb'
这里我们可以先找到flag，发现是flag生成了随机的key，通过aes加密的，而key通过round函数进行了多轮的lfsr的加密得到了一个输出结果，所以很明显是要恢复出key来。
0x02 解题思路
>> 1.根据题目脚本分析一下代码，首先定义了四个用作线性反馈移位寄存器（LFSR）操作的位掩码mask1-mask4。
mask1 = 211151158277430590850506190902325379931mask2 = 314024231732616562506949148198103849397mask3 = 175840838278158851471916948124781906887mask4 = 270726596087586267913580004170375666103
>> 2.接着是LFSR函数，该函数执行LFSR（线性反馈移位寄存器）操作的一次迭代：
def lfsr(R, mask):R_bin = [int(b) for b in bin(R)[2:].zfill(128)]mask_bin = [int(b) for b in bin(mask)[2:].zfill(128)]s = sum([R_bin[i] * mask_bin[i] for i in range(128)]) & 1R_bin =展开收缩+ R_bin[:-1]return (int("".join(map(str, R_bin)), 2), s)
R_bin和mask_bin分别是R和mask的二进制位，填充位128位。
s是xor的操作结果，计算了R_bin和mask_bin的点积，然后取模2，生成一个单独的位。
R_bin向右移一位，并将s插入开头，最后返回一个跟新的后的R值和位s的元组。
>> 3.接着是位操作函数ff。
def ff(x0, x1, x2, x3):return (int(sha512(long_to_bytes(x0 * x2 + x0 + x1**4 + x3**5 + x0 * x1 * x2 * x3 + (x1 * x3) ** 4)).hexdigest(), 16) & 1)
接收四个输入位，对它们执行一系列的位运算操作。结果返回为一个单独的位，用于加密轮次中。
>> 4.加密轮次函数
def round(R, R1_mask, R2_mask, R3_mask, R4_mask):out = 0R1_NEW, _ = lfsr(R, R1_mask)R2_NEW, _ = lfsr(R, R2_mask)R3_NEW, _ = lfsr(R, R3_mask)R4_NEW, _ = lfsr(R, R4_mask)for _ in range(256):R1_NEW, x1 = lfsr(R1_NEW, R1_mask)R2_NEW, x2 = lfsr(R2_NEW, R2_mask)R3_NEW, x3 = lfsr(R3_NEW, R3_mask)R4_NEW, x4 = lfsr(R4_NEW, R4_mask)out = (out << 1) + ff(x1, x2, x3, x4)return out
out初始化为0，在每次迭代中累加生成的位。
初始化LFSRs，通过对R和每个掩码应用lsrf函数来生成R1_NEW，R2_NEW，R3_NEW，R4_NEW
循环执行256轮次，每次更新每个LFSR并获得新的x1，x2，x3，x4
ff函数提供一个单个位并将其添加到out。
最后返回256轮次后，out是一个256位的结果，就是这个函数最终的输出。
>> 5.加密部分
key = getRandomNBitInteger(128)out = round(key, mask1, mask2, mask3, mask4)cipher = AES.new(long_to_bytes(key), mode=AES.MODE_ECB)print(out)print(cipher.encrypt(pad(flag, 16)))
首先生产key，用于AES加密。
然后调用round函数，传入key和四个掩码生成一个256位的输出生成out。
通过AES加密flag。
0x03 解题脚本
解题思路其实就靠从LFSR生成的伪随机序列out中提取约束条件，将其转换为线性方程组，最终推导出加密密钥key。利用该密钥，成功解密密文enc并获取到flag。
实际计算发现out.bit_length = 126，加上一定有key[126] = 1，那么就有127个xor 形方程，理论可以高斯消元解出。实际测试发现应该有线性相关的方程，所以再手动枚举一下剩下的两位即可。
from Crypto.Cipher import AESfrom Crypto.Util.number import *from Crypto.Util.Padding import padfrom hashlib import sha512from copy import deepcopyout =68014145798558789680147296296059748493170180017159509061459191404846898978879enc =b'x9cxafx89x98x90<xdfxe8xefxd7x06x9cxf1xb0x1c3xccx12xabxdcx0exfa/x1bx95xe8xd6xa9axe6x86"x18x86q|xfaxa6xf9xedxe7x80Gx16ax18x04xcb'mask1 = 211151158277430590850506190902325379931mask2 = 314024231732616562506949148198103849397mask3 = 175840838278158851471916948124781906887mask4 = 270726596087586267913580004170375666103m = matrix(GF(2),128,129)M1,M2,M3 = matrix(GF(2),128,128),matrix(GF(2),128,128),matrix(GF(2),128,128)for i inrange(128):M1[i,0] = int(bin(mask1)[2:][i])M2[i,0] = int(bin(mask2)[2:][i])M3[i,0] = int(bin(mask4)[2:][i])if i != 127:M1[i,i+1] = 1M2[i,i+1] = 1M3[i,i+1] = 1out = bin(out)[2:].zfill(256)print(out)si = []for i inrange(256):if out[i] == '1':si.append(i)print(si,len(si))n = 0MM1,MM2,MM3 = identity_matrix(GF(2),128),identity_matrix(GF(2),128),identity_matrix(GF(2),128)MM1 *= M1MM2 *= M2MM3 *= M3for i inrange(256):MM1 *= M1MM2 *= M2MM3 *= M3if i in si:m[:,n] = (MM1+MM2+MM3)[:,0]n += 1assert n == 126output = matrix([1]*126+[0]*3)MM1,MM2,MM3 = identity_matrix(GF(2),128),identity_matrix(GF(2),128),identity_matrix(GF(2),128)MM1 *= M1MM2 *= M2MM3 *= M3for i inrange(256):MM1 *= M1MM2 *= M2MM3 *= M3if i notin si:m[:,-3] = (MM1+MM2+MM3)[:,0]MMM1,MMM2,MMM3 = deepcopy(MM1),deepcopy(MM2),deepcopy(MM3)for j inrange(i+1,256):MMM1 *= M1MMM2 *= M2MMM3 *= M3if j notin si:m[:,-2] = (MMM1+MMM2+MMM3)[:,0]for j inrange(i+1,256):MMM1 *= M1MMM2 *= M2MMM3 *= M3if j notin si:m[:,-1] = (MMM1+MMM2+MMM3)[:,0]try:key = (m.solve_left(output))[0]key = ''.join(str(_) for _ in key)key = int(key,2)cipher = AES.new(long_to_bytes(key), mode=AES.MODE_ECB)print(cipher.decrypt(enc))except:continue#flag{41fe9100-0ac8-4869-9193-69a5a047c060}
0x04 后记
这类题目在比赛中见得也比较少，这类题目之前在byteCTF中有过类似的题目，基本是差不多的类型，只不过out的有效方程数是127。
参考链接：
https://cloud.tencent.com/developer/article/2462389
免责声明：本文仅供安全研究与讨论之用，严禁用于非法用途，违者后果自负。
点此亲启
ABOUT US
宸极实验室隶属山东九州信泰信息科技股份有限公司，致力于网络安全对抗技术研究，是山东省发改委认定的“网络安全对抗关键技术山东省工程研究中心”。团队成员专注于 Web 安全、移动安全、红蓝对抗等领域，善于利用黑客视角发现和解决网络安全问题。
团队自成立以来，圆满完成了多次国家级、省部级重要网络安全保障和攻防演习活动，并积极参加各类网络安全竞赛，屡获殊荣。
对信息安全感兴趣的小伙伴欢迎加入宸极实验室，关注公众号，回复『招聘』，获取联系方式。
原文始发于微信公众号（黑白之道）：『CTF』密码学-一道LFSR
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论