LCG 状态逐字节恢复:利用后续消息只含数字字符的约束
crypto/prng · verified
一句话结论
当 LCG 的模数 M=2^n、乘数 A、增量 C 已知,密文为 m_i XOR S_i,且后续若干条消息被约束为只含 ASCII 数字(0x30–0x39)时,可以从最低字节开始逐字节枚举初始状态 S_1 的候选,利用数字字符约束剪枝,最终唯一恢复 S_1 并解密全部消息(包括 flag)。
原理
- LCG 递推:
S_{i+1} = (A·S_i + C) mod M,M = 2^n(文章 n = flag 长度 × 8,模数为 2 的幂)。 - 加密:
cipher_i = m_i XOR S_i。已知cipher_i时,若知道S_i就能得到m_i;反之,已知m_i的部分字符集可反过来约束S_i。 - 关键性质:模
2^k的运算只依赖低 k 字节。对S_1 mod 2^{8k}的每个候选,都能递推得到S_i mod 2^{8k},进而得到m_i mod 2^{8k}(即消息的低 k 字节)。 - 逐字节提升:先枚举
S_1的最低字节(256 种),用“第 2–5 条消息的低 1 字节必须是'0'..'9'”过滤;保留下来的候选再扩展下一字节(每个候选 ×256),继续用低 2 字节的数字字符约束过滤;重复到 n 字节,候选收敛为唯一S_1。 - 为什么约束足够强:每条随机消息的每个字节都必须落在 10 个数字字符上,5 条消息 × 每字节的 10/256 概率,能在很少的字节后把候选压到唯一;flag 消息不参与约束(只用于最后解密)。
- 恢复
S_1后按完整M递推生成所有S_i,与密文异或即得明文。
触发条件
- 已知 LCG 参数
M(2 的幂)、A、C,以及至少 2–5 条密文。 - 除 flag 外的消息格式已知且字符集受限(如纯十进制数字字符串),能对每个字节做
0x30..0x39检查。 - flag 长度已知或等于最短密文长度;所有消息按同一 LCG 状态序列加密。
- 约束足够强(消息条数 × 长度)使候选唯一;否则需要更多已知明文/额外约束。
利用步骤
- 从题目获取
M、A、C与密文列表;确认M是 2 的幂(n字节)。 - 令
mod_k = 256,初始化候选S_1低字节集合为 0..255。 - 对每个候选,按
S_{i+1} = (A·S_i + C) mod mod_k递推得到各条消息的低 k 字节;检查第 2–5 条消息的每个字节是否都在0x30..0x39,不满足则淘汰。 mod_k *= 256,把保留下来的候选扩展一个字节(base + b<<(8*(k-1))),重复步骤 3,直到 k=n。- 用唯一候选
S_1在完整模M下递推,异或所有密文得到明文;第一条即 flag。
PoC
文章 exp 的核心逻辑(简化):
from Crypto.Util.number import bytes_to_long, long_to_bytes
M = 105312291668557186697918027683670432318895095400549111254310977536
A = 88374959429094291779410031678823825774338019588313091797786329067
C = 96051380126051117777593583876658604814834203814405720083455837449
ciphers = [bytes.fromhex(x) for x in [
"674c6ac59d0703753f7ccd89e563d732866af287e3bb0a1abe92c0",
"76791d13292326ad2e86ae69b9493aed416d8f71cd4a080164e3c3",
"75e03966148fd58fe623ed5fc76f62e67c8ec4be72bb6ca4b057c9",
"99201d1bd01631ce3a26687c14014030e0c2a6c01e8c1f2c115668",
"e12611c1b6f104e2f9dd18fe10e688c2e4d9c1555b57c88959b38f",
]]
n = len(ciphers[0])
def lift_S1(M, A, C, ciphers):
cs = [bytes_to_long(c) for c in ciphers]
candidates = [0]
mod_k = 1
for k in range(1, n + 1):
mod_k *= 256
A_k, C_k = A % mod_k, C % mod_k
new_cands = []
for base in candidates:
for b in range(256):
S1 = base + (b << (8 * (k - 1)))
S = S1
ok = True
for i, c in enumerate(cs):
m_low = (c ^ S) % mod_k
if i > 0: # 后续消息必须是数字字符串
if any(not (0x30 <= bb <= 0x39) for bb in m_low.to_bytes(k, "big")):
ok = False
break
S = (A_k * S + C_k) % mod_k
if ok:
new_cands.append(S1)
candidates = list(set(new_cands))
return candidates[0]
S1 = lift_S1(M, A, C, ciphers)
S = S1
for c in ciphers:
print(long_to_bytes(bytes_to_long(c) ^ S))
S = (A * S + C) % M
变体与关联
- 变体:消息约束可以是纯字母、十六进制、Base64 字符集、固定前缀;约束越强,恢复越快。
- 变体:若
A/C未知但模数已知且前若干输出公开,可先恢复参数;见 [[crypto-prng-lcg-known-modulus-xor-keystream]]。 - 变体:模数不是 2 的幂时,逐字节提升不成立,需要格/Coppersmith 或分支定界;见 [[crypto-prng-truncated-lcg-coppersmith-lattice-cvp]]。
- 关联:[[crypto-prng-lcg-high16-state-recovery-enumeration]]、[[crypto-prng-lcg-parameter-recovery-delta-gcd]]。
- 边界:约束太弱(消息条数少、字符集大)时候选不唯一;密文长度/消息长度未知时需先确定字节数。
检测与防御
- 检测:CTF/审计中看到
M=2^n、cipher = m XOR S、后续消息为固定字符集的 LCG 题,即可套用逐字节恢复。 - 防御:不要用 LCG 直接做加密/密钥流;对状态/输出做密码学安全的 KDF 或使用 CSPRNG;避免让攻击者获得同一状态序列下的多条结构化明文。
- 加固:需要可证明安全时使用 AES-GCM/ChaCha20-Poly1305 等认证加密,而不是异或线性同余输出。