『CTF』密码学-一道LFSR

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 = 270726596087586267913580004170375666103def 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)]) & 1    R_bin = [s] + R_bin[:-1]    return (int("".join(map(str, R_bin)), 2), s)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)def round(R, R1_mask, R2_mask, R3_mask, R4_mask):    out = 0    R1_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 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'\x9c\xaf\x89\x98\x90<\xdf\xe8\xef\xd7\x06\x9c\xf1\xb0\x1c3\xcc\x12\xab\xdc\x0e\xfa/\x1b\x95\xe8\xd6\xa9a\xe6\x86"\x18\x86q|\xfa\xa6\xf9\xed\xe7\x80G\x16a\x18\x04\xcb'

这里我们可以先找到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)]) & 1    R_bin = [s] + 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 = 0    R1_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'\x9c\xaf\x89\x98\x90<\xdf\xe8\xef\xd7\x06\x9c\xf1\xb0\x1c3\xcc\x12\xab\xdc\x0e\xfa/\x1b\x95\xe8\xd6\xa9a\xe6\x86"\x18\x86q|\xfa\xa6\xf9\xed\xe7\x80G\x16a\x18\x04\xcb'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 in range(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] = 1        M2[i,i+1] = 1        M3[i,i+1] = 1out = bin(out)[2:].zfill(256)print(out)si = []for i in range(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 in range(256):    MM1 *= M1    MM2 *= M2    MM3 *= M3    if 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 in range(256):    MM1 *= M1    MM2 *= M2    MM3 *= M3    if i not in si:        m[:,-3] = (MM1+MM2+MM3)[:,0]        MMM1,MMM2,MMM3 = deepcopy(MM1),deepcopy(MM2),deepcopy(MM3)        for j in range(i+1,256):            MMM1 *= M1            MMM2 *= M2            MMM3 *= M3            if j not in si:                m[:,-2] = (MMM1+MMM2+MMM3)[:,0]                for j in range(i+1,256):                    MMM1 *= M1                    MMM2 *= M2                    MMM3 *= M3                    if j not in 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

免责声明：本文仅供安全研究与讨论之用，严禁用于非法用途，违者后果自负。