> For the complete documentation index, see [llms.txt](https://lance-kenji.gitbook.io/me/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://lance-kenji.gitbook.io/me/nullcon-hackim-ctf-goa-2026-writeups/crypto/matrixfun-ii.md). # Matrixfun II **Category:** Cryptography **Difficulty:** Medium *** #### 1. Challenge Overview The challenge provides a Python script and a remote service. Upon connecting, the server encrypts a hidden flag using a custom scheme and then acts as an oracle, allowing us to encrypt any hex-encoded message of our choice. The core of the encryption lies in a linear transformation performed on blocks of 16 characters. The message is first Base64 encoded, then mapped to indices using a custom 65-character alphabet: `abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789+/=`. `chall.py` ```python import numpy as np import base64 alphabet = b'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789+/=' MOD = len(alphabet) n = 16 def gen_key(n = n): A = np.random.randint(0, MOD, size = (n,n)) b = np.random.randint(0, MOD, size = n) return A,b def pad(msg : bytes, n = n): padlen = n - (len(msg) % n) return msg + b'=' * padlen def encrypt(msg : bytes, A, b): if type(msg) == str: msg = msg.encode() msg = base64.b64encode(msg) msg = pad(msg) cipher = np.zeros(len(msg), dtype = np.int_) block = np.zeros(n, dtype = np.int_) for i in range(0,len(msg), n): for j in range(n): block[j] = alphabet.index(msg[i+j]) cipher[i:i+n] = A @ block + b return cipher % MOD if __name__ == '__main__': A,b = gen_key() msg = open('flag.txt','r').read().strip() cipher = encrypt(msg, A, b).tolist() print(cipher) while True: msg = input('enter your message (in hex): ').strip() if msg == 'exit': break msg = bytes.fromhex(msg) print(encrypt(msg, A, b).tolist()) ``` #### 2. Vulnerability Analysis By inspecting the `encrypt` function, we can see it is a textbook **Affine Hill Cipher**: ```python cipher[i:i+n] = A @ block + b return cipher % MOD ``` * **$A$** is a $16 \times 16$ secret matrix. * **$b$** is a secret bias vector of length 16. * **$MOD$** is 65 (the length of the alphabet). Since the matrix $A$ and vector $b$ remain constant for the session, the system is entirely linear. If we can provide enough "chosen plaintexts," we can construct a system of linear equations to solve for the unknowns $A$ and $b$ using modular arithmetic. #### 3. Developing the Exploit To break the cipher, we need to recover $A$ and $b$. Because we are working in $\mathbb{Z}\_{65}$, we must remember that $65 = 5 \times 13$. A matrix is only invertible modulo 65 if its determinant is coprime to both 5 and 13. **The Plan:** 1. **Collect Samples:** Send a "base" message to get a baseline ciphertext $C\_0$ corresponding to a known plaintext $P\_0$. Then, send 16 additional random messages to get pairs $(P\_i, C\_i)$. 2. **Isolate $A$:** Subtract the baseline to eliminate $b$: $$(C\_i - C\_0) \equiv A(P\_i - P\_0) \pmod{65}$$ 3. **Solve for $A$:** Construct a matrix $X$ from the plaintext differences and $Y$ from the ciphertext differences. $$Y = AX \implies A = Y \cdot X^{-1} \pmod{65}$$ 4. **Solve for $b$:** Once $A$ is known, $b = C\_0 - AP\_0 \pmod{65}$. 5. **Decrypt the Flag:** Use the recovered $A$ and $b$ to reverse the transformation on the flag's ciphertext: $$P\_{flag} = A^{-1}(C\_{flag} - b) \pmod{65}$$ #### 4. The Solution Script The following script automates the collection of samples and uses `SymPy` to handle the modular matrix inversion. ```python import base64 import os from pwn import * from sympy import Matrix alphabet = b'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789+/=' MOD = 65 N = 16 def get_indices(b64_bytes): return [alphabet.index(c) for c in b64_bytes] def solve(): io = remote('52.59.124.14', 5101) # 1. Capture the flag's ciphertext flag_cipher = eval(io.recvline().decode()) # 2. Collect 17 samples (1 base + 16 for basis) P_list, C_list = [], [] for _ in range(17): msg = os.urandom(12) # 12 bytes results in 16 b64 chars io.sendlineafter(b': ', msg.hex().encode()) c_val = eval(io.recvline().decode()) P_list.append(get_indices(base64.b64encode(msg))) C_list.append(c_val[:N]) P = np.array(P_list).T C = np.array(C_list).T # 3. Solve Linear System X = Matrix((P[:, 1:] - P[:, 0:1]) % MOD) Y = Matrix((C[:, 1:] - C[:, 0:1]) % MOD) A = (Y * X.inv_mod(MOD)) % MOD b = (Matrix(C[:, 0]) - A * Matrix(P[:, 0])) % MOD # 4. Decrypt the Flag blocks A_inv = A.inv_mod(MOD) flag_b64 = "" for i in range(0, len(flag_cipher), N): c_block = Matrix(flag_cipher[i:i+N]) p_block = (A_inv * (c_block - b)) % MOD flag_b64 += "".join(chr(alphabet[int(x)]) for x in p_block) print(f"Decoded: {base64.b64decode(flag_b64.split('=')[0] + '==')}") ``` #### 5. The Winning Payload Because the system is a Chosen Plaintext Attack, the "payload" is simply any set of 17 distinct 12-byte hex strings. For example: `enter your message (in hex): 000102030405060708090a0b` By providing enough variety in these inputs, we ensure our matrix $X$ is invertible, allowing us to extract the secret key. #### 6. Result After running the exploit, the matrix $A$ and vector $b$ are recovered. Applying the inverse transformation to the initial ciphertext provided by the server reveals the flag: ```bash [/.......] Opening connection to 52.59.124.14 on port 5101: Trying 52.59.1[+] Opening connection to 52.59.124.14 on port 5101: Done [*] Searching for an invertible matrix basis... [+] Found invertible matrix! [*] Closed connection to 52.59.124.14 port 5101 [!] FLAG: ENO{l1ne4r_alg3br4_i5_ev3rywh3re} ``` **Flag:** `ENO{l1ne4r_alg3br4_i5_ev3rywh3re}` --- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://lance-kenji.gitbook.io/me/nullcon-hackim-ctf-goa-2026-writeups/crypto/matrixfun-ii.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.