4 位半字节进位链加密逆向:低 4 位传给下一字符高 4 位,解必须按正序一边解 LCG 密钥一边推进
ctf/reverse · verified
一句话结论
当每个输出字节由「上一字符残留的低 4 位 XOR 本次密钥的高 4 位」拼成、且本次解出的低 4 位又要留给下一个字符时,字节之间形成强依赖链,必须从头正序逐字节解,同时用一个初值固定的 16 位 LCG(x = (291x + 1110) & 0xffff)同步推密钥;单字节独立爆破或倒序解都解不出来。
原理
- 编码器为每字符维护
tmp1(首字符固定为常量,如0x40):输出的高 4 位来自tmp1 ^ (ans >> 4),其中ans = 16bit_in ^ lcg_state;输出后tmp1 = (ans << 4) & 0xff,即把本次ans的低 4 位提升为下一字符的高 4 位。 - 因为
ans依赖当前 LCG 状态,而状态是纯递增序列(与明文无关),所以密钥流可任意跳读、可预计算;但tmp1依赖上一个字符的解密结果,所以明文的推进必须串行。 - 存储上每题把每个字符写成 8 字节(两个小端 16 位或 1 字节 + 7 字节补零),有效信息只有前 2 字节:
lo = enc[i] | enc[i+1] << 8,与 LCG 状态异或后得到ans。 - 反推顺序:先由
lcg_state算出ans = lo ^ state,再取ans >> 4与tmp1异或得到明文高 4 位;随后tmp1 = (ans << 4) & 0xff供下一轮。首次的tmp1是硬编码常量,可从初始化代码或直接枚举 0x00–0xFF 中唯一能产出可打印前缀的那个值确定。 - 这类题的“加密”本质上是一个状态机(上一输出的低半字节喂给下一输入),安全性为零,但逆向时必须识别依赖方向,否则会错误地写成并行解密。
触发条件
- 密文按固定宽度(常见 8 字节)分块存放,每块只有前 2 字节非零。
- 加密循环里出现
<<4、>>4、& 0xff、& 0xfff/& 0xffff这类半字节操作,且上一轮结果参与下一轮。 - 存在一个初值固定的伪随机数发生器(LCG/xorshift)产生逐字符密钥。
利用步骤
- 定位加密循环,确认块宽(8)、有效字节位置(前 2 字节)、LCG 常数与掩码。
- 确认
tmp1的初值来源:硬编码常量或初始化函数内赋值。 - 按块正序遍历:
state = (a*state + c) & mask;ans = lo ^ state;chr = tmp1 ^ (ans >> 4);tmp1 = (ans << 4) & 0xff。 - 若首字符不可打印,枚举
tmp1的 256 个候选,选整串落在[0x20,0x7e]且匹配已知 flag 头(如DASCTF{)的那个。
PoC
tmp = 0xDEAD # LCG 初值
enc = [0xB9,0x22,0,0,0,0,0,0, 0xF8,0xC9,0,0,0,0,0,0] # 每字符 8 字节,仅前 2 字节有效
flag = []
tmp1 = 0x40 # 上一字符低 4 位(首字符硬编码初值)
for i in range(0, len(enc), 8):
tmp = (291 * tmp + 1110) & 0xffff
x = (enc[i+1] << 8) + enc[i]
ans = x ^ tmp
flag.append(tmp1 ^ (ans >> 4))
tmp1 = (ans << 4) & 0xff
print(bytes(flag))
首字符未知时枚举初值:
for init in range(256):
tmp, tmp1, out = 0xDEAD, init, []
for i in range(0, len(enc), 8):
tmp = (291 * tmp + 1110) & 0xffff
ans = ((enc[i+1] << 8) + enc[i]) ^ tmp
out.append(tmp1 ^ (ans >> 4))
tmp1 = (ans << 4) & 0xff
if all(0x20 <= c < 0x7f for c in out) and bytes(out).startswith(b"DASCTF{"):
print(init, bytes(out))
变体与关联
- 变体:链方向反过来(高 4 位留给下一字节的低 4 位)时,只需解方程
ans_low = next_tmp_high ^ ...,但仍是串行推进。 - 变体:密钥流换成 xorshift/MT19937 时,只要状态可复现,解密框架不变。
- 变体:若块宽不是 8 而是 4,
enc[i+1]<<8改成直接取 16 位大端。 - 关联:[[ctf-reverse-lfsr-derived-keystream-bit-swap-xor]](伪随机密钥流 + 位操作混合)、[[ctf-reverse-custom-feistel-20round-dword-key-rotation-inverse]](同一赛题中的多轮结构逆向)。
- 边界:如果输出不保留“上一字符 4 位”而是丢弃,链断开,可并行解;如果 LCG 常数依赖输入,则需联立求解。
检测与防御
- 本题为 CTF 反解题,无线上攻击面。工程上:不要用“半字节链 + 固定种子 PRNG”当混淆,密钥流与明文强相关才能提高逆向成本(如把 LCG 状态混入明文)。