857 字
3 分钟
KAOHE
这里是一些题目的 WP
re1
这是一个 64 位 Linux ELF，而且是 静态链接 + 去符号，所以直接看符号会比较痛苦，里面会混很多 libc / libstdc++ 的代码。
再搜字符串：
wrongflag{md5 (your input)}同时 将整个程序给AI分析, 发现这是一个走迷宫程序，题目使用一个巨大的有向图的数据结构，一共存在 799 个节点若干条边
程序在函数 SUB_4047d2 中构建节点和边, 整个程序将 wasd 4个字符映射为边移动的操作， 如果存在一条从初始态 -0x1910 到 -0x20 的路径且步数正好为 0x10c 步， 则这个路径的的md5为 flag
所以接下来得到flag 的步骤就很明了，这是一个迷宫路径问题， 其中起点和终点是确定的， 然后如果我们要找到最后一步的操作N, 则可以求出第N-1 步操作的值， 依此类推，可以将找到终点路劲转化为找到到达前一个路径的子问题且子问题很容易重叠,同时局部最优方案，即确定的决策不影响后续决策，所以显然可以使用动态规划解决.
脚本:
import reimport hashlibimport subprocess
BIN = "./re1"START = "-0x1910"TARGET = "-0x20"LENGTH = 0x10cCHARS = {"a": (6, 1), "d": (6, 4), "s": (7, 3), "w": (7, 7)}
# 提取边asm = subprocess.check_output(["objdump", "-d", "-M", "intel", "--start-address=0x4047d2", "--stop-address=0x462d6b", BIN], text=True)
edges = {}last_rbx = last_rax = high = low = None
for line in asm.splitlines(): m = re.search(r"mov rbx,QWORD PTR \[rbp-(0x[0-9a-f]+)\]", line) if m: last_rbx = "-" + m.group(1)
m = re.search(r"mov rax,QWORD PTR \[rbp-(0x[0-9a-f]+)\]", line) if m: last_rax = "-" + m.group(1)
m = re.search(r"DWORD PTR \[rbp-0x1918\],(0x[0-9a-f]+)", line) if m: high = int(m.group(1), 16)
m = re.search(r"DWORD PTR \[rbp-0x1914\],(0x[0-9a-f]+)", line) if m: low = int(m.group(1), 16)
if "mov QWORD PTR [rax],rbx" in line and all(x is not None for x in [last_rax, high, low, last_rbx]): edges[(last_rax, high, low)] = last_rbx
print(f"[+] Edges: {len(edges)}")
dp = {START: ""}for step in range(LENGTH): ndp = {}
for state, path in dp.items(): # 剪枝 for ch, (hi, lo) in CHARS.items(): next_state = edges.get((state, hi, lo)) if next_state and next_state not in ndp: ndp[next_state] = path + ch dp = ndp if TARGET in dp: print(f"[+] Target reached at step {step + 1}")
answer = dp[TARGET]md5_value = hashlib.md5(answer.encode()).hexdigest()
print(f"[+] Input length: {len(answer)}")print(f"[+] Input:\n{answer}")print(f"[+] MD5: {md5_value}")print(f"[+] Flag: flag{{{md5_value}}}")
# 验证out = subprocess.check_output([BIN], input=(answer + "\n").encode())print(out.decode())运行结果:
[+] edges: 4794[+] reached target at step: 268[+] input length: 268[+] md5: 8b587367b99e5e2fcbdb6598da14b9bc[+] flag: flag{8b587367b99e5e2fcbdb6598da14b9bc}[+] program output:flag{md5(your input)}所以 flag 为: flag{8b587367b99e5e2fcbdb6598da14b9bc}
re2
同样使用ida 打开发现函数量巨大，所以使用AI 分析：
2.1 主流程 (sub_402380 @ 0x402380)
sub_402380(name, code): 1. 初始化 MIRACL big 整数结构 2. 计算 hash = MD5(name) → 16 字节 3. 构建 target = "Ginkgo26" + hash → 24 字节 4. 解析 code (48 hex chars → 24 bytes, 字节序反转) 5. 对 code 进行 9 轮 RSA 变换 6. 比较结果前 20 字节与 target[:20]2.2 哈希函数识别
通过对 sub_41DEB0 (@ 0x41DEB0) 的逆向分析:
-
IV 常量:
- A = 0x67452301
- B = 0xEFCDAB89
- C = 0x98BADCFE
- D = 0x10325476
-
轮函数特征:
- 轮 1 (0-15):
F = (B & C) | (~B & D), 移位量 [7,12,17,22] - 轮 2 (16-31):
F = B ^ C ^ D, 移位量 [5,9,14,20] - 轮 3 (32-47):
F = (B & C) | (B & D) | (C & D), 移位量 [4,11,16,23] - 轮 4 (48-63):
F = B ^ C ^ D, 移位量 [6,10,15,21]
- 轮 1 (0-15):
-
消息字访问模式:
- 轮 1: 顺序
w[i] - 轮 2:
w[(1+5i) % 16] - 轮 3:
w[(5+3i) % 16] - 轮 4:
w[(7i) % 16]
- 轮 1: 顺序
-
加法常数:
floor(abs(sin(i+1)) * 2^32)— MD5 标准常数
结论: 使用的是标准 MD5，非 SHA-1。 先前的分析报告中错误地将 MD5 IV 识别为 SHA-1 IV（两者 H0-H3 相同，但 SHA-1 额外有 H4=0xC3D2E1F0）。
2.3 硬编码模数 N
在 0x402780 处找到 192-bit 常量（以 little-endian 嵌入在 mov 指令中）：
字节序列 (地址递增):56 F6 75 50 F1 6A 00 39 0D CF 0B 27 15 70 8E 61 C5 B3 F2 31 01 86 2F C1作为 big-endian 大整数解释：
N = 0x56F67550F16A00390DCF0B2715708E61C5B3F23101862FC1 = 2132319876367679106148824069448800305036941072478331350977 (58 位十进制)2.4 模数分解 (msieve)
使用 msieve 的二次筛法分解 58-digit 的 N：
msieve v1.53 - quadratic sieve输入: 2132319876367679106148824069448800305036941072478331350977 (58 digits)
p = 45424490472579293708671645907 (29 digits, 96 bits)q = 46942075831425428541187578011 (29 digits, 96 bits)
验证: p * q = N ✓三、算法还原
3.1 正向变换
对输入 code (24 字节) 进行以下操作，对每个指数 e ∈ [3, 7, 11, 17, 19, 23, 29, 31, 37]：
1. x = bytes_to_bigint(buf, big-endian)2. y = x^(-e) mod N (即先求 x^e mod N，再取模逆)3. buf = y.to_bytes(24, big-endian)4. inc4(buf) (前 4 字节作为 little-endian u32 加 1)其中 inc4 操作：
def inc4(data): val = int.from_bytes(data[:4], 'little') val = (val + 1) & 0xFFFFFFFF data[:4] = val.to_bytes(4, 'little')3.2 验证条件
forward(code)[:20] == (b"Ginkgo26" + MD5(name))[:20]注意：只比较前 20 字节，低 4 字节有 2^32 的自由度。这意味着同一个 name 可能对应多个有效 code。
3.3 数学原理
正向变换的核心是 RSA 式运算：
y ≡ x^(-e) (mod N)其中N = p * q
由于 N 是两个 96-bit 素数的乘积，要知道 φ(N) 必须分解 N（这就是为什么需要 msieve）。
四、逆向求解
4.1 单轮逆变换
已知输出 y，求输入 x：
1. buf = dec4(y) (inc4 的逆操作)2. a = buf^(-1) mod N → 恢复 x^e mod N3. d = e^(-1) mod φ(N) → 求 e 的模逆4. x = a^d mod N → 求 e 次根4.2 完整逆算法
从 target = "Ginkgo26" + MD5(username) 出发对 e ← reverse([3,7,11,17,19,23,29,31,37]): 1. buf = dec4(cur) 2. y = int.from_bytes(buf, 'big') 3. x^e = pow(y, -1, N) 4. x = pow(x^e, pow(e, -1, φ(N)), N) 5. cur = x.to_bytes(24, 'big')返回 cur.hex().upper()脚本
import hashlib
# ----- 参数 -----N = 0x56f67550f16a00390dcf0b2715708e61c5b3f23101862fc1p = 46942075831425428541187578011q = 45424490472579293708671645907assert p * q == Nphi = (p - 1) * (q - 1)
EXPONENTS = [3, 7, 11, 17, 19, 23, 29, 31, 37]# 全部 stage 都是模逆（x^{-e} mod N）ALL_INVERSE = True # 如果以后发现有不逆的，可以改为列表
def inc4(data: bytes) -> bytes: """缓冲区前4字节小端解释 +1，然后写回""" buf = bytearray(data) val = int.from_bytes(buf[:4], 'little') val = (val + 1) & 0xFFFFFFFF buf[:4] = val.to_bytes(4, 'little') return bytes(buf)
def dec4(data: bytes) -> bytes: """inc4 的逆操作""" buf = bytearray(data) val = int.from_bytes(buf[:4], 'little') val = (val - 1) & 0xFFFFFFFF buf[:4] = val.to_bytes(4, 'little') return bytes(buf)
def forward(code_hex: str) -> bytes: buf = bytes.fromhex(code_hex) assert len(buf) == 24 for e in EXPONENTS: x = int.from_bytes(buf, 'big') # 全部 stage：先 x^e 再取逆 y = pow(x, e, N) y = pow(y, -1, N) # x^{-e} buf = inc4(y.to_bytes(24, 'big')) return buf
def solve_for_username(username: str) -> str: md5 = hashlib.md5(username.encode()).digest() target = b'Ginkgo26' + md5 cur = target for e in reversed(EXPONENTS): buf = dec4(cur) y = int.from_bytes(buf, 'big') # 正向是 y = (x^e)^{-1} = x^{-e} # 所以 a = y^{-1} = x^e a = pow(y, -1, N) # 求 e 次根 d = pow(e, -1, phi) x = pow(a, d, N) cur = x.to_bytes(24, 'big') return cur.hex().upper()
if __name__ == '__main__': # 验证公开样例 pub_name = 'D07B8307A5B4240F' pub_code = '1C88187098D29DEF801A192D0419A1A0F9AC83308EB6D7EB' expected = (b'Ginkgo26' + hashlib.md5(pub_name.encode()).digest()).hex().upper()
computed = forward(pub_code).hex().upper() print(f'[+] forward(pub_code) = {computed}') print(f' 期望 target = {expected}') assert computed == expected, "正向验证失败！" solved = solve_for_username(pub_name) print(f'[+] reverse(pub_name) = {solved}') assert solved == pub_code, "逆向验证失败！" print('公开样例验证通过 ✓\n')
# 目标用户名 user = '3xyyy' result = solve_for_username(user) print(f'[+] 用户名 "{user}" 的序列号：') print(f' {result}')
final_target = forward(result).hex().upper() expected_target = (b'Ginkgo26' + hashlib.md5(user.encode()).digest()).hex().upper() assert final_target == expected_target, "最终结果验证失败！" print('正向验证通过，序列号正确 ✓')re4
初步查看这是一个 网页 wasm 逆向
script.js 加载 vault.wasm，将用户输入写入 mem[0]，调用 unlock() 返回 0/1。
const { unlock, memory } = await WebAssembly.instantiate(bytes, { env: { x(n) { let r=0; while(n){r^=n&1;n>>>=1;} return r; } }});// 输入写入 mem[0]，null 终止，调用 unlock()2. 去混淆
WASM 中 390 处 call 0(N) = env.x(N)。这是不透明谓词——常量 N 的奇偶性在编译时已确定。
wasm2c vault.wasm -o vault.c # 反编译为 Cpython deobfuscate_c.py # 替换 390 处奇偶调用为 0/13. 算法还原
去混淆后 f22 比对逻辑：
if (mem[1536] != mem[3584]) return 0; // counter 必须相等n = (mem[1536] + 7) / 8; // 比对字节数for (i=0; i<n; i++) if (mem[1540+i] != mem[3588+i]) return 0; // 逐字节比对return 1;mem[3584] = 435 → 比对 55 字节。期望数据在 mem[3588]。
4. 编码算法
f2: 统计输入字符频率，额外加入 \0 (频率=1) 作为终止符f15/f16: 用频率构建 Huffman 树f19: preorder 写树到 bit 流 internal node → 写 1 leaf node → 写 0，然后写 8-bit 字符值（LSB-first）f21/f20: 对每个输入字符按 Huffman 树路径编码（0=left, 1=right），最后编码 \0f18: 整包 MSB-first 写入字节，总 bit 数 = counterf22: 比对 counter 和打包字节5. 解码
from pwn import * # 仅用于 bytes.fromhex
exp = bytes.fromhex("""f6 30 9b 00 1b 2e c6 17 31 38 ad 21 56 86 33 5bcb ee cc 16 43 8a 6d 68 0c d1 84 ca b1 38 95 1d68 74 5d c1 6b db 91 f9 fe 48 6b 72 a8 39 83 7c1e ec eb 3c 6e bc 80""")
# 1. 提取 435 个 bit (MSB-first)bits = []for b in exp: bits += [(b >> (7 - i)) & 1 for i in range(8)]bits = bits[:435]
# 2. 解析 Huffman 树 (preorder)class Node: def __init__(self, v=None, l=None, r=None): self.v, self.l, self.r = v, l, r
def parse(pos): if bits[pos]: # 1 → internal l, pos = parse(pos+1) r, pos = parse(pos) return Node(l=l, r=r), pos # 0 → leaf: 读 8-bit LSB-first v = sum(bits[pos+1+i] << i for i in range(8)) return Node(v=v), pos+9
root, pos = parse(0)
# 3. 解码 flag: 0→left, 1→right, \0 终止out, n = [], poswhile n < 435: node = root while node.v is None: # 走到叶节点 node = node.r if bits[n] else node.l n += 1 if node.v == 0: break # \0 终止 out.append(node.v)
print(bytes(out).decode()) # GKCTF{3ee36850-3949-4c0f-88c1-de1d2040a572}6. Flag
GKCTF{3ee36850-3949-4c0f-88c1-de1d2040a572}验证: Result: 1, counter=435, 55/55 bytes match。
分享
如果这篇文章对你有帮助，欢迎分享给更多人！
部分信息可能已经过时
相关文章 智能推荐