HackThisSite - Programming Mission 3

posted
read
921 words · 3 min
tags
#ctf#hackthissite#writeup#programming#encryption#reverse-engineering
contents

Challenge

This level is about reversing an encryption algorithm.

关卡给出 PHP 加密函数 encryptString 的源码，以及一段空格分隔的整数密文；要把密文还原成明文 serial 文件，提交最后一个 serial。限时 120 秒。

每次访问实例页，服务端都会换一组随机的 password 和明文，所以取密文、解密、提交必须放在同一次运行里。

Solution

Step 1: 加密链

关卡页面的 PHP 源码是这样的两个函数：

function evalCrossTotal($strMD5) {
    $intTotal = 0;
    $arrMD5Chars = str_split($strMD5, 1);
    foreach ($arrMD5Chars as $value)
        $intTotal += '0x0' . $value;          // 十六进制数字串，取值 0..15
    return $intTotal;
}


function encryptString($strString, $strPassword) {
    $strPasswordMD5 = md5($strPassword);
    $intMD5Total = evalCrossTotal($strPasswordMD5);
    $arrEncryptedValues = array();
    $intStrlen = strlen($strString);
    for ($i = 0; $i < $intStrlen; $i++) {
        $arrEncryptedValues[] = ord(substr($strString, $i, 1))
                              + ('0x0' . substr($strPasswordMD5, $i % 32, 1))
                              - $intMD5Total;
        $intMD5Total = evalCrossTotal(substr(md5(substr($strString, 0, $i + 1)), 0, 16)
                                    . substr(md5($intMD5Total), 0, 16));
    }
    return implode(' ', $arrEncryptedValues);
}

逐字节写成公式：

total_0      = evalCrossTotal(md5(password))    # md5(pw) 的 32 个十六进制位之和
enc[i]       = ord(plain[i]) + hexval(md5(pw)[i % 32]) - total_i
total_{i+1}  = evalCrossTotal(md5(plain[:i+1])[:16] + md5(str(total_i))[:16])

两个 PHP 语义细节决定了模型是否对得上：

  • '0x0'.$c（$c 是 hex 字符）在 PHP 5 里是带 0x 前缀的数字串，按十六进制解释，所以 evalCrossTotal 就是把每个字符当 hex 位加起来，取值范围 0..15。
  • md5($int) 会把整数按十进制字符串化再取摘要，也就是代码里的 md5(str(total_i))。

关键在于 total 的演进方向：第 i+1i+1 步的 total 由 明文前 i+1 个字符的 md5 和 当前 total 的十进制 MD5 拼出来，也就是只依赖已经解出的前缀。这是一个逐字节向前推进的链，第 ii 个字节的减法里用到的 totali\mathrm{total}_{i} 是前面所有字节共同算出来的。同时 md5(pw)[i % 32] 说明密码哈希的 32 个 nibble 每 32 列循环使用一次。这条链意味着逐列独立求解不成立：单个字节的 totali\mathrm{total}_{i} 由全部已解前缀共同决定，搜索只能按链状态整体推进。

Step 2: 搜索约束

password 本身不需要知道，它只通过 md5(password) 进入公式。真正的未知量是 32 个 nibble h[0..31]，以及初始值 total0=sum⁡(h)\mathrm{total}_{0} = \operatorname{sum}(h)。可以从两个层面把搜索压住：

  • 逐位置枚举局部候选：第 i 个字符满足 ord⁡(plain[i])=enc[i]−h[i mod 32]+totali\operatorname{ord}(\mathrm{plain}[i]) = \mathrm{enc}[i] - h[i \bmod 32] + \mathrm{total}_{i}。h 只有 16 种取值；一旦某个 r=i mod 32r = i \bmod 32 被解出来，后面每一轮循环到同一个 r 时都复用它，不再重新枚举。
  • serial 格式提供硬约束：官方示例 serials_example.txt 显示明文是固定宽度的 serial 行，形如 XXX-XXX-OEM-XXX-1.1，每行以 UNIX 换行结尾（示例文件里那句 Don't forget the UNIX-style line breaks. 指的就是这个）；末尾的 \n 同样参与加密，模板宽度是 serial 长度加 1（这里 20 列），不是排版噪声。逐列统计示例文件后发现，20 列里有 11 列是恒定字符（两个 -、OEM、尾部 1.1、换行），这些列的候选集被压到唯一字符；其余列限定在 [A-Z0-9]。这样绝大多数位置上 16 个候选里只有 1 个能活下来。
  • 全局约束收口：total0 是 32 个 nibble 之和，上界只有 32×15=48032 \times 15 = 480，直接枚举 0..480；搜索到最后要求 h 已经集齐 32 个 nibble 且 sum⁡(h)=total0\operatorname{sum}(h) = \mathrm{total}_{0}。错误的 total0 会在前几十个字符内因为候选集与模板冲突而全灭，只有正确的那个能走到第 100 个字符。实测单次搜索 1.7–5.6 秒。

Script

下面是自包含的解密脚本，只读密文文件和示例 serial 文件，不联网：

#!/usr/bin/env python3
"""HackThisSite Programming Mission 3 -- 只靠密文还原明文 serial 文件。


关卡页面给出的 PHP 加密链（等价形式）：


    total_0     = evalCrossTotal(md5(password))          # md5 的 32 个 nibble 之和
    enc[i]      = ord(plain[i]) + hexval(md5(pw)[i % 32]) - total_i
    total_{i+1} = evalCrossTotal(md5(plain[:i+1])[:16] + md5(str(total_i))[:16])


password 未知，真正的未知量是 h[0..31] = md5(password) 的 32 个 nibble，
以及 total0 = sum(h)。serial 模板把每列候选压到 1 个或 36 个字符，
枚举 total0(0..480) 做前向搜索即可恢复明文。


用法：python decrypt.py [ciphertext.txt]
"""


import hashlib
import os
import re
import sys
87 collapsed lines


ALNUM = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
HERE = os.path.dirname(os.path.abspath(__file__))


def md5(s):
    return hashlib.md5(s.encode("ascii")).hexdigest()


def hexval(c):
    return int(c, 16)


def eval_cross_total(s):
    """PHP evalCrossTotal：'0x0' 前缀让每个字符按十六进制解释，取值 0..15。"""
    return sum(hexval(c) for c in s)


def encrypt_hash(plain, pwd_md5):
    """给定 md5(password) 的十六进制字符串，复刻 encryptString。"""
    total = eval_cross_total(pwd_md5)
    out = []
    for i, ch in enumerate(plain):
        out.append(ord(ch) + hexval(pwd_md5[i % 32]) - total)
        total = eval_cross_total(md5(plain[: i + 1])[:16] + md5(str(total))[:16])
    return out


def build_template(example_text):
    """从官方示例 serial 推每列允许的 ord 集合，返回 (template, width)。"""
    lines = [ln for ln in example_text.splitlines()
             if ln and not ln.startswith("(")]
    width = len(lines[0]) + 1
    tpl = []
    for pos in range(width - 1):
        seen = {ln[pos] for ln in lines}
        tpl.append({ord(seen.pop())} if len(seen) == 1
                   else {ord(c) for c in ALNUM})
    tpl.append({ord("\n")})              # 每行以 UNIX 换行结束
    return tpl, width


def recover(enc, template, width, max_states=2_000_000):
    """返回所有与密文、模板一致的明文。state = (total, h_tuple, prefix)。"""
    solutions = []
    for total0 in range(0, 32 * 15 + 1):          # sum(32 个 nibble) 的上界 480
        states = [(total0, (), "")]
        dead = False
        for i in range(len(enc)):
            r = i % 32
            allow = template[i % width]
            nxt = []
            for total, h, pre in states:
                cands = (h[r],) if r < len(h) else range(16)
                for hv in cands:
                    o = enc[i] - hv + total         # ord = enc - h + total
                    if o not in allow:
                        continue
                    ch = chr(o)
                    h2 = h + (hv,) if r >= len(h) else h
                    nxt.append((eval_cross_total(
                        md5(pre + ch)[:16] + md5(str(total))[:16]), h2, pre + ch))
            if not nxt or len(nxt) > max_states:
                dead = True
                break
            states = nxt
        if dead:
            continue
        for total, h, plain in states:
            if len(h) == 32 and sum(h) == total0:
                solutions.append((plain, h, total0))
    return solutions


def load_template():
    for path in (os.path.join(HERE, "serials_example.txt"), "/tmp/serials_example.txt"):
        if os.path.exists(path):
            with open(path, encoding="utf-8") as fh:
                return build_template(fh.read())
    raise SystemExit("serials_example.txt not found")


def main():
    path = sys.argv[1] if len(sys.argv) > 1 else os.path.join(HERE, "ciphertext.txt")
    with open(path, encoding="utf-8") as fh:
        enc = [int(x) for x in re.findall(r"-?\d+", fh.read())]
    template, width = load_template()
    print("ciphertext: %d values" % len(enc))
    sols = recover(enc, template, width)
    if not sols:
        raise SystemExit("no plaintext found")
    for plain, h, total0 in sols:
        pwd_hash = "".join(format(x, "x") for x in h)
        assert encrypt_hash(plain, pwd_hash) == enc, "re-encryption mismatch"
        serials = [ln for ln in plain.splitlines() if ln]
        print("total0=%d  md5(password)=%s  serials=%d"
              % (total0, pwd_hash, len(serials)))
        for ln in serials:
            print(ln)
        print("last serial: %s" % serials[-1])


if __name__ == "__main__":
    main()

脚本里最后那行 assert encrypt_hash(plain, pwd_hash) == enc 是自校验：把恢复出的明文用恢复出的 md5(password) 再加密一遍，必须和原始密文逐字节相等才算通过。搜索模型本身也用一次回环自测验证过（加密一段已知明文后不告诉求解器 total0，让它盲解）：

case=serials-15  len=300 enc[0:4]=[-182, -207, -172, -229] -> 1 solution(s), exact=True
               recovered total0=241  hash==md5(pwd): True
               re-encrypt matches ciphertext: True
case=serials-5   len=100 enc[0:4]=[-174, -177, -158, -213] -> 1 solution(s), exact=True
               recovered total0=231  hash==md5(pwd): True
               re-encrypt matches ciphertext: True
case=serials-2   len= 40 enc[0:4]=[-154, -240, -175, -233] -> 1 solution(s), exact=True
               recovered total0=220  hash==md5(pwd): True
               re-encrypt matches ciphertext: True

三个长度（整份 15 行、5 行、2 行）都只解出唯一解，且恢复出的哈希与加密时用的密码哈希一致。

Verify

服务端接受的那次实例的输出（密文与求解器在同一目录）：

Terminal window
$ cd /tmp/wu3          # ciphertext.txt + serials_example.txt + decrypt_wu.py
$ python decrypt_wu.py ciphertext.txt
ciphertext: 100 values
total0=215  md5(password)=82aab273c5920649ac0d8b947a00875b  serials=5
T7F-EJS-OEM-XBO-1.1
2GT-IE2-OEM-T4Y-1.1
M0R-76P-OEM-H47-1.1
20L-W3T-OEM-CIC-1.1
5FO-TI5-OEM-N1J-1.1
last serial: 5FO-TI5-OEM-N1J-1.1