交互题 checker 未校验查询下标上界:直接查询 A_n 每一位
ctf/misc · verified
一句话结论
交互题题面声称查询只能选 1 ≤ i ≤ n-1、目标是求最后一个元素 A_n,但 checker 实际没有拒绝 i = n;直接发送 ? n (1<<k) 并观察返回 0/1,32 次查询即可按位恢复 A_n,再提交答案。
原理
- 交互题通常用
? i x查询第i个元素与x的某种关系;题面把i限制在1..n-1,意图是让选手通过前缀/集合关系间接推导A_n。 - 如果 checker 只解析参数、未校验
1 <= i <= n-1,那么i = n会被当作合法下标,直接返回A_n与x的比较/位测试结果。 - 利用返回值的二进制语义:查询
x = 1<<k,若返回 1 说明A_n的第 k 位为 1;对 k=0..31 循环即可恢复 32 位整数。 - 为什么可行:题面约束与代码校验不一致(logic flaw);交互协议没有对越界下标做拒绝/惩罚,攻击者可以绕过预期解题路径。
- 若
A_n超过 32 位,按实际位宽扩展;若返回的是比较而非位测试,可改用二分/逐位构造。
触发条件
- 交互式 checker 接受
i作为查询下标,但只校验格式/类型,未校验上界。 - 查询返回值能区分
A_n的位/大小(如返回 0/1 或比较结果)。 - 目标
A_n的位宽已知或可推断(如 32 位整数)。 - 交互次数/超时允许约 32 次查询。
利用步骤
- 阅读题面与协议,确认查询格式(如
? i x)和返回语义。 - 先用合法下标测试协议;再尝试
i = n,观察是否被拒绝。 - 若未被拒绝,发送
? n (1<<k),记录返回值;k 从 0 到 31。 - 按返回值置位,拼出
A_n;必要时用已知样例/小 n 验证位序。 - 发送
! ans提交;若 checker 还要求其他字段,按协议补齐。 - 若
i=n被拒绝,尝试i=n+1、负数、极大值、类型混淆等边界,寻找其他校验缺口。
PoC
from pwn import *
context.log_level = "info"
io = remote("target", 19442)
t = int(io.recvline())
for _ in range(t):
n = int(io.recvline())
ans = 0
for k in range(32):
io.sendline(f"? {n} {1 << k}".encode())
if int(io.recvline()) == 1:
ans |= 1 << k
io.sendline(f"! {ans}".encode())
print(io.recvall(timeout=3).decode(errors="ignore"))
说明:PoC 为原文 exp 的结构化精简,未在本机执行;原文通过 ? n (1<<k) 恢复 12 组 A_n 后拿到 flag。
变体与关联
- 变体(越界类型):
i=0、i=n、i>n、负数、超大整数、非整数;不同 checker 的校验缺口不同。 - 变体(返回值):位测试、比较结果、距离、哈希/随机化;可按语义改造成二分/逐位/统计 oracle。
- 变体(协议):多轮交互、批量查询、带权查询;先找“题面约束 vs 代码校验”的差异。
- 关联:[[ctf-misc-tupper-self-referential-formula-decode]](按位/大整数解码);[[ctf-pwn-bytecode-sandbox-header-memsize-stack-oob-rop]](边界取自输入头部的同类逻辑缺陷)。
- 边界:checker 严格校验下标、查询有次数/惩罚限制、返回值不携带位信息时,本方法不成立。
检测与防御
- 检测:交互协议中
i未做1 <= i <= n-1校验;返回 0/1 的位测试接口可被逐位枚举;题面约束与实现不一致。 - 防御:checker 对所有输入做严格范围/类型校验;对越界查询返回错误/终止;不要用单个 bit 直接暴露目标值,加入随机化/批量约束。
- 加固:题面与实现保持一致;对交互次数/异常模式做限制;用 property-based testing 覆盖边界下标。