X3CTF (feat. MVM)#

This is my first time in participating international CTFs
I got lucky to solve a couple of challenges

Man vs Matrix#

Category: #Crypto

Desc: I’ve just built an RNG algorithm from scratch. Can you break it?

TL;DR

Linear Functions: Modeled each sample as a linear equation involving the RNG’s matrix entries and states.
State Propagation: Tracked deterministic state updates via exponentiation in GF(p) to compute all required states.
Matrix Recovery: Solved the system using SageMath to reverse-engineer the matrix from the samples.
Seed Extraction: Converted matrix entries to 3-byte chunks (big-endian) to reconstruct the seed.

Final Flag: ||MVM{l1n34r_fuNcT10n5_4r3_my_f4v}||

Code

1
from sage.all import *
2
from Crypto.Util.number import long_to_bytes
3

4
samples = [6192533, 82371, 86024, 4218430, 12259879, 16442850, 6736271, 7418630, 15483781]
5

6
p = next_prime(2**24)
7
F = GF(p)
8
gen = F(2)
9

10
# Compute all states S0 to S9
11
states = []
12
current_state = vector(F, [ord(c) for c in "Mvm"])  # S0
13
states.append(current_state)
14
for _ in range(9):
15
    next_state = vector(F, [gen**int(s) for s in current_state])
16
    states.append(next_state)
17
    current_state = next_state
18

19
# Prepare the coefficient matrix A and vector b
20
A = []
21
b = []
22
for k in range(9):
23
    S_prev = states[k]
24
    S_curr = states[k+1]
25
    equation = []
26
    # Expand (M * S_prev) ⋅ S_curr = sum_{i,j} M[i,j] * S_prev[j] * S_curr[i]
27
    for i in range(3):
28
        for j in range(3):
29
            equation.append(S_prev[j] * S_curr[i])
30
    A.append(equation)
31
    b.append(samples[k])
32

33
# Solve the system A * M_flattened = b
34
A_matrix = matrix(F, A)
35
b_vector = vector(F, b)
36
M_flattened = A_matrix.solve_right(b_vector)
37

38
# Reshape the flattened matrix into 3x3
39
M = matrix(F, 3, 3, M_flattened)
40

41
# Extract seed from matrix M
42
seed_bytes = b""
43
for element in M.list():
44
    seed_bytes += int(element).to_bytes(3, 'big')
45

46
# Construct the flag
47
flag = b"MVM{" + seed_bytes + b"}"
48
print(flag.decode('latin1'))