Finite Realm of Random (498 points, 4 solves)

Introduction

Our team Black Bauhinia participated in the idekCTF 2023 which spaces two days. Finite Realm of Random was an interesting math / crypto puzzle. In the end, only 3 teams solved it the intended way, and we were the second.

Problem Statement

Description: I took a flag, and shuffled it. I took a part, and randomized it. I took the bits and pieces, and scattered them across the field. Now, only an haphazard mess remains.

Author: A~Z

Binary: finite-realm-of-random.tar.gz

Solution Outline

By observing that the code maps the original flag-encoded polynomial to its Galois conjugates, we try all 32 possibilities and retrieve the flag.

A Bit of Math

Let $L = \mathbb{F}_{127^32}$ and $g$ be a fixed generator of $L$. The flag is splitted into character blocks and the following operation is performed:

1. The block is encoded by $\vec{c} = (c_0, c_1, \cdots, c_{31}) \mapsto f = c_0 + c_1g + \cdots + c_{31}g^{31}$
2. For at most $5$ times:
   • Two elements $r_1$ and $r_2$ are chosen with the same minimal polynomial in $L$
   • Find a polynomial $g(X) \in \mathbb{F}_{127}[X]$ satisfying $\deg(g) \leq 31$ and $g(r_1) = f$
   • Replace $f$ by $g(r_2)$
3. We receive the resulting $f$

Let us first analyse the curious code in 2(a) by recalling the following fact.

In fancy math terms, we say that the minimal polynomial of $\alpha$ are precisely the Galois conjugates of $\alpha$. Applying this to our problem, we see that $r_2 = \sigma(r_1)$ for some $\sigma \in \mathrm{Gal}(L / K)$. Moreover, recall that the Galois group of a finite field is generated by the Frobenius endomorphism $\mathrm{Frob}_p$, defined by the map $x \mapsto x^p$. That is,

$$ \mathrm{Gal}(\mathbb{F}_{p^n} / \mathbb{F}_p) = {\mathrm{Frob}_p^i : 0 \leq i < n} \cong \mathbb{Z} / n\mathbb{Z} $$

In fact, we can check this in Sage:

sage: GF(17^16).galois_group()
Galois group C16 of GF(17^16)

This implies that $r_2$ and $r_1$ are Galois conjugates of each other, or more concretely, $r_2 = r_1^{p^k}$ for some $k$. Now, let us move on to the rest of the algorithm. The provided code then computes a polynomial that maps $g: r_1 \mapsto f$ and correspondingly maps $r_2 \mapsto g(r_2)$. Since $g$ is a polynomial, we can apply Freshman’s Dream for the following transformation:

$$ \begin{align*} g(r_1)^{p^k} &= \left(\sum_{i = 0}^{31} g_i r_1^i\right)^{p^k} \ &= \sum_{i = 0}^{31} (g_i r_1^i)^{p^k} \ &= \sum_{i = 0}^{31} g_i r_1^{ip^k} \ &= g(r_1^{p^k}) \ &= g(r_2) \end{align*} $$

Where we used the fact that $\forall \sigma \in \mathrm{Gal}(L / K), x \in K, \sigma(x) = x$, which gives $g_i \in \mathbb{F}_p \implies g_i^{p^k} = g_i$. Finally, this means that step 2 of the code just maps $f \mapsto g(r_2) = g(r_1)^{p^k} = f^{p^k} = \mathrm{Frob}_p^k(f)$. Therefore, to recover the original $f$, we simply look at all 32 conjugates of the given $f$.

Code

# Curiously, random is not random
L = GF(127)
for i in range(5):
    L = L['x'].irreducible_element(2, algorithm='random').splitting_field(f't{i}')

# Parses resulting f
ct = bytes.fromhex(open('out.txt', 'r').read())
assert len(ct) % L.degree() == 0
blocks = [L(list(map(int, ct[i:i + L.degree()]))) for i in range(0, len(ct), L.degree())]

def convert(poly):
    return bytes(map(int, poly.polynomial().coefficients()))

for c in blocks:
    for i in range(32):
        # Checks conjugates by f -> f^(p^i)
        r = bytes(vector(c^(127^i)))
        if all(32 <= t < 127 or t == 0 for t in r):
            print(r.decode())

Flag: idek{4nd_7hu5_5p0k3_G4!015:_7h3_f1n1t3_r34Lm_sh4ll_n07_h4rb0ur_r4nd0mn355,_0n!y_7h3_fr0b3n1u5__}