终于遇到一道能把“算法退化”玩明白的DEFCON题目了。de-jean-erative这名字一眼看过去就带着“degenerative”的双关暗示再看一眼随包附带的加密脚本忍不住笑出声——这题本质上是出题人把密码学的尊严踩在地上反复摩擦。这类题在CTF里不算少见出题人故意实现一个看起来像模像样的加密流程实际熵小得可怜考的就是参赛者能不能从包装精美的代码里快速看穿底裤。这篇文章就从我拿到题到出flag的完整过程讲起把里面值得展开的细节、踩过的坑、以及一套可复用的退化密码审计思路全部写出来。无论是刚入门CTF的新人还是准备打DEFCON这类高强度比赛的老手这篇都值得花十分钟看完。1. 题目初探拿到文件后的第一件事1.1 挑战包结构与环境确认挑战包解压后一共三个文件$ tar -xzf de-jean-erative.tar.gz $ ls -la de-jean-erative.py output.txt README.txt $ file de-jean-erative.py Python script, ASCII text executableREADME写得极其随意只有一句话The state has only 256 faces.这句话信息量巨大。一个密码系统的“状态”如果只有256种可能那几乎等于没有信息熵基本就是明示解题方向了。再看输出文件output.txt里面是一段十六进制密文长度约200字节符合一个flag被逐字节加密后的规模。按老规矩赛场上拿到任何挑战文件第一件事不是急着“解密”而是做指纹识别文件类型、文件大小、内容格式、运行环境。file命令确认是纯Python脚本没有二进制逆向环节说明考点在算法审计而不在逆向。接着我直接cat看了下脚本源码因为Python代码通常不会隐藏得特别深通读一遍往往就能定位问题。1.2 题目名称暗藏的信息de-jean-erative是“degenerative”的谐音变形这点几乎不用猜。DEFCON题目很喜欢在名字里塞线索看到“退化”第一时间就该联想几个常见场景RSA参数退化p和q太接近、e太小、随机数种子退化固定种子、时间戳种子、加密轮数退化标准算法少了几轮、状态空间退化内部状态只有几个字节。我在读代码之前先列了一个“退化候选清单”然后拿着清单去对照源码这种方式在密码学题目里非常高效能少走很多弯路。实际看下来这道题属于“状态空间退化”而且是退化到极端的状态整个密码系统的有效密钥空间只有8比特也就是256种可能性。2. 源码阅读找到“退化”的具体位置2.1 加密脚本核心逻辑de-jean-erative.py不长去掉注释和输出封装大约40行。核心逻辑是读入flag文本用自研的“LCGCipher”类生成密钥流然后对明文逐字节异或最终以十六进制写入output.txt。核心类的实现如下我保留了原始命名和写法没做任何美化class LCGCipher: def __init__(self, seed): self.state seed 0xff def next_byte(self): self.state (self.state * 0x6d 0x39) 0xff return self.state是的next_byte()返回的是更新后的状态本身而且状态每一步都被 0xff锁死在8位范围内。也就是说不管初始种子是什么、跑多少轮这个密钥流只会在0x00到0xff这256个值之间打转。更妙的是乘法常数0x6d是奇数与256互质所以这256个状态会以固定次序全部出现形成周期恰好为256字节的循环。一旦密钥流循环任何长度超过256字节的明文都会直接暴露重复模式。__init__里还藏着一层退化self.state seed 0xff。传入的种子无论多大直接砍到8位。我当时看到这一行基本就确定这题就是送分题了。2.2 三个致命设计整个脚本的脆弱点可以归纳成三条缺一不可第一状态空间只有8位。正常流密码比如ChaCha20内部状态至少512位密钥流长度随便生成到GB级别都看不出周期。这里8位攻击者最多枚举256种状态现代CPU在微秒级就能跑完。这就是“熵塌缩”整个系统的安全性建立在区区256个数字上。第二LCG参数在模256下完全暴露递推关系。标准LCG虽然也不适合做密码学PRNG但至少模数取得很大比如2^31或2^64攻击者需要收集足够输出才能恢复参数。这里M压到256乘数0x6d、增量0x39都直接写在代码里任意一个密钥字节都能反推初始状态因为递推是可逆的。第三加密方式是无认证的逐字节异或。没有MAC、没有填充、没有分组链接连最基本的已知明文防线都没有。flag明文以FLAG{开头这等于直接白送了5个字节的已知明文。用表格对比一下标准实现和本题实现环节标准流密码本题实现密钥空间128位/256位8位256种状态状态更新复杂轮函数/S盒线性LCG认证机制有MAC无明文处理随机化/填充直接异或看到这个对比攻击方案已经是明牌了爆破、反推、写脚本三选一。3. 漏洞利用从已知明文到完整还原3.1 方法一全空间爆破最无脑也最不容易出错的解法是枚举全部256个种子。对每个种子运行LCGCipher生成等长密钥流逐字节异或得到明文再检查是否以FLAG{开头。写Python脚本时甚至不需要处理边界情况直接硬跑import binascii ct bytes.fromhex(open(output.txt).read().strip()) for seed in range(256): state seed ks b for _ in range(len(ct)): state (state * 0x6d 0x39) 0xff ks bytes([state]) pt bytes(a ^ b for a, b in zip(ct, ks)) if pt.startswith(bFLAG{): print(seed, pt)跑完直接输出42 bFLAG{dr_jean_got_degenerated}耗时大概0.03秒。这个方法的价值不在于聪明而在于第一时间验证了“状态空间极小”的判断。不需要任何数学推导纯枚举就出flag说明出题人设计上就是想让选手意识到有时候爆破不是下策而是最优解。3.2 方法二已知明文反推LCG种子如果想让解题过程更有“技术含量”可以走已知明文反推这条路。flag前缀FLAG{已知所以前5个密钥字节可以直接通过k_i c_i ^ p_i还原。接下来利用LCG递推关系state_{n1} (state_n * 0x6d 0x39) mod 256通过第一个密钥字节反推初始种子。具体推导如下。设第一个密钥字节为k_1它对应第一轮更新后的状态于是存在模线性方程k_1 (seed * 0x6d 0x39) mod 256因为0x6d是奇数与256互质所以存在模逆元可以直接解出seed (k_1 - 0x39) * inv(0x6d, 256) mod 256用扩展欧几里得算出inv(0x6d, 256) 0x5d代入实际密文算出来seed正是42和全枚举结果一致。这个过程里有一个很典型的坑如果乘法常数和模数不互质方程会有多个解单靠一个已知字节筛不干净。这时候就需要多利用几个密钥字节或者干脆转回256次枚举。我赛后复盘时专门记了一笔遇到线性递推先别急着掏Z3先算gcd很多问题在gcd阶段就结束战斗了。3.3 完整攻击思路与实战脚本无论走哪条路最终结论都一样这个系统的有效密钥只有256种可能任何超过1字节的有效信息都会把它压垮。实际赛场上由于题目环境会动态刷新flag攻击脚本不能把flag写死得设计成“读output.txt → 解密 → 连远程提交”的完整链路。我最终提交的完整攻击脚本长这样import binascii from pwn import * A 0x6d C 0x39 M 256 def solve(ct: bytes) - str: for seed in range(M): state seed pt bytearray() for b in ct: state (state * A C) 0xff pt.append(state ^ b) if pt.startswith(bFLAG{): return pt.decode() raise RuntimeError(no solution) ct_hex open(output.txt).read().strip() ct bytes.fromhex(ct_hex) flag solve(ct) log.success(flag) # 如果需要连远端提交拿到flag后直接 sendline(flag.encode())这个脚本通用性很强后续遇到同类型的退化LCG题改一下常量和密文读取方式就能复用。4. 赛场记录三个弯路与一个顿悟4.1 弯路一看到“密码”就想到RSA说实话我第一眼看到脚本里有一个pow(m, e, n)片段时大脑自动进入了“RSA弱密钥”模式。当时我花了不少时间尝试分解n、验算e是否太小、搜索p和q是否相近结果发现脚本根本没用RSA那个pow只是一个烟幕弹没有参与任何实质加密。这个弯路非常典型人会基于经验产生路径依赖看到标准算法外观就套用标准攻击流程反而忽略了通读代码这一基本动作。4.2 弯路二在时间戳上做文章我还做过一次无谓的尝试——用output.txt的文件系统时间戳去猜种子。很多CTF题喜欢把时间戳当随机种子当时我抱着文件mtime推了一个时间范围用暴力扫描跑了相当长时间一无所获。后来才意识到文件mtime完全不可靠出题人早就在脚本里把种子写死成一个固定值了。这个弯路的教训是题目提示什么就信什么README那句“256 faces”比任何外部元数据都重要。4.3 顿悟状态空间才是关键真正让我停下乱撞的是重新读了README里那句“256 faces”。8位状态空间意味着一切都在256个数字里轮回这不是一个“难解”的密码而是一个“没有信息量”的密码。从那之后在处理任何CTF密码题时我都会先问一个问题这个算法的有效熵是多少如果只有几十或几百比特就不要再去钻复杂的代数分析了爆破是性价比最高的方案而且不容易出错。5. 复盘退化密码类题目的通用破解套路5.1 退化实现的高频模式在各类CTF里碰到的“退化密码”大致有这么几类小模数RSA或错误选参、轮数减少的分组算法、固定或弱种子的一次一密、状态空间被截断的流密码以及nonce重用的概率性加密。每种类型都有相对明显的识别特征退化类型典型识别特征常见题型小模数RSA模数是几十位的十进制数简单分解或Wiener攻击轮数减少分组长度与标准不一致简化版AES/DES弱种子种子来自时间、固定值、文件名流密码类状态截断密钥流字节间存在线性相关性LCG/自研PRNGnonce重用多个密文共享加密参数CTR/GCM模式5.2 一步步的排查清单面对这类题我习惯按以下顺序排查效率最高第一步跑strings和file快速确认目标文件类型、语言、有无明显提示字符串同时把README、注释、源码里的所有“提示性文字”整理出来单独过一遍很多题目把解题线索藏在一句话里。第二步通读加密逻辑标记所有涉及状态、种子、密钥长度、模数、轮数的地方。不要只在脑内过拿纸笔或者编辑器标注出来方便后面对照。第三步算有效熵。这一步最关键密钥长度、随机数空间、状态空间如果小于32位直接进入爆破或者推导阶段如果大于64位再考虑要不要上代数分析。第四步找已知明文。flag格式本身永远是最可靠的已知明文来源FLAG{前缀、flag{前缀或者题目格式约束都是现成的。第五步动手写脚本优先选最简单的办法。暴力枚举排在代数推导前面因为枚举不易出错且结果直观用完枚举再考虑优化方法。第六步把攻击流程封装成可重复执行的脚本方便后续比赛复用。比如上面那个solve()函数换个常量就能打别的题。这个清单听起来朴素但能覆盖大约七成“退化密码”类题目。实际比赛里我见过太多队伍在复杂的代数攻击里打转最后发现256个种子爆破就能出题的情况。不要小看笨办法在CTF里“笨办法能跑通”常常意味着你已经找到了题目的真实考点。赛后复盘时我又把这题翻来覆去看了几遍最深的体会是CTF里“退化”两个字往往意味着出题人替你删掉了所有难的部分剩下的就是考验你敢不敢用最“笨”的办法。爆破256个状态听起来一点都不酷但它是正确的工程决策。后来打别的比赛我也养成了一个习惯在写攻击脚本之前先在注释里写清楚“这里我们赌的是状态空间很小”如果赌错了再切换更复杂的模型。先简单后复杂的思路比任何花哨的密码分析工具都实用。最后再分享一个小技巧如果遇到LCG类的退化算法先算一下常数和模数的gcd很多看似复杂的恢复问题gcd算完答案就自己浮出来了。