hxp CTF 2025: Sharing Solution
hubertf, 2025-12-30

High-Level Flow:
Takes flag as command-line argument (38 bytes: hxp{...34 chars...})
Spawns a worker thread
Both threads perform GF(251) matrix transformations
Main thread accumulates results from both threads
Success if all output bytes equal 0

Mathematical Model:
The transformation is linear in Galois Field GF(251):
output = A × flag + b (mod 251)

where:
A is a 42x42 matrix in GF(251)
b is a constant vector (depends on hardcoded values)
flag is the user input (42 bytes, padded with zeros if shorter)

Since the transformation is linear:

A × flag + b = 0
A × flag = -b
flag = A⁻¹ × (-b)

Solution:

(venv.39c3) 39c3$ cat ../2solve.py
#!/usr/bin/env python3
"""
hxp CTF 2025 - "sharing" Challenge Solver
"""

import subprocess
import json
import os
import sys
import tempfile

def gf251_add(a, b): return (a + b) % 251
def gf251_sub(a, b): return (a - b + 251) % 251
def gf251_mul(a, b): return (a * b) % 251
def gf251_inv(a): return pow(a, 249, 251) if a else 0

def matrix_inverse_gf251(mat):
    n = len(mat)
    aug = [[mat[i][j] for j in range(n)] + [1 if i==k else 0 for k in range(n)] for i in range(n)]
    for col in range(n):
        pivot = next((r for r in range(col, n) if aug[r][col] != 0), None)
        if pivot is None: return None
        aug[col], aug[pivot] = aug[pivot], aug[col]
        inv_p = gf251_inv(aug[col][col])
        aug[col] = [gf251_mul(x, inv_p) for x in aug[col]]
        for row in range(n):
            if row != col and aug[row][col] != 0:
                f = aug[row][col]
                aug[row] = [gf251_sub(aug[row][j], gf251_mul(f, aug[col][j])) for j in range(2*n)]
    return [[aug[i][n+j] for j in range(n)] for i in range(n)]

def matrix_vector_mul(mat, vec):
    return [sum(gf251_mul(mat[i][j], vec[j]) for j in range(len(vec))) % 251 for i in range(len(mat))]

def get_output_via_gdb(binary_path, flag_str, debug=False):
    """Extract 42-byte output using GDB with Python."""
    escaped = flag_str.replace('\\', '\\\\').replace('"', '\\"')

    gdb_script = f'''set pagination off
set confirm off
set args "{escaped}"
starti
python
import gdb
output = gdb.execute("info proc mappings", to_string=True)
base = None
for line in output.split('\\n'):
    # Look for executable section (r-xp) of our binary
    if 'r-xp' in line and 'sharing' in line:
        parts = line.split()
        base = int(parts[0], 16)
        break
if base is None:
    print("ERROR: Could not find base address")
    gdb.execute("quit")
bp_addr = base + 0xb73
gdb.execute(f"break *{{hex(bp_addr)}}")
gdb.execute("continue")
result = []
for i in range(42):
    val = gdb.parse_and_eval(f"*(unsigned char*)($rsp+0x40+{{i}})")
    result.append(int(val))
print("RESULT:" + ",".join(map(str, result)))
end
quit
'''

    with tempfile.NamedTemporaryFile(mode='w', suffix='.gdb', delete=False) as f:
        f.write(gdb_script)
        script_path = f.name

    try:
        result = subprocess.run(
            ['gdb', '-batch', '-x', script_path, binary_path],
            capture_output=True, text=True, timeout=30
        )

        if debug:
            print("=== GDB STDOUT ===")
            print(result.stdout[-2000:])
            print("=== GDB STDERR ===")
            print(result.stderr[-500:])

        for line in result.stdout.split('\n'):
            if line.startswith('RESULT:'):
                vals = [int(x) for x in line[7:].split(',')]
                if len(vals) == 42:
                    return vals
            if line.startswith('ERROR:'):
                print(f"[!] {line}")
    except Exception as e:
        print(f"[!] GDB error: {e}")
    finally:
        os.unlink(script_path)

    return None

def extract_matrix(binary_path, size=42):
    print("[*] Extracting transformation matrix...")
    base_flag = "hxp{" + " " * 37 + "}"

    print("[*] Testing GDB extraction...")
    base_output = get_output_via_gdb(binary_path, base_flag, debug=True)
    if base_output is None:
        raise RuntimeError("GDB extraction failed - see debug output above")

    print(f"[+] Base output: {base_output[:6]}...")

    A_cols = []
    for col in range(size):
        chars = list(base_flag)
        if col < len(chars):
            chars[col] = chr((ord(chars[col]) + 1) % 256)
        test_flag = ''.join(chars)

        out = get_output_via_gdb(binary_path, test_flag)
        if out is None:
            print(f"[!] Failed at column {col}")
            A_cols.append([0] * size)
        else:
            A_cols.append([gf251_sub(out[i], base_output[i]) for i in range(size)])

        if (col + 1) % 10 == 0:
            print(f"[*] Progress: {col + 1}/{size}")

    return {'A': A_cols, 'b': base_output, 'base_flag': [ord(c) for c in base_flag]}

def solve(data):
    A = [[data['A'][j][i] for j in range(42)] for i in range(42)]
    A_inv = matrix_inverse_gf251(A)
    if A_inv is None:
        raise RuntimeError("Matrix singular")
    neg_b = [(251 - x) % 251 for x in data['b']]
    delta = matrix_vector_mul(A_inv, neg_b)
    flag = [gf251_add(data['base_flag'][i], delta[i]) for i in range(42)]
    while flag and flag[-1] == 0:
        flag.pop()
    return bytes(flag)

def main():
    binary = './sharing'
    cache = 'matrix_cache.json'

    if not os.path.exists(binary):
        print(f"[!] Binary not found: {binary}")
        sys.exit(1)

    if '--extract' in sys.argv or not os.path.exists(cache):
        print("[*] Extracting matrix (~2 min)...")
        data = extract_matrix(binary)
        with open(cache, 'w') as f:
            json.dump(data, f)
        print(f"[+] Saved to {cache}")
    else:
        print(f"[*] Loading {cache}")
        with open(cache) as f:
            data = json.load(f)

    print("[*] Solving...")
    flag = solve(data)
    print(f"\n[+] Flag: {flag.decode()}")

    result = subprocess.run([binary, flag.decode()], capture_output=True, text=True)
    if ':)' in result.stdout:
        print("[+] Verified!")
    else:
        print("[!] Verification failed")

if __name__ == '__main__':
    main()


Run it:

(venv.39c3) 39c3$ python3 ../2solve.py --extract
[*] Extracting matrix (~2 min)...
[*] Extracting transformation matrix...
[*] Testing GDB extraction...
=== GDB STDOUT ===

This GDB supports auto-downloading debuginfo from the following URLs:
  <https://debuginfod.ubuntu.com>
Enable debuginfod for this session? (y or [n]) [answered N; input not from terminal]
Debuginfod has been disabled.
To make this setting permanent, add 'set debuginfod enabled off' to .gdbinit.

Program stopped.
0x00007ffff7fe4540 in _start () from /lib64/ld-linux-x86-64.so.2
Breakpoint 1 at 0x555555556b73
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".
[New Thread 0x7ffff77ff6c0 (LWP 175730)]
[Thread 0x7ffff77ff6c0 (LWP 175730) exited]

Thread 1 "sharing" hit Breakpoint 1, 0x0000555555556b73 in ?? ()
RESULT:5,100,31,189,7,159,128,125,151,209,217,83,1,109,96,26,69,151,111,3,203,139,103,168,53,139,246,4,123,133,0,164,126,213,14,21,15,113,118,16,161,119

=== GDB STDERR ===

[+] Base output: [5, 100, 31, 189, 7, 159]...
[*] Progress: 10/42
[*] Progress: 20/42
[*] Progress: 30/42
[*] Progress: 40/42
[+] Saved to matrix_cache.json
[*] Solving...

[+] Flag: hxp{te4mw0rk-maKe5-the-n!ghtm4re-w0rk}
[+] Verified!
(venv.39c3) 39c3$
(venv.39c3) 39c3$ ./sharing 'hxp{te4mw0rk-maKe5-the-n!ghtm4re-w0rk}'
:)

Enjoy!