20251024115755 - BLG - Flare-on12 Chall 6 - Chain of Demands
Description
This is a crypto-rev challenge. This core challenge is written in Python, using tkinter module for the user interface. The challenge hides cryptographic functions in two different slightly obfuscated smart contracts that are used in implementation of PRNG. Values from the PRNG are used as part of encryption of messages that are revealed in the chatroom. The seed for the PRNG is the hash of the username of the machine. Furthermore, the encrypted message contains the flag for the challenge with unknown username.
Reason why it is possible to solve is because we have two of three components of the triple XOR oracle, allowing us to eventually leak other variables from LCG. This escalates to leaking the initial seed which allows us to create the decryption key for the flag. This post focuses more on the mathematical side of things rather than a code walkthrough.
Decompilation
Given that it is python program, pyinxtractor.py was used in an attempt to extract challenge_to_compile.pyc. To decompile, pycdc was used. However, there were unsupported opcodes messages littered within the decompilation.
def resource_path(relative_path):Unsupported opcode: PUSH_EXC_INFO (105)......
def save_chat_log(self):Unsupported opcode: BEFORE_WITH (108) pass # WARNING: Decompyle incomplete...
class ChatApp(tk.Tk):Unsupported opcode: MAKE_CELL (225) passTo clean things up, we can follow https://corgi.rip/blog/pyinstaller-reverse-engineering/
We can add the following into ASTree.cpp in our pycdc source at around 1023 (might change if you are trying along this depending on pycdc version) before recompiling:
case Pyc::PUSH_EXC_INFOcase Pyc::MAKE_CELL_Acase Pyc::BEFORE_WITHcase Pyc::RERAISEcase Pyc::RERAISE_Acase Pyc::CHECK_EXC_MATCHcase Pyc::COPY_FREE_VARS_Acase Pyc::LOAD_FREE_VARS_Acase Pyc::LOAD_SUPER_ATTR_Acase Pyc::JUMP_IF_FALSE_A
Now running pycdc again, decompilation is not the best but its better than nothing :D
# Source Generated with Decompyle++# File: challenge_to_compile.pyc (Python 3.12)
import tkinter as tkfrom tkinter import scrolledtext, messagebox, simpledialog, Checkbutton, BooleanVar, Toplevelimport platformimport hashlibimport timeimport jsonfrom threading import Threadimport mathimport randomfrom Crypto.PublicKey import RSAfrom Crypto.Util.number import bytes_to_long, long_to_bytes, isPrimeimport osimport sysfrom web3 import Web3from eth_account import Accountfrom eth_account.signers.local import LocalAccount
def resource_path(relative_path):Warning: Stack history is not empty!Warning: block stack is not empty! ''' Get the absolute path to a resource, which works for both development and for a PyInstaller-bundled executable. ''' base_path = sys._MEIPASS return os.path.join(base_path, relative_path) if None: pass if Exception and Exception: base_path = os.path.abspath('.') continue if None: pass if None: pass
class SmartContracts: rpc_url = '' private_key = ''
def deploy_contract(contract_bytes, contract_abi):Warning: Stack history is not empty!Warning: block stack is not empty! w3 = Web3(Web3.HTTPProvider(SmartContracts.rpc_url)) if not w3.is_connected(): raise ConnectionError(f'''[!] Failed to connect to Ethereum network at {SmartContracts.rpc_url}''') print(f'''[+] Connected to Sepolia network at {SmartContracts.rpc_url}''') print(f'''[+] Current block number: {w3.eth.block_number}''') if not SmartContracts.private_key: raise ValueError('Please add your private key.') account = Account.from_key(SmartContracts.private_key) w3.eth.default_account = account.address print(f'''[+] Using account: {account.address}''') balance_wei = w3.eth.get_balance(account.address) print(f'''[+] Account balance: {w3.from_wei(balance_wei, 'ether')} ETH''') if balance_wei == 0: print('[!] Warning: Account has 0 ETH. Deployment will likely fail. Get some testnet ETH from a faucet (e.g., sepoliafaucet.com)!') Contract = w3.eth.contract(abi = contract_abi, bytecode = contract_bytes) gas_estimate = Contract.constructor().estimate_gas() print(f'''[+] Estimated gas for deployment: {gas_estimate}''') gas_price = w3.eth.gas_price print(f'''[+] Current gas price: {w3.from_wei(gas_price, 'gwei')} Gwei''') transaction = Contract.constructor().build_transaction({ 'from': account.address, 'nonce': w3.eth.get_transaction_count(account.address), 'gas': gas_estimate + 200000, 'gasPrice': gas_price }) signed_txn = w3.eth.account.sign_transaction(transaction, private_key = SmartContracts.private_key) print('[+] Deploying contract...') tx_hash = w3.eth.send_raw_transaction(signed_txn.raw_transaction) print(f'''[+] Deployment transaction sent. Hash: {tx_hash.hex()}''') print('[+] Waiting for transaction to be mined...') tx_receipt = w3.eth.wait_for_transaction_receipt(tx_hash, timeout = 300) print(f'''[+] Transaction receipt: {tx_receipt}''') if tx_receipt.status == 0: print('[!] Transaction failed (status 0). It was reverted.') return None contract_address = tx_receipt.contractAddress print(f'''[+] Contract deployed at address: {contract_address}''') deployed_contract = w3.eth.contract(address = contract_address, abi = contract_abi) return deployed_contract if None: pass if ConnectionError and ConnectionError: e = None print(f'''[!] Connection error: {e}''') print('Please check your RPC_URL and network connection.') e = None del e return None e = None del e if None: pass if ValueError and ValueError: e = None print(f'''[!] Configuration error: {e}''') e = None del e return None e = None del e if None: pass if Exception and Exception: e = None print(f'''[!] An unexpected error occurred: {e}''') e = None del e return None e = None del e if None and None: pass if None: pass
class LCGOracle:
def __init__(self, multiplier, increment, modulus, initial_seed): self.multiplier = multiplier self.increment = increment self.modulus = modulus self.state = initial_seed self.contract_bytes = '6080604052348015600e575f5ffd5b506102e28061001c5f395ff3fe608060405234801561000f575f5ffd5b5060043610610029575f3560e01c8063115218341461002d575b5f5ffd5b6100476004803603810190610042919061010c565b61005d565b6040516100549190610192565b60405180910390f35b5f5f848061006e5761006d6101ab565b5b86868061007e5761007d6101ab565b5b8987090890505f5f8411610092575f610095565b60015b60ff16905081816100a69190610205565b858260016100b49190610246565b6100be9190610205565b6100c89190610279565b9250505095945050505050565b5f5ffd5b5f819050919050565b6100eb816100d9565b81146100f5575f5ffd5b50565b5f81359050610106816100e2565b92915050565b5f5f5f5f5f60a08688031215610125576101246100d5565b5b5f610132888289016100f8565b9550506020610143888289016100f8565b9450506040610154888289016100f8565b9350506060610165888289016100f8565b9250506080610176888289016100f8565b9150509295509295909350565b61018c816100d9565b82525050565b5f6020820190506101a55f830184610183565b92915050565b7f4e487b71000000000000000000000000000000000000000000000000000000005f52601260045260245ffd5b7f4e487b71000000000000000000000000000000000000000000000000000000005f52601160045260245ffd5b5f61020f826100d9565b915061021a836100d9565b9250828202610228816100d9565b9150828204841483151761023f5761023e6101d8565b5b5092915050565b5f610250826100d9565b915061025b836100d9565b9250828203905081811115610273576102726101d8565b5b92915050565b5f610283826100d9565b915061028e836100d9565b92508282019050808211156102a6576102a56101d8565b5b9291505056fea2646970667358221220c7e885c1633ad951a2d8168f80d36858af279d8b5fe2e19cf79eac15ecb9fdd364736f6c634300081e0033' self.contract_abi = [ { 'inputs': [ { 'internalType': 'uint256', 'name': 'LCG_MULTIPLIER', 'type': 'uint256' }, { 'internalType': 'uint256', 'name': 'LCG_INCREMENT', 'type': 'uint256' }, { 'internalType': 'uint256', 'name': 'LCG_MODULUS', 'type': 'uint256' }, { 'internalType': 'uint256', 'name': '_currentState', 'type': 'uint256' }, { 'internalType': 'uint256', 'name': '_counter', 'type': 'uint256' }], 'name': 'nextVal', 'outputs': [ { 'internalType': 'uint256', 'name': '', 'type': 'uint256' }], 'stateMutability': 'pure', 'type': 'function' }] self.deployed_contract = None
def deploy_lcg_contract(self): self.deployed_contract = SmartContracts.deploy_contract(self.contract_bytes, self.contract_abi)
def get_next(self, counter): print(f'''\n[+] Calling nextVal() with _currentState={self.state}''') self.state = self.deployed_contract.functions.nextVal(self.multiplier, self.increment, self.modulus, self.state, counter).call() print(f''' _counter = {counter}: Result = {self.state}''') return self.state
class TripleXOROracle:
def __init__(self): self.contract_bytes = '61030f61004d600b8282823980515f1a6073146041577f4e487b71000000000000000000000000000000000000000000000000000000005f525f60045260245ffd5b305f52607381538281f3fe7300000000000000000000000000000000000000003014608060405260043610610034575f3560e01c80636230075614610038575b5f5ffd5b610052600480360381019061004d919061023c565b610068565b60405161005f91906102c0565b60405180910390f35b5f5f845f1b90505f845f1b90505f61007f85610092565b9050818382181893505050509392505050565b5f5f8290506020815111156100ae5780515f525f5191506100b6565b602081015191505b50919050565b5f604051905090565b5f5ffd5b5f5ffd5b5f819050919050565b6100df816100cd565b81146100e9575f5ffd5b50565b5f813590506100fa816100d6565b92915050565b5f5ffd5b5f5ffd5b5f601f19601f8301169050919050565b7f4e487b71000000000000000000000000000000000000000000000000000000005f52604160045260245ffd5b61014e82610108565b810181811067ffffffffffffffff8211171561016d5761016c610118565b5b80604052505050565b5f61017f6100bc565b905061018b8282610145565b919050565b5f67ffffffffffffffff8211156101aa576101a9610118565b5b6101b382610108565b9050602081019050919050565b828183375f83830152505050565b5f6101e06101db84610190565b610176565b9050828152602081018484840111156101fc576101fb610104565b5b6102078482856101c0565b509392505050565b5f82601f83011261022357610222610100565b5b81356102338482602086016101ce565b91505092915050565b5f5f5f60608486031215610253576102526100c5565b5b5f610260868287016100ec565b9350506020610271868287016100ec565b925050604084013567ffffffffffffffff811115610292576102916100c9565b5b61029e8682870161020f565b9150509250925092565b5f819050919050565b6102ba816102a8565b82525050565b5f6020820190506102d35f8301846102b1565b9291505056fea26469706673582212203fc7e6cc4bf6a86689f458c2d70c565e7c776de95b401008e58ca499ace9ecb864736f6c634300081e0033' self.contract_abi = [ { 'inputs': [ { 'internalType': 'uint256', 'name': '_primeFromLcg', 'type': 'uint256' }, { 'internalType': 'uint256', 'name': '_conversationTime', 'type': 'uint256' }, { 'internalType': 'string', 'name': '_plaintext', 'type': 'string' }], 'name': 'encrypt', 'outputs': [ { 'internalType': 'bytes32', 'name': '', 'type': 'bytes32' }], 'stateMutability': 'pure', 'type': 'function' }] self.deployed_contract = None
def deploy_triple_xor_contract(self): self.deployed_contract = SmartContracts.deploy_contract(self.contract_bytes, self.contract_abi)
def encrypt(self, prime_from_lcg, conversation_time, plaintext_bytes): print(f'''\n[+] Calling encrypt() with prime_from_lcg={prime_from_lcg}, time={conversation_time}, plaintext={plaintext_bytes}''') ciphertext = self.deployed_contract.functions.encrypt(prime_from_lcg, conversation_time, plaintext_bytes).call() print(f''' _ciphertext = {ciphertext.hex()}''') return ciphertext
class ChatLogic:
def __init__(self): self.lcg_oracle = None self.xor_oracle = None self.rsa_key = None self.seed_hash = None self.super_safe_mode = False self.message_count = 0 self.conversation_start_time = 0 self.chat_history = [] self._initialize_crypto_backend()
def _get_system_artifact_hash(self): artifact = platform.node().encode('utf-8') hash_val = hashlib.sha256(artifact).digest() seed_hash = int.from_bytes(hash_val, 'little') print(f'''[SETUP] - Generated Seed {seed_hash}...''') return seed_hash
def _generate_primes_from_hash(self, seed_hash): primes = [] current_hash_byte_length = (seed_hash.bit_length() + 7) // 8 current_hash = seed_hash.to_bytes(current_hash_byte_length, 'little') print('[SETUP] Generating LCG parameters from system artifact...') iteration_limit = 10000 iterations = 0 if len(primes) < 3 and iterations < iteration_limit: current_hash = hashlib.sha256(current_hash).digest() candidate = int.from_bytes(current_hash, 'little') iterations += 1 if candidate.bit_length() == 256 and isPrime(candidate): primes.append(candidate) print(f'''[SETUP] - Found parameter {len(primes)}: {str(candidate)[:20]}...''') if len(primes) < 3 and iterations < iteration_limit: continue if len(primes) < 3: error_msg = '[!] Error: Could not find 3 primes within iteration limit.' print('Current Primes: ', primes) print(error_msg) exit() return (primes[0], primes[1], primes[2])
def _initialize_crypto_backend(self): self.seed_hash = self._get_system_artifact_hash() (m, c, n) = self._generate_primes_from_hash(self.seed_hash) self.lcg_oracle = LCGOracle(m, c, n, self.seed_hash) self.lcg_oracle.deploy_lcg_contract() print('[SETUP] LCG Oracle is on-chain...') self.xor_oracle = TripleXOROracle() self.xor_oracle.deploy_triple_xor_contract() print('[SETUP] Triple XOR Oracle is on-chain...') print('[SETUP] Crypto backend initialized...')
def generate_rsa_key_from_lcg(self):Something TERRIBLE happened!Something TERRIBLE happened!Warning: Stack history is not empty!Warning: block stack is not empty! print('[RSA] Generating RSA key from on-chain LCG primes...') lcg_for_rsa = LCGOracle(self.lcg_oracle.multiplier, self.lcg_oracle.increment, self.lcg_oracle.modulus, self.seed_hash) lcg_for_rsa.deploy_lcg_contract() primes_arr = [] rsa_msg_count = 0 iteration_limit = 10000 iterations = 0 if len(primes_arr) < 8 and iterations < iteration_limit: candidate = lcg_for_rsa.get_next(rsa_msg_count) rsa_msg_count += 1 iterations += 1 if candidate.bit_length() == 256 and isPrime(candidate): primes_arr.append(candidate) print(f'''[RSA] - Found 256-bit prime #{len(primes_arr)}''') if len(primes_arr) < 8 and iterations < iteration_limit: continue print('Primes Array: ', primes_arr) if len(primes_arr) < 8: error_msg = '[RSA] Error: Could not find 8 primes within iteration limit.' print('Current Primes: ', primes_arr) print(error_msg) return error_msg n = None for p_val in primes_arr: n *= p_val phi = 1 for p_val in primes_arr: phi *= p_val - 1 e = 65537 if math.gcd(e, phi) != 1: error_msg = '[RSA] Error: Public exponent e is not coprime with phi(n). Cannot generate key.' print(error_msg) return error_msg self.rsa_key = None.construct((n, e)) if open('public.pem', 'wb'): pass f = open('public.pem', 'wb') f.write(self.rsa_key.export_key('PEM')) None(None, None) print("[RSA] Public key generated and saved to 'public.pem'") return 'Public key generated and saved successfully.' if None: pass with None: if None or None: pass continue if None and None: pass if Exception and Exception: e = None print(f'''[RSA] Error saving key: {e}''') del e return None None = None del e if None and None: pass if None: pass
def process_message(self, plaintext): if self.conversation_start_time == 0: self.conversation_start_time = time.time() conversation_time = int(time.time() - self.conversation_start_time) if self.super_safe_mode and self.rsa_key: plaintext_bytes = plaintext.encode('utf-8') plaintext_enc = bytes_to_long(plaintext_bytes) _enc = pow(plaintext_enc, self.rsa_key.e, self.rsa_key.n) ciphertext = _enc.to_bytes(self.rsa_key.n.bit_length(), 'little').rstrip(b'\x00') encryption_mode = 'RSA' plaintext = '[ENCRYPTED]' else: prime_from_lcg = self.lcg_oracle.get_next(self.message_count) ciphertext = self.xor_oracle.encrypt(prime_from_lcg, conversation_time, plaintext) encryption_mode = 'LCG-XOR' log_entry = { 'conversation_time': conversation_time, 'mode': encryption_mode, 'plaintext': plaintext, 'ciphertext': ciphertext.hex() } self.chat_history.append(log_entry) self.save_chat_log() return (f'''[{conversation_time}s] {plaintext}''', f'''[{conversation_time}s] {ciphertext.hex()}''')
def save_chat_log(self):Warning: Stack history is not empty!Warning: block stack is not empty! if open('chat_log.json', 'w'): pass f = open('chat_log.json', 'w') json.dump(self.chat_history, f, indent = 2) None(None, None) return None if None: pass with None: if None or None: pass return None if None and None: pass if Exception and Exception: e = None print(f'''Error saving chat log: {e}''') e = None del e return None e = None del e if None and None: pass if None: pass
class ChatApp(tk.Tk): if None: pass __module__ = __name__ __qualname__ = 'ChatApp'
def __init__(self = None): if None: pass if self: pass self() self.title('Chain of Demands - Secure Chat') self.geometry('1000x800') top_frame = tk.Frame(self, bd = 5) top_frame.pack(fill = 'x') chat_frame = tk.Frame(self, bd = 5) chat_frame.pack(expand = True, fill = 'both') input_frame = tk.Frame(self, bd = 5) input_frame.pack(fill = 'x') tk.Label(top_frame, text = 'Connect to IP:').pack(side = 'left') self.ip_entry = tk.Entry(top_frame, width = 20) self.ip_entry.insert(0, '127.0.0.1') self.ip_entry.pack(side = 'left', padx = 5) self.connect_button = tk.Button(top_frame, text = 'Connect', command = self.connect_to_peer) self.connect_button.pack(side = 'left') self.load_files_button = tk.Button(top_frame, text = 'Last Convo', command = self.load_last_generated_files) self.load_files_button.pack(side = 'left', padx = 10) self.web3_config_button = tk.Button(top_frame, text = 'Web3 Config', command = self.open_web3_config_window) self.web3_config_button.pack(side = 'left') self.status_label = tk.Label(top_frame, text = 'Status: Disconnected', fg = 'red') self.status_label.pack(side = 'left', padx = 10) self.chat_box = scrolledtext.ScrolledText(chat_frame, state = 'disabled', wrap = tk.WORD, bg = '#f0f0f0') self.chat_box.pack(expand = True, fill = 'both') self.msg_entry = tk.Entry(input_frame, width = 60) self.msg_entry.pack(side = 'left', expand = True, fill = 'x', padx = 5) self.msg_entry.bind('<Return>', self.send_message_event) self.msg_entry.config(state = 'disabled') self.send_button = tk.Button(input_frame, text = 'Send', command = self.send_message_event) self.send_button.pack(side = 'left') self.send_button.config(state = 'disabled') self.super_safe_var = BooleanVar() self.super_safe_check = Checkbutton(top_frame, text = 'Enable Super-Safe Encryption', variable = self.super_safe_var, command = self.toggle_super_safe) self.super_safe_check.pack(side = 'right', padx = 10) self.logic = ChatLogic()
def open_web3_config_window(self): if None or None or None: pass config_window = Toplevel(self) config_window.title('Web3 Configuration') config_window.geometry('650x150') config_window.resizable(False, False) main_frame = tk.Frame(config_window, padx = 10, pady = 10) main_frame.pack(expand = True, fill = 'both') tk.Label(main_frame, text = 'RPC URL:').grid(row = 0, column = 0, sticky = 'w', pady = 5) rpc_entry = tk.Entry(main_frame, width = 60) rpc_entry.grid(row = 0, column = 1, sticky = 'ew') rpc_entry.insert(0, SmartContracts.rpc_url) tk.Label(main_frame, text = 'Private Key:').grid(row = 1, column = 0, sticky = 'w', pady = 5) pk_entry = tk.Entry(main_frame, width = 60) pk_entry.grid(row = 1, column = 1, sticky = 'ew') pk_entry.insert(0, SmartContracts.private_key)
def save_and_close(): if None: pass new_rpc_url = rpc_entry.get().strip() new_pk = pk_entry.get().strip() if new_rpc_url and new_pk: SmartContracts.rpc_url = new_rpc_url SmartContracts.private_key = new_pk print(f'''[CONFIG] Web3 RPC URL updated to: {new_rpc_url}''') print('[CONFIG] Web3 Private Key updated.') messagebox.showinfo('Success', 'Web3 configuration has been updated.', parent = config_window) config_window.destroy() return None messagebox.showerror('Error', 'Both fields are required.', parent = config_window)
save_button = tk.Button(main_frame, text = 'Save & Close', command = save_and_close) save_button.grid(row = 2, column = 1, sticky = 'e', pady = 10) config_window.transient(self) config_window.grab_set() self.wait_window(config_window) self.logic = ChatLogic()
def connect_to_peer(self): ip = self.ip_entry.get() if ip: self.status_label.config(text = f'''Status: Connected to {ip}''', fg = 'green') self.display_message_in_box('--- Welcome to Secure Chat ---', 'system') self.display_message_in_box(f'''[SYSTEM] Connection to {ip} established.\n''', 'system') self.display_message_in_box('You are now talking with the ransomware operator.', 'system') self.display_message_in_box('--------------------------------------------------\n', 'system') self.msg_entry.config(state = 'normal') self.send_button.config(state = 'normal') return None
def display_message_in_box(self, message, tag): self.chat_box.config(state = 'normal') self.chat_box.insert(tk.END, message + '\n', tag) self.chat_box.config(state = 'disabled') self.chat_box.see(tk.END) self.chat_box.tag_config('user', foreground = 'blue') self.chat_box.tag_config('peer', foreground = 'green') self.chat_box.tag_config('system', foreground = 'red') self.chat_box.tag_config('error', foreground = 'orange')
def send_message_event(self, event = (None,)): msg = self.msg_entry.get() if msg: self.display_message_in_box(f'''You: {msg}''', 'user') (_, encrypted_msg_display) = self.logic.process_message(msg) self.display_message_in_box(f'''Peer (Encrypted): {encrypted_msg_display}''', 'peer') self.msg_entry.delete(0, tk.END) return None
def toggle_super_safe(self): if self.super_safe_var.get(): self.logic.super_safe_mode = True self.display_message_in_box('[SYSTEM] Super-Safe mode enabled. Generating RSA key...', 'system') Thread(target = self.generate_rsa_and_update_gui, daemon = True).start() return None self.logic.super_safe_mode = False self.display_message_in_box('[SYSTEM] Super-Safe mode disabled. Reverting to standard LCG-XOR.', 'system')
def generate_rsa_and_update_gui(self): result_msg = self.logic.generate_rsa_key_from_lcg() self.display_message_in_box(f'''[SYSTEM] {result_msg}''', 'system')
def load_last_generated_files(self):Warning: Stack history is not empty!Warning: block stack is not empty! files_window = Toplevel(self) files_window.title('Generated Files') files_window.geometry('700x500') tk.Label(files_window, text = 'chat_log.json', font = ('Helvetica', 12, 'bold')).pack(pady = (10, 0)) json_text_area = scrolledtext.ScrolledText(files_window, wrap = tk.WORD, height = 15) json_text_area.pack(expand = True, fill = 'both', padx = 10, pady = 5) json_path = resource_path('chat_log.json') if open(json_path, 'r'): pass f = open(json_path, 'r') json_data = json.load(f) pretty_json = json.dumps(json_data, indent = 2) json_text_area.insert(tk.END, pretty_json) None(None, None) json_text_area.config(state = 'disabled') tk.Label(files_window, text = 'public.pem', font = ('Helvetica', 12, 'bold')).pack(pady = (10, 0)) pem_text_area = scrolledtext.ScrolledText(files_window, wrap = tk.WORD, height = 8) pem_text_area.pack(expand = True, fill = 'both', padx = 10, pady = (5, 10)) pem_path = resource_path('public.pem') if open(pem_path, 'r'): pass f = open(pem_path, 'r') pem_data = f.read() pem_text_area.insert(tk.END, pem_data) None(None, None) pem_text_area.config(state = 'disabled') return None if None: pass with None: if None or None: pass continue if None and None: pass if FileNotFoundError and FileNotFoundError: json_text_area.insert(tk.END, 'chat_log.json not found.\n\nSend a message to generate it.') continue if Exception and Exception: e = None json_text_area.insert(tk.END, f'''Error reading chat_log.json:\n{e}''') e = None del e continue e = None del e if None and None: pass if None and None: pass with None: if None or None: pass continue if None and None: pass if FileNotFoundError and FileNotFoundError: pem_text_area.insert(tk.END, "public.pem not found.\n\nEnable 'Super-Safe Encryption' to generate it.") continue if Exception and Exception: e = None pem_text_area.insert(tk.END, f'''Error reading public.pem:\n{e}''') e = None del e continue e = None del e if None and None: pass if None: pass
__classcell__ = None
if __name__ == '__main__': app = ChatApp() app.mainloop() return NoneChallenge Breakdown
The challenge file contains five classes. LCGOracle and TripleXorOracle both contains both smart contract bytecodes and ABI. Both of these classes makes use of SmartContracts class which exposes the functions described in respective contracts. ChatLogic contains the initialization of the different classes and cryptographic backend and core logic for ChatApp.
Cryptographic Backend (ChatLogic)
Here is what happen with my username being Owl4444. First my username is being hashed via SHA256 to create the hash seed.
def _get_system_artifact_hash(self): artifact = platform.node().encode('utf-8') ########### USERNAME OWL4444 for me hash_val = hashlib.sha256(artifact).digest() seed_hash = int.from_bytes(hash_val, 'little') print(f'''[SETUP] - Generated Seed {seed_hash}...''') return seed_hashAfter creating the seed, it is used to create three prime numbers by hashing with SHA256 until three prime numbers are created. After which, they would be returned as a tuple. The three prime numbers are the multiplier, constant and modulo.
def _generate_primes_from_hash(self, seed_hash): primes = [] current_hash_byte_length = (seed_hash.bit_length() + 7) // 8 current_hash = seed_hash.to_bytes(current_hash_byte_length, 'little') print('[SETUP] Generating LCG parameters from system artifact...') iteration_limit = 10000 iterations = 0
if len(primes) < 3 and iterations < iteration_limit: current_hash = hashlib.sha256(current_hash).digest() candidate = int.from_bytes(current_hash, 'little') iterations += 1 if candidate.bit_length() == 256 and isPrime(candidate): primes.append(candidate) print(f'''[SETUP] - Found parameter {len(primes)}: {str(candidate)[:20]}...''') if len(primes) < 3 and iterations < iteration_limit: continue if len(primes) < 3: error_msg = '[!] Error: Could not find 3 primes within iteration limit.' print('Current Primes: ', primes) print(error_msg) exit() return (primes[0], primes[1], primes[2])During the initialization of cryptographic backend, the contracts are deployed to prepare the LCG and XOR functions for usage by the application.
LCGOracle
Smart Contract Function
This exposes the LCG PRNG function that supplies application with the next random number. Using dedaub.com, we are able to extract the actual decompilation of the LCGOracle smart contract bytes.
// Decompiled by library.dedaub.com// 2025.09.27 00:44 UTC// Compiled using the solidity compiler version 0.8.30
function _SafeMul(uint256 varg0, uint256 varg1) private { require(!varg0 | (varg1 == varg0 * varg1 / varg0), Panic(17)); // arithmetic overflow or underflow return varg0 * varg1;}
function _SafeSub(uint256 varg0, uint256 varg1) private { require(varg0 - varg1 <= varg0, Panic(17)); // arithmetic overflow or underflow return varg0 - varg1;}
function _SafeAdd(uint256 varg0, uint256 varg1) private { require(varg0 <= varg0 + varg1, Panic(17)); // arithmetic overflow or underflow return varg0 + varg1;}
function fallback() public payable { revert();}
function 0x11521834(uint256 varg0, uint256 varg1, uint256 varg2, uint256 varg3, uint256 varg4) public payable { require(4 + (msg.data.length - 4) - 4 >= 160); require(varg2, Panic(18)); // division by zero require(varg2, Panic(18)); // division by zero if (varg4 > 0) { v0 = v1 = 1; } else { v0 = v2 = 0; } v3 = _SafeMul(uint8(v0), (varg3 * varg0 % varg2 + varg1) % varg2); v4 = _SafeSub(1, uint8(v0)); v5 = _SafeMul(v4, varg3); v6 = _SafeAdd(v5, v3); return v6;}
// Note: The function selector is not present in the original solidity code.// However, we display it for the sake of completeness.
function __function_selector__( function_selector) public payable { MEM[64] = 128; require(!msg.value); if (msg.data.length >= 4) { if (0x11521834 == function_selector >> 224) { 0x11521834(); } } fallback();}The generator is defined by recurrence relation:
The first emitted LCG output we recover from the traffic later on will be denoted x_0. It is also very important to note that the “seed” in the previous x_{-1} state such that:
The python equivalent for this would be:
from collections.abc import Generator
def lcg(modulus: int, a: int, c: int, seed: int) -> Generator[int, None, None]: """Linear congruential generator.""" while True: seed = (a * seed + c) % modulus yield seedTo get the next random value, invoke the get_next function as well as the message count. Doing this would invoke the nextVal function from the smart contract. This function takes in the increment, modolus, state and counter. Though counter is provided, it is not really useful for our cause.
TripleXorOracle
Similarly, by decompiling and extracting the bytes at the right offset, we are able to decompile the smart contract and confirm that it is just xoring three values together. This is initialized in the Cryptographic Backend and is used as described in
// Decompiled by library.dedaub.com// 2025.09.27 01:35 UTC// Compiled using the solidity compiler version 0.8.30
function fallback() public payable { revert();}
function 0x62300756(uint256 varg0, uint256 varg1, bytes varg2) public payable { require(4 + (msg.data.length - 4) - 4 >= 96); require(varg2 <= uint64.max); require(4 + varg2 + 31 < 4 + (msg.data.length - 4)); require(varg2.length <= uint64.max, Panic(65)); // failed memory allocation (too much memory) v0 = new bytes[](varg2.length); require(!((v0 + ((varg2.length + 31 & 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe0) + 32 + 31 & 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe0) > uint64.max) | (v0 + ((varg2.length + 31 & 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe0) + 32 + 31 & 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe0) < v0)), Panic(65)); // failed memory allocation (too much memory) require(varg2.data + varg2.length <= 4 + (msg.data.length - 4)); CALLDATACOPY(v0.data, varg2.data, varg2.length); v0[varg2.length] = 0; if (v0.length <= 32) { v1 = v2 = MEM[v0.data]; } return v1 ^ varg0 ^ varg1;}
// Note: The function selector is not present in the original solidity code.// However, we display it for the sake of completeness.
function __function_selector__( function_selector) public payable { MEM[64] = 128; if (msg.data.length >= 4) { if (0x62300756 == function_selector >> 224) { 0x62300756(); } } fallback();}Encryption Modes
RSA (Custom Implementation)
When generating RSA key, 8 prime numbers are generating via LCG. Anyone familiar with RSA would quickly realize that the RSA implementation here is not really RSA.
def generate_rsa_key_from_lcg(self): print('[RSA] Generating RSA key from on-chain LCG primes...') lcg_for_rsa = LCGOracle(self.lcg_oracle.multiplier, self.lcg_oracle.increment, self.lcg_oracle.modulus, self.seed_hash) lcg_for_rsa.deploy_lcg_contract() primes_arr = [] rsa_msg_count = 0 iteration_limit = 10000 iterations = 0 if len(primes_arr) < 8 and iterations < iteration_limit: candidate = lcg_for_rsa.get_next(rsa_msg_count) rsa_msg_count += 1 iterations += 1 if candidate.bit_length() == 256 and isPrime(candidate): primes_arr.append(candidate) print(f'''[RSA] - Found 256-bit prime #{len(primes_arr)}''') if len(primes_arr) < 8 and iterations < iteration_limit: continue print('Primes Array: ', primes_arr) if len(primes_arr) < 8: error_msg = '[RSA] Error: Could not find 8 primes within iteration limit.' print('Current Primes: ', primes_arr) print(error_msg) return error_msg n = None for p_val in primes_arr: n *= p_val phi = 1 for p_val in primes_arr: phi *= p_val - 1 e = 65537 if math.gcd(e, phi) != 1: error_msg = '[RSA] Error: Public exponent e is not coprime with phi(n). Cannot generate key.' print(error_msg) return error_msg self.rsa_key = None.construct((n, e)) if open('public.pem', 'wb'): pass f = open('public.pem', 'wb') f.write(self.rsa_key.export_key('PEM')) None(None, None) print("[RSA] Public key generated and saved to 'public.pem'") return 'Public key generated and saved successfully.' ...The modulo for RSA N here is calculated by multiplying all 8 generated prime numbers that was generated by LCG with our hashed username as seed. The phi for RSA here is also not standard whereby it is the multiplication of all primes subtracted by 1. However, the encryption algorithm is the same. This means that the decryption calculation can be calculated by finding the inverse of the exponent e modulo phi as seen in the notations presented below. The catch here is that while N can have more than 1 factorizations, it is still not possible to find decryption d right off the bat because the phi calculation is not standard. This hints that we need to crack LCG algorithm without knowing the username used to encrypt the flag messages in the chat room. With 8 prime numbers generated, RSA can be broken with:
With this, when the encryption mode is “RSA”, the message would be encrypted with calculated e. Also, with this mode, the output message would not display the plaintext but “[ENCRYPTED]” so there are no plaintext to work with as well.
def process_message(self, plaintext): if self.conversation_start_time == 0: self.conversation_start_time = time.time() conversation_time = int(time.time() - self.conversation_start_time) if self.super_safe_mode and self.rsa_key: plaintext_bytes = plaintext.encode('utf-8') plaintext_enc = bytes_to_long(plaintext_bytes) _enc = pow(plaintext_enc, self.rsa_key.e, self.rsa_key.n) ciphertext = _enc.to_bytes(self.rsa_key.n.bit_length(), 'little').rstrip(b'\x00') encryption_mode = 'RSA' plaintext = '[ENCRYPTED]' else: ... return (f'''[{conversation_time}s] {plaintext}''', f'''[{conversation_time}s] {ciphertext.hex()}''')LCG-XOR
Another location where LCG is being used is during the encryption of messages when the encryption mode is “LCG-XOR”. It encrypts the message by xor’ing three values:
- LCG value
- conversation time
- plaintext
Looking at the code, note that the conversation time, plaintext as well as ciphertext are exposed in this mode. This means that we can always retrieve the LCG values at different stage. We can extract these values from chatroom as well.
def process_message(self, plaintext): if self.conversation_start_time == 0: self.conversation_start_time = time.time() conversation_time = int(time.time() - self.conversation_start_time) if self.super_safe_mode and self.rsa_key: ... else: prime_from_lcg = self.lcg_oracle.get_next(self.message_count) ciphertext = self.xor_oracle.encrypt(prime_from_lcg, conversation_time, plaintext) encryption_mode = 'LCG-XOR' log_entry = { 'conversation_time': conversation_time, 'mode': encryption_mode, 'plaintext': plaintext, 'ciphertext': ciphertext.hex() } self.chat_history.append(log_entry) self.save_chat_log() return (f'''[{conversation_time}s] {plaintext}''', f'''[{conversation_time}s] {ciphertext.hex()}''')Conversation Messages
By viewing the chatroom, we can see conversations. Of which, the first few messages were done in encryption mode “LCG-XOR” which was later switched to “RSA” where plaintext is redacted. The flag exists in messages encrypted with “RSA” mode.
chat = [{ "conversation_time": 0, "mode": "LCG-XOR", "plaintext": "Hello", "ciphertext": "e934b27119f12318fe16e8cd1c1678fd3b0a752eca163a7261a7e2510184bbe9" }, { "conversation_time": 4, "mode": "LCG-XOR", "plaintext": "How are you?", "ciphertext": "25bf2fd1198392f4935dcace7d747c1e0715865b21358418e67f94163513eae4" }, { "conversation_time": 11, "mode": "LCG-XOR", "plaintext": "Terrible...", "ciphertext": "c9f20e5561acf172305cf8f04c13e643c988aa5ab29b5499c93df112687c8c7c" }, { "conversation_time": 13, "mode": "LCG-XOR", "plaintext": "Is this a secure channel?", "ciphertext": "3ab9c9f38e4f767a13b12569cdbf13db6bbb939e4c8a57287fb0c9def0288e46" }, { "conversation_time": 16, "mode": "LCG-XOR", "plaintext": "Yes, it's on the blockchain.", "ciphertext": "3f6de0c2063d3e8e875737046fef079d73cc9b1b7a4b7b94da2d2867493f6fc5" }, { "conversation_time": 24, "mode": "LCG-XOR", "plaintext": "Erm enable super safe mode", "ciphertext": "787cf6c0be39caa21b7908fcd1beca68031b7d11130005ba361c5d361b106b6d" }, { "conversation_time": 30, "mode": "LCG-XOR", "plaintext": "Ok, activating now", "ciphertext": "632ab61849140655e0ee6f90ab00b879a3a3da241d4b50bab99f74f169d456db" }, { "conversation_time": 242, "mode": "RSA", "plaintext": "[ENCRYPTED]", "ciphertext": "680a65364a498aa87cf17c934ab308b2aee0014aee5b0b7d289b5108677c7ad1eb3bcfbcad7582f87cb3f242391bea7e70e8c01f3ad53ac69488713daea76bb3a524bd2a4bbbc2cfb487477e9d91783f103bd6729b15a4ae99cb93f0db22a467ce12f8d56acaef5d1652c54f495db7bc88aa423bc1c2b60a6ecaede2f4273f6dce265f6c664ec583d7bd75d2fb849d77fa11d05de891b5a706eb103b7dbdb4e5a4a2e72445b61b83fd931cae34e5eaab931037db72ba14e41a70de94472e949ca3cf2135c2ccef0e9b6fa7dd3aaf29a946d165f6ca452466168c32c43c91f159928efb3624e56430b14a0728c52f2668ab26f837120d7af36baf48192ceb3002" }, { "conversation_time": 249, "mode": "RSA", "plaintext": "[ENCRYPTED]", "ciphertext": "6f70034472ce115fc82a08560bd22f0e7f373e6ef27bca6e4c8f67fedf4031be23bf50311b4720fe74836b352b34c42db46341cac60298f2fa768f775a9c3da0c6705e0ce11d19b3cbdcf51309c22744e96a19576a8de0e1195f2dab21a3f1b0ef5086afcffa2e086e7738e5032cb5503df39e4bf4bdf620af7aa0f752dac942be50e7fec9a82b63f5c8faf07306e2a2e605bb93df09951c8ad46e5a2572e333484cae16be41929523c83c0d4ca317ef72ea9cde1d5630ebf6c244803d2dc1da0a1eefaafa82339bf0e6cf4bf41b1a2a90f7b2e25313a021eafa6234643acb9d5c9c22674d7bc793f1822743b48227a814a7a6604694296f33c2c59e743f4106" }]Math Time
Triple Xor Details
Based on the ABI for Triple Xor, we see that the output is 32 bytes long.
self.contract_abi = [ { 'inputs': [ { 'internalType': 'uint256', 'name': '_primeFromLcg', 'type': 'uint256' }, { 'internalType': 'uint256', 'name': '_conversationTime', 'type': 'uint256' }, { 'internalType': 'string', 'name': '_plaintext', 'type': 'string' }], 'name': 'encrypt', 'outputs': [ { 'internalType': 'bytes32', 'name': '', 'type': 'bytes32' }], 'stateMutability': 'pure', 'type': 'function' }]Furthermore, looking up Contract ABI Specification — Solidity 0.8.31-develop documentation, we see that strings that are smaller than the 32 bytes are right-zero padded.
74776f0000000000000000000000000000000000000000000000000000000000 - encoding of "two"7468726565000000000000000000000000000000000000000000000000000000 - encoding of "three"As for the conversationTime, it is a Big Endian 32 bytes value. And the following summarizes how we can recover the 32 bytes state (generated by LCG). By doing this, we can get the state x_i for each of the conversation data.
LCG Details
Recall LCG equation:
To make calculation easier with this recurrence relation, we can get the difference between two states. This gets rid of the constant c and giving us a linear relation.
To double confirm, we can consider two consecutive vectors v_iand v_{i+1}
We can substitute the first two equations from the top of the previous image into z_i to prove that this expanded equation is equivalent to 0 mod n. This means the following as well.
Obtaining LCG Modulo n
Since we have many conversations, we can extract various states x_{i}, calculate the respective z_{i} and get the GCD to obtain the unknown modulo for the LCG!
Solving for multiplier m and constant c
Solving for multiplier and constant is possible because of m and n being coprime with m being super unlikely to be 0 because of hashing algorithm.
Calculating Seed (x_-1)
The following shows how we can recover the initial seed without the need to know the username of the user!
Cracking RSA
With the initial seed, the same algorithm can be run to create the 8 prime numbers to recalculate phi and modulo N for the RSA algorithm. The decryption key can then be created and thus allowing us to decrypt the messages and eventually the flag.
Solve Script
Once this part is understood, ChatGPT is able to spin up a very powerful and accurate script!
#!/usr/bin/env python3import json, argparse, sysfrom math import gcd, prodfrom functools import reducefrom typing import List, Tuple
# ---------- Helpers ----------
def be32(x: int) -> bytes: return x.to_bytes(32, 'big')
def pad32_utf8(s: str) -> bytes: b = s.encode('utf-8') return b[:32] if len(b) > 32 else b + b'\x00' * (32 - len(b))
def invmod(a: int, n: int) -> int: return pow(a % n, -1, n) # Python 3.8+
def hx(x: int, width: int = 64) -> str: h = f"{x:0{width}x}" h = h.lstrip('0') or '0' if len(h) % 2: h = '0' + h return '0x' + h
# ---------- LCG recovery ----------
def recover_x_from_entry(entry: dict) -> int: """be32(x_i) = C ⊕ P32 ⊕ be32(t)""" t = int(entry["conversation_time"]) P32 = pad32_utf8(entry["plaintext"]) C = bytes.fromhex(entry["ciphertext"]) T = be32(t) Xi_bytes = bytes(a ^ b ^ c for a, b, c in zip(C, P32, T)) return int.from_bytes(Xi_bytes, 'big')
def collect_lcg_outputs(chat: List[dict]) -> List[int]: xs = [recover_x_from_entry(e) for e in chat if e.get("mode") == "LCG-XOR"] if len(xs) < 4: raise ValueError("Need ≥4 LCG-XOR entries to recover n.") return xs
def z_values(xs: List[int]) -> List[int]: Z = [] for i in range(len(xs) - 3): s0 = xs[i + 1] - xs[i] s1 = xs[i + 2] - xs[i + 1] s2 = xs[i + 3] - xs[i + 2] z = s2 * s0 - s1 * s1 if z: Z.append(abs(z)) if not Z: raise ValueError("All z_i vanish; need more diverse data.") return Z
def gcd_all(nums: List[int]) -> int: return reduce(gcd, nums)
def recover_n(xs: List[int]) -> int: return gcd_all(z_values(xs))
def recover_m_c(xs: List[int], n: int) -> Tuple[int, int, int]: """ From x1 ≡ m x0 + c (mod n), x2 ≡ m x1 + c (mod n): subtract: (x2 - x1) ≡ m (x1 - x0) (mod n) => m ≡ (x2 - x1) * (x1 - x0)^{-1} (mod n), then c ≡ x1 - m x0 (mod n). Returns (m, c, index_used). """ for i in range(len(xs) - 2): d0 = (xs[i + 1] - xs[i]) % n d1 = (xs[i + 2] - xs[i + 1]) % n if gcd(d0, n) == 1: m = (d1 * invmod(d0, n)) % n c = (xs[i + 1] - m * xs[i]) % n return m, c, i raise RuntimeError("No invertible consecutive difference; need more data.")
def check_recurrence(xs: List[int], m: int, c: int, n: int) -> Tuple[bool, List[int]]: bad = [] for i in range(len(xs) - 1): if (m * xs[i] + c) % n != xs[i + 1] % n: bad.append(i) return (len(bad) == 0), bad
# ---------- LCG stepping / seed ----------
def lcg_step(x: int, m: int, c: int, n: int) -> int: return (m * x + c) % n
def recover_seed_from_x0(x0: int, m: int, c: int, n: int) -> int: """Seed = m^{-1} * (x0 - c) (mod n) if gcd(m, n) = 1.""" return ((x0 - c) * invmod(m, n)) % n
# ---------- Primality (Miller-Rabin) ----------
_MR_BASES_256 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
def is_probable_prime(n: int) -> bool: if n < 2: return False small = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] for p in small: if n == p: return True if n % p == 0: return False # write n-1 = d * 2^s d = n - 1 s = 0 while d % 2 == 0: d //= 2 s += 1
def trial(a): x = pow(a, d, n) if x in (1, n - 1): return True for _ in range(s - 1): x = (x * x) % n if x == n - 1: return True return False
for a in _MR_BASES_256: if a % n == 0: return True if not trial(a): return False return True
def harvest_lcg_primes(seed: int, m: int, c: int, n: int, need: int = 8, limit: int = 10000) -> List[int]: xi = seed primes = [] for _ in range(limit): xi = lcg_step(xi, m, c, n) if xi.bit_length() == 256 and is_probable_prime(xi): primes.append(xi) if len(primes) >= need: break return primes
# ---------- RSA from LCG primes ----------
def build_rsa_private(primes: List[int], e: int = 65537) -> Tuple[int, int, int]: if not primes: raise ValueError("No primes provided.") N = prod(primes) phi = prod(p - 1 for p in primes) d = invmod(e, phi) return N, e, d
def rsa_decrypt_le(cipher_hex: str, N: int, d: int) -> bytes: """Decrypts ciphertext that was logged as little-endian raw pow(m,e,N).""" c = int.from_bytes(bytes.fromhex(cipher_hex), 'little') m = pow(c, d, N) # Convert back to big-endian bytes (like long_to_bytes in challenge) blen = (m.bit_length() + 7) // 8 return m.to_bytes(blen, 'big').rstrip(b'\x00')
# ---------- Main ----------
def main(argv=None): ap = argparse.ArgumentParser( description= "Full solver: recover LCG (n,m,c), seed, harvest 8 primes, build RSA, decrypt RSA-mode messages." ) ap.add_argument( "json", nargs="?", help="Path to chat_log.json. If omitted, uses embedded demo.") args = ap.parse_args(argv)
if args.json: with open(args.json, "r", encoding="utf-8") as f: chat = json.load(f) else: chat = [{ "conversation_time": 0, "mode": "LCG-XOR", "plaintext": "Hello", "ciphertext": "e934b27119f12318fe16e8cd1c1678fd3b0a752eca163a7261a7e2510184bbe9" }, { "conversation_time": 4, "mode": "LCG-XOR", "plaintext": "How are you?", "ciphertext": "25bf2fd1198392f4935dcace7d747c1e0715865b21358418e67f94163513eae4" }, { "conversation_time": 11, "mode": "LCG-XOR", "plaintext": "Terrible...", "ciphertext": "c9f20e5561acf172305cf8f04c13e643c988aa5ab29b5499c93df112687c8c7c" }, { "conversation_time": 13, "mode": "LCG-XOR", "plaintext": "Is this a secure channel?", "ciphertext": "3ab9c9f38e4f767a13b12569cdbf13db6bbb939e4c8a57287fb0c9def0288e46" }, { "conversation_time": 16, "mode": "LCG-XOR", "plaintext": "Yes, it's on the blockchain.", "ciphertext": "3f6de0c2063d3e8e875737046fef079d73cc9b1b7a4b7b94da2d2867493f6fc5" }, { "conversation_time": 24, "mode": "LCG-XOR", "plaintext": "Erm enable super safe mode", "ciphertext": "787cf6c0be39caa21b7908fcd1beca68031b7d11130005ba361c5d361b106b6d" }, { "conversation_time": 30, "mode": "LCG-XOR", "plaintext": "Ok, activating now", "ciphertext": "632ab61849140655e0ee6f90ab00b879a3a3da241d4b50bab99f74f169d456db" }, { "conversation_time": 242, "mode": "RSA", "plaintext": "[ENCRYPTED]", "ciphertext": "680a65364a498aa87cf17c934ab308b2aee0014aee5b0b7d289b5108677c7ad1eb3bcfbcad7582f87cb3f242391bea7e70e8c01f3ad53ac69488713daea76bb3a524bd2a4bbbc2cfb487477e9d91783f103bd6729b15a4ae99cb93f0db22a467ce12f8d56acaef5d1652c54f495db7bc88aa423bc1c2b60a6ecaede2f4273f6dce265f6c664ec583d7bd75d2fb849d77fa11d05de891b5a706eb103b7dbdb4e5a4a2e72445b61b83fd931cae34e5eaab931037db72ba14e41a70de94472e949ca3cf2135c2ccef0e9b6fa7dd3aaf29a946d165f6ca452466168c32c43c91f159928efb3624e56430b14a0728c52f2668ab26f837120d7af36baf48192ceb3002" }, { "conversation_time": 249, "mode": "RSA", "plaintext": "[ENCRYPTED]", "ciphertext": "6f70034472ce115fc82a08560bd22f0e7f373e6ef27bca6e4c8f67fedf4031be23bf50311b4720fe74836b352b34c42db46341cac60298f2fa768f775a9c3da0c6705e0ce11d19b3cbdcf51309c22744e96a19576a8de0e1195f2dab21a3f1b0ef5086afcffa2e086e7738e5032cb5503df39e4bf4bdf620af7aa0f752dac942be50e7fec9a82b63f5c8faf07306e2a2e605bb93df09951c8ad46e5a2572e333484cae16be41929523c83c0d4ca317ef72ea9cde1d5630ebf6c244803d2dc1da0a1eefaafa82339bf0e6cf4bf41b1a2a90f7b2e25313a021eafa6234643acb9d5c9c22674d7bc793f1822743b48227a814a7a6604694296f33c2c59e743f4106" }]
lcg_x = collect_lcg_outputs(chat) print("[+] Recovered LCG outputs x_i:") for i, x in enumerate(lcg_x): print(f" x[{i}] = {hx(x)}")
n = recover_n(lcg_x) print(f"\n[+] Modulus n = {hx(n)}")
m, c, idx = recover_m_c(lcg_x, n) print(f"[+] Multiplier m = {hx(m)}") print( f"[+] Increment c = {hx(c)} (derived using triple starting at i={idx})" )
ok, bad = check_recurrence(lcg_x, m, c, n) print(f"\n[+] Recurrence check: {'OK' if ok else 'FAILED'}") if not ok: print(" Bad indices: ", bad)
# Decrypt LCG-XOR entries (sanity) print("\n[+] Decrypting LCG-XOR entries (should match logged plaintexts):") j = 0 for e in chat: if e.get("mode") == "LCG-XOR": C = bytes.fromhex(e["ciphertext"]) T = be32(int(e["conversation_time"])) K = be32(lcg_x[j]) P32 = bytes(a ^ b ^ c for a, b, c in zip(C, T, K))
print(f" i={j:02d} t={e['conversation_time']:>4} P=", P32.rstrip(b'\\x00').decode('utf-8', 'replace')) j += 1
# Recover seed and harvest 8 primes for RSA seed = recover_seed_from_x0(lcg_x[0], m, c, n) print(f"\n[+] Recovered LCG seed = {hx(seed)}")
primes = harvest_lcg_primes(seed, m, c, n, need=8, limit=20000) print(f"[+] Found {len(primes)} 256-bit primes from LCG (first 8 shown):") for k, p in enumerate(primes[:8]): print(f" p[{k}] = {hx(p)}")
if len(primes) >= 2: N, e, d = build_rsa_private(primes, e=65537) print(f"\n[+] Built RSA private key from LCG primes:") print(f" N = {hx(N, width=len(primes)*64)}") print(f" e = {e}") print(f" d (hex) = {hx(d, width=len(primes)*64)}")
# Try to decrypt any RSA-mode entries rsa_entries = [e for e in chat if e.get("mode") == "RSA"] if rsa_entries: print( "\n[+] Attempting to decrypt RSA-mode entries (little-endian ciphertext quirk):" ) for r in rsa_entries: pt = rsa_decrypt_le(r["ciphertext"], N, d) try: s = pt.decode('utf-8') except: s = pt.hex() print(f" t={r['conversation_time']:>4} plaintext: {s}") else: print("\n[+] No RSA-mode entries found in input.") else: print("\n[!] Could not collect enough primes for RSA.")
if __name__ == '__main__': main()Output
Flag : It's [email protected]
Conclusion
This challenge is interesting and has definitely revived some of the archived mathematics concepts somewhere in my brain and I can finally tell what I studied mathematics for now :D