flag 不在附件里無法獲取只能解題以下是解題過程本地工具api鋪助完成水平小菜可以擴(kuò)寬眼界和學(xué)習(xí)作用實(shí)際無法幫助提交題目從NSSCTF平臺獲取。noisy-nfsr 解題報(bào)告1. 題目概覽服務(wù)是一個提交隨機(jī)挑戰(zhàn) 會話密鑰的 oracle先過一個 4 字符[A-Za-z0-9]的 Proof-of-Work。服務(wù)器隨機(jī)生成一個12-bitLFSRseed, maskbit11 置 1用于產(chǎn)生噪聲兩個128-bitLFSRseeds[0..1],masks[0..1]bit127 置 1。打印兩個 128-bit 的masksseeds不打印。選擇參數(shù)(n, m)隨后可反復(fù)選擇[H]it用當(dāng)前seeds重置兩個 128-bit LFSR輸出m字節(jié)密鑰流[S]tand提交猜的seeds全對則打印 flag[Q]uit退出。目標(biāo)在最多n次交互內(nèi)恢復(fù)兩個 128-bitseeds。2. 組件分析2.1 LFSRdef __next__(self): b (self.state self.mask).bit_count() 1 self.state ((self.state 1) | b) (2**128 - 1) return b狀態(tài)左移、低位補(bǔ)反饋位。記狀態(tài)轉(zhuǎn)移為T第t拍反饋位b_t mask, T^t seed (GF(2) 內(nèi)積)反饋位等于輸出位因此seed - 輸出序列是 GF(2) 線性映射。2.2 NFSR組合器def __next__(self): b0, b1 self.lfsr0(1), self.lfsr1(1) return b0 ^ b1 ^ next(self.noise)輸出out L0 ^ L1 ^ y其中L0/L1是兩個 128-bit LFSR 的比特流y是噪聲流。2.3 噪聲生成器def NOISE(lfsr, p2/3): while True: if lfsr(1): yield int(rand() p) # 以 1/3 概率得到 1 else: yield int(rand() p) # 以 2/3 概率得到 1記 12-bit LFSR 第g拍輸出為c_g噪聲位為y_gP(y_g 1^c_g) 2/3, P(y_g c_g) 1/3即y_g c_g ^ e_g其中e_g是以2/3概率取 1 的錯誤位。這是本題唯一的信息泄漏點(diǎn)噪聲與一個 12-bit LFSR 強(qiáng)相關(guān)。2.4 三個關(guān)鍵結(jié)構(gòu)性質(zhì)每次Hit都會用同一seeds重置兩個 128-bit LFSR但noise生成器只創(chuàng)建一次、在整個連接內(nèi)持續(xù)前進(jìn)。每次Hit輸出m字節(jié)即P 8m比特。第k次Hit的第t位為O[k*P t] S[t] ^ y_{k*Pt}, S[t] L0[t] ^ L1[t]其中S[t]每次都一樣只有噪聲在推進(jìn)。3. 攻擊思路3.1 差分消掉未知的 S把相隔恰好一個Hit的兩位異或U[g] : O[g] ^ O[gP] y_g ^ y_{gP}S被完全消掉且U只與噪聲有關(guān)U[g] (c_g ^ c_{gP}) ^ (e_g ^ e_{gP}) C[g] ^ f_g其中C[g] c_g ^ c_{gP}f_g e_g ^ e_{gP}。由P(e1)2/3P(f_g 0) (2/3)^2 (1/3)^2 5/9 P(f_g 1) 4/9即U是C的一個以 5/9 正確的帶噪觀測。3.2 相關(guān)性恢復(fù) 12-bit 噪聲 LFSR候選噪聲 LFSR 由(mask, seed)各 12-bit最高位固定為 1確定。對候選(M, s)c_g v_g, s, v_g (T?)^g M共軛遞推adjointdef adj(y, M): return (y 1) ^ (M if (y 1) else 0)于是C[g] c_g ^ c_{gP} v_g ^ v_{gP}, s w_g, s用相關(guān)性給候選打分score(s) Σ_g [w_g, s U[g]] N/2 (1/2) Σ_g (-1)^{U[g] ^ w_g,s}對正確候選該項(xiàng)期望約為N/9隨機(jī)候選約為 0。關(guān)鍵優(yōu)化固定M時w_g只依賴M先做統(tǒng)計(jì)H[w] Σ_{g : w_g w} (-1)^{U[g]}再對 4096 長的H做一次Fast Walsh–Hadamard TransformFWT(H)[s] Σ_w H[w] (-1)^{w, s} Σ_g (-1)^{U[g] ^ w_g, s}一次 FWT 就同時評估該 mask 下全部 2048 個合法 seed。外層枚舉 2048 個 mask總計(jì)約2048 × (build O(212·12))幾秒完成。3.3 多數(shù)表決恢復(fù) S得到正確噪聲 LFSRc后用?_g 1 ^ c_g作為噪聲預(yù)測正確率 2/3構(gòu)造pred_g O[g] ^ (1 ^ c_g) S[t] ^ (1 ^ e_g)對固定的t跨所有Hit做多數(shù)表決S[t] majority_k ( O[k*P t] ^ (1 ^ c_{k*Pt}) )每一票正確率 2/3h n-1 255票下誤碼率約10??/bit2048 位幾乎必然全對。3.4 線性求解兩個 128-bit 種子已知兩個掩碼L0/L1輸出對seed線性。對每一talpha0_t, seed0 ^ alpha1_t, seed1 S[t]其中alpha0_t / alpha1_t分別是兩個 128-bit mask 的 adjoint 軌道(T?)^t mask。疊加seed 最高位為 1這一仿射約束把seed 212? | x代入得到254 個未知數(shù)、P 2048個方程的超定 GF(2) 線性系統(tǒng)用位掩碼高斯消元求解。4. 兩處退化情形及處理4.1 種子映射非單射必須換連接極少數(shù)隨機(jī)掩碼對會令映射(seed0, seed1) - S出現(xiàn)核實(shí)測約15%即存在(δ0, δ1) ≠ 0使L0(δ0) ^ L1(δ1) ≡ 0從而兩個不同的種子對產(chǎn)生完全相同的密鑰流信息論上無法區(qū)分。處理在讀入masks后立即計(jì)算該映射的秩rank_sub若 254直接重連換一組掩碼。4.2 噪聲 LFSR 的 P-周期歧義相關(guān)性只能確定C[g] c_g ^ c_{gP}因此噪聲 LFSR 只被確定到相差一個P-周期序列d且c ^ d仍是合法 12-bit LFSR 輸出。用 V-一致性過濾一個候選只有當(dāng)它導(dǎo)出的解滿足線性系統(tǒng)完全一致殘差為 0時才接受若這樣的候選不唯一說明本連接存在等價解釋直接重連。5. 參數(shù)選擇項(xiàng)值說明args索引1對應(yīng)(n, m) (256, 256)P 8m2048每次Hit的密鑰流長度bith n-1255先做 255 次Hit最后一次用于提交N12000相關(guān)性使用的U長度正解約N/9 ≈ 1333隨機(jī)約±110候選閾值G - 5√N(yùn)保證納入真解同時排除隨機(jī)峰6. 實(shí)現(xiàn)解題腳本solve_cn.py#!/usr/bin/env python3 # -*- coding: utf-8 -*- noisy-nfsr 解題腳本 【密碼學(xué)分析】 每次 Hit 輸出 S[t] L0[t] ^ L1[t] ^ y[t]其中 * L0、L1 是兩個 128-bit LFSR**每次 Hit 都用同一組 seeds 重置** * y 是噪聲流由一個獨(dú)立的 12-bit LFSR 產(chǎn)生其 seed/mask 都是 12 位、 最高位 bit11 為 1且不打印出來。 12-bit 噪聲 LFSR 的第 g 拍輸出 c_g 讓噪聲位滿足 P(y_g 1 ^ c_g) 2/3 , P(y_g c_g) 1/3 也就是 y_g c_g ^ e_ge_g 以 2/3 概率取 1。 因?yàn)閮蓚€ 128-bit LFSR 每次 Hit 都重置、而噪聲發(fā)生器在整條連接里持續(xù)前進(jìn) 所以把相隔一個 HitP 8*m 位的兩比特異或即可消掉 S O[g] ^ O[gP] y_g ^ y_{gP} (c_g ^ c_{gP}) ^ (e_g ^ e_{gP}) 這就得到 C[g] c_g ^ c_{gP} 的一個“帶噪觀測”于是可以用相關(guān)性攻擊恢復(fù) 那個 12-bit 噪聲 LFSR對每個候選 mask 做一次快速沃爾什-哈達(dá)瑪變換一次性 評估全部 4096 個 seed。 知道噪聲 LFSR 后就能預(yù)測 y對每條 Hit 做多數(shù)表決還原 S[t]每票 2/3 正確 再解 GF(2) 線性方程組 L0[seed0][t] ^ L1[seed1][t] S[t] 得到兩個 128-bit 種子兩者最高位恒為 1。 【兩處退化情形】 1. 映射 (seed0, seed1) - S 偶爾不是單射約 15% 的隨機(jī)掩碼對會出現(xiàn)多個 等價種子對信息論上無法區(qū)分 —— 用 rank_sub 提前檢測命中就換連接。 2. 噪聲 LFSR 只能確定到一個 P-周期的等價類 —— 枚舉所有候選只接受能令線性 系統(tǒng)**一致且唯一**的那個否則重連。 import sys import os import re import time import socket import hashlib import string import itertools import subprocess import shutil import tempfile try: # Windows 控制臺cp936/cp1252下避免打印崩潰 sys.stdout.reconfigure(encodingutf-8, errorsreplace) sys.stderr.reconfigure(encodingutf-8, errorsreplace) except Exception: pass # args 取索引 1 - (n, m) (256, 256) ARGS_INDEX 1 M_BYTES 256 P_HIT 8 * M_BYTES # 每次 Hit 產(chǎn)出的密鑰流比特?cái)?shù) N_HITS 256 # 主循環(huán)次數(shù) n H_HITS N_HITS - 1 # 先做 255 次 Hit最后一次用于提交 N_RECOVER 12000 # 相關(guān)性攻擊使用的 U 長度 MAX_TRIES 12 # 最多重連次數(shù) PLACEHOLDER_FLAG flag{no_local_flag_file__seeds_are_correct} # -------------------------------------------------------------------------- # GF(2) 基礎(chǔ)工具 # -------------------------------------------------------------------------- def adj(y, M): 共軛adjointLFSR 的一步計(jì)算 (T^T) y。 return (y 1) ^ (M if (y 1) else 0) def fwt(H): 原地快速沃爾什-哈達(dá)瑪變換長度 4096。 mm 1 n len(H) while mm n: for i in range(0, n, mm * 2): for j in range(i, i mm): x H[j] y H[j mm] H[j] x y H[j mm] x - y mm * 2 return H def _seq_info(M): 返回掩碼 M 的共軛軌道 (序列, 預(yù)周期長度, 周期長度)。 seen {} v [] y M while True: s seen.get(y, -1) if s 0: return v, s, len(v) - s seen[y] len(v) v.append(y) y adj(y, M) def _build_H(M, signs, P, N): 累加 H[w] Σ_{g : v_g ^ v_{gP} w} signs[g]。 v, start, L _seq_info(M) # 周期性部分r 為 (g-start) mod L wres [v[start r] ^ v[start ((r P) % L)] for r in range(L)] H [0] * 4096 # 預(yù)周期start 之前的部分單獨(dú)處理 for g in range(start): t2 g P w v[g] ^ v[t2] if t2 len(v) else v[g] ^ v[start ((t2 - start) % L)] H[w] signs[g] r 0 for g in range(start, N): H[wres[r]] signs[g] r 1 if r L: r 0 return H def scan(U, P, N): 對每個 12-bit mask 返回 (最高相關(guān)分, mask, 最優(yōu) seed)。 signs [1 if x 0 else -1 for x in U] res [] for M in range(2048, 4096): # seed/mask 最高位為 1只需枚舉 2048..4095 H fwt(_build_H(M, signs, P, N)) bi 2048 bv H[2048] for s in range(2049, 4096): if H[s] bv: bv H[s] bi s res.append((bv, M, bi)) return res def enumerate_hi(M, U, P, N, thr): 列出 mask M 下所有相關(guān)分 thr 的 seed。 signs [1 if x 0 else -1 for x in U] H fwt(_build_H(M, signs, P, N)) return [(H[s], M, s) for s in range(2048, 4096) if H[s] thr] def rank_sub(mask0, mask1, P): (seed0,seed1) - S 映射的秩兩個種子最高位固定為 1。 LOW (1 127) - 1 a0, a1 mask0, mask1 piv {} for _ in range(P): c (a0 LOW) | ((a1 LOW) 127) a0 (a0 1) ^ (mask0 if (a0 1) else 0) a1 (a1 1) ^ (mask1 if (a1 1) else 0) cc c while cc: b cc.bit_length() - 1 if b in piv: cc ^ piv[b] else: piv[b] cc break return len(piv) def solve_residual(R, P, mask0, mask1): 解線性系統(tǒng)返回 (不一致方程條數(shù), seed0, seed1)。 LOW (1 127) - 1 a0, a1 mask0, mask1 piv {} resid 0 for t in range(P): # 第 t 個方程alpha0_t, seed0 ^ alpha1_t, seed1 R[t] rhs R[t] ^ ((a0 127) 1) ^ ((a1 127) 1) # 去掉最高位恒為 1的貢獻(xiàn) coeff (a0 LOW) | ((a1 LOW) 127) a0 (a0 1) ^ (mask0 if (a0 1) else 0) a1 (a1 1) ^ (mask1 if (a1 1) else 0) c, r coeff, rhs while c: b c.bit_length() - 1 pv piv.get(b) if pv is None: piv[b] (c, r) break c ^ pv[0] r ^ pv[1] else: if r: resid 1 # 系數(shù)消光但右端為 1 - 不一致 # 回代按主元從低位到高位求值 sol 0 for b in sorted(piv): c, r piv[b] if r ^ ((c sol).bit_count() 1): sol | (1 b) return resid, (sol LOW) | (1 127), ((sol 127) LOW) | (1 127) def _majority_R(out, h, P, mask, seed): 用候選噪聲 LFSR 預(yù)測噪聲再對每條 Hit 做多數(shù)表決得到 R。 cnt [0] * P st seed t 0 for g in range(h * P): b (st mask).bit_count() 1 # 12-bit 噪聲 LFSR 輸出 c_g st ((st 1) | b) 0xFFF cnt[t] out[g] ^ (1 ^ b) # 預(yù)測 ? 1 ^ c_g t 1 if t P: t 0 half h / 2.0 return bytearray(1 if c half else 0 for c in cnt) def solve_keystream(out, h, P, N, mask0, mask1, verboseTrue): 恢復(fù)兩個種子無法唯一確定時返回 None由調(diào)用方重連。 # 差分U[g] O[g] ^ O[gP] y_g ^ y_{gP} U bytes(out[g] ^ out[g P] for g in range(N)) t0 time.time() per scan(U, P, N) if verbose: print([*] 噪聲相關(guān)性掃描完成用時 %.1fs % (time.time() - t0)) G max(bv for bv, _, _ in per) thr G - 5 * int(N ** 0.5) # 閾值真解約在 G 附近隨機(jī)峰約 ±√N(yùn) cands [] for bv, M, s in per: if bv thr: cands enumerate_hi(M, U, P, N, thr) if verbose: print([*] 閾值以上共有 %d 個候選噪聲 LFSR % len(cands)) # 只保留能讓線性系統(tǒng)“完全一致”的候選 good [] for val, M, s in cands: R _majority_R(out, h, P, M, s) resid, x0, x1 solve_residual(R, P, mask0, mask1) if resid 0: good.append((x0, x1)) if len(good) 1: return good[0] if verbose: print([!] 一致候選有 %d 個存在等價解- 重連 % len(good)) return None def solve_pow(suffix, target_hex): 暴力 4 字符前綴使 sha256(prefix suffix) target。 target bytes.fromhex(target_hex) alph (string.ascii_letters string.digits).encode() suf suffix.encode() for tup in itertools.product(alph, repeat4): cand bytes(tup) if hashlib.sha256(cand suf).digest() target: return cand.decode() return None # -------------------------------------------------------------------------- # 傳輸層socket遠(yuǎn)程或子進(jìn)程本地 # -------------------------------------------------------------------------- class SocketTube: def __init__(self, host, port, timeout300): self.s socket.create_connection((host, port), timeouttimeout) self.buf b def recvuntil(self, marker): if isinstance(marker, str): marker marker.encode() while marker not in self.buf: d self.s.recv(65536) if not d: raise EOFError(連接已關(guān)閉) self.buf d i self.buf.index(marker) len(marker) res, self.buf self.buf[:i], self.buf[i:] return res def sendline(self, x): if isinstance(x, str): x x.encode() self.s.sendall(x b\n) def close(self): try: self.s.close() except OSError: pass class ProcTube: def __init__(self, argv, cwd): env dict(os.environ) env[PYTHONIOENCODING] utf-8 # 子進(jìn)程要打印 控制臺可能是 gbk env[PYTHONUTF8] 1 self.p subprocess.Popen(argv, cwdcwd, stdinsubprocess.PIPE, stdoutsubprocess.PIPE, stderrsubprocess.STDOUT, envenv) self.buf b def recvuntil(self, marker): if isinstance(marker, str): marker marker.encode() while marker not in self.buf: d self.p.stdout.read1(65536) if not d: raise EOFError(子進(jìn)程已退出最后輸出: %r % self.buf[-600:]) self.buf d i self.buf.index(marker) len(marker) res, self.buf self.buf[:i], self.buf[i:] return res def sendline(self, x): if isinstance(x, str): x x.encode() self.p.stdin.write(x b\n) self.p.stdin.flush() def close(self): try: self.p.kill() except OSError: pass # -------------------------------------------------------------------------- # 一次完整交互 # -------------------------------------------------------------------------- def run_attempt(tube, verboseTrue): 跑一次協(xié)議流程成功返回 flag 字符串否則返回 None。 # 1) Proof-of-Work banner tube.recvuntil(XXXX) m re.search(rbsha256\(XXXX \ (.{16})\) ([0-9a-f]{64}), banner) if not m: raise RuntimeError(無法解析 PoW: %r % banner[:200]) suffix, target m.group(1).decode(), m.group(2).decode() if verbose: print([*] 解 PoW后綴 %r % suffix) tube.sendline(solve_pow(suffix, target)) # 2) 讀取打印出來的兩個 128-bit 掩碼 chunk tube.recvuntil(args) nums re.findall(rb\d{10,}, chunk) if len(nums) 2: raise RuntimeError(無法解析 masks: %r % chunk[:200]) mask0, mask1 int(nums[0]), int(nums[1]) if verbose: print([*] mask0%d mask1%d % (mask0, mask1)) # 3) 秩門控非單射就換連接否則種子對不唯一 if rank_sub(mask0, mask1, P_HIT) ! 254: if verbose: print([!] 該掩碼對下種子映射非單射 - 重連) return None # 4) 選參數(shù)收集 255 次 Hit 的密鑰流 tube.sendline(str(ARGS_INDEX)) tube.recvuntil(| inp) # 先吃掉第一個菜單提示 out bytearray() for _ in range(H_HITS): tube.sendline(h) resp tube.recvuntil(| inp) hx re.search(rbbits\.hex\(\) ([0-9a-f]), resp) out bytes.fromhex(hx.group(1).decode()) if verbose: print([*] 已收集 %d 字節(jié)密鑰流 % len(out)) # 字節(jié) - 比特每字節(jié)高位在前和程序 self(8) 的順序一致 bits bytearray() for byte in out: for k in range(7, -1, -1): bits.append((byte k) 1) # 5) 恢復(fù)種子 seeds solve_keystream(bits, H_HITS, P_HIT, N_RECOVER, mask0, mask1, verbose) if seeds is None: return None seed0, seed1 seeds if verbose: print([*] 恢復(fù)出 seed0%d seed1%d % (seed0, seed1)) # 6) 提交并讀 flag tube.sendline(s) tube.recvuntil(| seed) tube.sendline(str(seed0)) tube.recvuntil(| seed) tube.sendline(str(seed1)) try: tail tube.recvuntil(| Bye) except EOFError: # task.py 崩了裸 except 會打印 | Nah 后退出 tail bytes(getattr(tube, buf, b)) if verbose: print([!] 子進(jìn)程/服務(wù)在 | Bye 之前就退出了) txt tail.decode(utf-8, replace) if verbose: print(txt.encode(ascii, replace).decode(ascii)) # 控制臺安全打印 m re.search(rflag\{[^}\n]*\}, txt) if m: return m.group(0).strip() m re.search(\U0001F3C1\\s*(.), txt) # 之后的內(nèi)容 return m.group(1).strip() if m else None def _make_local_dir(src_dir, flag_pathNone): 把 task.py / utils.py 復(fù)制到臨時目錄并 - 把 POSIX 專有的 signal.alarm() 換成 pass使題目在 Windows 也能跑 - 把裸 except: 換成會打印真實(shí) traceback 的版本便于排錯 - 保證存在一個 flag 文件沒有就寫占位。 用戶自己的文件不會被修改。 d tempfile.mkdtemp(prefixnfsr_local_) shutil.copy(os.path.join(src_dir, utils.py), d) with open(os.path.join(src_dir, task.py), r, encodingutf-8) as f: src f.read() src re.sub(r^[ \t]*signal\.alarm\([^)]*\)[ \t]*$, pass # signal.alarm() 已被移除僅 POSIX 可用, src, flagsre.M) src re.sub(r^([ \t]*)except:[ \t]*$, r\1except Exception:\n\1 import traceback; traceback.print_exc(), src, flagsre.M) with open(os.path.join(d, task.py), w, encodingutf-8) as f: f.write(src) flag_src flag_path or os.path.join(src_dir, flag) if os.path.exists(flag_src): shutil.copy(flag_src, os.path.join(d, flag)) src_desc flag_src else: with open(os.path.join(d, flag), w) as f: f.write(PLACEHOLDER_FLAG) src_desc 占位符本地沒有 flag 文件僅驗(yàn)證種子是否正確 print([*] 臨時副本目錄: %s (flag: %s) % (d, src_desc)) return d def main(): args sys.argv[1:] local --local in args args [a for a in args if a ! --local] flag_path None if --flag in args: k args.index(--flag) flag_path args[k 1] del args[k:k 2] run_dir None if local: if not os.path.exists(task.py): print([-] --local 需要當(dāng)前目錄下有 task.py以及 utils.py) print([-] 當(dāng)前目錄: %s % os.getcwd()) return 3 run_dir _make_local_dir(os.getcwd(), flag_path) for attempt in range(1, MAX_TRIES 1): print([*] 第 %d/%d 次嘗試 % (attempt, MAX_TRIES)) if local: tube ProcTube([sys.executable, -u, task.py], cwdrun_dir) else: if len(args) 2: print(用法: solve_cn.py host port 或 --local [--flag 文件]) return 2 tube SocketTube(args[0], int(args[1])) try: flag run_attempt(tube) except KeyboardInterrupt: raise except Exception as e: import traceback print([!] 第 %d 次嘗試失敗: %r % (attempt, e)) traceback.print_exc() flag None finally: tube.close() if flag: print([] FLAG: %s % flag) if flag PLACEHOLDER_FLAG: print([i] 這只是占位符本地沒找到 flag 文件但種子已正確恢復(fù)。) print([i] 連遠(yuǎn)程solve_cn.py host port或用 --flag 文件 指定真 flag。) return 0 print([-] 已用盡嘗試次數(shù)) return 1 if __name__ __main__: sys.exit(main())solve_cn.py 命令行使用方法兩種模式1. 遠(yuǎn)程模式連真實(shí) CTF 服務(wù)器python solve_cn.py host port示例python solve_cn.py 127.0.0.1 80802. 本地模式在本地跑 task.py 驗(yàn)證邏輯python solve_cn.py --local需要當(dāng)前目錄下有task.py和utils.py。可選參數(shù)python solve_cn.py --local --flag flag文件路徑指定本地 flag 文件沒有的話用占位符flag{no_local_flag_file__seeds_are_correct}。參數(shù)說明參數(shù)說明host遠(yuǎn)程服務(wù)器地址port遠(yuǎn)程服務(wù)器端口--local本地運(yùn)行模式復(fù)制 task.py 到臨時目錄自動移除 POSIX 專有的 signal.alarm--flag 路徑指定 flag 文件路徑僅本地模式用