文章总结： 文章解析HITCON2017CTFLuaky题目，针对三种基于PRNG的石头剪刀布对手设计必胜策略。核心包括破解模3计数器的直接预测、利用模溢出特性收敛状态范围、及基于群论预计算查找表定位状态。文中提供完整Lua脚本与数学推导，展示了从简单观察到复杂代数攻击的PRNG破解路径。 综合评分： 90 文章分类： CTF,漏洞分析,逆向分析
HITCON 2017 Luaky 完整技术解析
原创
破镜安全 破镜安全
破镜安全
2026年3月4日 08:00 四川
HITCON 2017 Luaky 完整技术解析
题目背景
本题来自 HITCON 2017 CTF，是一道 Crypto 题，核心是设计一个用 Lua 脚本语言编写的石头剪刀布 AI，通过分析服务器使用的伪随机数生成器（PRNG），预测对手出招并稳定取胜。
附件为一个 ELF 64 位可执行文件（服务器端程序），使用 liblua5.3.so 执行选手提交的 Lua 脚本。
题目规则
服务器共有三种对手形态，每种形态用不同的简单 PRNG 生成出招序列：
- Slime：
state = (state + 1) % 3，cpuhand = state - Alpaca：
state = (state + yourlasthand + 0x9E3779B9) % 0x100000000，cpuhand = state % 3 - Nozomi：
state = (state * 48271) % 0x7fffffff，cpuhand = state % 3
每轮 100000 次石头剪刀布，赢 90000 次算赢一轮。种子来自 /dev/urandom，完全随机，不可直接枚举。
选手的 Lua 脚本只需实现一个 play(prev_cpu_hand) 函数：输入是电脑上一次出招，输出是本次出招（0、1 或 2）。
出招编码与胜负规则：
通过分析 Slime 的极端简单情况可以推导出游戏胜负规则。Slime 的 state 按 (state+1)%3 递增，每轮 cpuhand = state，即电脑依次循环出 0→1→2→0→…。
play() 函数每轮接收电脑的上一次出招（prev = state_prev），此时电脑出的是新 state = (state_prev + 1) % 3。如果我们返回 prev（state_prev），则：
- 我方出 0，电脑出 1：胜（0 = 石头，1 = 剪刀，石头胜剪刀）
- 我方出 1，电脑出 2：胜（1 = 剪刀，2 = 布，剪刀胜布）
- 我方出 2，电脑出 0：胜（2 = 布，0 = 石头，布胜石头）
因此本题出招编码为：0 = 石头，1 = 剪刀，2 = 布。
胜负公式：出招 X 可以击败出招 (X + 1) % 3。等价地，若已知对方下一次出招为 Y，我方应出 (Y - 1) % 3 来取胜。
第一关：破解 Slime
PRNG 机制：
state = (state + 1) % 3
cpuhand = state
state 每轮加 1 再取模，所以电脑的出招序列是一个固定的 0→1→2→0→… 循环，与种子无关（种子决定了初始相位，但规律完全固定）。
破解方法：
play() 接收的 prev_cpu_hand 正好等于 state_prev，而电脑下一轮将出 (state_prev + 1) % 3。我们返回 state_prev 即可，因为 state_prev 能击败 (state_prev + 1) % 3。
function play(prev)
return prev
end
这样可以在 100000 轮中赢下全部（除第一轮外，因为第一轮没有 prev 参考值）。
第二关：破解 Alpaca
PRNG 机制：
state = (state + yourlasthand + 0x9E3779B9) % 0x100000000
cpuhand = state % 3
其中 yourlasthand 是我们上一轮的出招，由我们完全控制。0x9E3779B9 是黄金比例常数（Fibonacci hashing 中常见的魔数）。
关键数学性质：
首先验证两个关键余数：
0x9E3779B9 % 3 = 0
0x100000000 % 3 = 1
由于 0x9E3779B9 % 3 = 0，如果我们始终出招 0（yourlasthand = 0），则状态更新退化为：
state_new = (state + 0x9E3779B9) % 0x100000000
现在分析 state_new % 3（即电脑下一次出招）与 state % 3（电脑当前出招）的关系：
情况一：不发生溢出
条件：state < 0x100000000 - 0x9E3779B9 = 0x61C88647（称为阈值 THRESHOLD）
此时 state_new = state + 0x9E3779B9，直接相加无截断，因此：
state_new % 3 = (state + 0x9E3779B9) % 3
= state % 3 + 0
= state % 3
= cpuhand（不变）
结论：若当前 state 在阈值以下，电脑下一轮出招与本轮相同。
情况二：发生溢出
条件：state >= 0x61C88647
此时 state_new = state + 0x9E3779B9 - 0x100000000（截断后的值），因此：
state_new % 3 = (state + 0x9E3779B9 - 0x100000000) % 3
= state % 3 + 0 - 1 (mod 3)
= (cpuhand - 1) % 3
结论：若当前 state 超过阈值，电脑下一轮出招比本轮退后一步（即 (cpuhand - 1) % 3）。
破解策略：
通过观察连续两轮电脑出招是否相同，判断当前 state 处于阈值的哪一侧：
cpu_hand_new == cpu_hand_prev：无溢出，state 在[0, THRESHOLD-1]范围内cpu_hand_new != cpu_hand_prev：有溢出，state 在[THRESHOLD, 0xFFFFFFFF]范围内
用两个变量 alp_low、alp_high 维护当前 state 的估计范围，初始为 [0, 0xFFFFFFFF]。每轮观察后根据有无溢出收缩范围：
- 无溢出：
alp_high = min(alp_high, THRESHOLD-1)，再加上GOLDEN更新到新 state 的范围 - 有溢出：
alp_low = max(alp_low, THRESHOLD)，再减去MODULUS并加GOLDEN
经过数轮观察，范围会逐渐收窄。当 alp_high < THRESHOLD 时，可以确定下一轮无溢出（电脑出相同的手）；当 alp_low >= THRESHOLD 时，可以确定下一轮有溢出（电脑出 (cpuhand-1)%3）。一旦能够准确预测，就按 (predicted_next - 1) % 3 出招取胜。
第三关：破解 Nozomi
PRNG 机制：
state = (state * 48271) % 0x7fffffff
cpuhand = state % 3
这是经典的 Park-Miller 线性同余生成器（LCG），模数 M = 0x7fffffff = 2^31 - 1 是梅森素数，乘数 48271 是标准 Park-Miller LCG 所使用的参数之一。
群论基础：
由费马小定理，模素数 p 的乘法群阶为 p-1。此处：
M = 2^31 - 1 = 2147483647（梅森素数）
群阶 = M - 1 = 2147483646
可验证：pow(48271, M-1, M) = 1（费马小定理）
因此，从任意非零初始 state 出发，LCG 的轨道长度整除 2147483646。
破解思路：
种子来自 /dev/urandom，无法直接枚举（空间约 2^31）。但观察发现 state 的轨道是一个封闭循环，我们可以利用 LCG 的代数结构预计算一张查找表。
构建查找表：
定义”签名”（signature）为连续 5 次出招的元组，例如 (2, 0, 1, 1, 2)。
从 state = 1 出发，记录每个位置的 5 步签名以及这 5 步后对应的 state 值，然后跳跃 9000 步到下一个采样点，重复此过程。
跳跃 9000 步等价于乘以：
pow(48271, 9000, 0x7fffffff) = 1467418072
一共采样 250000 个点，验算覆盖范围：
250000 * 9000 = 2,250,000,000 > 2,147,483,646（群的阶）
采样点总数超过群阶，因此必然覆盖了整个循环。换言之，无论服务器选取什么种子，其状态序列中必然包含某个采样点，且这个采样点距最近的查找表条目不超过 9000 步。
表的形式：
table[(hand_1, hand_2, hand_3, hand_4, hand_5)] = state_after_5_hands
查找并预测：
在对战 Nozomi 的过程中，维护一个滑动窗口，记录电脑最近 50 次出招。每轮取最新的 5 次出招组成签名，查询表中是否存在：
- 若存在：得到这 5 步后的 state 值，继续推进 1 步（
state = state * 48271 % 0x7fffffff）即可得到电脑下一轮的 state，从而预测出招并出(cpuhand - 1) % 3取胜 - 若不存在：继续积累观察数据
由于表的覆盖保证，在连续观察 9050 次后必然找到匹配（因为相邻两个采样点之间恰好 9000 步，窗口大于间距则必有交集）。一旦找到匹配后，后续所有轮次都可以精确预测，稳定取胜。
关于时间分配：
构建这张 250000 条目的表需要约 250000 * 6 = 1.5M 次乘法，在 Lua 中运行时间较长。题目说明中有一个重要细节：在脚本加载阶段（play() 函数首次被调用之前）没有时间限制，只有每轮 play() 调用有 1 秒限制。因此，建表逻辑放在 Lua 脚本的全局初始化区域执行，在对战开始前完成。在对战 Slime 和 Alpaca 的过程中，建表也已同步完成，为后续对战 Nozomi 做好准备。
完整 Lua 脚本逻辑（伪代码）
-- 全局初始化区域（无时间限制）
local M = 0x7fffffff
local MULT = 48271
local SKIP = 1467418072 -- pow(48271, 9000, M)
local GOLDEN = 0x9E3779B9
local THRESHOLD = 0x100000000 - GOLDEN
-- 构建 Nozomi 查找表
local noz_table = {}
local state = 1
for i = 1, 250000 do
local s = state
local hands = {}
for j = 1, 5 do
s = (s * MULT) % M
hands[j] = s % 3
end
local key = hands[1] * 81 + hands[2] * 27 + hands[3] * 9 + hands[4] * 3 + hands[5]
noz_table[key] = s
state = (state * SKIP) % M
end
-- Alpaca 状态追踪变量
local alp_low = 0
local alp_high = 0xFFFFFFFF
local prev_cpu = nil
-- Nozomi 滑动窗口
local noz_window = {}
local noz_state = nil -- 一旦找到即锁定
-- game_type 由外部环境设置，标识当前对手类型
function play(last_cpu)
if game_type == "slime" then
return last_cpu
elseif game_type == "alpaca" then
-- 更新 state 范围估计
if prev_cpu ~= nil then
if last_cpu == prev_cpu then
-- 无溢出
alp_high = math.min(alp_high, THRESHOLD - 1) + GOLDEN
alp_low = alp_low + GOLDEN
else
-- 有溢出
alp_low = math.max(alp_low, THRESHOLD) + GOLDEN - 0x100000000
alp_high = alp_high + GOLDEN - 0x100000000
end
end
prev_cpu = last_cpu
-- 预测并出招
local pred
if alp_high < THRESHOLD then
pred = last_cpu
elseif alp_low >= THRESHOLD then
pred = (last_cpu - 1 + 3) % 3
else
return 0 -- 尚未收敛，出默认值
end
return (pred - 1 + 3) % 3
elseif game_type == "nozomi" then
-- 更新滑动窗口
table.insert(noz_window, last_cpu)
if #noz_window > 50 then table.remove(noz_window, 1) end
-- 若已锁定 state，直接预测
if noz_state ~= nil then
noz_state = (noz_state * MULT) % M
local pred = noz_state % 3
noz_state = (noz_state * MULT) % M -- 预读下下轮
return (pred - 1 + 3) % 3
end
-- 尝试用最新 5 步匹配查找表
if #noz_window >= 5 then
local w = noz_window
local n = #w
local key = w[n-4] * 81 + w[n-3] * 27 + w[n-2] * 9 + w[n-1] * 3 + w[n]
local found = noz_table[key]
if found ~= nil then
noz_state = found -- state after these 5 hands
noz_state = (noz_state * MULT) % M
local pred = noz_state % 3
noz_state = (noz_state * MULT) % M
return (pred - 1 + 3) % 3
end
end
return 0 -- 尚未找到匹配，随机出招
end
end
数学原理汇总
Slime — 等差周期序列
PRNG 输出序列为 0, 1, 2, 0, 1, 2, ...（以 3 为周期），完全可预测。无需任何密钥恢复。
Alpaca — 基于模运算的侧信道恢复
核心利用的性质：
0x9E3779B9 ≡ 0 (mod 3)：加法常数不影响state mod 30x100000000 ≡ 1 (mod 3)：溢出截断使state mod 3减 1
通过观察出招序列中的”是否发生溢出”，逐步缩小 state 的估计区间，最终实现预测。这是一种基于行为观测的侧信道分析方法。
Nozomi — 乘法群上的预计算攻击
利用线性同余生成器具有代数循环结构的特性：
- 模梅森素数的乘法群是循环群，轨道封闭可枚举
- 通过快速幂
pow(m, k, M)实现跳跃采样，以 9000 为间隔预计算整个轨道 - 利用 5 步签名窗口（
3^5 = 243种可能值）在表中定位当前位置 - 覆盖性保证：
250000 × 9000 > M - 1，查找必然成功
这是一种针对 LCG 的已知输出攻击（Known-Output Attack），利用 LCG 的可逆代数结构完全恢复内部状态。
获得 Flag
按上述策略对战：
- 赢下 Slime（第一轮，100000 次全胜）
- 赢下 Alpaca 10 轮（观察几百轮后稳定预测，轻松达成 90000/100000）
- 赢下 Nozomi 10 轮（建表完成后同样达成）
第一个 Flag（Alpaca 或 Nozomi 其中一个赢满 10 轮）：
hitcon{Hey Lu4ky AI, I am Alpaca… MEH!}
总结
本题将三种经典 PRNG 攻击手法浓缩在一道题中：
| 对手 | PRNG 类型 | 攻击方法 | | — | — | — | | Slime | 模 3 计数器 | 直接预测，无需任何分析 | | Alpaca | 模 2^32 加法 LCG | 侧信道：观察溢出行为收敛 state 范围 | | Nozomi | 模梅森素数乘法 LCG（Park-Miller） | 预计算查找表，利用群结构定位内部状态 |
这三道题对应的技术难度依次提升，从零知识预测到代数侧信道分析，再到基于群论的预计算攻击。这是 PRNG 安全研究中非常经典的攻击路径。
免责声明：
本文所载程序、技术方法仅面向合法合规的安全研究与教学场景，旨在提升网络安全防护能力，具有明确的技术研究属性。
任何单位或个人未经授权，将本文内容用于攻击、破坏等非法用途的，由此引发的全部法律责任、民事赔偿及连带责任，均由行为人独立承担，本站不承担任何连带责任。
本站内容均为技术交流与知识分享目的发布，若存在版权侵权或其他异议，请通过邮件联系处理，具体联系方式可点击页面上方的联系我。
本文转载自：破镜安全 破镜安全 破镜安全《HITCON 2017 Luaky 完整技术解析》
版权声明
本站仅做备份收录，仅供研究与教学参考之用。
读者将信息用于其他用途的，全部法律及连带责任由读者自行承担，本站不承担任何责任。
评论