HackThisSite - Extended Basic Mission 11

Posted on Edited on In Views: Disqus:

Challenge

关卡给出一段 Windows 批处理（batch）写的认证脚本，要求输入一个能让脚本认证通过的密码。脚本用 SET /P 读取输入，然后逐字符与字母表比对，命中时把一个累乘变量乘以对应的素数：

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
@ECHO OFF
SETLOCAL ENABLEDELAYEDEXPANSION
SET PRIME=2  3  5  7  11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101
SET CHARS=a  b  c  d  e  f  g  h  i  j  k  l  m  n  o  p  q  r  s  t  u  v  w  x  y  z
SET PASSWORDVALUE=1
SET INPUT=
SET /P INPUT=Insert password:
IF "%INPUT%"=="" "%~0"
ECHO Authenticating...
:OVERLOOP
SET CURRENTPOSITION=0
:SUBLOOP
IF /I "!INPUT:~%CHARACTERPOSITION%,1!"=="!CHARS:~%CURRENTPOSITION%,1!" SET /A PASSWORDVALUE*=!PRIME:~%CURRENTPOSITION%,3!
SET /A CURRENTPOSITION+=3
IF NOT %CURRENTPOSITION%==78 GOTO :SUBLOOP
SET /A CHARACTERPOSITION+=1
IF NOT "!INPUT:~%CHARACTERPOSITION%,1!"=="" GOTO :OVERLOOP
:END
ENDLOCAL&IF NOT %PASSWORDVALUE%==1065435274 GOTO :ACCESSDENIED
ECHO You have been authenticated. Welcome aboard!
GOTO :SILENTPAUSE
:ACCESSDENIED
ECHO Access denied!
:SILENTPAUSE
PAUSE > NUL

Solution

脚本语义

PRIME 与 CHARS 都是等宽分隔的字符串：PRIME 里每个素数被右填充到 3 个字符宽，CHARS 里每个字母后面也有两个空格。内层循环的 CURRENTPOSITION 取 0,3,6,…,75 共 26 个位置，!PRIME:~%CURRENTPOSITION%,3! 正好截出对应的一个素数，!CHARS:~%CURRENTPOSITION%,1! 截出 a 到 z。

外层对输入里每个字符位置 CHARACTERPOSITION 走一遍这 26 个槽位。IF /I 是大小写不敏感的，所以一个大写字母也会命中。命中的后果只有一个：SET /A PASSWORDVALUE*=!PRIME:~…,3!，也就是把累乘值乘上该字母对应的那个素数。因此

  • 输入里每个字符最多贡献一次乘法，乘的是 {2,3,5,…,101} 中的某一个素数；
  • 非字母字符不贡献任何乘法；
  • 重复同一个字母就是重复乘同一个素数。

为什么不能按原意凑出目标

关卡的门槛是

1
IF NOT %PASSWORDVALUE%==1065435274 GOTO :ACCESSDENIED

把目标值分解：

1
1065435274 = 2 × 6827 × 78031

6827 与 78031 都是素数，且都大于 101，不在脚本能乘到的素数表里。换句话说，任何由列表内素数组成的乘积都不可能精确等于 1065435274。如果只盯着凑乘积这一个方向，该关无法通过。

32 位溢出

SET /A 的整数运算是 32 位有符号 的，累乘过程中超过 2**31 会回环绕。于是真正需要满足的条件是同余：

1
∏(选中的素数) ≡ 1065435274 (mod 2**32)

因为乘法在模 2**32 下可结合，最终值只取决于所选素数构成的多重集合（与输入顺序无关）。

再看目标值的 2-adic 赋值：1065435274 = 2 × 532717637，532717637 是奇数。2**32 以内的偶数按 2 的幂次分层，目标只含一个因子 2，所以素数 2（字母 a）必须恰好出现一次，其余部分是一个奇数乘积，需要满足

1
X ≡ 532717637 (mod 2**32)

只剩 25 个奇素数（3 到 101）可选，每个的多重度未知。用中间相遇（meet-in-the-middle）：把奇素数分成两半分别枚举各自的多重集合乘积，在一半的哈希表里查另一半需要的补数（对奇数取模逆），取总乘法次数最少的组合。每个素数的重数上限取 2 就足够：25 个奇素数、每个重数取 0..2，组合数在 3**25 量级，远多于模数 2**32，解很多而长度很小。

完整求解器：

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
from itertools import product

MOD = 1 << 32
TARGET = 1065435274
PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,
          41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101]
LETTERS = "abcdefghijklmnopqrstuvwxyz"

def search(limit=2):
    """Find prime multiplicities (0..limit per odd prime) with product == TARGET mod 2**32."""
    odd = PRIMES[1:]
    left, right = odd[:12], odd[12:]
    table = {}
    ranges = [range(limit + 1)] * len(right)
    for counts in product(*ranges):
        r = 1
        for q, k in zip(right, counts):
            r = r * pow(q, k, MOD) % MOD
        table.setdefault(r, counts)
    best = None
    for counts in product(*([range(limit + 1)] * len(left))):
        l = 1
        for q, k in zip(left, counts):
            l = l * pow(q, k, MOD) % MOD
        need = (TARGET // 2) * pow(l, -1, MOD) % MOD
        rc = table.get(need)
        if rc is not None and (best is None or sum(counts) + sum(rc) < best[0]):
            best = (sum(counts) + sum(rc), counts, rc)
    return best

def build(best):
    _, lc, rc = best
    counts = {2: 1}
    for q, k in dict(zip(PRIMES[1:13], lc)).items():
        counts[q] = counts.get(q, 0) + k
    for q, k in dict(zip(PRIMES[13:], rc)).items():
        counts[q] = counts.get(q, 0) + k
    pw = "".join(LETTERS[q_index] * k
                 for q_index, k in sorted((PRIMES.index(q), k) for q, k in counts.items()))
    return counts, pw

def replay(pw):
    """Model the batch loop: each letter multiplies its prime; result is signed 32-bit."""
    value = 1
    for ch in pw.lower():
        idx = LETTERS.find(ch)
        if idx >= 0:
            value = value * PRIMES[idx] % MOD
    return value - MOD if value >= (1 << 31) else value

if __name__ == "__main__":
    counts, pw = build(search())
    print("counts:", counts)
    print("password:", pw)
    assert replay(pw) == TARGET, "replay mismatch"
    assert pw == "aghilmort"

Result

搜索得到 9 个字符的最短解：

1
2
密码：aghilmort
对应素数：a=2, g=17, h=19, i=23, l=37, m=41, o=47, p=61, t=71

乘积在 32 位下回绕：

1
2
2×17×19×23×37×41×47×61×71 = 4588090507402
4588090507402 mod 2**32 = 1065435274

正好落在门槛值上。

Verify

把关卡脚本原样复制成 replica.bat（去掉末尾的 PAUSE），在 wine 下喂入输入：

1
2
3
### input=aghilmort -> AUTHENTICATED
### input=wrongpass -> DENIED
### input=aaaaaa -> DENIED

aghilmort 触发 You have been authenticated. Welcome aboard!，其它输入落到 Access denied!。

随后带 Referer: <关卡页> 提交到 POST /missions/extbasic/template.php：响应里出现指向下一关 /missions/playit/extbasic/12 的 go-on 链接，账号 profile 的 Extbasic: 行也新增了 (11)。两个独立判据同时成立。

Key points

批处理 SET /A 是 32 位有符号运算，累乘不检查溢出；一个乘法哈希只要允许回绕，就不能靠算术基本定理保证唯一可逆。用模 2**32 的同余条件反推多重集合，比精确因式分解更直接。

aghilmort