Cryptohackack Megalomaniac 1-3

题目网址：https://cryptohack.org/challenges/web/

协议梳理

先看懂客户端的密钥分层：

PASS(20位随机口令) ──PBKDF2(SALT,1000轮,SHA512)──> enc_key(16B) ‖ auth_key(16B)
                                                     │
master_key(16B 随机) ──AES-ECB(enc_key)──> master_key_enc（服务器持有）
RSA私钥(p,q,d,u)    ──AES-ECB(master_key)──> share_key_enc（服务器持有）
flag               ──AES-ECB(SHA256(p‖q))──> get_encrypted_flag 返回

连接时服务器把用户的注册材料直接贴给你：

1 2	`{"auth_key_hashed": "...", "master_key_enc": "...", "share_key_pub": [n, 65537], "share_key_enc": "..."}`

登录阶段（wait_login → send_challenge）客户端会重新创建一个同口令的登录实例 C_，然后用它的私钥解密你提交的 SID_enc 并把结果（去掉末 16 字节）回显——这就是我们要喂料的解密预言机。

私钥的序列化格式是带 2 字节大端长度前缀的 (p, q, d, u)，AES-ECB 整体加密后存储：

def format_rsa_privkey(self):
    data  = self.format_number(self.share_key.p)
    data += self.format_number(self.share_key.q)
    data += self.format_number(self.share_key.d)
    data += self.format_number(self.share_key.u)
    return pad(data, 16)

Megalomaniac 1

裁坏 CRT 系数 + 二分

利用点清单

#	源码位置	弱点
A	`Challenge.__init__` 的 `material`	注册材料（含加密私钥）全公开
B	`Client` / `Client_new_login` 的 `gen_keys`	同 PASS/SALT，PBKDF2 确定性，`C_.enc_key == C.enc_key`
C	`AES.new(self.master_key, AES.MODE_ECB)`	ECB 无认证：密文块可裁剪重排，客户端无感知
D	`parse_rsa_privkey` 的切片 + `assert len==4`	越界静默截断，裁剪后照样恰好解析出 4 个元素
E	`wait_login` 分支没有 `current_step` 检查	状态机可无限重置，预言机无限次使用
F	`RSA_CRT_decrypt` 的 `m = h*p + mp`	mod p 恒等于 mp，与 u 对错无关
G	`SID = SID[:-16]`	砍掉低 16 字节：错误解密也能以数据形式回显（观察窗口）
H	`get_encrypted_flag` 用 `SHA256(p‖q)`	flag 密钥只依赖 p、q

其中 B 是重放的前提：banner 里 C 的 master_key_enc 原样重放给 C_，由于 enc_key 相同，客户端解出的就是 C 的真 master_key；再用它解 share_key_enc，C 的真私钥就被装进了登录实例。

核心数学：CRT 的”半边正确性”

Garner 公式：

mp = ct^d  mod p          # = m mod p
mq = ct^d  mod q          # = m mod q
t  = (mq − mp) mod q
h  = t·u mod q            # u = p⁻¹ mod q
m  = h·p + mp

盯住 m mod p = mp——p 那一项被模掉了，与 u 对错无关。所以 u 错了，解密结果 mod p 仍然正确、mod q 全是垃圾。u 坏 = “只对 mod p 正确的解密机”。

再用一个关键性质把输出变成判定：发 SID_enc = s^e，则 mp = s mod p。

s < p 时 mp = s，t = (mq − s) mod q = 0（因为 mq ≡ s mod q），h = 0——u 根本没上场，输出精确还原为 s；
s ≥ p 时 t = p mod q ≠ 0，坏 u 算出错误的 h，输出 ≠ s。

用小数字验证（p=5, q=11, e=3, d=7, 真 u=9，坏 u′=4，s=13≥5）：ct = 52，mp=3, mq=2；真 u 算出 m=13 ✓，坏 u′ 算出 m′=38——38 mod 5 = 3 仍对，38 mod 11 = 5 已是垃圾；且 gcd(38−13, 55) = 5 = p（Bellcore 故障攻击同款）。

⟹ 回显是否精确等于预期 ⟺ s 是否小于 p。单调谓词，二分即可。

exp

#!/usr/bin/env python3
import json, time
from pwn import remote, log
from Crypto.Util.number import long_to_bytes
from Crypto.Hash import SHA256
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

HOST, PORT = "socket.cryptohack.org", 13408
BLK = 16

def send_json(io, obj):
    io.sendline(json.dumps(obj).encode())
    while True:
        try:
            return json.loads(io.recvline())
        except Exception:
            continue

io = remote(HOST, PORT)
io.recvuntil(b"uploading crypto material...\n")
banner = json.loads(io.recvline())
n, e = banner["share_key_pub"]
master_key_enc = bytes.fromhex(banner["master_key_enc"])
share_key_enc  = bytes.fromhex(banner["share_key_enc"])

send_json(io, {"action": "wait_login"})
flag_ct = bytes.fromhex(send_json(io, {"action": "get_encrypted_flag"})["encrypted_flag"])

# ECB 裁剪: 保留块 0..32 + 块 40(合法填充), 删块 33..39 → u 只剩 16 字节(残废)
evil = share_key_enc[:33*BLK] + share_key_enc[40*BLK:]

def oracle(s):
    send_json(io, {"action": "wait_login"})            # 无限重置状态机
    resp = send_json(io, {
        "action":        "send_challenge",
        "SID_enc":       long_to_bytes(pow(s, e, n)).hex(),
        "share_key_enc": evil.hex(),                   # ← 裁剪后的
        "master_key_enc": master_key_enc.hex(),        # ← 原样重放
    })
    return resp.get("SID") == long_to_bytes(s)[:-16].hex()   # True ⟺ s < p

assert oracle(1 << 1023)                               # 自检: s<p 必须精确还原
lo, hi = 1 << 1023, 1 << 1024
prog = log.progress("binary search")
while hi - lo > 1:
    mid = (lo + hi) // 2
    if oracle(mid): lo = mid
    else:           hi = mid
    prog.status(f"剩余 {(hi-lo).bit_length()} bit")

p, q = hi, n // hi
secret = SHA256.new(long_to_bytes(p) + long_to_bytes(q)).digest()
print(unpad(AES.new(secret, AES.MODE_ECB).decrypt(flag_ct), 16).decode())

约 1024 次查询跑完。唯一的小概率翻车点：d 恰好不是 256 字节（概率 ~1/256）会让布局错位，重连一次即可。

Megalomaniac 2

第二关和第一关相比，只有一个不同点：多了remaining_logins = 4
也就是我们只有4次登录的机会

第二关唯一的改动：

self.remaining_logins = 4
...
if message["action"] == "wait_login":
    if self.remaining_logins == 0:
        self.exit = True
        return {"error": "You died miserably waiting for a login..."}
    self.remaining_logins -= 1

wait_login 只有 4 次，而 send_challenge 又必须处于 LOGIN 态——第一关的 1024 次查询二分直接被腰斩（每次查询只泄露 1 bit，4 次 = 4 bit，连 p 的零头都不够）。

预算从 1024 次砍到 4 次，等于出题人明示：每次查询必须给出百比特级的信息。这就轮到 Coppersmith 了——它只需要 1 次查询。

Coppersmith 攻击

坏 u 预言机对 ct = s^e 的输出满足：

1	`m′ ≡ s (mod p) ← 无论 u 对错恒成立(上一关的性质 F)`

取 s = 2^1024 − 1（保证 p ≤ s < 2p）。服务器回显 R = ⌊m′/2^128⌋，于是：

1 2	`m′ = R·2^128 + r, r ∈ [0, 2^128) ← 唯一未知量 m′ − s = p·(h′ − 1) ← p 的倍数!`

构造线性多项式 f(x) = x + (R·2^128 − s)，它在 mod p 下有一个 2^128 的小根 r，而 p ≥ n^0.5——标准 Coppersmith 场景（根界预算约 n^0.2 = 2^400，绰绰有余）。求出 r 后：

1	`p = gcd(f(r), n) = gcd(R·2^128 + r − s, n)`

exp

注：该脚本也能解Megalomaniac 1

#!/usr/bin/env python3
# sage -python mega2.py
import json
from pwn import remote
from pwn import log as pwlog          # 起别名, 避免和 sage.all 的符号 log 冲突
from sage.all import PolynomialRing, Zmod
from math import gcd
from Crypto.Util.number import long_to_bytes
from Crypto.Hash import SHA256
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

HOST, PORT = "socket.cryptohack.org", 13409

def send_json(io, obj):
    io.sendline(json.dumps(obj).encode())
    while True:
        try:
            return json.loads(io.recvline())
        except Exception:
            continue

io = remote(HOST, PORT)
io.recvuntil(b"uploading crypto material...\n")
banner = json.loads(io.recvline())
n, e = banner["share_key_pub"]
master_key_enc = bytes.fromhex(banner["master_key_enc"])
share_key_enc  = bytes.fromhex(banner["share_key_enc"])

send_json(io, {"action": "wait_login"})                       # 登录 1/4
flag_ct = bytes.fromhex(send_json(io, {"action": "get_encrypted_flag"})["encrypted_flag"])

# XOR 块39(u[104:120]): 弄坏 u, 其余(含填充)原样——比删块更简洁, 不依赖解析器截断
buf = bytearray(share_key_enc)
delta = b"MEGA-F4ULT-BLOCK"
for i in range(16):
    buf[39*16 + i] ^= delta[i]
evil = bytes(buf)

send_json(io, {"action": "wait_login"})                       # 登录 2/4
resp = send_json(io, {
    "action":        "send_challenge",
    "SID_enc":       long_to_bytes(pow(2**1024 - 1, e, n)).hex(),
    "share_key_enc": evil.hex(),
    "master_key_enc": master_key_enc.hex(),
})

R  = int(resp["SID"], 16)
s  = (1 << 1024) - 1
C0 = R * 2**128 - s

# Coppersmith: f(x) = x + C0 在 mod p 下有 <2^128 的根, p >= n^0.5
PR = PolynomialRing(Zmod(n), 'x')
x  = PR.gen()
r  = (x + C0).small_roots(X=2**128, beta=0.45)[0]
p  = gcd(int(C0 + int(r)), n)
assert n % p == 0
q = n // p

secret = SHA256.new(long_to_bytes(p) + long_to_bytes(q)).digest()
print(unpad(AES.new(secret, AES.MODE_ECB).decrypt(flag_ct), 16).decode())

Megalomaniac 3：p 送到手上，1 次查询读出文件

题目变化

第三关代码与第二关几乎一致，但有三处关键改动：

banner 变成三段，新增两个密文：

def prepare_file(self, data):
    node_key = get_random_bytes(16)
    self.file_enc = AES.new(node_key, AES.MODE_ECB).encrypt(pad(data, 16))
    self.node_key_enc = self.cipher_master.encrypt(node_key)   # AES-ECB(master_key)

flag 不再在 SHA256(p‖q) 下面，而是藏进了”文件”里：文件 → node_key 加密，node_key → master_key 加密。
2. recovered_shared_key 直接给出 (n, e, p)——“Wow what a hacker, you already managed to grab this user share_key…”，默认你已经打完了前两关。
3. get_encrypted_flag 动作没了；登录次数恢复不限。

于是目标从”恢复 p”变成：拿到 node_key，解开 file_enc。node_key = AES_dec(master_key, node_key_enc)，master_key 依然摸不到——但这次我们不需要摸到它。

攻击原理：把 node_key_enc 种进 u 字段，借客户端之手解密，再逆着 CRT 混合读出来

第 1 步：栽赃

1	`evil = share_key_enc[:3316] + node_key_enc + share_key_enc[4016:]`

保留块 0~32（p、q、d 完整 + u 前 8 字节）和块 40（合法填充），把空出来的块 33 换成 node_key_enc——它恰好 16 字节，是一个完整的 ECB 块。客户端解密后，这个位置变成 AES_dec(master_key, node_key_enc) = node_key。parse 出的四元组：

1 2	`p, q, d ← 全部真实 u′ = u[0:8] ‖ node_key ‖ u[120:128] ← 32 字节, 中间 16 字节就是我们要的!`

第 2 步：让客户端当”混合器”

选 s ∈ [p, 2p)（p 已知，随便选），发 SID_enc = s^e。由费马小定理，客户端算出的 mp = s mod p = s − p、mq = s mod q——全程不需要 d。于是：

1
2
3

t = (mq − mp) mod q          ← 离线可算!
h′ = t·u′ mod q              ← node_key 的信息在这里
m′ = mp + p·h′

第 3 步：`[:-16]` 的噪声被 p “除没了”

回显 R = ⌊m′/2^128⌋，即 m′ = R·2^128 + r（r < 2^128 未知）。由 m′ = (s−p) + p·h′：

1 2	`p·h′ = R·2^128 + r − s + p = X + r, X = R·2^128 − s + p 已知 h′ = (X + r) / p`

r 的活动范围 2^128 除以 p（~2^1023）后宽度小于 1——所以 h′ 只可能是 ⌊X/p⌋ 或 ⌊X/p⌋+1 两个值。第一关里砍掉的 128 位是逐位二分的动力，第二关里要请 Coppersmith 来吃，第三关知道 p 之后它连一个整数都改变不了。

第 4 步：反解 node_key

1	`u′ ≡ h′·t⁻¹ (mod q)`

真值 u′ 只有 32 字节（< 2^256 ≪ q），模 q 剩余就是它本身；两个 h 候选各算一个 u′，用”解出的明文是否含 Congratulations 前缀”做最终裁决。

exp

#!/usr/bin/env python3
import json
from pwn import remote, log
from Crypto.Util.number import long_to_bytes
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

HOST, PORT = "socket.cryptohack.org", 13410

def send_json(io, obj):
    io.sendline(json.dumps(obj).encode())
    while True:
        try:
            return json.loads(io.recvline())
        except Exception:
            continue

io = remote(HOST, PORT)

io.recvuntil(b"crypto material...\n")
material    = json.loads(io.recvline())
io.recvuntil(b"uploading a file...\n")
file_upload = json.loads(io.recvline())
io.recvuntil(b"user share_key...\n")
recovered   = json.loads(io.recvline())

n, e, p = recovered["share_key"]
q = n // p
assert p * q == n
master_key_enc = bytes.fromhex(material["master_key_enc"])
share_key_enc  = bytes.fromhex(material["share_key_enc"])
node_key_enc   = bytes.fromhex(file_upload["node_key_enc"])
file_enc       = bytes.fromhex(file_upload["file_enc"])

s  = 2 * p - 1                      # s ∈ [p, 2p): mp = s-p, mq = s mod q
mp = s - p
mq = s % q
t  = (mq - mp) % q
assert t != 0

# 栽赃: 块33 = node_key_enc → parse 出 u' = u[0:8]‖node_key‖u[120:128]
evil = share_key_enc[:33*16] + node_key_enc + share_key_enc[40*16:]

send_json(io, {"action": "wait_login"})
resp = send_json(io, {
    "action":        "send_challenge",
    "SID_enc":       long_to_bytes(pow(s, e, n)).hex(),
    "share_key_enc": evil.hex(),
    "master_key_enc": master_key_enc.hex(),
})
assert "SID" in resp and resp["SID"], resp

R = int(resp["SID"], 16)
X = R * 2**128 - s + p
for h in (X // p, X // p + 1):
    u2 = h * pow(t, -1, q) % q
    if u2 >= 2**256:
        continue
    node_key = long_to_bytes(u2, 32)[8:24]
    pt = AES.new(node_key, AES.MODE_ECB).decrypt(file_enc)
    if b"Congratulations" in pt:
        print(unpad(pt, 16).decode())
        break

#crypto #刷题

Cryptohackack Megalomaniac 1-3

https://baymax-fools.github.io/2026/09/12/crypto/Cryptohack-Megalomaniac-1-3/

Author

Baymax

Posted on

September 12, 2026

Updated on

September 13, 2026

Licensed under

Zero-knowledge proofs(零知识证明) Previous

综合密码协议学习 Next

Cryptohackack Megalomaniac 1-3

协议梳理

Megalomaniac 1

利用点清单

核心数学：CRT 的”半边正确性”

exp

Megalomaniac 2

Coppersmith 攻击

exp

Megalomaniac 3：p 送到手上，1 次查询读出文件

题目变化

攻击原理：把 node_key_enc 种进 u 字段，借客户端之手解密，再逆着 CRT 混合读出来

第 1 步：栽赃

第 2 步：让客户端当”混合器”

第 3 步：[:-16] 的噪声被 p “除没了”

第 4 步：反解 node_key

exp

第 3 步：`[:-16]` 的噪声被 p “除没了”