HackThisSite - Application Mission 17

Posted on Edited on In Views: Disqus:

Challenge

Keygen challenge. The program generates a license key based on the username. Reverse engineer the key generation algorithm and write a keygen that produces valid keys for any username.

密钥生成器 (keygen) 挑战。程序根据用户名生成 license key，需要逆向分析 key 生成算法，编写一个可以为任意用户名生成正确 key 的 keygen 程序。

HTS 附带的压缩包里同时有 Windows 版 (app17win.exe) 和 UNIX 版 (app17unix.tar.gz)。UNIX 版是 未 strip 的 ELF，符号表里直接留着 enc_and_check / main 的名字，用它反汇编最省事，而且可以直接跑起来做验证。

Solution

  • file 报 ELF 64-bit LSB PIE、x86-64，not stripped。
  • nm 直接给出两个关键符号：_Z13enc_and_checkPcS_（enc_and_check(char*, char*)，就是校验函数）和 main。
  • 程序运行后提示 Username: 和 Password:，把用户名的 key 填进 Password 就会打印 Congratulations! Enter that password on HackThisSite.，也就是说校验完全在本地完成，不需要连服务器就能确认 key 的正确性。
1
2
3
$ nm unix/app17unix | grep -E 'enc_and|main'
0000000000001919 T main
000000000000148f T _Z13enc_and_checkPcS_

Step 1: 从符号找校验函数

enc_and_check(rdi=username, rsi=key) 里第一个分支就限定了 key 的长度：strlen(key) <= 3 直接返回 1（失败）。接下来把 key 的前 4 个字节与一张常量表比较，而比较方式是把 key 的字符左移 2 位（lea edx,[rax*4+0]）：

1
2
3
4
5
6
7
8
9
10
11
12
; enc_and_check(char* username /*rdi->[rbp-0x488]*/, char* key /*rsi->[rbp-0x490]*/)
14bc  mov    rax,[rbp-0x490]        ; key
14c6  call   strlen
14cb  cmp    rax,0x3
154a  mov    DWORD PTR [rbp-0x440],0x120
1554  mov    DWORD PTR [rbp-0x43c],0x150
155e  mov    DWORD PTR [rbp-0x438],0x14c
1568  mov    DWORD PTR [rbp-0x434],0xb4
15b7  movzx  eax,BYTE PTR [rax]      ; key[i]
15ba  movsx  eax,al
15bd  lea    edx,[rax*4+0x0]         ; key[i] * 4
15d2  cmp    edx,eax                 ; == 表里的常量？

0x120/4=0x48='H'，0x150/4=0x54='T'，0x14c/4=0x53='S'，0xb4/4=0x2d='-'。所以 key 必须以 HTS- 开头。

Step 2: key 的格式

后面几段循环分别规定了分隔符位置和内容长度：

  • 从下标 3 开始每隔 5 个字符必须是 -（add rbp-0x460, 5），即 HTS- 之后是每 4 个 hex 一组、用 - 分隔。
  • 另一段循环把 key 里所有的 - 去掉，用一个 sprintf(buf, "%s%c", buf, key[i]) 拼成一个纯 hex 串。
  • 最后要求这个纯 hex 串的长度恰好等于 2 * strlen(username)：
1
2
3
4
5
6
7
16bb  mov    rax,[rbp-0x488]        ; username
16c5  call   strlen
16ca  lea    rbx,[rax+rax*1]        ; rbx = 2 * strlen(username)
16d5  call   strlen                 ; strlen(hex buffer)
16dd  cmp    rbx,rax
16e0  je     ok
16e2  mov    eax,0x1                ; 长度不符 -> 失败

也就是说：每个用户名字符对应 2 个 hex 位（1 byte），整个 key 是 HTS- 加若干 4-hex 一个的分组。格式串也可以直接在 .rodata 里读到：0x3008="%s%c"、0x300d="%02X"。

Step 3: 逆向字节生成算法

主循环对用户名的每个字符 j 做一次计算。它先把第 j 对的两个 hex 字符用 sscanf(..., "%02X", ...) 解析成一个整数 hexval，然后按下面的公式算出应有的值 result，并要求 result == hexval：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
171e  movzx  eax,BYTE PTR [buf+idx]  ; 取两个 hex 字符
174e  call   sscanf("%02X")          ; -> hexval  ([rbp-0x474])
1773  mov    eax,[rbp-0x470]         ; acc（上一字节算出的值，初值 0）
1779  mov    [rbp-0x46c],eax         ; t = acc
177f  cmp    DWORD PTR [rbp-0x46c],0x1f
1786  jle    1791
1788  sub    DWORD PTR [rbp-0x46c],0x1f   ; while (t > 31) t -= 31;  -> t = acc mod 31
178f  jmp    177f
1791  mov    rdx,[rbp-0x488]         ; username
17a2  movzx  eax,BYTE PTR [rdx+j]
17a5  movsx  eax,al                  ; u = (signed char)username[j]
17a8  sub    eax,[rbp-0x470]         ; u - acc
17ae  sar    eax,1                   ; (u - acc) >> 1   （算术右移）
17b0  mov    esi,eax
17c3  movzx  eax,BYTE PTR [rdx+j]
17c6  movsx  edx,al                  ; u
17cf  mov    ecx,eax(=t)             ; cl = t
17d1  shl    edx,cl                  ; u << (t & 31)
17d5  not    eax                     ; ~(u << t)
17d7  and    eax,esi
17d9  mov    [rbp-0x464],eax         ; result

即：

1
2
3
t      = acc mod 31                # acc<=31 时不减，等价 acc % 31
result = ((signed_char)username[j] - acc) >> 1
result &= ~(username[j] << (t & 31))

算完之后 acc 更新为 result（18d5: mov [rbp-0x470], hexval），因为前面已经校验过 result == hexval，两者相等，所以下一轮的起点就是当前字节的值。

有一个伪装用的内层循环（0x17f7~0x18bb）遍历整个 key 和用户名，对 acc 执行一组 and/ shl / or / +1 运算。该循环位于 result 计算之后；acc 在循环结束时又通过 mov eax,[rbp-0x468] 被赋回此前保存的 hexval（0x18d5），因此这些运算的副作用不会影响 result，属于作者放置的烟雾弹。

Step 4: keygen

把上面的公式原样搬到 Python。两个细节必须对齐 x86：

  • username[j] 是 signed char（movsx），高位字节按负数处理。
  • 所有中间量都是 32-bit 补码，>> 1 是算术右移；移位量按 x86 规则只取低 5 位（& 31）。
  • 每个字节只有落在 0x00..0xFF 才能写成两个 hex 位，所以并非所有用户名都能表示，超出范围时报告不可解。
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
#!/usr/bin/env python3
"""HackThisSite Application Challenge 17 keygen.

Reconstructed from _Z13enc_and_checkPcS_ in app17unix (objdump -d -Mintel).

The binary checks a key of the form  HTS-XXXX-XXXX-...  where the number of
hex digits equals 2 * len(username).  For each username byte u and the running
state `acc` (starts at 0), it recomputes

    result = ((u - acc) >> 1) & ~(u << (acc mod 31))        # 32-bit, signed

and demands that the two hex digits for that position equal `result`; the next
state becomes `result`.  `>>` is an arithmetic shift (x86 `sar`) and the shift
count is taken modulo 32 (x86 `shl cl`).  Every intermediate is 32-bit two's
complement, but only values 0..0xFF can be written as two hex digits, so a
username is solvable only when every step lands in 0..255.
"""

MASK = 0xFFFFFFFF


def s32(x):
    """Wrap to 32-bit signed."""
    x &= MASK
    return x - 0x100000000 if x & 0x80000000 else x


def reduce31(acc):
    """Faithful port of the binary's `while (t > 31) t -= 31` for signed int."""
    if acc <= 31:            # negative acc never enters the loop
        return acc
    return acc % 31          # for acc > 31 the loop yields acc in [0, 31]


def key_bytes(username):
    """Return the list of per-character bytes the key has to encode."""
    acc = 0
    out = []
    for ch in username.encode('latin-1'):
        u = ch - 256 if ch >= 128 else ch          # movsx (signed char)
        t = reduce31(acc)
        res = s32(u - acc) >> 1                    # sar eax, 1
        shifted = s32(u << (t & 31))               # shl edx, cl
        res = s32(res & s32(~shifted))             # not / and
        out.append(res)
        acc = res
    return out


def keygen(username):
    payload = key_bytes(username)
    if any(b < 0 or b > 0xFF for b in payload):
        raise ValueError(
            'username %r is not representable in the 2-hex-digit format: %r'
            % (username, payload))
    hexs = ''.join('%02X' % b for b in payload)
    return 'HTS-' + '-'.join(hexs[i:i + 4] for i in range(0, len(hexs), 4))


if __name__ == '__main__':
    import sys
    usernames = sys.argv[1:] or ['demo']
    for name in usernames:
        print('%-14s -> %s' % (name, keygen(name)))

Step 5: Verify

用 pty 驱动真实二进制，把用户名和 keygen 算出的 key 喂进去，看它是否打印成功信息：

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
#!/usr/bin/env python3
"""Feed keygen_final outputs to the real app17unix binary and report verdict."""
import os
import pty
import select
import sys
import time

HERE = os.path.dirname(os.path.abspath(__file__))
BIN = os.path.join(HERE, 'unix', 'app17unix')
sys.path.insert(0, HERE)
from keygen_final import keygen


def run(username, key, timeout=6.0):
    pid, fd = pty.fork()
    if pid == 0:
        os.execv(BIN, [BIN])
    out = b''
    sent_user = sent_key = sent_extra = False
    deadline = time.time() + timeout
    while time.time() < deadline:
        r, _, _ = select.select([fd], [], [], 0.2)
        if r:
            try:
                data = os.read(fd, 4096)
            except OSError:
                break
            if not data:
                break
            out += data
        if not sent_user and b'Username:' in out:
            os.write(fd, username.encode() + b'\n')
            sent_user = True
        elif sent_user and not sent_key and b'Password:' in out:
            os.write(fd, key.encode() + b'\n')
            sent_key = True
        elif sent_key and not sent_extra and b'Congratulations' in out:
            os.write(fd, b'\n')
            sent_extra = True
            break
    try:
        os.close(fd)
    except OSError:
        pass
    try:
        os.waitpid(pid, 0)
    except OSError:
        pass
    return out


if __name__ == '__main__':
    for name in (sys.argv[1:] or ['demo']):
        key = keygen(name)
        out = run(name, key)
        ok = b'Congratulations' in out
        print('username=%-12s key=%-28s -> %s'
              % (name, key, 'ACCEPTED' if ok else 'rejected'))
1
2
3
4
5
6
7
8
9
10
11
12
13
$ python3 keygen_final.py demo testuser Hash-Cat a A
demo           -> HTS-1229-2206
testuser       -> HTS-0A2D-2328-2626-1F29
Hash-Cat       -> HTS-241E-2A1F-071E-2129
a              -> HTS-10
A              -> HTS-20

$ python3 verify_final.py demo testuser Hash-Cat a A
username=demo         key=HTS-1229-2206                -> ACCEPTED
username=testuser     key=HTS-0A2D-2328-2626-1F29      -> ACCEPTED
username=Hash-Cat     key=HTS-241E-2A1F-071E-2129      -> ACCEPTED
username=a            key=HTS-10                       -> ACCEPTED
username=A            key=HTS-20                       -> ACCEPTED

证据等级：static + dynamic。算法本身来自对未 strip ELF 的 objdump -d -Mintel 反汇编（静态），以及 .rodata 里 %s%c / %02X 格式串的直接读取；正确性由真实二进制在 pty 中逐个接受 keygen 输出获得（动态）。

Vulnerabilities

校验逻辑和所需秘密全部打包在客户端可执行文件里，且 ELF 未 strip，enc_and_check 的算法可以被逐指令读出来。任何拿到二进制的人都能按公式反推出任意用户名的 key，因此生成一个与账号绑定的 key 不具备任何防伪能力。修复方向：把校验放到服务端，序列号用只有服务器持有的密钥签名（或至少做不可逆的哈希校验），客户端只负责提交而不是自行判定。

spoiler 里的 key 是对占位用户名 demo 生成的示例；提交给 HTS 时必须用自己账号的用户名重新跑 keygen（同一算法已在真实二进制上用其它用户名验证过，均被接受）。

HTS-1229-2206