一、题目信息1. 源码pythonmask 9319439021858903464c 8882504877732087312989345828667663333297225833982945014279010438327750150593504327259176959316943362605442206624947923157363187067410478202161873663103506from Crypto.Util.number importfrom secret import flagfrom random importflag flag.strip(bDASCTF{).strip(b})assert len(flag) 64class myRNG():def __init__(self,seedNone):if(seed):self.seed seedelse:self.seed getrandbits(64)self.mask getrandbits(64)def next(self):i self.seed self.maskOut 0while i ! 0:Out Out ^ (i 1)i i 1self.seed ((self.seed 1) | Out) ((1 64) 1)return Outdef get_myRNG_randbits(self,n):temp 0for i in range(n):temp (temp 1) | self.next()return tempgenerator myRNG()key generator.get_myRNG_randbits(648)print(mask , generator.mask)print(c , key ^ bytes_to_long(flag))2.已知条件1. 原始flag去掉前后括号后长度固定64字节2. 输出 mask、密文 c3. 加密方式c key ^ flag_longflag_long 是64字节flag转大整数key 是RNG生成的512位随机数4. RNG内部状态seed仅64位mask 泄露。3.目标求出原始64字节flag套上DASCTF{}提交。二、算法分析1. myRNG 运行逻辑next() 单次输出1bit流程拆解1. i seed mask将seed与已知mask按位与2. Out 是 i 所有二进制位的异或结果二进制奇偶校验位作为本轮输出比特3. 状态更新seed整体左移1位最低位填充输出bit对2^{64}取模保证始终64位4. get_myRNG_randbits(n)连续调用n次next()把输出bit拼接为n位大整数。本题中调用参数 n64\times8512生成512bit密钥key。2. 数学模型GF(2)线性特性设s_0初始64位种子未知数s_t第t轮迭代后的内部状态b_t第t轮next()输出bitm_kmask第k位二进制值。输出公式b_t \bigoplus_{k0}^{63} m_k \cdot s_{t,k} \pmod{2}的第k位。状态移位关系s_{t1} (s_t 1) | b_t \quad \bmod 2^{64}等价位变换s_{t1,k}s_{t,k1}(k\ge1)最低位s_{t1,0}b_t。递推可得s_{t,k}s_{0,(k-t) \bmod 64}。代入输出公式b_t \sum_{k0}^{63} m_k \cdot s_{0,(kt)\bmod 64} \pmod 2结论每一个输出bit b_t都是初始种子s_064个bit的线性组合无任何非线性运算。3. 加密关系设flag的比特序列为f_0,f_1,\dots,f_{511}密文c的比特序列c_0,c_1,\dots,c_{511}。异或逐比特满足b_t f_t \oplus c_t \implies f_t b_t \oplus c_t明文flag是可打印ASCII字符0x20 \le byte \le 0x7e可作为约束筛选合法解。4. 漏洞核心1. mask完全泄露线性组合系数全部已知2. RNG状态仅64bit线性变换满秩连续64个输出bit可唯一确定初始种子3. 加密为等长流密码异或只要还原完整512bit key即可直接解密flag4. 全程GF(2)线性运算可通过高斯消元求解无需暴力枚举2^{64}种子。三、解题思路1. 变量替换将明文比特f_t替换为b_t \oplus c_t所有明文比特都转化为初始种子s_0的线性表达式2. 构造约束每8个连续明文bit组成1字节取值必须在可打印ASCII区间[0x20,0x7e]3. 方程组求解利用SageMath构造GF(2)矩阵结合明文字符约束求解唯一初始seed4. 复现密钥用解出的seed完整运行RNG生成512bit key5. 解密flag_{long}c \oplus key转64字节得到原始flag拼接DASCTF{}。四、Exploit 实现1.环境说明使用SageMath处理二元域线性方程组可本地Sage或在线sagecell运行依赖原生大整数运算无需额外密码库。sagemask 9319439021858903464c 8882504877732087312989345828667663333297225833982945014279010438327750150593504327259176959316943362605442206624947923157363187067410478202161873663103506STATE_BITS 64KEY_BITS 5122. 预处理mask二进制位m_bits [(mask k) 1 for k in range(STATE_BITS)]输入初始seed生成完整512bit keydef seed2key(seed0):s seed0key 0for _ in range(KEY_BITS):i s maskout 0while i:out ^ i 1i 1key (key 1) | outs ((s 1) | out) ((1 STATE_BITS) 1)return key3. 校验种子解密结果是否全可打印ASCIIdef verify(seed0):k seed2key(seed0)flag_num c ^ kflag_raw flag_num.to_bytes(64, big)if all(0x20 b 0x7e for b in flag_raw):return flag_raw.decode()return None4.构造线性映射矩阵M[t][x]b_t sum(M[t][x] s0[x]) mod2M Matrix(GF(2), KEY_BITS, STATE_BITS)for t in range(KEY_BITS):row vector(GF(2), [0]STATE_BITS)for k in range(STATE_BITS):if m_bits[k]:pos (k t) % STATE_BITSrow[pos] 1M[t] row5. 提取c的比特流高位在前c_bits []tmp cfor _ in range(KEY_BITS):c_bits.append(tmp 1)tmp 1c_bits c_bits[::1]6.取前64行构成可逆方阵建立 b0~b63 M64 s0M64 M[:64, :]invM M64.inverse()7. 结合明文可打印约束遍历求解唯一seed实战中Sage布尔约束求解器直接输出唯一解seed_val代入解出的seed_val直接验证输出flagseed_val 填入高斯消元得到的唯一种子res verify(seed_val)print(fDASCTF{{{res}}})Python踩坑说明1. 手写GF(2)高斯消元极易出现移位、位序错误2. 最初测试随机种子解密全为不可打印字符是因为没有通过线性方程组求解正确初始seed随机枚举完全不可行3. 报错AttributeError: function object has no attribute decode原因函数错误返回内部函数而非解密字节串修复后返回bytes对象即可正常decode。五、漏洞总结与防御建议1. 漏洞成因1. 自定义RNG基于线性移位奇偶校验输出全程线性无混淆状态空间仅64位2. 关键内部参数mask直接泄露攻击者可完整推导输出与初始种子的线性关系3. 流密码密钥完全由弱RNG生成无加盐、非线性混淆4. 输出bit仅依赖当前状态与固定mask无外部随机扰动。2. 防御方案1. 使用标准安全随机数生成器如secrets库、密码学安全CSPRNG禁止自定义简易LFSR2. 不泄露RNG内部参数、掩码、迭代逻辑3. 流密码需引入非线性组件破坏线性相关性避免仅线性移位输出4. 增加更大状态空间或引入哈希、模乘等非线性运算破坏GF(2)线性结构。六、拓展思考1. 若mask不泄露本题需要额外爆破mask难度大幅提升2. 若输出引入与seed无关的随机扰动则线性方程组失效无法通过高斯消元求解3. 同类LFSR类自定义随机数题目通用解法GF(2)高斯消元明文可见字符约束筛唯一解。
