HackThisSite - Programming Mission 5

Posted on Edited on In Views: Disqus:

Challenge

Level 5 — Fix a corrupted file

有人用 Windows 命令行 ftp 客户端下载了一个 bz2 压缩的 PNG，PNG 里有一个重要密码；他漏考虑了一件事，文件因此损坏。下载 corrupted.png.bz2，把它修好并提交里面的密码。限时 600 秒。

Get this file HERE, reconstruct it and send the password as answer.

状态：verified（服务端返回 Good Job, ***, You have successfully completed this mission）。

Solution

  • 实例页 https://www.hackthissite.org/missions/prog/5/，文件链接是 /missions/prog/5/corrupted.png.bz2。链接必须补尾斜杠（/corrupted.png.bz2/）才是真实资源，少一个斜杠会 301 到一个空 body（下载到 0 字节）。
  • 文件每个实例都不一样（两次抓到的分别是 13075 / 13961 / 15232 字节，内容与密码都不同），所以必须取文件 → 修复 → 读密码 → 提交在一次 600 秒窗口内完成。
  • file 报 bzip2 compressed data，但 bzip2 -t 失败 → 这就是题面说的损坏。
1
2
3
4
5
6
$ curl -sL -b '<mission-cookie>' 'https://www.hackthissite.org/missions/prog/5/corrupted.png.bz2/' -o corrupted.png.bz2
$ ls -l corrupted.png.bz2 && file corrupted.png.bz2
13075 corrupted.png.bz2
corrupted.png.bz2: bzip2 compressed data, block size = 900k
$ bzip2 -t corrupted.png.bz2
bzip2: corrupted.png.bz2: data integrity (CRC) error in data

题面提示用 Windows ftp 客户端下载、漏考虑了一件事，指的就是没有切到 binary 模式：ASCII 模式会把流里的每个 0x0A 换成 0x0D 0x0A。压缩数据是近乎随机的字节流，被这样插字节之后，整个 bz2 位流就错位了。

证据就在字节统计里：

1
2
$ python3 -c "d=open('corrupted.png.bz2','rb').read(); print(len(d), d.count(b'\r'), d.count(b'\n'), d.count(b'\r\n'))"
13075 115 57 55
  • \r 比 \n 多了 58 个 → 就是被插入的 CR；
  • 文件里 \r\r\n 出现 0 次 → 说明原本就是 \r\n 的位置没有被二次膨胀，插入只发生在原来的 0x0A 前；
  • 另外还有 2 处 \n\r（例如 ... 0d 0a 0d ...），说明原始位流里确实有少量天然的 \r\n 相邻（转换后转换结果呈现为 CRLF，但其中的 CR 是原始数据）。

所以修复不是简单 dos2unix：要决定哪些 CRLF 里的 CR 是插入的、哪些是原始数据。只删掉一部分、猜错一个位置，解出来的即为无意义的垃圾数据。

观测到的 CRLF 对很少（50-60 个），而天然 CRLF 通常只有 0-2 个。于是直接枚举保留子集，用解压结果是否以 PNG 魔数开头来判定：

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
import bz2
import itertools

PNG_MAGIC = b"\x89PNG\r\n\x1a\n"

def crlf_positions(data):
    """每个 0x0D 0x0A 对的起始下标。"""
    return [i for i in range(len(data) - 1)
            if data[i] == 0x0D and data[i + 1] == 0x0A]

def rebuild(data, keep, positions):
    """删掉每一个 CRLF 对里的 CR，但 keep 里的下标保留 CR（=原始数据）。

    注意不能用 data.replace(b'\\r\\n', b'\\n')：相邻的 CRLF 会互相影响，
    必须逐对扫描。
    """
    keep = set(keep)
    out, i, j = bytearray(), 0, 0
    while i < len(data):
        if i + 1 < len(data) and data[i] == 0x0D and data[i + 1] == 0x0A:
            if j in keep:
                out.append(data[i])
            out.append(data[i + 1])
            i += 2
            j += 1
        else:
            out.append(data[i])
            i += 1
    return bytes(out)

def repair(data, max_keep=3):
    pos = crlf_positions(data)
    for k in range(max_keep + 1):
        for combo in itertools.combinations(range(len(pos)), k):
            try:
                plain = bz2.decompress(rebuild(data, combo, pos))
            except Exception:
                continue
            if plain[:8] == PNG_MAGIC:
                return rebuild(data, combo, pos), plain, [pos[i] for i in combo]
    raise SystemExit("could not repair the archive")

真实的一次运行：

1
2
3
4
5
[1] downloaded 15232 bytes
[2] 15232 bytes, 58 CRLF pair(s); searching for the genuine ones
[3] keep=2 tried=1398 -> decompressed 17109 bytes, PNG signature ok
    genuine CRLF byte offsets: [9429, 14250]
[4] PNG verified: 1750x115, chunks ['IHDR', 'bKGD', 'pHYs', 'vpAg', 'IDAT', 'IEND'], all CRCs ok

k=0（全删）和 k=1 都不行，k=2 在枚举到第 1398 个组合时命中（即这次的两个 CR 属于原始数据）。恢复出的 PNG 还能过 chunk CRC 校验，说明重建完全正确。

PNG 是 1750×115 的横条，密码用粗体无衬线字体画在浅色背景上。读取分两步：按列切分字形（同一行文字，字符之间有空列；这里不能把 1 像素的小缝隙合并，否则两个字符会粘成一个、10 个字符读成 9 个，后面全错位），再逐字形分类。

分类用参考字体渲染 + 高度类约束 + 位图 IoU，关键是把相对基线的高度归一化到 x-height 再比较（否则数字/升部字母与 x-height 字母完全比不上）：

1
2
3
4
5
6
7
8
9
10
def classify(glyph_bitmap, refs, top, bot, xh):
    """refs[ch] = (参考位图, 升部相对基线, 底部相对基线, 宽度/x-height)"""
    tn, bn = top / xh, bot / xh
    ranked = []
    for ch, (rbm, t, b, wr) in refs.items():
        if abs(t - tn) > 0.45 or abs(b - bn) > 0.45:      # 高度类必须一致
            continue
        ranked.append((iou(glyph_bitmap, rbm), ch))
    ranked.sort(reverse=True)
    return ranked[0][1] if ranked else "?"

低于基线、只有几个像素高的横条直接判成下划线（之前的尝试把它当成 m/w，因为字母表里没有 _）。

自动读出的结果另用字形位图人工复核一次：把每个字形打成 ASCII 点阵（# = 有墨），数字与字母的形状即可辨识：

1
2
3
4
5
6
7
8
9
10
11
for i, (s, e) in enumerate(segments(mask), 1):
    ink = mask[:, s:e + 1]
    ys = np.where(ink.any(axis=1))[0]
    ink = ink[ys.min():ys.max() + 1]
    h, w = ink.shape
    rows, cols = min(18, h), max(4, int(round(w * 18 / h * 0.5)))
    arr = np.array(Image.fromarray((ink * 255).astype("uint8"))
                   .resize((cols, rows), Image.LANCZOS)) > 110
    print(f"--- glyph {i} (w={w}, h={h})")
    for r in arr:
        print("   " + "".join("#" if v else "." for v in r))

一次真实的字形点阵（8）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
..##..
.####.
.#..#.
##..##
##..##
##..##
##..##
.####.
.####.
.#..#.
##..##
#....#
#....#
#....#
##..##
##..##
.####.
..##..

十个字形依次读出 8 j q 9 s l 1 p 8 h（j、q、p 的降部都落在基线以下，与点阵里的长度一致），提交后服务端接受：

1
2
[6] submitted '8jq9sl1p8h' -> accepted=True
server: ... Good Job, ***, You have successfully completed this mission

注意：密码是每个实例一次生成的（同一账号换一次页面就是另一串），所以 spoiler 里给的是本次被接受的实例值；重做时按上面流程现算现交即可。

  • 不能用 replace(b'\r\n', b'\n')：相邻 CRLF 会互相影响，必须逐对扫描决定保留哪一个 CR。
  • 修复判据要用内容而不是解压不报错：删错 CR 的版本依然能解出 15000-20000 字节数据（bz2 的 Huffman 解码会成功），只有 PNG 魔数能证明修对了。

Vulnerabilities

这道题的损坏是经典的真实世界传输事故：文本模式的 FTP 会把二进制文件当文本处理，静默插入 0x0D。防御上：二进制传输永远走 binary 模式（ftp 里 bin，或直接 scp/curl），下载后校验哈希/魔数；对压缩包这类强结构数据，还应当用内容特征（魔数、CRC）而不是命令退出码来判断完整性。本例中解压器在数据已损坏时仍会输出字节流，只看退出码会误判。另外，密码以明文绘制在图片里再压缩交付，本身就是把答案交给客户端的做法。

8jq9sl1p8h（本次实例；密码每实例随机）