Lucky Draw: Win the Window

项目	内容
分类 / 难度	Misc / Crypto-ish / Medium
分值	250
类型	PRNG 种子恢复（LCG 预测）
目标	从 8 次已开奖结果反推种子，预测第 9 次并提交

1. 界面与接口

一个"整点抽奖"页面：每小时开一次奖，展示历史 8 期结果，允许你在下一期之前提交一次六位数预测。命中的话解锁 Jackpot。

GET  /api/meta     活动元信息（含种子**小时**窗口）
GET  /api/history  已开奖的 8 期结果
POST /api/claim    提交六位数预测（每会话一次）

curl http://target/api/meta

{
  "campaign_id": "YQHL-LUCKY-01",
  "campaign_started_hour_utc": "2026-10-31T14:00:00Z",
  "seed_window_start": 1793455200,
  "seed_window_end":   1793458799,
  "engine": "LEGACY-LCG31",
  "output_range": "000000-999999",
  "attempt_policy": "one submission per session"
}

curl http://target/api/history

{
  "campaign_id": "YQHL-LUCKY-01",
  "results": [
    {"draw":1,"result":"756526"}, {"draw":2,"result":"719759"},
    {"draw":3,"result":"299996"}, {"draw":4,"result":"513317"},
    {"draw":5,"result":"840186"}, {"draw":6,"result":"597675"},
    {"draw":7,"result":"470408"}, {"draw":8,"result":"862625"}
  ],
  "note": "The audit export omits the exact seed second."
}

最后那句 note 是全题的关键：只给了种子所在的"小时"，没给那一秒。

1793455200 到 1793458799 正好 3600 个整数 —— 3600 个候选种子。这个规模的暴力枚举在 Python 里是毫秒级的。

2. 引擎

"engine": "LEGACY-LCG31"

LEGACY-LCG31 这个名字直说了两件事：

LCG：线性同余发生器；
31：模数是 2^31。

算法名里的三个词已经把实现钉死了，照着写就行。有一个细节值得留意：LCG 的乘法在 64 位下不能溢出。1103515245 * state 在最坏情况下约 2^61，PHP 的整数是 64 位有符号（上限 2^63 - 1），刚好不溢出——但如果你在 Python 里复现，天然就是大整数，不用担心；在 C 里复现就得用 unsigned long long 或者先取模。所以算式写成：

state = (1103515245 * state + 12345) % (2 ** 31)
out   = state % 1000000

对 8 条历史记录逐项验证时，只要有一条不匹配就说明参数猜错了。这一步是整题唯一可能"假成功"的地方——如果前几条对上、后面开始偏，说明模数或乘子不对（比如误以为是 2^32）。

顺带确认一下输出格式：历史记录的 result 都是 6 位零填充字符串（299996、007431 这类），说明服务端是 sprintf('%06d')，预测值也要按这个格式提交。

这组参数正是 glibc rand() 用的乘法同余参数（Numerical Recipes 版），在 CTF 里几乎可以当模板用。

注意 output 只取 state % 1000000 —— 这意味着输出丢失了高位信息，所以不能从单个输出直接反解 state，但可以正向枚举种子。

3. 攻击思路

给定的约束极其宽松：

约束	数量
候选种子	3600（一小时的秒数）
已知输出	8 个
需要预测	第 9 个

每个种子正向跑 9 次 LCG，恰好 9 次。8 个已开奖值全部吻合的那个种子，就是真种子；它的第 9 个输出就是答案。

假阳性概率极低：一次比对要匹配 8 个 6 位数，单次随机吻合概率 10^-48。3600 次尝试里不可能撞出第二个解。

4. 完整利用

import json, urllib.request, http.cookiejar

BASE = "http://target"
cj = http.cookiejar.CookieJar()
op = urllib.request.build_opener(urllib.request.HTTPCookieProcessor(cj))

def g(p):
    with op.open(BASE + p, timeout=10) as r:
        return json.loads(r.read().decode())

def post(p, d):
    req = urllib.request.Request(BASE + p, data=json.dumps(d).encode(),
                                 headers={"Content-Type": "application/json"},
                                 method="POST")
    try:
        with op.open(req, timeout=10) as r:
            return json.loads(r.read().decode())
    except urllib.error.HTTPError as e:
        return json.loads(e.read().decode())

meta  = g("/api/meta")
hist  = g("/api/history")
known = [x["result"] for x in hist["results"]]

A, C, M = 1103515245, 12345, 1 << 31

def outputs(seed, n):
    st, out = seed, []
    for _ in range(n):
        st = (A * st + C) % M
        out.append("%06d" % (st % 1000000))
    return out

hit = None
for seed in range(meta["seed_window_start"], meta["seed_window_end"] + 1):
    r = outputs(seed, 9)
    if r[:8] == known:
        hit = (seed, r[8])
        break

print("[seed]", hit)
print("[claim]", post("/api/claim", {"prediction": hit[1]}))

实测输出：

[meta] 1793455200 1793458799
[hist] ['756526', '719759', '299996', '513317', '840186', '597675', '470408', '862625']
[seed] (1793457321, '785478')
[claim] {'ok': True, 'won': True, 'message': 'Prediction accepted. Jackpot unlocked.',
         'flag': 'flag{local_verify_lot01}'}

命中种子：1793457321
该种子落在窗口内（1793455200 ≤ 1793457321 ≤ 1793458799），距窗口起点 2121 秒；
第 9 次输出（预测值）：785478

5. 一个必须注意的点：会话一次性

attempt_policy 是 one submission per session，服务端这样实现的：

if (!empty($_SESSION['attempted'])) {
    jsonResponse(['ok' => false, 'error' => 'attempt_already_used',
                  'message' => 'This session has already submitted a prediction.'], 429);
}
...
$_SESSION['attempted'] = true;
session_write_close();          // 先落盘再校验

也就是说：

提交前必须把种子算准 —— 交错一次这个 session 就废了；
但 $_SESSION['attempted'] 是按 session 维度的，不是按 IP 或按账号。所以交错一次不用慌，清掉 cookie 换个 session 重来即可（题目本身没做频率限制）。当然这不是正路，正路是稳准地算出来一次过。

# 想重开一局：丢掉 cookie jar 里的 PHPSESSID
cj.clear()

还有一个不要浪费尝试的坑：/api/claim 的 prediction 校验是 /^\d{1,6}$/ 然后左补零到 6 位。如果你打算先提交一个"试探值"看看返回格式 —— 不行，那一次机会就没了。先离线把种子算出来。

6. 为什么 `state % 1000000` 不能直接反解

自然会想：既然 output = state mod 10^6，那 state = k * 10^6 + output，k 在 [0, 2148) 之间，2148 个候选 —— 能不能直接枚举 k 反推种子？

理论上可以，但有两个麻烦：

每次迭代都要在 2148 个分支里搜，8 轮后是 2148^8，爆炸；
反推前一个 state 需要解 state_prev = (state - C) * A^{-1} mod 2^31，虽然 A 与 2^31 互质（A 是奇数）所以逆元存在，但每层都得分叉。

而正向枚举 3600 个种子是 3600 × 9 = 32400 次迭代，一次线性扫描就完了。选对方向比优化算法重要得多。

顺便记住：A = 1103515245 是奇数，gcd(A, 2^31) = 1，所以 A^{-1} mod 2^31 存在（A^{-1} = 1857678181）。这是"如果能拿到完整 state"时反向攻击的基础，本题用不上，但值得知道。

7. 踩坑提示

坑	说明
把 `seed_window_start/end` 当成 seed 本身	它们是边界，seed 在中间随机某一秒
枚举范围用了 `end - 1`	`end` 是闭区间（`window_start + 3599`），`range(a, b+1)` 才对
只跑 8 次	要预测第 9 个，必须 `outputs(seed, 9)` 取最后一个
先试探性提交	每次 session 只有一次机会，试探即废
用 `state % 1000000` 反推	能反推但要分叉，几万倍慢于正向枚举
忘了 `sprintf("%06d")`	结果 `12345` 必须补成 `"012345"` 才能和接口返回值对齐；`prediction` 提交时服务端会补零，但比对历史时你这边也得补
整数溢出	PHP 这里是 64 位整数；Python 天然大数，无此问题。若用 C/Go 实现要注意用 int64

8. 从防守角度看

这题的"漏洞"不是代码 bug，是架构选择错误：

用时间戳当种子 —— 时间戳是低熵且公开的。哪怕只暴露"小时"，3600 个候选也远低于任何可接受的安全阈值；
用非密码学 PRNG 做抽奖 —— LCG 的输出存在线性关系，8 个输出足够完全确定序列；
把种子窗口写进公开 API —— /api/meta 主动给 seed_window_start/end，等于把搜索空间从 2^31 缩到 3600；
8 次历史全公开 —— 给足了约束条件。

正确做法：

用 random_bytes() / CSPRNG 生成一次性随机数，不用时间戳；
抽奖结果在开奖瞬间才生成并公开承诺（commit-reveal：先公布 sha256(seed)，开奖后公布 seed 供验证）；
不要在开奖前暴露任何与种子相关的窗口信息；
若必须可审计，用**可验证随机函数（VRF）**而不是 LCG。

9. 小结

全题就一句话：“小时窗口 + 8 个输出"已经足够确定 LCG 的种子。

/api/meta    -> 3600 个候选种子
/api/history -> 8 个输出，作为筛选条件
正向枚举     -> 32400 次迭代，毫秒级
命中         -> seed = 1793457321，第 9 个输出 = 785478
/api/claim   -> Jackpot

答案：

seed_window        1793455200 .. 1793458799
命中种子           1793457321
预测值（第 9 次）   785478
FLAG               flag{local_verify_lot01}