LilacCTF2026 Writeup
本届 LilacCTF 2026由XCTF联赛的合作单位哈尔滨工业大学 Lilac 战队组织,由赛宁网安提供技术支持。作为第十届XCTF国际联赛的分站赛,本次比赛将采用在线网络安全夺旗挑战赛的形式,面向全球开放
Misc
Welcome
题目给了一串16进制数
789c0540b10980400c5ce92442067849153bc1f278ae1031ad95b87bc8bba6c611df6925ec46076bc955f2e0056ccc773c7f03fb580c81看到789c开头就想到是zlib压缩了
放到cyberchef点两下魔法棒就出了
LilacCTF{W3lc0M3_70_l1L4cc7F_g00D_LuCk}
Your GitHub, mine
这个题目是要通过Issue触发的邮件,去给lilacctf-tech发邮件,这个邮件的X-GitHub-Sender必须是tynqf4hn8z-byte
题目同时也能通过tynqf4hn8z-byte去创建一个Issue,那就先发一封试试
先加入Classroom
发现要验证,还是选择暴力破解
import hashlib
from itertools import count
PREFIX = "wBzY6Dc1o2"
TARGET_PREFIX = "000000"
print(f"[*] 正在爆破 SHA256('{PREFIX}' + X) ...")
print(f"[*] 目标: hash 开头 {len(TARGET_PREFIX)} 个 0")
def sha256_hex(s: str) -> str:
return hashlib.sha256(s.encode()).hexdigest()
for i in count(0):
x = str(i)
digest = sha256_hex(PREFIX + x)
if digest.startswith(TARGET_PREFIX):
print("\n[SUCCESS]")
print(f"X = {x}")
print(f"Hash = {digest}")
break
if i % 100_000 == 0:
print(f"尝试中... {i}", end="\r")同时也要去把Watch设置上,能同步收到邮件
提交Issue后,邮箱收到了Issue邮件,X-GitHub-Sender为tynqf4hn8z-byte
虽然 lilacctf-tech 这个项目本身是处于 Watching 状态,但题目里也明确说明:通过 nc 触发的那封邮件不计入。
另一方面,Issue 是可以通过 mentioned 来触发通知的。不过一开始直接 @lilacctf-tech 并不会有任何反应。于是就尝试把该账号添加为项目成员,这里测试时给了管理员权限。
在成为项目成员(管理员)之后,@lilacctf-tech 就可以被正常 mention 了。
同时还发现,这个 Issue 我本身是有编辑权限的。于是直接编辑 Issue,在内容里同时 @lilacctf-tech 和我自己的账号,提交之后就成功收到了邮件,并且邮件头里显示的是 tynqf4hn8z-byte。
至此,条件满足,顺利拿到了 Flag。
LilacCTF{D1sCov3r_Mor3_G17hU8_f347ur32}
Questionnaire
问卷题目,直接交就行
LilacCTF{7h4nk_U_f0r_p4rt1cip4t1n9_L1l4cCTF_2026}
Sky Is Ours
经典的Osint找航班
直接百度识图
找到是青岛航空
没认出来这是哪里
下面是大连,应该是经过,向南飞的航班,然后去flightradar24查看青岛航空从东北出发的航线
想起是哈工大出的题目,猜测是学生去打比赛拍摄的
稍微排查一下
QW6097符合条件(应该是去福州打数字中国拍摄的)
LilacCTF{D1sCov3r_Mor3_G17hU8_f347ur32}Residue
题目给出的是某个“真实模型”在某段输入文本上的 logits 序列(通常形状是 [1, seq_len, vocab]),要求我们反推出最可能的原始输入文本。
这类题的关键点是:
- GPT 类模型是自回归:第
t个位置的 logits 是在输入前缀x_1..x_t的条件下产生的。 - 如果我们用同一个模型(同权重、同 tokenizer、同 dtype/精度设置尽量一致)去跑“猜测的前缀”,那么在正确 token 上,模型最后一位 logits 会和给定 target_logits 高度一致。
核心思路
对第 t 个 token 做枚举:
- 已恢复前缀 token ids:
ids = [x1, x2, ..., x_{t-1}] - 枚举候选 token
c,构造ids + [c] - 喂给 GPT2,取输出 logits 的最后一位
logits[-1],与题目给的target_logits[t-1]做距离 - 距离最小的
c就是最可能的x_t
MSE:
这个距离非常直观:如果模型输出完全一致,loss 会接近 0。
正确性判据:loss 数量级
观察到的现象:
- 正确 token:best loss 往往在
1e-12 ~ 1e-9(几乎数值误差级别) - 错误 token:best loss 通常直接跳到
1e-2 ~ 1e+1
这说明题目给的 logits 很可能来自:
- 同一个模型(如
gpt2-medium) - 非常一致的推理环境(至少 logits 误差很小)
- 或者题目本来就希望你用“loss 断崖”当剪枝依据
所以在 recover 过程中,只要某一步 best loss 突然“断崖式变大”,基本可判定前缀已经走歪。
候选集剪枝(提速关键)
如果每步枚举全 vocab(~50k),84 步会爆炸。
因此需要剪枝:
- 字符集约束候选 token
- 只保留 decode 出来的字符串在允许字符集里(如
[A-Za-z0-9_{}]) - 并限制 token decode 长度(1~5)避免奇怪的控制符、空格、BPE 残片等
- 前缀 hint 锁定
- 例如 flag 往往形如
LilacCTF{...} - 前 6 步直接把候选集锁死为
["L"], ["il"], ["ac"], ["CT"], ["F"], ["{"] - 这能极大降低前期分支,避免从一开始就跑歪
- 逐步叠加
- 先用单字符/小 token 拼出稳定前缀
- 前缀稳定后再放开候选集合
- 利用 loss 断崖作为“正确路径信号”
exp:
import os
import string
from dataclasses import dataclass
from typing import Dict, List, Optional, Tuple
import numpy as np
import torch
from transformers import GPT2LMHeadModel, GPT2Tokenizer
# ===== 环境(与你一致)=====
os.environ["HF_ENDPOINT"] = "https://hf-mirror.com"
os.environ["HF_HOME"] = os.path.expanduser("~/.cache/huggingface")
@dataclass
class Config:
model_name: str = "gpt2-medium"
target_file: str = "target_logits.npy"
seq_len: int = 84
# 候选 token decode 后允许的字符范围
allowed_chars: str = string.ascii_letters + string.digits + "_{}"
# 限制 token decode 的长度(避免奇怪 BPE 残片太长)
max_piece_len: int = 5
# batch 大小(越大越快,但更吃显存)
batch_size: int = 512
# 进度输出频率
progress_every: int = 1
STEP_HINT: Dict[int, List[str]] = {
1: ["L"],
2: ["il"],
3: ["ac"],
4: ["CT"],
5: ["F"],
6: ["{"],
}
def get_device() -> str:
return "cuda" if torch.cuda.is_available() else "cpu"
def load_target_logits(path: str, device: str) -> torch.Tensor:
arr = np.load(path)
t = torch.from_numpy(arr).float().to(device)
return t
def build_global_candidates(tokenizer: GPT2Tokenizer, cfg: Config) -> List[int]:
allowed = set(cfg.allowed_chars)
keep: List[int] = []
for tid in range(tokenizer.vocab_size):
s = tokenizer.decode([tid])
if not (1 <= len(s) <= cfg.max_piece_len):
continue
if all(ch in allowed for ch in s):
keep.append(tid)
print(f"[*] Global candidates kept: {len(keep)} / {tokenizer.vocab_size}")
return keep
def build_step_candidates(tokenizer: GPT2Tokenizer, step: int) -> Optional[List[int]]:
"""如果该 step 有锁定 hint,就返回匹配这些 decode 字符串的 token id 列表;否则返回 None。"""
if step not in STEP_HINT:
return None
targets = set(STEP_HINT[step])
cand: List[int] = []
for tid in range(tokenizer.vocab_size):
if tokenizer.decode([tid]) in targets:
cand.append(tid)
print(f"[*] Step {step} locked to: {sorted(list(targets))} (tokens={len(cand)})")
return cand
@torch.no_grad()
def score_candidates_batch(
model: GPT2LMHeadModel,
device: str,
prefix_ids: List[int],
cand_ids: List[int],
target_vec: torch.Tensor,
batch_size: int,
) -> Tuple[int, float]:
"""
对 cand_ids 做批量评估:
- 对每个候选 c:输入 [prefix_ids + c]
- 取 logits 的最后一位,与 target_vec 做 MSE
返回 (best_token_id, best_loss)
"""
best_tok = -1
best_loss = float("inf")
# 逐批处理,避免一次性堆太大
for start in range(0, len(cand_ids), batch_size):
chunk = cand_ids[start : start + batch_size]
# 拼 batch 输入:每行 = prefix + [c]
seqs = [prefix_ids + [c] for c in chunk]
x = torch.tensor(seqs, device=device, dtype=torch.long) # [B, T]
out = model(x)
logits_last = out.logits[:, -1, :] # [B, V]
# MSE: mean((logits - target)^2) over vocab dim
# target_vec: [V] -> broadcast to [B, V]
losses = torch.mean((logits_last - target_vec) ** 2, dim=1) # [B]
min_val, min_idx = torch.min(losses, dim=0)
l = float(min_val.item())
if l < best_loss:
best_loss = l
best_tok = chunk[int(min_idx.item())]
return best_tok, best_loss
def solve(cfg: Config) -> str:
device = get_device()
print("[*] Device:", device)
tokenizer = GPT2Tokenizer.from_pretrained(cfg.model_name)
model = GPT2LMHeadModel.from_pretrained(cfg.model_name).float().to(device)
model.eval()
target_logits = load_target_logits(cfg.target_file, device)
# 期望形状 [1, seq_len, vocab]
assert target_logits.dim() == 3, f"unexpected target_logits dim={target_logits.dim()}"
assert target_logits.size(1) >= cfg.seq_len, "target seq_len smaller than expected"
assert target_logits.size(2) == model.config.vocab_size, "vocab mismatch"
print("[*] target_logits:", tuple(target_logits.shape))
print("[*] vocab_size:", model.config.vocab_size)
global_cand = build_global_candidates(tokenizer, cfg)
recovered: List[int] = []
for step in range(1, cfg.seq_len + 1):
target_vec = target_logits[0, step - 1, :] # [V]
step_cand = build_step_candidates(tokenizer, step)
if step_cand is None:
step_cand = global_cand
best_tok, best_loss = score_candidates_batch(
model=model,
device=device,
prefix_ids=recovered,
cand_ids=step_cand,
target_vec=target_vec,
batch_size=cfg.batch_size,
)
if best_tok < 0:
raise RuntimeError(f"step {step}: no candidate found")
recovered.append(best_tok)
if step % cfg.progress_every == 0:
piece = tokenizer.decode([best_tok])
text = tokenizer.decode(recovered)
print(f"[step {step:02d}] token={repr(piece):>14s} loss={best_loss:.3e}")
print(f" current={text}\n")
# 可选:利用你观察到的“断崖”快速报警
# 这里不强制中断,只提示(你也可以直接 raise)
if best_loss > 1e-3:
print(f"[!] warning: loss jumped to {best_loss:.3e} at step {step}, prefix may be wrong.")
final_text = tokenizer.decode(recovered)
print("[*] Full recovered text:")
print(final_text)
return final_text
if __name__ == "__main__":
cfg = Config(
model_name="gpt2-medium",
target_file="target_logits.npy",
seq_len=84,
batch_size=512,
max_piece_len=5,
)
solve(cfg)LilacCTF{Injective_LLM_WDZwFXWVppFFhc4twobFBWzpi_never_G0nn4_9iv3_u_up_never_Gonna_let_you_down_9087675_976433535_979654332_I_Lov3_Lily_Whit3}
very_good_ssh
应该是非预期了
直接把宿主机文件挂在mnt目录下了,之后传公钥,用密钥登陆root即可
Reverse
ezPython
这题拿到 main.exe,应该是是 PyInstaller
先用 strings 看一眼:
strings main.exe | grep -i pyinstaller能看到一堆很“标志性”的内容,比如:
PYZ-00.pyzpython39.dllpyimod01_archiveMEI\x0c\x0b\x0a\x0b\x0e
PyInstaller 的尾部会带一个 cookie(魔数):
MEI\014\013\012\013\016在文件末尾附近搜索这个魔数,就可以解析 cookie 拿到:
- 包起始位置(pkg start)
- TOC 偏移(Table of Contents)
- TOC 长度等信息
然后按 TOC 格式逐条解析 entry(核心字段大概是):
entry_lendata_offsetcompressed_sizeuncompressed_sizecflag(是否压缩)typename
照这个结构把文件逐个解出来,最终会拿到若干关键模块
解出来的文件里,真正跟题目逻辑强相关的通常就那几个:
smain:主逻辑入口(没有 pyc 头,marshal 的 code object)myalgo:加密/校验算法crypto:辅助模块(有时是一些编码/混淆)PYZ-00.pyz:标准库/依赖库集合(大多不用细看)
到这一步,其实方向已经很明确:主逻辑在 smain,算法在 myalgo。
smain 不是标准 .pyc(没有 header),但本质就是 Python 3.9 的 code object,被 marshal 序列化了。
把它 marshal.loads() 后反编译(或者直接用 dis 看逻辑)能还原出等价源码结构,大概是下面这样:
print(base64.b64decode(welcome_msg).decode())
flag = input(a85decode(input_msg).decode())
if not flag.startswith("LilacCTF{"):
print("Wrong Flag!"); exit()
if not flag.endswith("}"):
print("Wrong Flag!"); exit()
if len(flag) != 26:
print("Wrong Flag!"); exit()
flag = flag[9:25] # 只取中间 16 字符(LilacCTF{ 后到 } 前)
res = [761104570, 1033127419, 3729026053, 795718415]
key = list(struct.unpack("<IIII", b"1111222233334444"))
inp = list(struct.unpack("<IIII", flag.encode()))
myalgo.btea(inp, 4, key)
if inp == res:
print("Right, congratulations!")
else:
print("Wrong Flag!")- flag 固定前后缀:
LilacCTF{和} - 总长必须 26 → 中间内容必须是 16 字符
- 中间 16 字符会被
struct.unpack("<IIII")拆成 4 个uint32 - 调用
myalgo.btea(inp, 4, key)做变换 - 输出要等于给定常量数组
res
因此本质是:中间 16 字符经过某种 TEA 类算法加密后等于 res
去看 myalgo,里面有很典型的:
MX()混合函数btea(v, n, key)的结构rounds = 6 + 52//n这种固定轮数公式
这就是经典的 Block TEA / XXTEA 系列实现(btea 常用名就是它)。
主程序里调用是 btea(inp, 4, key),即 n=4,对 4 个 uint32 块加密。
既然是对称算法,那逆向就很简单:把 res 当作密文,做 n=-4 的解密即可得到原始 4 个 uint32,再 pack 回 16 字符。
题目里 key 是固定的:
key = struct.unpack("<IIII", b"1111222233334444")密文也是固定的:
cipher = [761104570, 1033127419, 3729026053, 795718415]我们实现一份 btea 解密(把加法改成减法/逆向循环),然后:
- 解密得到
plain_words(4 个 uint32) struct.pack("<IIII", *plain_words)变回 16 bytes- decode 得到中间 16 字符
- 拼回 flag:
LilacCTF{...}
示例解密脚本如下(核心点是与题目实现保持一致):
import struct
def btea_decrypt(v, k):
DELTA = 0x9E3779B9
n = 4
rounds = 6 + 52 // n
mask = 0xffffffff
def MX(y, z, sum_, p, e):
return (((z >> 5 ^ y << 2) + (y >> 3 ^ z << 4))
^ ((sum_ ^ y) + (k[(p & 3) ^ e] ^ z)))
sum_ = (rounds * DELTA) & mask
y = v[0]
while rounds > 0:
e = (sum_ >> 2) & 3
for p in range(n - 1, 0, -1):
z = v[p - 1]
y = v[p] = (v[p] - MX(y, z, sum_, p, e)) & mask
z = v[n - 1]
y = v[0] = (v[0] - MX(y, z, sum_, 0, e)) & mask
sum_ = (sum_ - DELTA) & mask
rounds -= 1
return v
cipher = [761104570, 1033127419, 3729026053, 795718415]
key = list(struct.unpack("<IIII", b"1111222233334444"))
plain = btea_decrypt(cipher.copy(), key)
mid = struct.pack("<IIII", *plain).decode("ascii")
flag = f"LilacCTF{{{mid}}}"
print(flag)LilacCTF{e@sy_Pyth0n_SMC!}C++++
起手调试:
expected ciphertext在校验分支附近通常会看到类似:
memcmp(enc_input, expected, 32) == 0这里 expected 长度是 32 bytes(也就是 2 个 16 字节 block)。
在程序数据区/反编译常量里能拿到它对应的 hex:
A20492152735B4F6ECBAA359DB64417B
DF277A73B085666034CF38E748D8FBD4合并写成一行:
A20492152735B4F6ECBAA359DB64417BDF277A73B085666034CF38E748D8FBD4结论:这是一个 128-bit 分组密码 输出(16B * 2 block),输入 token 很可能被处理成固定 32B 再加密。
继续向下跟到加密核心函数,进入内部能看到两个关键特征:
- 外层是 16 轮 Feistel/类 Feistel
- 以 4 个 uint32 作为状态(128-bit)
- 轮间有 swap(最后一轮不 swap)
- 轮里出现
rol/ror、+ subkey、^混合 - 前后都有 whitening(输入 XOR K[0..3],输出 XOR K[4..7])
- 轮函数 gFunc 是查表型结构
你看到的 “大量越界检查/数组寻址” 本质上是 AOT/.NET 多维数组(MD array)访问产生的边界检查代码,不是核心加密逻辑。真正逻辑是:
- S-box/Q-box(byte 表)替换
- MDS(4×256 uint32)查表混合
- XOR 合成 32-bit 输出
这套结构非常贴 Twofish:
- 128-bit block
- 16 轮 Feistel
- Q permutation(Q0/Q1)
- MDS matrix 查表实现
- RS 编码生成 S-key(key schedule 的一部分)
因此可以确定算法就是 Twofish
Twofish 的 key schedule 很烦,在动态调试过程中(断到 key schedule / encryption init 相关位置),内存里能看到 key 明文
57 4F 4E 44 45 52 46 55 4C 26 26 50 45 41 43 45ASCII 即:
WONDERFUL&&PEACE长度 16 bytes → Twofish-128。
轮函数/查表需要用到程序中的表。最方便的方式是:在调试暂停时,直接从寄存器指向的表对象 dump 原始数据。
R12指向 MDS(大表)RAX指向 Q/Sbox(小表)
然后跳过对象头(常见 +0x20),分别 dump:
v30_mds.bin:0x1000 bytes(1024 个 uint32)v31_q.bin:0x200 bytes(前 256 为 SBOX,后 256 为 INV_SBOX)
这一步做完,脚本侧就能完全复刻 Twofish 的 g 函数。
我们手上已经有:
- key:
WONDERFUL&&PEACE - expected ciphertext:32 bytes(2 blocks)
- Q/SBOX + MDS 表(dump 文件)
Twofish/Feistel 的好处:解密只要反向轮顺序,轮函数不需要可逆。
因此做法是:
- 由 key 生成 ctx(S-key)和 40 个子密钥 K(含 whitening + round subkeys)
- 对每个 16B block:
- undo output whitening(XOR K[4..7])
- 从 round 15 → 0 逆着跑,注意 swap 规则
- undo input whitening(XOR K[0..3])
- 拼回 32B 明文,去掉 padding(末尾 0x00)
- 得到 token/flag
exp:
import struct
from pathlib import Path
# ====== load dumped tables ======
Q = Path("v31_q.bin").read_bytes()
SBOX = list(Q[:256])
INV_SBOX = list(Q[256:])
M = Path("v30_mds.bin").read_bytes()
mds = list(struct.unpack("<1024I", M))
MDS = [mds[i * 256:(i + 1) * 256] for i in range(4)]
def rol32(x, r):
r &= 31
x &= 0xFFFFFFFF
return ((x << r) & 0xFFFFFFFF) | (x >> (32 - r) if r else 0)
def ror32(x, r):
r &= 31
x &= 0xFFFFFFFF
return (x >> r) | ((x << (32 - r)) & 0xFFFFFFFF if r else 0)
# ====== RS encode (from binary logic) ======
def rs_encode(even_word, odd_word):
res = 0
for i in range(2):
v = odd_word if i == 0 else even_word
res ^= v & 0xFFFFFFFF
for _ in range(4):
b3 = (res >> 24) & 0xFF
v7 = 29 if (res & 0x80000000) else 0
v8 = 0x8E if (res & 0x01000000) else 0
t0 = (v7 ^ ((2 * b3) & 0xFF) ^ v8 ^ ((b3 >> 1) & 0x7F) ^ (res & 0xFF)) & 0xFF
t1 = (((res >> 8) & 0xFF) ^ v7 ^ ((2 * b3) & 0xFF)) & 0xFF
t2 = (v7 ^ ((2 * b3) & 0xFF) ^ v8 ^ ((b3 >> 1) & 0x7F) ^ ((res >> 16) & 0xFF)) & 0xFF
res = t0 | (t1 << 8) | (t2 << 16) | (b3 << 24)
return res & 0xFFFFFFFF
# ====== Twofish g function (matches your simplified path) ======
def g_func(ctx_s, x, L_words=None):
b0 = x & 0xFF
b1 = (x >> 8) & 0xFF
b2 = (x >> 16) & 0xFF
b3 = (x >> 24) & 0xFF
if L_words is None:
w0, w1 = ctx_s[0], ctx_s[1]
else:
w0, w1 = L_words[0], L_words[1]
a = SBOX[b0]
b = INV_SBOX[(a ^ (w1 & 0xFF)) & 0xFF]
t = MDS[0][((w0 & 0xFF) ^ b) & 0xFF]
a = INV_SBOX[b1]
b = INV_SBOX[(a ^ ((w1 >> 8) & 0xFF)) & 0xFF]
t ^= MDS[1][(((w0 >> 8) & 0xFF) ^ b) & 0xFF]
a = SBOX[b2]
b = SBOX[(a ^ ((w1 >> 16) & 0xFF)) & 0xFF]
t ^= MDS[2][(((w0 >> 16) & 0xFF) ^ b) & 0xFF]
a = INV_SBOX[b3]
b = SBOX[(a ^ ((w1 >> 24) & 0xFF)) & 0xFF]
t ^= MDS[3][(((w0 >> 24) & 0xFF) ^ b) & 0xFF]
return t & 0xFFFFFFFF
# ====== key schedule (keylen=16 -> even/odd 2 words path) ======
KS0 = 0x0A0A0A0A
KS1 = 0x0D0D0D0D
KS2 = 0x0000000D
def make_ctx_and_subkeys(key16: bytes):
w = list(struct.unpack("<4I", key16))
even = [w[0], w[2]]
odd = [w[1], w[3]]
S0 = rs_encode(even[0], odd[0])
S1 = rs_encode(even[1], odd[1])
ctx_s = [S1, S0] # reversed storage (matches binary)
K = []
for i in range(20):
A = g_func(ctx_s, (i * KS0) & 0xFFFFFFFF, even)
B = rol32(g_func(ctx_s, (KS1 + i * KS0) & 0xFFFFFFFF, odd), 8)
K.append((A + B) & 0xFFFFFFFF)
K.append(rol32((A + 2 * B) & 0xFFFFFFFF, KS2))
return ctx_s, K
# ====== decrypt one 16B block (inverse of 16-round Feistel) ======
def decrypt_block(ct16: bytes, K, ctx_s):
y0, y1, y2, y3 = struct.unpack("<4I", ct16)
# undo output whitening
d0 = y0 ^ K[4]
d1 = y1 ^ K[5]
d2 = y2 ^ K[6]
d3 = y3 ^ K[7]
for j in range(15, -1, -1):
if j < 15:
# undo the round swap (encryption swaps for rounds 0..14)
d0, d1, d2, d3 = d2, d3, d0, d1
t0 = g_func(ctx_s, d0, None)
t1 = g_func(ctx_s, rol32(d1, 8), None)
F0 = (K[8 + 2 * j] + t0 + t1) & 0xFFFFFFFF
F1 = (K[8 + 2 * j + 1] + t0 + 2 * t1) & 0xFFFFFFFF
d2 = ror32(d2, 27) ^ F0
d3 = ror32(d3 ^ F1, 5)
# undo input whitening
x0 = d0 ^ K[0]
x1 = d1 ^ K[1]
x2 = d2 ^ K[2]
x3 = d3 ^ K[3]
return struct.pack("<4I", x0, x1, x2, x3)
def main():
key = b"WONDERFUL&&PEACE"
ctx_s, K = make_ctx_and_subkeys(key)
exp_hex = "A20492152735B4F6ECBAA359DB64417BDF277A73B085666034CF38E748D8FBD4"
ct = bytes.fromhex(exp_hex)
pt = b"".join(decrypt_block(ct[i:i + 16], K, ctx_s) for i in range(0, len(ct), 16))
pt = pt.rstrip(b"\x00")
print(pt.decode("utf-8", errors="replace"))
if __name__ == "__main__":
main()解出来的明文就是最终flag:
LilacCTF{I_ju3t_w@nnA_b3_hapPy}λm
在 AST 里能明确看到一共有 3 处 Z-combinator 调用,分别对应:
- 一段主逻辑
- 一段读取/展开输入的逻辑
- 一段辅助递归/遍历逻辑(暂定)
其中 Z 的定义是经典版本:
Z = λf.(λx.f(λv.x x v))(λx.f(λv.x x v))还出现了 ID = λx.x 这种恒等函数,整体形态很像把递归与数据结构拆开后再拼回去跑。
把主干抽象出来大致可以整理成:
core = Z(arg0_lambda)(arg1_expr)(ID)(node16_value)
result = core(TRUE)(1)(0)arg0_lambda:一个无自由变量的递归函数生成器(更像是“遍历/比较器”的递归骨架)arg1_expr:一个巨大常量结构(应该是固定的“目标/模板/变换表”之类)node16_value = node16.func(input_expr_value):这里的node16.func是闭包,可单独 eval 出来(也就是输入会先被某个函数预处理)- 最后
core(TRUE)(1)(0)这种写法很像 Church encoding 的“分支选择/布尔决策输出”
三处 Z 调用的特征(都推导出 generator arity=4):
Z_call0:gen_arity=4, has_subscript=FalseZ_call1:gen_arity=4, has_subscript=TrueZ_call2:gen_arity=4, has_subscript=False
初步推测:
Z_call0是主流程(最终判定输出的那条)Z_call1负责读取输入并做 bit-level 展开/结构化(因为它带下标访问,像是在取某个表或结构的元素)Z_call2可能是主流程用到的辅助递归函数(用于树遍历/比对等)
输入长度看起来固定为 32 bytes(256 bits)。在 Z_call1 里可以看到标准 Church 编码组件:
TRUE = λt.λf.t
FALSE = λt.λf.f
PAIR = λa.λb.λf.f(a)(b)读取时每个字节会被拆成 8 个 Church Bool,顺序是 LSB → MSB。然后用 PAIR 递归地拼成一棵完美平衡二叉树,单字节对应的树结构类似:
pair(
pair(pair(b0,b1), pair(b2,b3)),
pair(pair(b4,b5), pair(b6,b7))
)因此 32 个字节最终会变成一个“固定结构的巨大布尔树”,叶子全是 Church Bool。
我最开始的观测是:输入映射到类似 256×256 的扩展结构,并且“翻转任意 1 bit 会导致输出约 256 bit 的变化”。
这让我怀疑它不是简单线性展开,而更像:
- 行/列填充式构造(row/column fill)
- 或者 circulant matrix / 对角线循环填充(类似把 256-bit 向量复制成循环移位的矩阵)
同时也注意到有很多类似:
[λ__:λ_:_, λ__:λ_:_][x & 1]这种“按位挑 TRUE/FALSE”的写法共出现了 8 次,直觉上是在做 32×8=256 次 bit 选择(逐位把输入变成 Church Bool)。
另外还能看到 4 份纯常量(闭包环境为空)构造出来的 256-bit bit-tree,像是固定 mask/常量向量,用于后续比较或混合。
目前能确定的输入处理结果可以归纳为:
- 输入:32 bytes
- 展开:256 Church Bool(每字节 LSB→MSB)
- 结构化:用 PAIR 拼成固定形态的平衡树
- 后续:进入
node16.func和arg0_lambda/arg1_expr的递归核心比较/计算
附:当前观察到的相关 hash/输出标记为:
172064d8b6712022735da8fc088ca07ff344596e8bbca22b75df360b5226e31bb3a2f9f284JustROM
拿到 ROM 后先看机器码特征,能直接识别出是 SPARC:
9D E3 BF A0:典型save(函数序言)81 E8 00 00:restore81 C3 E0 08:retl
配合题目环境可确定是 SPARC 32-bit big-endian。
(ROM/RAM mapping:ROM base 0x10800000 size 0x10000;RAM base 0x107F0000 size 0x14000)
IDA 对 SPARC ROM 不太好用,直接上 Ghidra 反编译。
能看到几个关键函数:
FUN_00004060:32 位循环左移
return x >> (-(byte)r & 0x1f) | x << ((byte)r & 0x1f);这就是 32-bit ROTL(循环左移),是 ChaCha 的核心操作之一。
FUN_00004238:ChaCha core
在该函数里能看到非常明显的 ChaCha 特征:
- quarter round 结构
- 旋转常数固定是:
16, 12, 8, 7 - 循环结构只跑了 8 rounds(4 个 double-round),而不是标准 ChaCha20
结论:这是 ChaCha8。
FUN_0000409c:状态初始化
状态矩阵是典型的 ChaCha 4×4(16 个 uint32):
0..3:常量"expand 32-byte k"(sigma)4..11:256-bit key12:counter(这里固定为1)13..15:nonce(这里固定为0x41414141, 0x42424242, 0x43434343)
主函数(验证处)逻辑可以还原为四步:
- 程序内置两段数据:
ciphertext:32 bytes 真密文fake_flag:32 bytes 字符串"There_is_nothing_you_wanna_get.."
- 先做一次 XOR:
expected = fake_flag XOR ciphertext- 生成 ChaCha8 keystream(32 bytes),然后把用户输入做 XOR:
enc_input = user_input XOR keystream- 比较:
enc_input == expected → 通过因此要反推输入,其实就是:
user_input = expected XOR keystream从 ROM 固定偏移处拿到关键数据:
- key(32 bytes,大端读入 8 个 word),ROM 偏移
0xC000:
11 22 33 44 55 66 77 88 99 AA BB CC DD EE FF 00
DE AD BE EF CA FE BA BE 0B AD F0 0D 13 37 13 37- nonce(3 个 word):
0x41414141, 0x42424242, 0x43434343- counter:
1 - ciphertext(32 bytes):
37 32 9b f6 36 a9 18 fc f2 e7 49 73 61 49 f8 d4
4c f2 6a c9 3c 4c 62 83 78 12 5c 05 5f 30 95 9d- fake_flag:
"There_is_nothing_you_wanna_get.."exp:
import struct
# ---------------- ChaCha8 core ----------------
def rotl32(x, r):
x &= 0xFFFFFFFF
r &= 31
return ((x << r) & 0xFFFFFFFF) | (x >> (32 - r))
def quarter_round(x, a, b, c, d):
x[a] = (x[a] + x[b]) & 0xFFFFFFFF
x[d] ^= x[a]; x[d] = rotl32(x[d], 16)
x[c] = (x[c] + x[d]) & 0xFFFFFFFF
x[b] ^= x[c]; x[b] = rotl32(x[b], 12)
x[a] = (x[a] + x[b]) & 0xFFFFFFFF
x[d] ^= x[a]; x[d] = rotl32(x[d], 8)
x[c] = (x[c] + x[d]) & 0xFFFFFFFF
x[b] ^= x[c]; x[b] = rotl32(x[b], 7)
def chacha8_block(state16_words):
st = state16_words[:] # original
x = state16_words[:] # working
# 8 rounds = 4 double-rounds
for _ in range(4):
# column rounds
quarter_round(x, 0, 4, 8, 12)
quarter_round(x, 1, 5, 9, 13)
quarter_round(x, 2, 6, 10, 14)
quarter_round(x, 3, 7, 11, 15)
# diagonal rounds
quarter_round(x, 0, 5, 10, 15)
quarter_round(x, 1, 6, 11, 12)
quarter_round(x, 2, 7, 8, 13)
quarter_round(x, 3, 4, 9, 14)
out = [(x[i] + st[i]) & 0xFFFFFFFF for i in range(16)]
return out
def build_state(key_words_be, counter, nonce_words):
# sigma = "expand 32-byte k"
sigma = [0x61707865, 0x3320646e, 0x79622d32, 0x6b206574]
return sigma + key_words_be + [counter] + list(nonce_words)
def words_to_keystream_le(words16):
# ChaCha 输出字节序是 little-endian
return b"".join(struct.pack("<I", w) for w in words16)
# ---------------- problem data ----------------
FAKE = b"There_is_nothing_you_wanna_get.." # 32 bytes
CIPHERTEXT = bytes.fromhex(
"37329bf636a918fcf2e749736149f8d4"
"4cf26ac93c4c628378125c055f30959d"
)
KEY_BYTES = bytes.fromhex(
"112233445566778899aabbccddeeff00"
"deadbeefcafebabe0badf00d13371337"
)
# key words are read as big-endian in ROM
KEY_WORDS_BE = list(struct.unpack(">8I", KEY_BYTES))
COUNTER = 1
NONCE = (0x41414141, 0x42424242, 0x43434343)
def main():
# Step A (match binary): expected = fake_flag XOR ciphertext
expected = bytes(a ^ b for a, b in zip(FAKE, CIPHERTEXT))
# Step B: generate keystream from ChaCha8(state)
state = build_state(KEY_WORDS_BE, COUNTER, NONCE)
ks_words = chacha8_block(state)
keystream = words_to_keystream_le(ks_words)[:32]
# Step C (reverse check): user_input XOR keystream == expected
# => user_input = expected XOR keystream
flag = bytes(e ^ k for e, k in zip(expected, keystream))
print(flag.decode("ascii"))
if __name__ == "__main__":
main()运行输出:
LilacCTF{d0ntl@@kl1kechch4atall}
Nineapple
题目给的是标准 iOS App Bundle:
_CodeSignature/embedded.mobileprovisionInfo.plistNine(主二进制)PkgInfo
Nine 是 Mach-O 可执行文件,用 IDA/Ghidra 打开后,先从字符串入手,能快速定位主逻辑:
Please draw an unlock patternWrong..LetGoAndMovOn!Right! flag is :
对 Right! flag is : 做 XREF,可以直接跳到核心校验函数(IDA 里表现为 sub_100006D08() 这一段)。
sub_100006D08() 里能抽出非常清晰的流水线:
- 用户画九宫格路径(点序列),程序把路径转成数字串(例如
1478) - 每次输入一个字符的路径时,会维护一个
current_key:
current_key += digit * weight[idx]idx++
- 将数字串在
map_list(路径↔字符表)里查出对应字符并追加到current_flag - 同时把该字符对应的
current_key追加进key_all - 最终校验:
key_all必须与内置的target_all逐项相等 - 全部匹配则输出:
Right! flag is : <current_flag>
也就是说:target_all 本质上保存了 flag 每个字符的“路径编码值”。
current_key 的累加逻辑在 sub_1000069A4() 中实现,等价于:
[
enc(dstr) = \sum_{i=0}^{len(dstr)-1} digit[i] \cdot weight[i]
]
其中:
dstr是路径数字串(比如"1478")digit[i]是第 i 位字符对应的数字(1~9)weight[i]是固定权重数组(长度 9,对应最多 9 个节点)
从二进制的数据区可以直接读到 weight,例如:
weights = [10564859903, 880404991, 67723460, 4837390, 322492, 20155, 1185, 65, 3]通过 LockViewModel 初始化(你标的 sub_100006258 一带)可以定位到三份核心数据:
weights:用于计算路径编码target_all:33 个 u64,每个对应 flag 的一个字符map_list:路径数字串 ↔ 字符(Swift small-string 形式存储,条目很多)
map_list 的意义是“路径字符串能对应哪个字符”。比如:
"1478" -> 'L'"582" -> 'i'
而 target_all 存的就是每个字符对应路径的 enc(path) 的结果。
因此我们不需要模拟 UI 画图,也不需要跑程序,只要:
- 用
weights对 map_list 中的每个路径算enc(path) - 得到
enc(path) -> char的反查表 - 逐个读取
target_all[i],查回字符并拼起
import struct
BIN = "Nine"
# --- helpers ---
def u64le(buf, off):
return struct.unpack_from("<Q", buf, off)[0]
def parse_swift_small_string_16(chunk: bytes) -> str:
"""
Swift small string (16B inline) 常见格式:
- 最后一个字节带 tag bit(最高位)
- 低 4 bit 存长度
这题数据区符合这种模式。
"""
last = chunk[-1]
if (last & 0x80) == 0:
raise ValueError("not small-string")
ln = last & 0x0F
return chunk[:ln].decode("ascii", errors="ignore")
def enc_path(digitstr: str, weights):
ds = [int(c) for c in digitstr]
return sum(ds[i] * weights[i] for i in range(min(len(ds), len(weights))))
def main():
data = open(BIN, "rb").read()
# 这些偏移来自静态分析(同你记录)
WEIGHTS_OFF = 0x10340
TARGETS_OFF = 0x103B0
MAP_START = 0x104E0
MAP_END = 0x109C0
# 1) read weights
weights = [u64le(data, WEIGHTS_OFF + i * 8) for i in range(9)]
# 2) read targets (flag length = 33)
targets = [u64le(data, TARGETS_OFF + i * 8) for i in range(33)]
# 3) parse map_list as (char, digitstr) pairs
ss = []
for off in range(MAP_START, MAP_END, 16):
ss.append(parse_swift_small_string_16(data[off:off+16]))
pairs = [(ss[i], ss[i+1]) for i in range(0, len(ss), 2)] # (char, digitstr)
# 4) build reverse map: enc(digitstr) -> char
rev = {}
for ch, dstr in pairs:
rev[enc_path(dstr, weights)] = ch
# 5) decode flag
flag = "".join(rev[t] for t in targets)
print(flag)
if __name__ == "__main__":
main()Lilac{10S_aNd_l1lac_w1n3_f0r_you}Kilogram
样本带壳,先用脱壳机把主程序 dump 出来,再用 IDA 打开。
静态反编译函数很长,实际更快的切入点是动态:
- 程序运行后,内存里会出现关键字符串:
"flag"/"./flag.enc"等 - 给这些字符串地址下 硬件断点(read/write)
- 一路跟到写文件逻辑,就能落在真正的加密流程上
这样可以绕开 VMP 大量噪声,直接定位到“生成 key / 打乱 sbox / xor / 写出结构”的那段核心
核心逻辑:
- 程序生成一个 64 字节的
key1(其实是 sha512 的输出) - 初始化 S-box:
S[i] = (i + 4) mod 256(注意:不是标准 RC4 的 0..255,而是整体 +4) - 用
key1走一遍 KSA-like,把 S-box 打乱 - 用打乱后的 S-box 前 64 字节去 XOR
key1本身(等价于“把 key1 再加密一层”)
- 这 64 字节会被写入
flag.enc的头部区 - 程序再生成一个 64 字节
key2(来源是 PBKDF2-HMAC-SHA512 的结果)
- 用同样的 KSA-like(仍然是 S[i]=i+4)打乱 S-box
- 用该 S-box 去 XOR “真正的密文 payload”(也就是被加密的 flag 内容)
由于是 XOR 流加密结构,所以解密只要把相同的 keystream 再 XOR 一遍即可。
猜:
[ "lilac___" ]
[ metadata blocks ]
[ RC4-encrypted flag ]
[ md5 ]但复现后会发现:文件头不一定能直接解释成“有意义的文本结构”(可能是写入时拼接的 buffer,不是严格格式化)。
- 前 8 bytes:magic/占位(不影响解密)
- 接下来 64 bytes:加密后的
key1(我们记作key1_enc) - 接下来 32 bytes:salt(用于生成 key2)
- 后面主体:payload(加密后的 flag 内容)
- 最后 16 bytes:校验数据(你测试可忽略;实际像 md5 截断/附加校验)
所以真实布局可记为:
flag.enc =
[0x00:0x08] header(8)
[0x08:0x48] key1_enc(64)
[0x48:0x68] salt(32)
[0x68:-0x10] enc_payload
[-0x10:] check(16)验证 enc_payload 解出来是 JPG 文件头 FF D8 FF E0 ...,说明 flag 藏在图片里(或图片里直接写了 flag)
静态分析 findcrypt 能看到 md5 / sha512 / pbkdf2 字样,但复现时发现对不上。
回头看代码,关键点是:SHA-512 的 K 常量表被改了 1 项:
# K[??] = 0xF57D4FF7FEE6ED0D # 修改后的常量这会导致:
- sha512 输出不同
- hmac_sha512 不同
- pbkdf2_hmac_sha512 导出的 key2 不同
最终解密链条非常清晰:
- 从
flag.enc读取salt(32) - 计算:
key_base = sha512(salt + b"Lilac+present")key2 = pbkdf2_hmac_sha512(key_base, salt, iter=10000, dklen=64)
- 用 KSA-like(key2) 生成 keystream,解出
key1:
key1 = key1_enc XOR keystream_key2[:64]
- 用 KSA-like(key1) 生成 keystream,解出 payload:
payload = enc_payload XOR keystream_key1[i & 0xff]
- payload 写出为
out.jpg,直接打开得到 flag
import struct
from pathlib import Path
MASK64 = (1 << 64) - 1
# ---------- modified SHA-512 ----------
H0 = [
0x6a09e667f3bcc908, 0xbb67ae8584caa73b,
0x3c6ef372fe94f82b, 0xa54ff53a5f1d36f1,
0x510e527fade682d1, 0x9b05688c2b3e6c1f,
0x1f83d9abfb41bd6b, 0x5be0cd19137e2179,
]
K = [
0x428a2f98d728ae22, 0x7137449123ef65cd,
0xb5c0fbcfec4d3b2f, 0xe9b5dba58189dbbc,
0x3956c25bf348b538, 0x59f111f1b605d019,
0x923f82a4af194f9b, 0xab1c5ed5da6d8118,
0xd807aa98a3030242, 0x12835b0145706fbe,
0x243185be4ee4b28c, 0x550c7dc3d5ffb4e2,
0x72be5d74f27b896f, 0x80deb1fe3b1696b1,
0x9bdc06a725c71235, 0xc19bf174cf692694,
0xe49b69c19ef14ad2, 0xefbe4786384f25e3,
0x0fc19dc68b8cd5b5, 0x240ca1cc77ac9c65,
0x2de92c6f592b0275, 0x4a7484aa6ea6e483,
0x5cb0a9dcbd41fbd4, 0x76f988da831153b5,
0x983e5152ee66dfab, 0xa831c66d2db43210,
0xb00327c898fb213f, 0xbf597fc7beef0ee4,
0xc6e00bf33da88fc2, 0xd5a79147930aa725,
0x06ca6351e003826f, 0x142929670a0e6e70,
0x27b70a8546d22ffc, 0x2e1b21385c26c926,
0x4d2c6dfc5ac42aed, 0x53380d139d95b3df,
0x650a73548baf63de, 0x766a0abb3c77b2a8,
0x81c2c92e47edaee6, 0x92722c851482353b,
0xa2bfe8a14cf10364, 0xa81a664bbc423001,
0xc24b8b70d0f89791, 0xc76c51a30654be30,
0xd192e819d6ef5218, 0xd69906245565a910,
0xf40e35855771202a, 0x106aa07032bbd1b8,
0x19a4c116b8d2d0c8, 0x1e376c085141ab53,
0x2748774cdf8eeb99, 0x34b0bcb5e19b48a8,
0x391c0cb3c5c95a63, 0x4ed8aa4ae3418acb,
0x5b9cca4f7763e373, 0x682e6ff3d6b2b8a3,
0x748f82ee5defb2fc, 0x78a5636f43172f60,
0x84c87814a1f0ab72, 0x8cc702081a6439ec,
0x90befffa23631e28, 0xa4506cebde82bde9,
0xbef9a3f7b2c67915, 0xc67178f2e372532b,
0xca273eceea26619c, 0xd186b8c721c0c207,
0xeada7dd6cde0eb1e,
0xf57d4ff7fee6ed0d, # <-- patched constant
0x06f067aa72176fba, 0x0a637dc5a2c898a6,
0x113f9804bef90dae, 0x1b710b35131c471b,
0x28db77f523047d84, 0x32caab7b40c72493,
0x3c9ebe0a15c9bebc, 0x431d67c49c100d4c,
0x4cc5d4becb3e42b6, 0x597f299cfc657e2a,
0x5fcb6fab3ad6faec, 0x6c44198c4a475817,
]
def rotr(x, n):
return ((x >> n) | (x << (64 - n))) & MASK64
def Ch(x, y, z): return (x & y) ^ (~x & z)
def Maj(x, y, z): return (x & y) ^ (x & z) ^ (y & z)
def Sigma0(x): return rotr(x, 28) ^ rotr(x, 34) ^ rotr(x, 39)
def Sigma1(x): return rotr(x, 14) ^ rotr(x, 18) ^ rotr(x, 41)
def sigma0(x): return rotr(x, 1) ^ rotr(x, 8) ^ (x >> 7)
def sigma1(x): return rotr(x, 19) ^ rotr(x, 61) ^ (x >> 6)
def pad(msg: bytes) -> bytes:
l = len(msg) * 8
msg += b"\x80"
while (len(msg) % 128) != 112:
msg += b"\x00"
msg += l.to_bytes(16, "big")
return msg
def sha512(msg: bytes) -> bytes:
H = H0[:]
data = pad(msg)
for off in range(0, len(data), 128):
block = data[off:off+128]
W = [0]*80
for i in range(16):
W[i] = int.from_bytes(block[i*8:(i+1)*8], "big")
for i in range(16, 80):
W[i] = (sigma1(W[i-2]) + W[i-7] + sigma0(W[i-15]) + W[i-16]) & MASK64
a,b,c,d,e,f,g,h = H
for i in range(80):
T1 = (h + Sigma1(e) + Ch(e,f,g) + K[i] + W[i]) & MASK64
T2 = (Sigma0(a) + Maj(a,b,c)) & MASK64
h,g,f = g,f,e
e = (d + T1) & MASK64
d,c,b,a = c,b,a,(T1 + T2) & MASK64
H = [
(H[0] + a) & MASK64, (H[1] + b) & MASK64,
(H[2] + c) & MASK64, (H[3] + d) & MASK64,
(H[4] + e) & MASK64, (H[5] + f) & MASK64,
(H[6] + g) & MASK64, (H[7] + h) & MASK64,
]
return b"".join(x.to_bytes(8, "big") for x in H)
def hmac_sha512(key: bytes, msg: bytes) -> bytes:
bs = 128
if len(key) > bs:
key = sha512(key)
key = key.ljust(bs, b"\x00")
o_key = bytes(b ^ 0x5c for b in key)
i_key = bytes(b ^ 0x36 for b in key)
return sha512(o_key + sha512(i_key + msg))
def pbkdf2_hmac_sha512(password: bytes, salt: bytes, iterations: int, dklen: int) -> bytes:
if iterations <= 0:
raise ValueError("bad iterations")
hlen = 64
blocks = (dklen + hlen - 1) // hlen
out = bytearray()
for bi in range(1, blocks + 1):
u = hmac_sha512(password, salt + struct.pack(">I", bi))
t = bytearray(u)
for _ in range(1, iterations):
u = hmac_sha512(password, u)
for j in range(hlen):
t[j] ^= u[j]
out.extend(t)
return bytes(out[:dklen])
# ---------- KSA-like (RC4-ish but with +4 init) ----------
def ksa_like(key: bytes) -> bytearray:
S = bytearray(((i + 4) & 0xFF) for i in range(256))
j = 0
for i in range(256):
j = (j + S[i] + key[i % len(key)]) & 0xFF
S[i], S[j] = S[j], S[i]
return S
def main():
data = Path("flag.enc").read_bytes()
key1_enc = data[8:8+64]
salt = data[8+64:8+64+32]
enc_body = data[8+64+32:-16] # remove last 16B check
# derive key2
key_base = sha512(salt + b"Lilac+present")
key2 = pbkdf2_hmac_sha512(key_base, salt, iterations=10000, dklen=64)
# decrypt key1 using S-box from key2
s2 = ksa_like(key2)
key1 = bytes(key1_enc[i] ^ s2[i] for i in range(64))
# decrypt body using S-box from key1
s1 = ksa_like(key1)
body = bytes(enc_body[i] ^ s1[i & 0xFF] for i in range(len(enc_body)))
Path("out.jpg").write_bytes(body)
print("[+] wrote out.jpg (should be a JPEG)")
if __name__ == "__main__":
main()运行后得到 out.jpg,打开图片即可看到 flag:
Lilac{YOu_knOvv_h0w_tO_d3crypt_1t!!}
Crypto
MyBlock
服务端给你一个加密 oracle:输入 32-bit 明文(拆成 16-bit L0||R0),输出 32-bit 密文(L8||R8)。轮函数形如:
L_{i+1} = R_iR_{i+1} = L_i ⊕ F(R_i, k_i)
其中 k_i 是 8 个独立的 16-bit round key。F(x,k) 的实现是 GF(2^16) 上的三次映射:
[
F(x,k) = (x + k)^3
]
(这里 “+” 是域加法,即 XOR;乘法按题目指定的不可约多项式做约简。)
时间限制 512 秒,最多拿 675 对 (P,C)。暴力 2^128 不可能
Feistel 的好处是:你可以从两端往中间走。
难点在于:(x+k)^3 不是线性的,直接 MITM 需要存 2^64 级别的表也做不了。
这题真正的突破点是:3 次幂在 GF(2^16) 上代数增长慢,把若干轮的中间变量写成关于输入 (L0,R0) 的多项式时,项数不会爆炸。
于是可以把某个中间量 S(比如 3 轮后的 R3 或 L3)看成:
[
S(L0,R0) = \sum_{(a,b)\in \mathcal{B}} c_{a,b} \cdot L0^a \cdot R0^b
]
其中 basis 集合 B 的大小远小于“所有可能幂次组合”。
这意味着:对很多组明文 (L0,R0),你把每组对应的 L0^a R0^b 算出来,就能得到一个矩阵,其列空间/零空间会带来稳定的线性约束。
选择一个切分点:例如对第 t 轮 key 做恢复时:
- 明文端:走
f轮(不猜 key,只利用结构推导“中间量必须落在的多项式空间”) - 密文端:猜当前轮 key,反推
b轮,得到一批候选中间量
关键判定:
- 用明文端构建矩阵
M_fwd(每行是一组明文的 monomial 向量),求它的左零空间(kernel)QQ的每一行就是一个线性约束:对任何“合法中间量”,都应该满足q · vec = 0。 - 对某个 key 猜测,从密文端得到候选中间量
S_guess[i],构建M_bwd。 - 若 key 正确,则
Q * M_bwd应该“更接近零”,即秩会明显下降。 - key 错误时,
M_bwd像随机矩阵,Q*M_bwd基本满秩。
实践中不用追求“秩=0”,只要出现稳定的 rank drop(比如降 2 以上)就几乎可以锁定正确 key。
从末轮开始最顺:
- 猜
k7,把密文逆一轮,得到 7 轮状态 - 在这个状态上再猜
k6… - 每拿到一个 key,就把所有样本整体“退一轮”,下一轮继续
轮数分配经验法则:
fwd固定用 3 轮(约束够强且 basis 不至于爆)bwd用round_idx - 3- 当
round_idx < 3时,直接纯 peel(不用 rank 了,数据已经足够定死)
这题瓶颈不是网络,是:
- 每个 key 需要跑一次 rank check
- 每次 rank check 都要做若干次高斯消元
优化点:
- 只取少量样本行(经验:行数略大于列数就够了)
- 高斯消元用紧凑数据结构(Python 用
uint64分块;C++ 用__int128/uint64_tbitset) - 遇到 rank drop 直接 early stop
exp:
#!/usr/bin/env python3
from pwn import remote
import random
import struct
from typing import List, Tuple
POLY = 0x1002D # same irreducible poly as your notes
# ---------------- GF(2^16) ----------------
def gf_add(a: int, b: int) -> int:
return a ^ b
def gf_mul(a: int, b: int) -> int:
res = 0
for i in range(16):
if (b >> i) & 1:
res ^= (a << i)
# reduce
for i in range(30, 15, -1):
if (res >> i) & 1:
res ^= (POLY << (i - 16))
return res & 0xFFFF
def gf_pow(a: int, e: int) -> int:
r = 1
x = a
while e:
if e & 1:
r = gf_mul(r, x)
x = gf_mul(x, x)
e >>= 1
return r
def F(x: int, k: int) -> int:
t = gf_add(x, k)
return gf_mul(gf_mul(t, t), t) # t^3
# ---------------- Feistel primitives ----------------
def dec_one(L: int, R: int, k: int) -> Tuple[int,int]:
# inverse of:
# L' = R
# R' = L ^ (R + k)^3
L_in = R
R_in = gf_add(L, F(R, k))
return L_in, R_in
# ---------------- linear algebra (rank over GF(2^16)) ----------------
def inv_gf(a: int) -> int:
# inverse via Fermat: a^(2^16-2)
if a == 0:
raise ZeroDivisionError
return gf_pow(a, (1 << 16) - 2)
def rank_gf(mat: List[List[int]]) -> int:
# classic Gauss elimination
m = [row[:] for row in mat]
nrow = len(m)
ncol = len(m[0]) if nrow else 0
r = 0
for c in range(ncol):
piv = None
for i in range(r, nrow):
if m[i][c] != 0:
piv = i
break
if piv is None:
continue
m[r], m[piv] = m[piv], m[r]
invp = inv_gf(m[r][c])
for j in range(c, ncol):
m[r][j] = gf_mul(m[r][j], invp)
for i in range(nrow):
if i != r and m[i][c] != 0:
factor = m[i][c]
for j in range(c, ncol):
m[i][j] = gf_add(m[i][j], gf_mul(factor, m[r][j]))
r += 1
if r == nrow:
break
return r
def left_kernel_basis(A: List[List[int]]) -> List[List[int]]:
"""
Return a basis Q s.t. Q*A = 0.
Standard trick: row-reduce A^T to find nullspace, but we keep it simple.
"""
# Build augmented [A | I], row-reduce A, track operations on I
M = [row[:] for row in A]
n = len(M) # rows
m = len(M[0]) # cols
I = [[0]*n for _ in range(n)]
for i in range(n):
I[i][i] = 1
r = 0
pivcol = [-1]*n
for c in range(m):
piv = None
for i in range(r, n):
if M[i][c] != 0:
piv = i
break
if piv is None:
continue
M[r], M[piv] = M[piv], M[r]
I[r], I[piv] = I[piv], I[r]
invp = inv_gf(M[r][c])
for j in range(c, m):
M[r][j] = gf_mul(M[r][j], invp)
for j in range(n):
I[r][j] = gf_mul(I[r][j], invp)
for i in range(n):
if i != r and M[i][c] != 0:
f = M[i][c]
for j in range(c, m):
M[i][j] = gf_add(M[i][j], gf_mul(f, M[r][j]))
for j in range(n):
I[i][j] = gf_add(I[i][j], gf_mul(f, I[r][j]))
pivcol[r] = c
r += 1
if r == n:
break
# rows r..n-1 of I are left-kernel vectors (because those rows correspond to zero rows in M)
return I[r:]
# ---------------- basis generator (shape-only) ----------------
def basis_shape(fwd_rounds: int, bwd_rounds: int, target_right: bool):
"""
Generate exponent pairs (a,b) describing monomials L^a R^b that can appear.
This mirrors your idea but rewritten.
"""
def step_feistel(Lset, Rset):
# Feistel update with cubic on (side + const)
# track degrees as exponent pairs
base = set(Rset)
base.add((0,0)) # +K
T = set()
for e1 in base:
for e2 in base:
for e3 in base:
T.add((e1[0]+e2[0]+e3[0], e1[1]+e2[1]+e3[1]))
newR = set(Lset)
newL = set(Rset) | T
return newL, newR
L = {(1,0)}
R = {(0,1)}
for _ in range(fwd_rounds):
L, R = step_feistel(L, R)
fwd = R if target_right else L
# backward side (symmetric, just swapped roles)
Lb = {(1,0)}
Rb = {(0,1)}
for _ in range(bwd_rounds):
Lb, Rb = step_feistel(Lb, Rb)
bwd = Rb if target_right else Lb
return sorted(fwd), sorted(bwd)
def eval_monomials(L0: int, R0: int, exps: List[Tuple[int,int]]) -> List[int]:
# precompute powers up to max exp
md = 0
for a,b in exps:
md = max(md, a, b)
pL = [0]*(md+1)
pR = [0]*(md+1)
pL[0] = 1; pR[0] = 1
if md >= 1:
pL[1] = L0; pR[1] = R0
for i in range(2, md+1):
pL[i] = gf_mul(pL[i-1], L0)
pR[i] = gf_mul(pR[i-1], R0)
return [gf_mul(pL[a], pR[b]) for a,b in exps]
# ---------------- attack core ----------------
def recover_one_round(idx_from_end: int,
pts: List[Tuple[int,int]],
cts: List[Tuple[int,int]]) -> int:
"""
idx_from_end: 7..0 (recover k7 first)
"""
# choose split
if idx_from_end >= 3:
fwd = 3
bwd = idx_from_end - 3
else:
fwd = idx_from_end
bwd = 0
target_right = (bwd == 0) # same heuristic but renamed
fwd_basis, bwd_basis = basis_shape(fwd, bwd, target_right)
# pick only enough rows
need = len(fwd_basis) + len(bwd_basis) + 8
use = pts[:min(len(pts), need)]
use_ct = cts[:len(use)]
# build forward embedding matrix
Mf = []
for (L0,R0) in use:
Mf.append(eval_monomials(L0, R0, fwd_basis))
Q = left_kernel_basis(Mf) # constraints
# brute-force this 16-bit key, rank-filter
best = (10**9, None)
for k in range(0x10000):
# peel one round with guessed key
peeled = []
for (L8,R8) in use_ct:
Lp, Rp = dec_one(L8, R8, k)
peeled.append((Lp,Rp))
# map peeled state into bwd monomials
Mb = []
for (Lm,Rm) in peeled:
Mb.append(eval_monomials(Lm, Rm, bwd_basis) if bwd_basis else [Lm if target_right else Rm])
# check rank of Q*Mb (Q rows) x (Mb cols)
# build product matrix explicitly (small sizes)
# Mat[q][c] = sum_r Q[q][r]*Mb[r][c]
qn = len(Q)
rn = len(Mb)
cn = len(Mb[0])
Prod = [[0]*cn for _ in range(qn)]
for qi in range(qn):
for ri in range(rn):
if Q[qi][ri] != 0:
for ci in range(cn):
Prod[qi][ci] = gf_add(Prod[qi][ci], gf_mul(Q[qi][ri], Mb[ri][ci]))
rk = rank_gf(Prod)
if rk < best[0]:
best = (rk, k)
# early accept: rank drops noticeably
if rk <= max(0, cn - 2):
break
return best[1]
def peel_all_pairs(cts: List[Tuple[int,int]], k: int) -> List[Tuple[int,int]]:
out = []
for (L,R) in cts:
out.append(dec_one(L,R,k))
return out
# ---------------- I/O with server ----------------
def collect_pairs(host: str, port: int, q: int) -> Tuple[List[Tuple[int,int]], List[Tuple[int,int]]]:
io = remote(host, port)
io.recvuntil(b'> ')
io.sendline(str(q).encode())
pts = eval(io.recvline().decode().strip())
cts = eval(io.recvline().decode().strip())
io.close()
# normalize to 16-bit halves if given as 32-bit ints
def norm(x):
if isinstance(x, int):
return (x >> 16) & 0xFFFF, x & 0xFFFF
return x
pts = [norm(p) for p in pts]
cts = [norm(c) for c in cts]
return pts, cts
def main():
HOST, PORT = "101.245.97.249", 8088
Q = 600
pts, cts = collect_pairs(HOST, PORT, Q)
keys = [0]*8
cur_cts = cts[:]
# recover from last to first
for r in range(7, -1, -1):
k = recover_one_round(r, pts, cur_cts)
keys[r] = k
cur_cts = peel_all_pairs(cur_cts, k)
print(f"[+] round {r} key = {k:04x}")
final = ''.join(f"{k:04x}" for k in keys)
print("[+] key =", final)
# submit
io = remote(HOST, PORT)
io.recvuntil(b'> ')
io.sendline(str(Q).encode())
io.recvline(); io.recvline() # discard pairs
io.sendline(final.encode())
print(io.recvall(timeout=2).decode(errors="ignore"))
if __name__ == "__main__":
main()Noisy Forest
程序做的事情可以抽象成:
- 先
huge = random.getrandbits(50000) - 把
huge切成 32-bit 块,再把每块格式化成032b这样的 bit 串拼起来,得到一个full_bit_stream - 遍历明文
input_str:
- 只有当明文字元是“中文”(题目自定义范围)时,才消耗 1 个 bit
- bit=0:字符不变
- bit=1:字符码点
+9997 - 非中文:原样输出,不消耗 bit
关键:bit 的消耗位置取决于“明文是否中文”,而不是密文。
你最开始的做法是“每个位置候选两种:原字 or 减9997”,然后用 GB2312 当启发式剪枝再爆破 SHA256 前缀。
这一步能提高可读性,但它并不可靠:
- 剪枝会错(常用字/生僻字不总是正确标准)
- 少量位置仍然分叉 → 组合数爆炸
- 更致命的是:你后面要做 MT19937 状态恢复,明文哪怕错几个中文位,恢复出来的 bit 就错 → 状态克隆直接崩
所以这题正确姿势通常是:用少量“可信已知明文”去恢复 MT19937 → 预测后续 bit → 全文直接还原 → 再算 SHA256。
Python random 是 MT19937。内部状态是 624 个 32-bit。
只要我们拿到连续 624 个 getrandbits(32) 的输出(注意是 tempered 输出),就能 untemper 还原状态。
而题目刚好把 getrandbits(50000) 生成的巨整数按 32bit 切块再输出成 bit 流,等价于:
- 只要能从“部分已知明文段”里恢复出足够多的 bit(至少 19968 个中文位),就能拼出前 624 个 32-bit 输出块,从而克隆 RNG 状态。
- 之后就能预测剩余 bit,解出全文。
cnt = 0
for char in c:
if char not in ',。':
if int(full_bit_stream[cnt]):
m += chr(ord(char)-9997)
else:
m += char
cnt += 1这逻辑等价于:除了逗号句号之外的所有字符都消耗 bit。
但题目是:只有“中文字符”才消耗 bit。
所以会整体错位,从某一处开始全盘乱码,hash 当然就错。
exp
#!/usr/bin/env python3
import hashlib
import random
STEP = 9997
TOTAL_BITS = 50000
NEED_WORDS = 624
NEED_BITS = NEED_WORDS * 32
def is_chinese(ch: str) -> bool:
# 用题目给的“中文范围”口径
return '一' <= ch <= '龥'
# ---------------- MT19937 untemper / state recover ----------------
MASK32 = 0xFFFFFFFF
def unshift_right_xor(y, shift):
x = 0
# 从高位往低位恢复
for i in range(0, 32, shift):
part = y ^ (x >> shift)
x = part
return x & MASK32
def unshift_left_xor_and(y, shift, mask):
x = 0
# 从低位往高位恢复
for i in range(0, 32, shift):
part = y ^ ((x << shift) & mask)
x = part
return x & MASK32
def untemper(y):
y = unshift_right_xor(y, 18)
y = unshift_left_xor_and(y, 15, 0xefc60000)
y = unshift_left_xor_and(y, 7, 0x9d2c5680)
y = unshift_right_xor(y, 11)
return y & MASK32
def recover_state_from_32bit_outputs(outputs):
if len(outputs) < NEED_WORDS:
raise ValueError(f"need {NEED_WORDS} outputs, got {len(outputs)}")
st = [untemper(v) for v in outputs[:NEED_WORDS]]
# Python random state format: (version, (624 ints + index), gaussian_cache)
return (3, tuple(st + [624]), None)
# ---------------- main solve ----------------
def load_text(fn):
with open(fn, "r", encoding="utf-8") as f:
return f.read()
def extract_bits_from_known(ciphertext: str, known_plain: str) -> str:
"""
从已知明文段提取 bit:只在明文是中文时消耗 bit。
返回一个 0/1 串(长度=已知明文里中文字符数量)。
"""
bits = []
for i, (p, c) in enumerate(zip(known_plain, ciphertext)):
if is_chinese(p):
diff = ord(c) - ord(p)
if diff == 0:
bits.append('0')
elif diff == STEP:
bits.append('1')
else:
context_c = ciphertext[max(0,i-20):i+1]
context_p = known_plain[max(0,i-20):i+1]
raise ValueError(
f"Mismatch at idx={i}, diff={diff}\n"
f"cipher_ctx={context_c}\n"
f"plain_ctx ={context_p}\n"
f"cipher_char={c} plain_char={p}"
)
return "".join(bits)
def bits_to_words_msb_first(bitstr: str):
"""
题目拼 bit 流时是 format(val,'032b') 这种写法(MSB->LSB),
所以这里每 32 位直接 int(chunk,2) 就是当次 getrandbits(32) 的输出。
"""
out = []
for i in range(0, len(bitstr), 32):
chunk = bitstr[i:i+32]
if len(chunk) < 32:
break
out.append(int(chunk, 2))
return out
def rebuild_full_bit_stream(rng: random.Random, prefix_bits: str) -> str:
"""
已有前 NEED_BITS 位(对应前 624 个 32-bit 输出),接下来用克隆后的 RNG 继续生成补齐 TOTAL_BITS。
"""
num_chunks = (TOTAL_BITS + 31) // 32
remain_chunks = num_chunks - NEED_WORDS
tail = "".join(f"{rng.getrandbits(32):032b}" for _ in range(remain_chunks))
full = prefix_bits[:NEED_BITS] + tail
return full[:TOTAL_BITS]
def decrypt(ciphertext: str, bit_stream: str) -> str:
"""
严格复刻题目逻辑:
- 遍历“明文位”,即:只有当该位置明文是中文时才消耗 bit
但解密时明文未知,所以用“密文能否合法还原中文”来决定是否属于中文位:
* 若 chr(ord(c)-9997) 是中文,则它必然来自中文位且 bit=1 时成立
* 否则如果 c 自身是中文,也应当视为中文位(bit=0)
实战里题目文本几乎全中文+标点,因此这个判定足够稳定。
"""
res = []
bi = 0
for ch in ciphertext:
# 先尝试“这是被+9997过的中文”
back = chr(ord(ch) - STEP) if ord(ch) >= STEP else None
if back is not None and is_chinese(back):
# 这是一个中文位(一定消耗bit)
b = int(bit_stream[bi]); bi += 1
if b == 1:
res.append(back)
else:
# bit=0 时,本应不加密,说明该位密文本身就是明文
res.append(ch)
continue
if is_chinese(ch):
# 中文位但没发生 +9997(或者 +9997后不落回中文范围)
b = int(bit_stream[bi]); bi += 1
if b == 1:
# bit=1 但 back 不合法:一般说明“你的 is_chinese 口径/文本对齐有问题”
# 这里保守:仍然做 -9997,方便肉眼发现异常
res.append(chr(ord(ch) - STEP))
else:
res.append(ch)
continue
# 非中文位:不消耗 bit,原样
res.append(ch)
return "".join(res)
def main():
ciphertext = load_text("ciphertext.txt")
known_plain = load_text("ans.txt")
bitstr = extract_bits_from_known(ciphertext, known_plain)
print(f"[+] recovered chinese-bits = {len(bitstr)}")
if len(bitstr) < NEED_BITS:
raise SystemExit(f"[-] not enough bits: need {NEED_BITS}, got {len(bitstr)}. Extend/fix ans.txt.")
words = bits_to_words_msb_first(bitstr[:NEED_BITS])
if len(words) < NEED_WORDS:
raise SystemExit("[-] failed to rebuild enough 32-bit outputs.")
state = recover_state_from_32bit_outputs(words)
rng = random.Random()
rng.setstate(state)
full_bits = rebuild_full_bit_stream(rng, bitstr[:NEED_BITS])
plain = decrypt(ciphertext, full_bits)
h = hashlib.sha256(plain.encode("utf-8")).hexdigest()
print("[+] sha256 =", h)
print("LilacCTF{" + h + "}")
if __name__ == "__main__":
main()最终 hash 是:
df0f01281bfe925e72872c113bf0e32cc64b6033754cd5eff1所以 flag 是:
LilacCTF{df0f01281bfe925e72872c113bf0e32cc64b6033754cd5eff1}涵盖zlib解压、GitHub邮件提权、OSINT航班识别、LLM logits逆向、Twofish/ChaCha8逆向、iOS模式锁破解等多方向实战解题思路。
由 AI 根据全文自动生成,仅供参考,以原文为准
