time(0) 时间种子 + 双轮 65537 次洗牌与自定义 mix:按样本 mtime 窗口爆破 seed 并逆变换
ctf/reverse · verified
一句话结论
加密只依赖 time(0) 种子:48 字节输入被拆成 12 个 int32,先做两轮各 65537 次的 LCG 驱动交换,再对 4 组三元组做 65537 轮自定义可逆 mix。种子本身不可从密文直接恢复,但密文是在样本生成时运行的,按二进制文件 mtime 取 ±1 小时窗口枚举 time(0),对每个候选逆置换、逆 mix,再用 MD5 目标值验证即可得到唯一 seed 和明文。
原理
- seed 来源:
main_program_0调用time(0)并通过get_int读取,存入全局变量,后续洗牌全部依赖它;种子只有约 31 位,且与样本生成/运行时刻强相关。 - 数据打包:读入 48 个字符,按小端打包成 12 个 int32:
packed = c0 | c1<<8 | c2<<16 | c3<<24;后续所有变换都以 int32 为单位。 - LCG 变体:常量来自字符串
"staralgoiU K"的小端 4 字节切分: a = 0x72617473(star)c = 0x6f676c61(algo)m = 0x4b205569(iU K)- 状态更新:
tmp = (a*state + c) mod 2^32(按 int32 溢出),state = tmp % m,负数修正到0..m-1。 - 两轮洗牌:每轮连续调用两次 LCG,得到
i = state % 12、j = state % 12,交换idx[i]与idx[j],重复 65537 次;两轮使用同一 LCG 状态链。记录交换顺序即可得到最终置换new[pos] = old[idx[pos]]及其逆。 - 自定义 mix:12 个 int 分成 4 组(
a[0..2]、a[3..5]、a[6..8]、a[9..11]),每组独立做 65537 轮: - 每轮先更新常量
t*=p0; p0*=p1; p1*=t(32 位回绕); - 再依次更新 A、B、C,每次使用乘常数、C 语义的截断除法(
/13、/29等)与 XOR;A/B/C 的更新顺序使每步都依赖前一步结果。 - 可逆性:洗牌是置换,逆置换即可还原;mix 每轮只是“加上一个由当前变量计算出的值”,逆过程按 C→B→A 的顺序减回即可,除法只依赖尚未被该步修改的变量,因此可精确复算。
- 为什么用 mtime:样本作者生成密文时必然运行过程序,运行时刻通常接近文件编译/打包时间;
LastWriteTime给出秒级线索,±1 小时窗口通常只有几千个候选,逐个逆变换 + MD5 验证成本很低。 - MD5 作用:作为唯一的“是否正确”判据;没有它,逆变换结果可能看起来像随机字节,无法确定哪个 seed 命中。
触发条件
- 二进制中调用
time(0)/time(NULL)并用其返回值初始化 PRNG 或置换。 - 加密过程只包含可逆的置换、加减、XOR、乘法与除法,没有单向哈希(哈希只用于最终校验)。
- 程序或样本带有可读的文件时间、编译时间戳,或已知密文生成的大致日期。
- 校验端保存固定长度的 MD5/SHA 目标值。
利用步骤
- 反编译入口,确认
time(0)被读入并参与后续所有变换;记录迭代次数(示例 65537)与数组维度(12)。 - 从字符串/常量恢复 LCG 参数与 mix 常量,注意 int32 回绕和 C 的向零截断除法(Python
//是向下取整,负数时会不同)。 - 实现正向变换,用任意 seed 验证能与程序行为一致;再实现逆置换与逆 mix。
- 读取样本文件的
LastWriteTime,转 UNIX 秒后取±3600窗口;若文件被压缩包解压导致时间漂移,扩大窗口或改用 PE 编译时间戳、样本目录时间。 - 对窗口内每个 seed 执行逆变换,计算 MD5 与目标比较;命中后输出 seed 与明文。
- 若 MD5 不匹配,检查:种子是否被
& 0xFFFFFFFF/符号扩展、洗牌轮数是否两轮、mix 除法是否截断、字节序是否小端。
PoC
import hashlib, struct
CT = [961328601, 940839751, 705572502, -1296360751, 1510741316, -746016568,
1758503669, -312360224, 1117958716, -1263168281, -1534151026, -1968871781]
TARGET_MD5 = bytes.fromhex("2887941ed3ea0f6b7ca870cd11f0de13")
ITERS = 0x10001
def s32(x):
x &= 0xFFFFFFFF
return x - 0x100000000 if x & 0x80000000 else x
def u32(x): return x & 0xFFFFFFFF
def add(a, b): return s32(u32(a) + u32(b))
def sub(a, b): return s32(u32(a) - u32(b))
def mul(a, b): return s32(u32(a) * u32(b))
def xor(a, b): return s32(u32(a) ^ u32(b))
def div0(a, d): # C 语义:向零截断
q = abs(a) // abs(d)
return q if (a >= 0) == (d >= 0) else -q
def lcg(state):
a, c, m = 0x72617473, 0x6f676c61, 0x4b205569
return s32(u32(a * s32(state) + c)) % m
def perms(seed):
def one(st):
idx = list(range(12))
for _ in range(ITERS):
st = lcg(st); i = st % 12
st = lcg(st); j = st % 12
idx[i], idx[j] = idx[j], idx[i]
return st, idx
st, idx1 = one(s32(seed)); st, idx2 = one(st)
def inv(idx):
r = [0] * 12
for pos, old in enumerate(idx):
r[old] = pos
return r
return inv(idx1), inv(idx2)
def unshuffle(arr, inv):
return [arr[inv[i]] for i in range(12)]
STATES = []
t, p0, p1 = 1924939505, 396307405, 1601708927
for _ in range(ITERS):
t, p0, p1 = mul(t, p0), mul(p0, p1), mul(p1, t)
STATES.append((t, p0, p1))
def unmix(a, b, c):
for t, p0, p1 in reversed(STATES):
s0 = xor(add(mul(406831633, a), div0(b, 17)), add(mul(1648306586, a), div0(b, 23)))
s1 = xor(add(p1, a), sub(b, p1))
c = sub(c, xor(s0, s1))
s0 = xor(add(mul(666086835, c), div0(a, 11)), add(mul(1361690111, c), div0(a, 19)))
s1 = xor(add(p0, c), sub(a, p0))
b = sub(b, xor(s0, s1))
s0 = xor(add(mul(1126760380, b), div0(c, 13)), add(mul(660328234, b), div0(c, 29)))
s1 = xor(add(t, b), sub(c, t))
a = sub(a, xor(s0, s1))
return a, b, c
def decrypt(seed):
inv1, inv2 = perms(seed)
arr = unshuffle(CT, inv2)
for base in (0, 3, 6, 9):
arr[base:base + 3] = unmix(*arr[base:base + 3])
arr = unshuffle(arr, inv1)
return b"".join(struct.pack("<i", x) for x in arr)
# t0 由样本 mtime 转成 UNIX 秒;示例窗口 ±1 小时
for seed in range(t0 - 3600, t0 + 3600 + 1):
pt = decrypt(seed)
if hashlib.md5(pt).digest() == TARGET_MD5:
print("seed =", seed)
print(pt.decode())
break
示例中最终 seed 为 1764108097,明文为 flag{4waK1nG_1nTh3_L1gH7_0fA1LThE_s74r5_a1igNeD}。
变体与关联
- 本库已有“勒索样本 CRC32 ^ time(0) 作为 MT19937 种子、从加密文件 mtime 恢复时间”的卡片;本卡的区别是种子直接来自
time(0),且核心在双轮洗牌与三轮 mix 的逆变换。 - 其他时间源:
GetTickCount、clock()、rdtsc、std::chrono::system_clock;若种子由多个值组合,先恢复各分量的可能范围再爆破。 - 若种子是
srand(time(0))+rand(),直接复刻 glibc/MSVC 的 PRNG 实现;若种子被哈希包裹,先确认哈希是否可逆(通常不可逆,只能爆破)。 - 文件时间可能被 ZIP 解压、Git checkout、容器拷贝改写;可同时尝试 PE
TimeDateStamp、样本内嵌日期字符串、题目发布日期作为窗口中心。
检测与防御
- 检测特征:程序调用
time()后紧接 PRNG/置换初始化;循环次数为 65536/65537 等 2 的幂附近;密文长度固定且校验端保存 MD5。 - 防御(真实系统):不要把时间戳直接当密钥或种子;使用 CSPRNG 生成随机密钥,并对密文做 HMAC;若必须用时间,至少混入高熵 secret 并避免可预测的窄窗口。
- CTF 中遇到“逆变换结果无法判定”时,优先寻找最终哈希/比较目标,用其作为爆破 oracle;不要试图目测明文。