短路求值 + 昂贵表达式构造四态时间侧信道:50 次查询四叉搜索 100-bit 随机数
ctf/misc · verified
一句话结论
服务端只有 50 次机会猜一个 100-bit 随机数,正常二分需要约 100 次;但表达式求值器支持 and/or 短路和 ** 幂运算。攻击者构造一个表达式,使四个区间分别对应“Yes+快 / No+快 / Yes+慢 / No+慢”四种可区分结果(2×2 状态),每次查询把候选区间缩为 1/4,50 次即可覆盖 4^50 = 2^100。
原理
- 短路求值:
A and B在 A 为 False 时不计算 B;A or B在 A 为 True 时不计算 B。求值器按 AST 递归,未走到的分支不会产生副作用/耗时。 - 昂贵表达式:表达式语言支持
**,可构造2 ** (2**25)这类巨大整数幂,计算耗时明显(数秒级),形成“慢分支”。 - 四态 oracle:对当前区间
[L,R]取三个分割点q1,q2,q3,构造:text (x < q1) OR (x >= q2 AND x < q3 AND EXPENSIVE_TRUE) OR (x >= q3 AND EXPENSIVE_TRUE AND False) x < q1→ True,短路,快;q1 <= x < q2→ 第一项 False,第二/三项的前置条件 False,整体 False,快;q2 <= x < q3→ 第二项前置 True,计算EXPENSIVE,整体 True,慢;x >= q3→ 第三项前置 True,先算EXPENSIVE再AND False,整体 False,慢。- 信息量:每次查询得到 2 bit(Yes/No × 快/慢),四叉搜索;
4^50 = 2^100,刚好覆盖 100-bit 空间(实际可留少量余量)。 - 基线校准:网络抖动会影响时间判定;先测一个“必快”表达式的中位延迟,用
slow = dt > baseline*5 + 0.05等自适应阈值判定慢分支。 - 为什么不是普通二分:二分每次只有 1 bit;四态利用“输出值 + 是否执行昂贵分支”两个维度,把每次查询信息量翻倍。
触发条件
- 服务端允许用户提交表达式(AST/字符串),并按语言语义短路求值;支持幂运算或其它可构造长耗时操作的算子。
- 查询次数受限(示例 50 次)但小于正常二分所需(100 次);随机数范围约 100 bit。
- 响应时间可观测,且慢分支耗时远大于网络抖动(示例巨大幂运算);可多次校准基线。
- 表达式长度/嵌套深度限制允许构造三层嵌套;服务端未做超时/复杂度限制。
利用步骤
- 测基线:提交一个必快表达式(如
x < -1),记录响应时间;取中位数作为 baseline。 - 构造四叉表达式:按当前
[L,R]计算q1,q2,q3,用or/and与EXPENSIVE()构造上述表达式。 - 提交并分类:记录
Yes/No与dt;slow = dt > baseline*5 + 0.05(按环境调整)。 - 更新区间:
- Yes+快 →
[L,q1)- No+快 →[q1,q2)- Yes+慢 →[q2,q3)- No+慢 →[q3,R] - 重复 50 次:区间宽度按 1/4 缩小;50 次后宽度应 ≤1。
- 提交最终猜测:发送
L,拿到 flag/成功响应。 - 调参:若时间抖动大,增加
EXPENSIVE规模/重复次数,或每轮多次采样取中位数;若表达式长度受限,减少嵌套/用等价逻辑。
PoC
def EXPENSIVE():
return {"op": "**", "arg1": 2, "arg2": int(2**25)}
def expr_quarter(q1, q2, q3):
return {
"op": "or",
"arg1": {"op": "<", "arg1": "x", "arg2": q1},
"arg2": {
"op": "or",
"arg1": {"op": "and",
"arg1": {"op": ">=", "arg1": "x", "arg2": q2},
"arg2": {"op": "and",
"arg1": {"op": "<", "arg1": "x", "arg2": q3},
"arg2": EXPENSIVE()}},
"arg2": {"op": "and",
"arg1": {"op": ">=", "arg1": "x", "arg2": q3},
"arg2": {"op": "and", "arg1": EXPENSIVE(), "arg2": False}}
}
}
L, R = 0, 1 << 100
baseline = max(measure_fast(), 0.03)
for _ in range(50):
width = R - L + 1
if width <= 1: break
q1, q2, q3 = L + width//4, L + width//2, L + 3*width//4
out, dt = send_expr(expr_quarter(q1, q2, q3))
yes, slow = b"Yes" in out, dt > baseline*5 + 0.05
if yes and not slow: R = q1 - 1
elif not yes and not slow: L, R = q1, q2 - 1
elif yes and slow: L, R = q2, q3 - 1
else: L = q3
guess(L)
原文在 50 次配额下成功恢复 100-bit 随机数;EXPENSIVE 规模与阈值需按服务端性能调整。本卡不执行 PoC。
变体与关联
- 更多状态:若表达式支持多个昂贵分支/不同耗时等级,可构造 2^k 态 oracle,进一步减少查询次数;但时间分辨率/抖动限制实际可用状态数。
- 其它侧信道:内存分配(大数组/字符串)、递归深度、异常类型、日志/错误码都可替代时间;关键是把“区间判断”编码成可观测的副作用。
- 其它求值器:Python
eval、JSON 表达式、模板表达式、SQL CASE 等只要支持短路与可控耗时操作,都可尝试。 - 关联:[[ctf-misc-xargs-argmax-split-argv-key-injection]](服务端逻辑侧信道)、[[web-generic-auth-username-enumeration-timing-lockout]](时间侧信道)、[[crypto-ecc-ecdsa-time-side-channel-hnp]](时间侧信道密码分析)。
- 边界:需要可观测响应时间且慢分支远大于抖动;服务端若加超时、限制表达式复杂度、使用常数时间求值或固定 100 次配额,攻击失效。
检测与防御
- 限制表达式:禁止
**等可构造超大整数的算子,限制数字位宽/嵌套深度/求值步数;对表达式做复杂度分析。 - 常数时间/超时:为求值设置严格 CPU/时间上限,超时直接拒绝;不要让“是否执行某分支”影响可观测响应时间。
- 配额与随机性:增加查询配额或使用不可预测的随机数;对同一会话的查询频率/模式做限制。
- 检测:大量包含
**、超大指数、and/or嵌套的表达式;查询间隔/响应时间呈现四态分布;同一会话在 50 次内提交长表达式。 - 响应:阻断异常表达式、审计是否已泄露随机数、修复求值器复杂度限制。