ciruit map题目构成
block_cipher.py: 24-bit SPN。encrypt_data = 3 轮 (XOR key→S(6×4bit)→P(24bit)) + 末 XOR key。encrypt(m,k1,k2)=Ed(Ed(m,k1),k2)（k1 内层、k2 外层）；decrypt 相应。
yao_circuit.py: 每 wire 两个 24-bit label；garble_label(k0,k1,k2)=(encrypt(k2,k0,k1), encrypt(0,k0,k1))，第二项 validation 行 = Ed(Ed(0,k0),k1) —— 是本解法的 oracle。
circuit_map.json: AND(1,2)->5; AND(3,4)->6; AND(5,6)->7; XOR(7,4)->9; out=[9]。
public_data.py: 真实 G_Table（gate 5,6,7,9 各 4 行 (gl, validation)）。
task.py: the_chaos = concat(long_to_bytes(sum(keys[i])) for i in keys)；mask=md5(the_chaos)；flag_ct = xor(mask,flag).hex() = 1661fe85c7b01b3db1d432ad3c5ac83a；private_data.py（keys/flag）未下发。
攻击步骤
向量化 SPN（numpy int32，全空间 2^24 单遍 ~5-6s）。T[a]=Ed(0,a) 全局一次；U_r[b]=Dd(v_r,b) 每 gate 每行一次。
结构搜索（每 gate 6 个规范行配对模式 (i,j,k,l)：i,j 共享 a0/t0，k,l 共享 a1/t1，b0 跨 (i,k)、b1 跨 (j,l)）：key=(U_i[b0]<<24 | U_k[b0]) 与 (U_j[b1]<<24 | U_l[b1]) 交集 ⇒ t0=U_i[b0]=U_j[b1]、t1=U_k[b0]=U_l[b1]；t0,t1 必须在 imT 内 ⇒ a0=preimage(t0)、a1=preimage(t1)；b0,b1 即 wire-b 两标签（任取 witness）。单 witness 方案不可行（preimage 类平均 1.58，碰撞丢真结构）；排序连接一次覆盖全部 witness。
gl 校验：decrypt(gl,k0,k1) 必须符合 AND/XOR 真值表值模式，角色无关地给出wire_a/wire_b=(FALSE,TRUE)、out=(k2_0,k2_1)。AND 唯一；XOR 有 4 重真值歧义。
跨 gate 拼接：wire5=gate5.out==gate7.wa；wire6=gate6.out==gate7.wb；wire7=gate7.out==gate9.wa；wire4=gate6.wb==gate9.wb —— 得到唯一全局 keys。
flag：keys 迭代顺序 = gen_key.py set 构造（CPython 3.12 实测 [1,2,3,4,5,6,7,9]）；the_chaos/md5/xor 解明文；若顺序不符则按 SCTF{} 可打印枚举 9!。
关键参数（真实数据）
T=Ed(0,a) 建表约 14s；每 gate 的 4 个 U_r=Dd(v_r,b)（各 2^24）约 20-31s。
6 个规范行配对模式 sort-join（int64 打包 key=(t0<<24|t1) + 交集）每 gate 约 363-453s
（结构候选数（真实数据）：gate5=23、gate6=4、gate7=26、gate9=15；gl 校验后 AND 各 1、XOR 4（真值歧义）。跨 gate 拼接唯一全局解；总求解 1645-1778s。
单行 b→Dd(v,b) 像覆盖率约 62%（Poisson(1) preimage 类），故单 witness 方案必失败。
结果
解密明文:
#@DE-is-not-EZ@#（md5(mask) 直接还原可打印文本）最终 flag:
SCTF{#@DE-is-not-EZ@#}迭代顺序：CPython set 构造实测 [1,2,3,4,5,6,7,9]（9! 枚举无 SCTF 形态，确认该格式）
恢复 keys（wire: (FALSE标签, TRUE标签)）：1:(8343801,13675268) 2:(10251687,12870274) 3:(6827786,12490757) 4:(2096572,3391233)5:(15707475,4567418) 6:(14095476,3648155) 7:(14409690,8680011) 9:(9376523,2504390)
校验： validate_the_circuit(G_Table[9], keys7, keys4)==keys9通过；4 gate × 4 真值组合用恢复 labels 重放 (gl,v) 与 public_data.py 完全一致。
复现
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
solve_yao.py — 恢复 Yao 混淆电路全部 wire labels（24-bit SPN 双重加密），解出 flag。
挑战: ciruit map/
block_cipher.py : 24-bit SPN; encrypt(m,k1,k2)=Ed(Ed(m,k1),k2); 同理 decrypt
yao_circuit.py : garble_label(k0,k1,k2) = ( encrypt(k2,k0,k1), encrypt(0,k0,k1) )
第二项即 validation 行 => 可由 MITM 分解 (k0,k1)
public_data.py : 真实 G_Table (gate 5,6,7 AND; gate 9 XOR) 每 gate 4 行 (gl, validation)
task.py : the_chaos = concat(long_to_bytes(sum(keys[i])) for i in keys)
mask = md5(the_chaos); flag_ct = xor(mask,flag) = 1661fe85...
攻击:
对每个 gate 每行 validation v = Ed(Ed(0,k0),k1):
T[a] = Ed(0,a) 一次建表
U_r[b] = Dd(v_r,b) 每行一次
bp_r[a] = 能使 Dd(v_r,b)=Ed(0,a) 的 b (witness)
结构搜索: 4 行按 (a0,w1),(a0,w2),(a1,w1),(a1,w2) 配对, x=U_r3[b1]==y=U_r4[b2] 且
Ed(0,a1)=x => 候选 (a0,a1,w1,w2)
gl 校验: decrypt(gl, ka, kb) 必须符合 AND/XOR 真值表模式 => 唯一确定 labels
跨 gate: wire4/5/6/7 共享标签拼接 => keys
flag: 按 gen_key.py 的 set 迭代顺序 [1..9] 重建 the_chaos -> md5 -> xor
"""
import os, sys, json, time, hashlib, random
import numpy as np
HERE = os.path.dirname(os.path.abspath(__file__))
CDIR = os.path.join(HERE, "ciruit map")
sys.path.insert(0, CDIR)
from block_cipher import encrypt_data, decrypt_data, encrypt, decrypt, \
SBoxes, SInvBoxes, PBox, PInvBox
from Crypto.Util.number import long_to_bytes
SB = np.array(SBoxes, dtype=np.int32) # (6,16)
SIB = np.array(SInvBoxes, dtype=np.int32)
PB = np.array(PBox, dtype=np.int32)
PIB = np.array(PInvBox, dtype=np.int32)
SPACE = 2**24 # 24-bit label space
def S_arr(x, tab=SB):
out = np.zeros(x.shape[0], dtype=np.int32)
for i in range(6):
out |= tab[i][(x >> (4 * i)) & 15] << (4 * i)
return out
def P_arr(x, pb=PB):
out = np.zeros(x.shape[0], dtype=np.int32)
for i in range(24):
out |= ((x >> pb[i]) & 1) << i
return out
def Ed_arr(x, k):
"""encrypt_data vectorized over block array x, scalar key k."""
b = x
for _ in range(3):
b = P_arr(S_arr(b ^ k))
return b ^ k
def Dd_arr(x, k):
"""decrypt_data vectorized."""
b = x ^ k
for _ in range(3):
b = S_arr(P_arr(b, PIB), SIB)
b = b ^ k
return b
# ---- global T-table: T[a] = Ed(0, a), and its inverse ----
def build_T():
t0 = time.time()
a = np.arange(SPACE, dtype=np.int32)
T = Ed_arr(np.zeros(SPACE, dtype=np.int32), a) # T[a] = Ed(0, a): block 0, key a
order = np.argsort(T, kind="stable").astype(np.int32)
sT = T[order]
print(f"[T] Ed(0,a) for a in [0,{SPACE}) done in {time.time()-t0:.1f}s")
return T, order, sT
def preimages(sT, order, t):
lo = int(np.searchsorted(sT, t, "left"))
hi = int(np.searchsorted(sT, t, "right"))
return [int(x) for x in order[lo:hi]]
def gl_check(gtype, G, a0, a1, w1, w2, r1, r2, r3, r4):
"""combo->row map: r1=(a0,w1), r2=(a0,w2), r3=(a1,w1), r4=(a1,w2).
角色无关: 由 gl 实际解密值判定 TRUE/FALSE 标签, 不预设 w1/w2 与 a0/a1 的真假。
返回 wire_a/wire_b = (FALSE标签, TRUE标签); out = (k2_0, k2_1)。"""
rows = {r1: (a0, w1), r2: (a0, w2), r3: (a1, w1), r4: (a1, w2)}
k2 = {}
for r, (ka, kb) in rows.items():
k2[r] = decrypt(G[r][0], ka, kb)
v1, v2, v3, v4 = k2[r1], k2[r2], k2[r3], k2[r4]
if gtype == "AND":
# 唯一异值行 = (TRUE,TRUE) 组合
agg = {}
for val, r in ((v1, r1), (v2, r2), (v3, r3), (v4, r4)):
agg.setdefault(val, []).append(r)
if len(agg) != 2:
return None
gs = sorted(agg.items(), key=lambda kv: len(kv[1]))
if len(gs[0][1]) != 1 or len(gs[1][1]) != 3:
return None
diff_val, common_val = gs[0][0], gs[1][0]
diff_row = gs[0][1][0]
a_true, b_true = rows[diff_row]
a_false = a1 if a_true == a0 else a0
b_false = w2 if b_true == w1 else w1
return [{"wire_a": (a_false, a_true), "wire_b": (b_false, b_true),
"out": (common_val, diff_val)}]
else: # XOR: 反斜线等值: (r1==r4, r2==r3) 且两组不同
if v1 == v4 and v2 == v3 and v1 != v2:
# 4 重真值歧义: a 真值 2 选 x b 真值 2 选, 全部与 gl 值自洽;
# 由跨 gate 拼接与 flag 可打印性消解。out=(k2_0,k2_1) 随 (ta0==tw1) 翻转。
out = []
for t_a0 in (0, 1):
for t_w1 in (0, 1):
wire_a = (a0, a1) if t_a0 == 0 else (a1, a0)
wire_b = (w1, w2) if t_w1 == 0 else (w2, w1)
k20, k21 = (v1, v2) if (t_a0 == t_w1) else (v2, v1)
vv = {"wire_a": wire_a, "wire_b": wire_b, "out": (k20, k21)}
if vv not in out:
out.append(vv)
return out
return []
def solve_gate(gid, gtype, G, T, order, sT, sImT=None):
"""结构搜索: 对 gate 的 4 行做 (a,b) 标签恢复。
原理: 行 r 的 validation v_r 满足 Dd(v_r, b) = Ed(0, a) 当且仅当 (a,b) 是该行 combo。
对每行 r 预计算 U_r[b] = Dd(v_r, b) (b in [0,2^24))。
真结构 4 行 = (A0,B0),(A0,B1),(A1,B0),(A1,B1) 的某个置换。
6 个规范行配对模式 (i,j,k,l) (i,j 共享 a0/t0, k,l 共享 a1/t1, b0 跨 (i,k), b1 跨 (j,l)):
包 key = (U_i[b0]<<24 | U_k[b0]), B 侧 (U_j[b1]<<24 | U_l[b1]);
交集 => t0=U_i[b0]=U_j[b1] (t0 须在 imT 内以保证 a0=preimage(t0)) 且 t1 同理。
排序连接处理全部 (b0,b1) witness 分类, 不受单 witness 碰撞影响。
"""
t0t = time.time()
vals = np.array([v for _gl, v in G], dtype=np.int32)
a = np.arange(SPACE, dtype=np.int32)
Us = [Dd_arr(np.full(SPACE, int(v), dtype=np.int32), a) for v in vals]
t1t = time.time()
print(f"[gate {gid}] U_r built in {t1t-t0t:.1f}s, sort-join...")
if sImT is None:
sImT = np.sort(np.unique(T)).astype(np.int32)
n = len(sImT) - 1
def inT(x):
p = np.searchsorted(sImT, x)
pc = np.clip(p, 0, n)
return sImT[pc] == x
cands = {}
# 6 canonical patterns: partitions of rows into {i,j}|{k,l}
patterns = [(0, 1, 2, 3), (0, 1, 3, 2),
(0, 2, 1, 3), (0, 2, 3, 1),
(0, 3, 1, 2), (0, 3, 2, 1)]
for (i, j, k, l) in patterns:
u0, u1 = Us[i], Us[k]
msk = inT(u0) & inT(u1)
b0s = np.nonzero(msk)[0].astype(np.int32)
if len(b0s) == 0:
continue
keyA = (u0[b0s].astype(np.int64) << 24) | u1[b0s].astype(np.int64)
u2, u3 = Us[j], Us[l]
msk2 = inT(u2) & inT(u3)
b1s = np.nonzero(msk2)[0].astype(np.int32)
if len(b1s) == 0:
continue
keyB = (u2[b1s].astype(np.int64) << 24) | u3[b1s].astype(np.int64)
orderA = np.argsort(keyA, kind="stable")
sortA = keyA[orderA]
b0A = b0s[orderA]
orderB = np.argsort(keyB, kind="stable")
sortB = keyB[orderB]
b1B = b1s[orderB]
pos = np.searchsorted(sortB, sortA)
posc = np.clip(pos, 0, len(sortB) - 1)
m = sortB[posc] == sortA
for q in np.nonzero(m)[0]:
key = int(sortA[q])
t0v, t1v = key >> 24, key & 0xFFFFFF
b0v = int(b0A[q])
qb = int(np.searchsorted(sortB, key, "left"))
b1v = int(b1B[qb])
for a0v in preimages(sT, order, t0v):
for a1v in preimages(sT, order, t1v):
cands[(a0v, a1v, b0v, b1v)] = (i, j, k, l)
t2t = time.time()
print(f"[gate {gid}] structure candidates: {len(cands)} ({t2t-t1t:.1f}s), gl check...")
results = []
for (a0v, a1v, b0v, b1v), (i, j, k, l) in cands.items():
res = gl_check(gtype, G, a0v, a1v, b0v, b1v, i, j, k, l)
for r in (res or []):
if r not in results:
results.append(r)
print(f"[gate {gid}] gl-consistent label sets: {len(results)} ({time.time()-t2t:.1f}s)")
return results
def load_public():
import importlib.util
spec = importlib.util.spec_from_file_location("public_data", os.path.join(CDIR, "public_data.py"))
mod = importlib.util.module_from_spec(spec)
spec.loader.exec_module(mod)
return mod.G_Table
# ----------------- flag decode -----------------
def decode_flag(keys, order=None):
if order is None:
order = [1, 2, 3, 4, 5, 6, 7, 9] # CPython set 迭代顺序（已在本地复现验证）
chaos = b"".join(long_to_bytes(int(keys[i][0]) + int(keys[i][1])) for i in order)
mask = hashlib.md5(chaos).digest()
ct = bytes.fromhex("1661fe85c7b01b3db1d432ad3c5ac83a")
flag = bytes(a ^ b for a, b in zip(mask, ct))
return flag, chaos
def printable_check(flag):
return all(32 <= c < 127 for c in flag) and b"SCTF{" in flag[:6] and flag.endswith(b"}")
def try_order_enumeration(keys):
"""fallback: 枚举 9! 迭代顺序, 校验 flag 可打印 / SCTF{..} 格式"""
wires = [1, 2, 3, 4, 5, 6, 7, 9]
import itertools
sums = {i: keys[i][0] + keys[i][1] for i in wires}
ct = bytes.fromhex("1661fe85c7b01b3db1d432ad3c5ac83a")
for perm in itertools.permutations(wires):
chaos = b"".join(long_to_bytes(sums[i]) for i in perm)
mask = hashlib.md5(chaos).digest()
flag = bytes(a ^ b for a, b in zip(mask, ct))
if printable_check(flag):
return flag, perm
return None, None
# ----------------- self-test -----------------
def self_test():
print("=" * 60)
print("SELF-TEST: 生成合成 private keys/G_Table, 验证恢复")
print("=" * 60)
import random as rnd
rnd.seed(20240824)
circuit = json.load(open(os.path.join(CDIR, "circuit_map.json")))
keys_truth = {}
for w in [1, 2, 3, 4, 5, 6, 7, 9]:
keys_truth[w] = (rnd.randrange(SPACE), rnd.randrange(SPACE))
from yao_circuit import GarbledGate
G_Table = {g["id"]: GarbledGate(g, keys_truth) for g in circuit["gates"]}
myflag = b"SCTF{s3lfT3st!!}" # 16 bytes
order = [1, 2, 3, 4, 5, 6, 7, 9]
chaos = b"".join(long_to_bytes(keys_truth[i][0] + keys_truth[i][1]) for i in order)
ct = bytes(a ^ b for a, b in zip(hashlib.md5(chaos).digest(), myflag))
print("synthetic ct:", ct.hex())
keys = solve_all(G_Table, T, order, sT)
if not keys:
print("SELF-TEST FAILED: no consistent keys"); return False
ok = keys == keys_truth
flag = decode_flag(keys)[0]
print("recovered keys == truth:", ok)
print("decoded flag:", flag)
return ok and flag == myflag
def solve_all(G_Table, T, order, sT):
gtype = {5: "AND", 6: "AND", 7: "AND", 9: "XOR"}
R = {}
for gid in [5, 6, 7, 9]:
R[gid] = solve_gate(gid, gtype[gid], G_Table[gid], T, order, sT)
# dedupe per gate
for gid in R:
seen = []
for d in R[gid]:
if d not in seen:
seen.append(d)
R[gid] = seen
print("gate candidates:", {g: len(R[g]) for g in R})
sols = []
for c5 in R[5]:
for c6 in R[6]:
for c7 in R[7]:
if c7["wire_a"] != c5["out"] or c7["wire_b"] != c6["out"]:
continue
for c9 in R[9]:
if c9["wire_a"] != c7["out"] or c9["wire_b"] != c6["wire_b"]:
continue
keys = {1: c5["wire_a"], 2: c5["wire_b"], 3: c6["wire_a"],
4: c6["wire_b"], 5: c5["out"], 6: c6["out"],
7: c7["out"], 9: c9["out"]}
sols.append(keys)
print("cross-gate consistent global key sets:", len(sols))
return sols
if __name__ == "__main__":
mode = sys.argv[1] if len(sys.argv) > 1 else "real"
T, order, sT = build_T()
if mode == "selftest":
ok = self_test()
sys.exit(0 if ok else 1)
# real
import json as _json
G_Table = load_public()
t0 = time.time()
sols = solve_all(G_Table, T, order, sT)
print(f"solve finished in {time.time()-t0:.1f}s")
if not sols:
print("NO SOLUTION"); sys.exit(1)
keys = sols[0]
with open(os.path.join(HERE, "keys-recovered.json"), "w") as f:
_json.dump({str(w): list(v) for w, v in keys.items()}, f, indent=1)
print("keys:", keys)
print("saved -> keys-recovered.json")
for perm in ([1,2,3,4,5,6,7,9],):
flag, chaos = decode_flag(keys, perm)
print(f"flag(order={perm}):", flag, "printable:", printable_check(flag))
with open(os.path.join(HERE, "flag.txt"), "w") as f:
f.write(flag.decode("latin-1", "replace") + "\n")
# iteration-order fallback
flag, perm = try_order_enumeration(keys)
if flag:
print("order-enumeration flag:", flag, "order:", perm)
