第三届 SHCTF 部分 Writeup

[阶段2] LicenseVerifier

拿到附件，先打开DIE查壳，发现是py打包的程，用的python版本是3.13

这道题出题的时候比较早了，当时在线网站和工具反编译都是没有任何代码的，需要写dis进行反汇编（hhh...
直接通过在线网站https://pyinstxtractor-web.netlify.app/进行解包

解包后能发现main.pyc

在线网站https://pylingual.io/进行反编译main.pyc

# Decompiled with PyLingual (https://pylingual.io)
# Internal filename: 'main.py'
# Bytecode version: 3.13.0rc3 (3571)
# Source timestamp: 1970-01-01 00:00:00 UTC (0)import os
import sys
import ctypes
import sys_core
BASE_DIR = os.path.dirname(__file__)
def _load_library(name: str) -> bool:"""Attempts to load a DLL for environment setup."""# ***<module>._load_library: Failure: Different control flowpath = os.path.join(BASE_DIR, name)if not os.path.exists(path):return Falseelse:try:lib = ctypes.WinDLL(path)for init_func in ['init_vm', 'hook_init', 'init']:if hasattr(lib, init_func):passelse:try:getattr(lib, init_func)()except Exception:passreturn Trueexcept Exception:return Falsereturn True
def _check_decoy() -> None:# irreducible cflow, using cdg fallback"""Checks for decoy flags (CTF element)."""# ***<module>._check_decoy: Failure: Compilation Errorpath = os.path.join(BASE_DIR, 'decoy.dll')if os.path.exists(path) is None:try:lib = ctypes.WinDLL(path)f = lib.get_decoy_flagexcept Exception:passfake_flag_path = os.path.join(BASE_DIR, 'fake_flag.txt')if os.path.exists(fake_flag_path) is None:passwith open(fake_flag_path, 'r', encoding='utf-8', errors='ignore') as f, print(f'Hint: {f.read() / f.read().strip()}'):except Exception:return None
def main():"""Main entry point for the License Verifier."""# ***<module>.main: Failure: Different control flowprint('License Verifier v1.0')print('=====================')_check_decoy()if _load_library('hook.dll'):print('[System] Hook library loaded.')try:license_key = input('Enter License Key: ').strip()except EOFError:return Noneif sys_core.verify_license(license_key) and print('\n[Success] License Validated. Access Granted.'):print('\n[Error] Invalid License Key.')sys.exit(1)
if __name__ == '__main__':main()

main中导入了sys_core，核心逻辑也位于 sys_core
在线网站进行反编译

# Decompiled with PyLingual (https://pylingual.io)
# Internal filename: 'sys_core.py'
# Bytecode version: 3.13.0rc3 (3571)
# Source timestamp: 1970-01-01 00:00:00 UTC (0)import hashlib
import struct
import os
from typing import List, Optional
OP_PUSH, OP_XOR, OP_ADD, OP_SUB, OP_LOAD, OP_CHECK, OP_OUT, OP_HALT = range(1, 9)
class KernelError(Exception):# ***<module>.KernelError: Failure: Different bytecode"""Custom exception for Kernel errors."""__static_attributes__ = ()
class SystemKernel:"""\nLightweight virtual machine kernel for license verification.\n"""def __init__(self, code: bytes, user_input: str):self.code = codeself.ip = 0self.stack = []self.input_buffer = user_inputself.is_valid = Trueself.output = []def _fetch_byte(self) -> int:# ***<module>.SystemKernel._fetch_byte: Failure detected at line number 24 and instruction offset 14: Different bytecodeif self.ip >= len(self.code):val = self.code[self.ip]self.ip += 1return valelse:raise KernelError('Instruction Pointer Out of Bounds')def _fetch_word(self) -> int:return self._fetch_byte() | self._fetch_byte() << 8def run(self) -> bool:"""Executes the bytecode."""# ***<module>.SystemKernel.run: Failure: Different control flowif self.ip < len(self.code):op = self._fetch_byte()if op == OP_PUSH:self.stack.append(self._fetch_word())else:if op == OP_XOR:b, a = (self.stack.pop(), self.stack.pop())else:if op == OP_ADD:b, a = (self.stack.pop(), self.stack.pop())else:if op == OP_SUB:b, a = (self.stack.pop(), self.stack.pop())else:if op == OP_LOAD:idx = self._fetch_word()val = ord(self.input_buffer[idx]) if idx < len(self.input_buffer) else 0self.stack.append(val)else:if op == OP_CHECK:val, target = (self._fetch_word(), self.stack.pop())if val!= target:self.is_valid = Falseelse:if op == OP_OUT:self.output.append(chr(self.stack.pop() & 255))else:if op == OP_HALT:return self.is_validelse:raise KernelError(f'Unknown Opcode: {op:02x}')if not self.ip < len(self.code):passreturn self.is_valid
API_SECRET = 'SysCore@2025#internal_key'
def _derive_key(length: int) -> bytes:# ***<module>._derive_key: Failure: Different bytecodereturn hashlib.sha256((API_SECRET + str(length) / str(length)).encode()).digest()
def _load_config() -> bytes:"""Loads and decrypts the system configuration (bytecode)."""# ***<module>._load_config: Failure: Compilation Errorconfig_path = os.path.join(os.path.dirname(__file__), 'sys.config')with open(config_path, 'rb') as f:data = f.read()raise KernelError('Configuration Corrupted') if len(data) < 2 else struct.unpack('<H', data[:2])[0]encrypted_payload = data[2:]key = _derive_key(code_len)checksum, bytecode = (decrypted_body[:code_len], struct.unpack('<I', decrypted_body[code_len:code_len + 4]))[0]return bytecode
def verify_license(user_input: str) -> bool:"""Public API to verify the license key."""try:bytecode = _load_config()kernel = SystemKernel(bytecode, user_input)return kernel.run()except Exception:return False

由于版本问题，反编译不完全，但我们依旧能发现虚拟机逻辑
程序中实现了一套自定义虚拟机（SystemKernel 类）
_load_config：从 sys.config 中加载并解密字节码。
OP_PUSH（1）、OP_XOR（2）、OP_ADD（3）、OP_SUB（4）、OP_LOAD（5）、OP_CHECK（6）、OP_OUT（7）、OP_HALT（8）
_load_config 函数采用两层加密：

1. 密钥派生：SHA256("SysCore@2025#internal_key" + str(code_len))
2. 第一层：与序列 ((i * 165) ^ 92) & 255 进行异或。
3. 第二层：与派生密钥进行异或。

import hashlib
import struct
import osAPI_SECRET = 'SysCore@2025#internal_key'def derive_key(length):return hashlib.sha256((API_SECRET + str(length)).encode()).digest()def decrypt():config_path = 'LicenseVerifier.exe_extracted/sys.config'with open(config_path, 'rb') as f:data = f.read()code_len = struct.unpack('<H', data[:2])[0]encrypted_payload = data[2:]key = derive_key(code_len)layer1 = bytearray()for i, x in enumerate(encrypted_payload):val = x ^ (((i * 165) ^ 92) & 255)layer1.append(val)decrypted_body = bytearray()for i in range(len(layer1)):val = layer1[i] ^ key[i % len(key)]decrypted_body.append(val)bytecode = decrypted_body[:code_len]return bytecodedef solve(bytecode):OP_PUSH, OP_XOR, OP_ADD, OP_SUB, OP_LOAD, OP_CHECK, OP_OUT, OP_HALT = range(1, 9)ip = 0length = len(bytecode)flag_chars = {}while ip < length:op = bytecode[ip]ip += 1if op == OP_LOAD:idx = bytecode[ip] | (bytecode[ip+1] << 8)ip += 2if ip < length and bytecode[ip] == OP_PUSH:ip += 1val1 = bytecode[ip] | (bytecode[ip+1] << 8)ip += 2if ip < length and bytecode[ip] == OP_ADD:ip += 1if ip < length and bytecode[ip] == OP_PUSH:ip += 1val2 = bytecode[ip] | (bytecode[ip+1] << 8)ip += 2if ip < length and bytecode[ip] == OP_XOR:ip += 1if ip < length and bytecode[ip] == OP_CHECK:ip += 1target = bytecode[ip] | (bytecode[ip+1] << 8)ip += 2char_code = (target ^ val2) - val1flag_chars[idx] = chr(char_code)max_idx = max(flag_chars.keys())flag = "".join([flag_chars.get(i, '?') for i in range(max_idx + 1)])print(f"\nFlag : {flag}")if __name__ == '__main__':code = decrypt()solve(code)# SHCTF{Vm_1s_FuN_&_PyTh0n_1s_PoW3rFuL_But_R3aL_W0r1d_1s_M0r3_C0mp1ic4t3d}

[阶段3] Ring0 VM Labyrinth

下载附件有三个文件，阅读“读我.txt”，提示驱动使用了VMP3.4.0壳，按照要求启动驱动
先分析loader.exe，定位设备名和 IOCTL
DIE查壳，未显示加壳

运行loader.exe，看到题目逻辑

fuzz测出flag长度为48

打开IDA加载loader.exe，能发现 SUCCESS 字符串

定位函数，可发现函数中的 DeviceIoControl ，并确认 IOCTL 0x222000

windbg断点在驱动处理 IOCTL 的入口，拿到 IRP、SystemBuffer 地址
用 !drvobj 找 IRP_MJ_DEVICE_CONTROL 指针
!drvobj \Driver\ShCtfDriver 2
windbg 会输出驱动对象信息和 MajorFunction 表
MajorFunction[0e] （0x0E 就是 IRP_MJ_DEVICE_CONTROL）
MajorFunction[0e] = ......
在 DeviceControl 入口下断点，触发断点，让 loader 调一次校验，从 IRP 里拿到 SystemBuffer
在输入缓冲区下数据断点，断在驱动读取输入与期望值比较的位置
识别“比较指令”并抓 expected 指针，定位“输入指针”和“期望指针”
dump下来会发现这就是一个vm解释器，简单的异或算法
将密文提出

0x64 0x6c 0x72 0x8a 0x8d 0x43 0x17 0x61 0x49 0x5f 0x0b 0xb3 0xa0 0xff 0x9e 0xb4 0xfe 0x9d 0xcf 0x40 0x33 0x7f 0x53 0x89 0x8d 0x1e 0x19 0x32 0x44 0xd9 0xdd 0xec 0xdd 0xfc 0x03 0xf0 0xcf 0x90 0xc3 0x49 0x8f 0x26 0x51 0x87 0x28 0x44 0x64 0x19

exp：

#include <stdio.h>
#include <stdint.h>int main() {unsigned char out[] = {0x64, 0x6c, 0x72, 0x8a, 0x8d, 0x43, 0x17, 0x61, 0x49, 0x5f, 0x0b, 0xb3, 0xa0, 0xff, 0x9e, 0xb4, 0xfe, 0x9d, 0xcf, 0x40, 0x33, 0x7f, 0x53, 0x89, 0x8d, 0x1e, 0x19, 0x32, 0x44, 0xd9, 0xdd, 0xec, 0xdd, 0xfc, 0x03, 0xf0, 0xcf, 0x90, 0xc3, 0x49, 0x8f, 0x26, 0x51, 0x87, 0x28, 0x44, 0x64, 0x19};size_t len = sizeof(out) / sizeof(out[0]);for (int i = 0; i < len; i++) {int k = (0x07 + 0x0D * i) % 0xFB;unsigned char o = out[i];char c = (char)((o - 0x10) ^ k);printf("%c", c);}printf("\n");return 0;
}/* SHCTF{R3V3r53_3n9iN33riN9_WILL_CaU53_mI5f0r7Un3} */

[阶段1] AES的诞生

task.py是一个时间戳生成密钥，密文转为二进制数据通过7位一组随机填充的AES-CBC加密

def get_seed() -> Optional[bytes]:length = len((f"{int(time() * 10 ** 6)}" * 2).encode("utf-8"))if (length == 32) :return (f"{int(time() * 10 ** 6)}" * 2).encode("utf-8")

密钥是通过时间戳生成，长度为32位，也就是时间戳的长度需要是16位（整数部分10位，小数部分6位）
在task.py中未提供更多有关密钥的信息，但可以发现在附件中还提供了一个html文件，Advanced Encryption Standard (AES) Development Effort.html
html文件中提到AES的开发工作概述，结合题目名称"AES的诞生"，可以推测密钥的时间戳为某个特殊的时间点，这个时间点是AES-CBC正式发布的那一天

在https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.197.pdf也可找到发布时间

from cryptography.hazmat.primitives import padding
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modesKEY = b'10067040000000001006704000000000'
IV_HEX = 'd966f3a0c51cd460764b0b62ad10796a'
IV = bytes.fromhex(IV_HEX)ciphertexts_hex = ["50b46ebd11b82c5b5c802913e60b4ad5", "e4c04d26cab88eb53ff35618797b36e3","e666c6ae95791f32509ac9485bec53c0", "5a012218f52fc3dabf8c1a62ffdf528f","7b1fe7de83532b470cee24bad1bdc50e", "684ac74414d4c72121d99ccd8cb68662","1dfd5287ba9548cf80eb9c5d598d17a9", "e666c6ae95791f32509ac9485bec53c0","f0125aba503835d048f45bb2e1e2472b", "099069650820d9bfb5b016648c002078","f34fcd626acfbcf1b83145989cbca94e", "3ff5000e47d7f68d535b8471bb26fba4","4a5535d6cc72fbc62cef774824bc46e1", "2fb7071182f7ed8c9acbc8bdf83de3fd","4d79df16626b4031651cd8174fd0e806", "0aea4d6b0c0e42403c7df9a2952a8d2c","a6493b26d3337ffdbe1b2c83bbd2739e", "d69612f3057925b553f39611d9225c62","db870abe80d5eff1471a09c6db97cd81", "ec2023d57d870da28af5d7479f58a8c7","4a5535d6cc72fbc62cef774824bc46e1", "dee13aeb1c13fb3b70cd1cb08cdda12b","cc45333beaa5fc6aded6d9fbf17f8169", "099069650820d9bfb5b016648c002078","99992fd4689125b0fb33881276cf0526", "ef6335b6121381fac5175b2104d03ce0","f34fcd626acfbcf1b83145989cbca94e", "0e7c2f8959e79f1baf526b4305677b15","837edc45fdafa37a9c8b04d1676f99f0", "2fb7071182f7ed8c9acbc8bdf83de3fd","4815fbfcc88d1e0a1deebb0628122205", "c627216b0c71593a60eaab811d7a8b14","af29c5c8861ea09b2d3ccd450b723b1a", "10dc01f1052c63d1df6ef6e796589008","bea46045dfb08b8425d2cb7fb486f809", "4e0bbab19e2a62ffa47f68aec7910305","684ac74414d4c72121d99ccd8cb68662", "50e489ec38984d1d851f1a67c5382889","d69612f3057925b553f39611d9225c62", "ef270a10b5cc257757212a82583f80d1","f9e53372cecefd4388e41a8d7ea71715", "e4c04d26cab88eb53ff35618797b36e3","10dc01f1052c63d1df6ef6e796589008", "9a9449200e0ebbc4bc3ae6dd592bb6a1","837edc45fdafa37a9c8b04d1676f99f0", "2fb7071182f7ed8c9acbc8bdf83de3fd","f810a2efc313cbe8acb222c8e2288bec", "9a9449200e0ebbc4bc3ae6dd592bb6a1","af29c5c8861ea09b2d3ccd450b723b1a", "e1951078acf5c87748ff42f9f9d5fc2b","cc45333beaa5fc6aded6d9fbf17f8169", "0e7c2f8959e79f1baf526b4305677b15","602468ea5e8bfe0eeaefecfc28c7f2dd", "d042cb7ba9c25886c3f5b072cfc830a4","1641c7c3f60cb8fe6ad008566ecb596c", "b543b4b57b7334541273a331a4ae0e77","0ef83387d23cd7b3087610a869173033", "f174f12b81364591583b7e7f50c30b40","db870abe80d5eff1471a09c6db97cd81", "9d72039a047870f380e5f58f48186b94","bcf718eee8728257e6ade850a58270fe", "8dde48dd948d11dc532d47de0c1b2b60","9eb452aa005c262eb883c0511b3bd98c", "06a0067316f0a412285a45d6991634a6","a8074111b395f36ce86ac7960ca803b8", "e666c6ae95791f32509ac9485bec53c0","af29c5c8861ea09b2d3ccd450b723b1a", "aad6d56935d0f49473f7aab9c6ea77c4"
]def decrypt():decrypted_chunks = []for ct_hex in ciphertexts_hex:cipher = Cipher(algorithms.AES(KEY), modes.CBC(IV))decryptor = cipher.decryptor()ct_bytes = bytes.fromhex(ct_hex)padded_pt = decryptor.update(ct_bytes) + decryptor.finalize()unpadder = padding.PKCS7(128).unpadder()pt = unpadder.update(padded_pt) + unpadder.finalize()decrypted_chunks.append(pt.decode('utf-8'))base_binary = "".join(decrypted_chunks[:-1])last_chunk = decrypted_chunks[-1]for length in range(1, len(last_chunk) + 1):candidate_segment = last_chunk[:length]if not all(c in '01' for c in candidate_segment):continuefull_binary = base_binary + candidate_segmentval = int(full_binary, 2)byte_len = (val.bit_length() + 7) // 8flag = val.to_bytes(byte_len, "big")if flag.startswith(b'SHCTF'):print(f"{flag.decode('utf-8', errors='ignore')}")if __name__ == "__main__":decrypt()# SHCTF{HE1lO_ctf3r_W3Lcome_tO_5hc7f_THi5_iS_e5aY_cRypt0@!!!}

[阶段1] Stream

一段LCG加密
可通过已知明文恢复部分密钥流
根据密钥流序列，利用差分分析恢复LCG参数m、a、c
利用a和c反推初始种子s0

import binascii
from functools import reduce
from math import gcdP_know_text = b'Insecure_linear_congruential_random_number!!!!!!'
C_known_hex = "44e18dfa1acd14aa790fc3bac4ca54c137bcd47bdfc2209a53b83715ecad3e29249845720588cac007bfb94f8476d91a"
C_flag_hex  = "1995374a5b64c6696578c1d5bdc6fa3d1e974b813436eab4348db801fb7a6703658eaa4fefa2c6fd6792beb969df8ca70ad87a4f4aea6ca0040d65a3c1e3a5bf2655cafc1e5603a171edc9aa077c0ca264677c351907f35756c14dd7ece428cb424a3804b544ccb53e99935f9bc2d8483dd7587379c99b3542c222008a"C_known = binascii.unhexlify(C_known_hex)
C_flag = binascii.unhexlify(C_flag_hex)
full_cipher = C_known + C_flagsafe_len = len(P_know_text)
num_blocks = safe_len // 8X = []
for i in range(num_blocks):p_chunk = P_know_text[i*8 : (i+1)*8]c_chunk = C_known[i*8 : (i+1)*8]p_val = int.from_bytes(p_chunk, 'big')c_val = int.from_bytes(c_chunk, 'big')X.append(p_val ^ c_val)# print(f"Recovered {len(X)}")T = []
for i in range(len(X) - 1):T.append(X[i+1] - X[i])U = []
for i in range(len(T) - 2):val = T[i+2] * T[i] - T[i+1]**2U.append(val)m = abs(reduce(gcd, U))
while m % 2 == 0:m //= 2
# print(f"Recovered m: {m}")def egcd(a, b):if a == 0: return (b, 0, 1)else:g, y, x = egcd(b % a, a)return (g, x - (b // a) * y, y)def modinv(a, m):g, x, y = egcd(a, m)return x % minv_T0 = modinv(T[0], m)
a = (T[1] * inv_T0) % m
# print(f"Recovered a: {a}")c = (X[1] - a * X[0]) % m
# print(f"Recovered c: {c}")inv_a = modinv(a, m)
s0 = ((X[0] - c) * inv_a) % m
# print(f"Recovered s0: {s0}")total_len = len(full_cipher)
needed_blocks = (total_len + 7) // 8def lcg(m, a, c, s0, n):x = s0out = []for _ in range(n):x = (a * x + c) % mout.append(x)return outkeystream_nums = lcg(m, a, c, s0, needed_blocks)
keystream_bytes = b''.join(k.to_bytes(8, 'big') for k in keystream_nums)plaintext = bytearray()
for i in range(total_len):plaintext.append(full_cipher[i] ^ keystream_bytes[i])print(plaintext.decode())# Insecure_linear_congruential_random_number!!!!!!SHCTF{LLLLLLLLLLLLLLLCCCCCGGGGGGGGG_TGY%JgWOmAM6V5n55w3m*jcPJZjHO8E1VvzrGjT84tXS332D&o4GZe8%KKzEyAngmwwx9bp5dv_O4dPpOvMy1^hM}

[阶段1] TE

一道共模攻击的板子题
题目描述意思是贝祖定理，贝祖定理是RSA共模攻击的数学基础
task.py提供两个公钥和两个使用两个不同的公钥进行加密得到 c1 和 c2
典型的共模攻击

from Crypto.Util.number import *
from gmpy2 import *
from gmpy2 import gmpy2
from tqdm import trangee1 = 740153575
e2 = 2865243571
n = 136622832042809215646904518487100682818433235485047740604612449039291802103378650845690420527029208661555957840623544220907967041438993189882681277161437473818861280518627112617436473837014181944318974950710633690704711613682306786783611123590732850783007770603201513394002330426718261667816328404673167404897
c1 = 56187319559060690757544481076112948328826527679002578544683022765347668056620384831778729489197135280950314627119815558644487151419126272267146826463912815062442590228193753706779325992179790583792001196548329204758137104234662611732735693150331594645734142941475121453410494160975503459516324097097434727685
c2 = 45042409947237296641429229414329516753664139389113206575966507524195434716702812078844474626406932213486611190698953613898299571473488550533642524208077653917354039305279692307471529748408234617430389423630015569730564585740596832844917494965974840512412454337766930330443409183293514761911902752336129193323e = (gmpy2.gcd(e1,e2))d,x,y = gmpy2.gcdext(e1,e2)
m = pow(c1,x,n)*pow(c2,y,n) % nfor i in trange(10):if gmpy2.iroot(m+i*n,e)[-1]:flag = long_to_bytes(int(gmpy2.iroot(m+i*n,e)[0]))if flag.startswith(b'SHCTF'):print(f"{flag.decode('utf-8', errors='ignore')}")# SHCTF{lYQkkk3ud4hqV3fZtPWH077vhI2Bqcz19ZRxf1vwRU8Ej4uvrJcF02Sd4bzjxqUH5096qWDIdTyEJ$JzF}

[阶段2] Titanium Lock

task.py经过了三层加密

def f1(self, msg):random.seed(self.seed)enc, last = [], 0for c in str(bytes_to_long(msg)):r = random.randint(100000, 999999)last = ((int(c) + r) if int(c) % 2 == 0 else (int(c) * r)) ^ lastenc.append(last)return enc

将flag转为长整数字符串
基于一个 6 位数的种子 seed (100,000 - 999,999)
状态更新函数引入了非线性分支：
last = ((int(c) + r) if int(c) % 2 == 0 else (int(c) * r)) ^ last
对于每位长整数字符串：

• 若为偶数则：last = (c + r) ^ last
• 若为奇数则：last = (c * r) ^ last
• 其中r为初始化生成的伪随机数（seed为固定值，可预测）

def f2(self, v):v += [random.randint(0, 255) for _ in range(-len(v) % 12)]res = []for i in range(0, len(v), 12):chunk = v[i:i+12]res.extend([sum(self.c1[r][c] * chunk[c] for c in range(12)) + self.c2[r] for r in range(16)])return res

f2将f1生成的enc视为12维向量，进行了一个仿射变换
使用一个 16×12 的变换矩阵 c1 和一个 16 维偏置向量 c2，计算 res = c1⋅enc+c2
其中：

• c1是16×12的矩阵
• c2是16维向量
• 每个块产生16个输出值
  将数据从低维空间映射到高维空间

def f3(self, data):out = [[n := random.getrandbits(128), (bin(n & self.key).count('1') % 3) % 2] for _ in range(128 * 20)]k = md5(str(self.key).encode()).digest()return out, AES.new(k, AES.MODE_CTR, nonce=b"Tiffany\x00").encrypt(str(data).encode()).hex()

生成的一个 128 位的随机密钥 key
提供一个 Oracle ，对于给定的随机 nonce，返回

\[y = (\text{popcount}(nonce \ \& \ key) \pmod 3) \pmod 2 \]

生成2560个[nonce, bit]对，其中：

• nonce是128位随机数
• bit = (popcount(nonce & key) % 3) % 2
  用key的MD5作为AES-CTR的密钥加密f2()的输出
  encrypt加密流程

def encrypt(self, data):o, c = self.f3(self.f2(self.f1(data)))return {"p1": self.c1, "p2": self.c2, "trace": o, "result": c}

在解密的时候需要从f3 -> f2 -> f1
f3是一个变种的 LPN 问题。虽然最终结果模 2 引入了非线性（噪声），但在 GF(3)GF(3) 域上，popcount 是线性的
可以筛选出 p=1 的样本，
这意味着$$\text{popcount}(n \land key) \pmod 3 \neq 0$$
我们可以建立如下线性方程组（在$$GF(3)$$上）：

\[\sum_{i=0}^{127} n_i \cdot k_i \equiv 1 \pmod 3 \]

或者

\[\sum_{i=0}^{127} n_i \cdot k_i \equiv 2 \pmod 3 \]

由于我们不知道具体是 1 还是 2，这看起来有歧义。但实际上，我们可以简单地假设结果为 1 进行求解。如果方程组有解，我们就能恢复出密钥。 利用trace数据，使用 高斯消元法 在 $$GF(3) $$域上求解。
恢复密钥key后，解密res密文，然后逆向f2
f2是一个超定线性方程组（方程数 16 > 未知数 12）。我们可以使用 最小二乘法 或 正规方程 (Normal Equations) 来求解 x：

\[c1 \cdot x = y - c2 \]

\[c1^T \cdot c1 \cdot x = c1^T \cdot (y - c2) \]

\[x = (c1^T \cdot c1)^{-1} \cdot c1^T \cdot (y - c2) \]

由于是在整数域上运算且没有模数，我们可以直接使用分数运算 (fractions.Fraction) 来获得精确解，或者在浮点精度足够的情况下使用 numpy。
f1使用的seed种子范围仅为 100,000−999,999。我们可以枚举种子，生成对应的随机数序列 ri
对于每个种子，尝试解密前几位数据。如果解密出的数字 d 不在 0−9 范围内，或者不满足奇偶性校验，则该种子无效。
由于 c 是偶数还是奇数会导致不同的逆运算（减法 vs 除法），解密过程中会出现“碰撞”：同一个密文值可能对应一个偶数明文或一个奇数明文。
本题中的flag长度为67，使用BFS或DFS算法的解密时间会大大增加

使用 Beam Search 进行束搜索

• 限制每一层搜索树的宽度
• 只保留最“有希望”的路径
  利用 bytes_to_long 的性质：数字的高位决定了字节串的高位。
• 当我们从左到右恢复十进制数字时，数字的高位逐渐确定。
• 我们可以将当前恢复的数字串补 0（最小可能值）和补 9（最大可能值），分别转换为字节串。
• 比较这两个字节串的公共前缀（即“稳定字节”）。
• 剪枝规则：
  • 字节必须是可打印 ASCII 字符。
  • 字节的前缀必须匹配 SHCTF{。

import ast
import random
import string
from hashlib import md5
from fractions import Fraction
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytesdef gf3(M, v):rows, cols = len(M), len(M[0])M = [row + [v[i]] for i, row in enumerate(M)]pivot = 0for col in range(cols):for r in range(pivot, rows):if M[r][col] % 3 != 0:M[pivot], M[r] = M[r], M[pivot]breakinv = M[pivot][col]M[pivot] = [(x * inv) % 3 for x in M[pivot]]for r in range(rows):if r != pivot and M[r][col] != 0:f = M[r][col]M[r] = [(M[r][c] - f * M[pivot][c]) % 3 for c in range(cols + 1)]pivot += 1return [M[i][-1] for i in range(cols)]def gf2(y, A, B):def mat_mul(A, B):return [[sum(a * b for a, b in zip(row, col)) for col in zip(*B)] for row in A]def transpose(A):return list(map(list, zip(*A)))def inverse(A):n = len(A)M = [[Fraction(x) for x in row] + [Fraction(1 if i == j else 0) for j in range(n)] for i, row in enumerate(A)]for i in range(n):pivot = M[i][i]for j in range(i, 2 * n): M[i][j] /= pivotfor k in range(n):if k != i:f = M[k][i]for j in range(i, 2 * n): M[k][j] -= f * M[i][j]return [row[n:] for row in M]AT = transpose(A)pseudo_inv = mat_mul(inverse(mat_mul(AT, A)), AT)x_res = []dim_out = len(B)for i in range(0, len(y), dim_out):diff = [y[i + j] - B[j] for j in range(dim_out)]x_res.extend(int(sum(p * d for p, d in zip(row, diff))) for row in pseudo_inv)return x_resdef gf1(stream):printable = set(string.printable.encode())total_len = len(stream)for seed in range(100000, 1000000):random.seed(seed)rs = [random.randint(100000, 999999) for _ in range(total_len + 10)]queue = [(0, "", 0)]while queue:if len(queue) > 2000:random.shuffle(queue)queue = queue[:2000]next_q = []for idx, digs, last in queue:if idx == total_len:flag = long_to_bytes(int(digs))if b"SHCTF{" in flag and flag.endswith(b"}"):# print(f"Seed : {seed}")print(f"flag : {flag.decode()}")returnval, r = stream[idx], rs[idx]target = val ^ lastcandidates = set()d1 = target - rif d1 % 2 == 0 and 0 <= d1 <= 9: candidates.add(d1)if r != 0 and target % r == 0:d2 = target // rif d2 % 2 != 0 and 0 <= d2 <= 9: candidates.add(d2)for d in candidates:new_digs = digs + str(d)rem = total_len - len(new_digs)min_b = long_to_bytes(int(new_digs + '0' * rem))max_b = long_to_bytes(int(new_digs + '9' * rem))common_len = 0for b1, b2 in zip(min_b, max_b):if b1 == b2:common_len += 1else:breakstab = min_b[:common_len]if not all(c in printable for c in stab): continueif len(stab) > 0 and not (b"SHCTF{"[:min(6, len(stab))] == stab[:min(6, len(stab))]): continuenext_q.append((idx + 1, new_digs, val))queue = next_qdef solve():with open("data.txt") as f:data = {k.strip(): (v.strip() if k.strip() == "result" else ast.literal_eval(v.strip()))for line in f for k, v in [line.split("=", 1)]}samples = [(n, p) for n, p in data["trace"] if p == 1]eqs = [[(n >> i) & 1 for i in range(128)] for n, _ in samples[:140]]lpn_key = sum(b << i for i, b in enumerate(gf3(eqs, [1] * 140)))# print(f"Key : {lpn_key}")aes_key = md5(str(lpn_key).encode()).digest()pt = AES.new(aes_key, AES.MODE_CTR, nonce=b"Tiffany\x00").decrypt(bytes.fromhex(data["result"]))y_vec = ast.literal_eval(pt.decode())stream = gf2(y_vec, data["p1"], data["p2"])while stream and stream[-1] < 256: stream.pop()gf1(stream)if __name__ == "__main__":solve()# SHCTF{HYP3rLoN_mOd3_Lpn_@ff16X1Z_bl6_kl28_@3$_ctR_7FgDzBae0A8f3$61}