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

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:

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.

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:

[/.......] 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}