Okay honestly I don’t know how I can possibly justify this. Either this is hard or I fucked up spectacular. No this challenges has not been playtested. But a solve script exists.
Note from the infra team: No authors were hurt in the making of this CTF. They were insane already…
Category: Crypto
Solver: Greenscreen23, SchizophrenicFish2nds, 3mb0
Flag: GPNCTF{F1eLd_Th30ry_is_fun!11_05ba}
Writeup
Disclaimer: We are not mathematicians and many of these terms were new to us. This writeup therefore will include no proof but rather observations we had. We will also try to explain concepts we feel are beneficial to understanding the challenge (and sage code).
Context
We know that the server uses a known seed to generate $7$ Galois fields of random primes $p$ in $[2^{34}, 2^{38})$ to the power of $18$.
A Galois field $GF(p^{18})$ [1] is a field, i.e. a set of elements supporting two operations (addition and multiplication). There are $p^{18}$ elements in this field, which are represented as polynomials of degree $17$ by sage. So a field element is of the form $c_{17} gg^{17} + c_{16} gg^{16} + ... + c_0$ with $c_i$ between $0$ and $p-1$. They are not polynomials, just a way for sage to represent the elements. The value $gg$ is used as a substitute for $x$ to indicate that these are not polynomials.
The flag is interpreted as an integer and used as the exponent of a known primitive element of the fields.
The primitive element [2] of a Galois field is a generator of the multiplicative group of the field. Each sage $GF$ comes with a modulus polynomial, which is used to iterate the group starting from the primitive element. After each operation, the sage polynomial representation of the field element is reduced modulo this modulus polynomial. This way a single element can be a multiplicative generator and the polynomial degree never increases beyond $17$.
The “hash” we receive is the constant coefficient of the minimal polynomial of the resulting element, i.e. the minimal polynomial evaluated at $0$.
The minimal polynomial [3] of a field element $a$ is the monic polynomial [4] of lowest degree such that $a$ is a root the polynomial. A polynomial is monic if its highest coefficient is $1$. $a$ is a root of a polynomial $f$ if $f(a) = 0$.
Some facts about minimal polynomials: Each polynomial can be a minimal polynomial of at most its degree many elements. In our case the degrees of minimal polynomial don’t exceed $18$. A minimal polynomial also has to be irreducible, i.e. there are no two polynomials whose product this polynomial is. This is caused by the fact that it is the polynomial of minimal degree for which the field element is a root.
We can receive all of these values by connecting to the instance and asking for instance-0 to instance-6. The relevant values are the Field Base, which is the prime $p$, the gen (short for generator), which is the modulus used to represent the field and Hash, which is the minimum polynomial evaluated at $0$.
Decryption
Intuitively, the constant coefficients do not give us a lot of information, as in each field there are $p^{18}$ many elements with at least $\frac{p^{18}}{18}$ many minimal polynomials (each polynomial can have at most its degree many), which have to share the $p$ possible constant coefficients. Because $\frac{p^{18}}{18}$ is a lot larger than $p$, there are a lot of minimal polynomials per coefficient, and we can’t infer the polynomial from the coefficient. We can also see that the coefficient can never be $0$, since this would make the polynomial divisible by $x$, making it reducible.
However, if we order the elements of the field in the order they are generated by the primitive element, calculate the minimal polynomial on each and retrieve its constant coefficient, we can notice a pattern: Each subsequence of $p-1$ minimal polynomials almost has a permutation of the values $1$ to $p-1$ as their constant coefficients. There are some outliers, but in our testing they did not seem to occur that often, and we just hoped to not have to deal with them (which turned out to be true). For example, the constant coefficient of the neutral element’s minimal polynomial (yes, we know how scary this term must sound) was almost always an outlier.
We further noticed that there is a pattern to the permutation of the coefficients. The $i$-th value of the permutation seemed to be equal to the equation $b \cdot m^i$ modulo $p$ for some $b$ and $m$. This pattern can be reproduced using [7]. Because we have the constant coefficient of the minimal polynomial of the flag-th element in the sequence, we can find the value of the flag modulo $p-1$ by finding the position of the coefficient in the permutation. The coefficient $c_0$ has to satisfy the equation $c0 = b \cdot m^i$ mod $p$, so flag $ = \text{dlog}_m(\frac{c_0}{b})$ mod $p-1$ where $\text{dlog}_m(x)$ is the discrete logarithm of $x$ to the base $m$. The group size is at most $2^{38}$, so the discrete logarithm can already be computed efficiently using baby step giant step, but sage also implements other algorithms [5], making this quickly computable.
We now have $7$ equations for the flag modulo some $p-1$. We can compose these with CRT [6], and as the seeds are known we know the composed modulus. This is $1731648896272745876582362899926944345215023918199883985726424096$, which is enough to extract 26 bytes, but the flag is longer (35).
Instead, we leverage additional knowledge of the flag format: We know that the flag starts with GPNCTF{, which are the most significant bytes. The flag also ends with }. We can therefore write the flag as a sum of GPNCTF{\0 * 27} and the content in between. Subtracting the integer value of GPNCTF{\0 * 27} modulo our current modulus from what we currently know of our flag leaves us with $28$ bytes of unknown flag content.
Our modulus is now only two bytes short of the solution, so we extend it by guessing another residual and reconstruct the possible flag by adding the integer value of GPNCTF{\0 * 27} and testing whether the result is printable ASCII.
The whole process is implemented as a sage script [8]. We implement the extraction of the parameters $b$ and $m$ of the permutation by sampling the first $1000$ constant coefficients and looking at what values of $b$ and $m$ are most likely.
Other resources
Weblinks
[1] https://en.wikipedia.org/wiki/Finite_field
[2] https://en.wikipedia.org/wiki/Primitive_element_(finite_field)
[3] https://en.wikipedia.org/wiki/Minimal_polynomial_(field_theory)
[4] https://en.wikipedia.org/wiki/Monic_polynomial
[6] https://doc.sagemath.org/html/en/reference/rings_standard/sage/arith/misc.html#sage.arith.misc.CRT
Scripts
[7] Sage script to compare the permutations of different Galois fields. The plot especially highlights that the pattern is not totally perfect.
import matplotlib.pyplot as plt
p = 7
e = 3
K.<gg> = GF(p^e, modulus="primitive")
vals = [(gg^i).minpoly()(0) for i in range(p^e)]
print(vals[:(p-1)])
print(vals[(p-1):2*(p-1)])
fig, ax = plt.subplots()
ax.scatter(range(len(vals)), vals)
ax.plot(range(len(vals)), vals)
plt.show()
[8] Solve script in sage. For each instance of a Galois field we store the prime p, the constant coefficient h and the modulus polynomial of the Galois field mod. It is important to store the polynomial, as sage sometimes generates a different polynomial as the modulus, mixing the permutation of constant coefficients.
from collections import Counter
from Crypto.Util.number import long_to_bytes
instances = [
(
12989629649,
11361642223,
x**18
+ 9186841607 * x**17
+ 1274546038 * x**16
+ 8393840263 * x**15
+ 3223611090 * x**14
+ 8074867216 * x**13
+ 11712046102 * x**12
+ 51880999 * x**11
+ 1218742911 * x**10
+ 5282301310 * x**9
+ 10360318930 * x**8
+ 3827078469 * x**7
+ 12865034666 * x**6
+ 10220119708 * x**5
+ 5977930642 * x**4
+ 9414127687 * x**3
+ 6167009159 * x**2
+ 5003122651 * x
+ 3130386283,
),
(
14003207459,
11380806741,
x**18
+ 4986103062 * x**17
+ 12474563245 * x**16
+ 9626385123 * x**15
+ 6834442812 * x**14
+ 4066954572 * x**13
+ 22424825 * x**12
+ 141225218 * x**11
+ 1142267289 * x**10
+ 7303614185 * x**9
+ 7776510271 * x**8
+ 11132498721 * x**7
+ 4130803336 * x**6
+ 7568341171 * x**5
+ 1077600346 * x**4
+ 6112753666 * x**3
+ 2436371698 * x**2
+ 13411553863 * x
+ 141436191,
),
(
8337193087,
8224791240,
x**18
+ 4127734925 * x**17
+ 307198265 * x**16
+ 3138495650 * x**15
+ 1023344772 * x**14
+ 4091997163 * x**13
+ 12140960 * x**12
+ 7915651546 * x**11
+ 764078734 * x**10
+ 4738009242 * x**9
+ 2148890949 * x**8
+ 1524934434 * x**7
+ 5657088400 * x**6
+ 2964297141 * x**5
+ 3127846741 * x**4
+ 1467576749 * x**3
+ 7852140459 * x**2
+ 6370761594 * x
+ 1737050174,
),
(
16418997857,
11863444336,
x**18
+ 12727680211 * x**17
+ 7492206168 * x**16
+ 13197199385 * x**15
+ 2259085288 * x**14
+ 11663552223 * x**13
+ 10158227344 * x**12
+ 4109061946 * x**11
+ 11534871402 * x**10
+ 1939844297 * x**9
+ 7773215614 * x**8
+ 15397011011 * x**7
+ 15192001764 * x**6
+ 13831383633 * x**5
+ 2391963765 * x**4
+ 8348512898 * x**3
+ 5315016888 * x**2
+ 10791313777 * x
+ 3095416943,
),
(
2212516879,
471530723,
x**18
+ 1986490504 * x**17
+ 831744339 * x**16
+ 1868955369 * x**15
+ 1499940326 * x**14
+ 17642148 * x**13
+ 1162421070 * x**12
+ 409985592 * x**11
+ 1392395931 * x**10
+ 1530877688 * x**9
+ 1766788583 * x**8
+ 1270645035 * x**7
+ 144505055 * x**6
+ 1524635271 * x**5
+ 1377594543 * x**4
+ 1007964295 * x**3
+ 2108461419 * x**2
+ 763524619 * x
+ 2118619865,
),
(
2047088669,
455590877,
x**18
+ 1785928337 * x**17
+ 1958345164 * x**16
+ 1157860580 * x**15
+ 303784444 * x**14
+ 1717901304 * x**13
+ 972965351 * x**12
+ 838582366 * x**11
+ 2023201489 * x**10
+ 390194123 * x**9
+ 770295471 * x**8
+ 274634857 * x**7
+ 2045187296 * x**6
+ 1513001347 * x**5
+ 1996069867 * x**4
+ 1661127148 * x**3
+ 1650068670 * x**2
+ 1073723207 * x
+ 1387336801,
),
(
2169825653,
1067495220,
x**18
+ 1343748268 * x**17
+ 1208808064 * x**16
+ 2034617206 * x**15
+ 1278896403 * x**14
+ 961440812 * x**13
+ 1940066634 * x**12
+ 815486510 * x**11
+ 1024295669 * x**10
+ 1656539146 * x**9
+ 1621172462 * x**8
+ 1288627327 * x**7
+ 1852920111 * x**6
+ 1077242096 * x**5
+ 212126460 * x**4
+ 1197618664 * x**3
+ 395223692 * x**2
+ 1692859316 * x
+ 420081178,
),
]
FLAG_MASK = b"GPNCTF{\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00}"
mask = Integer(FLAG_MASK.hex(), 16)
def get_position_in_permutation(p, h, mod):
K.<gg> = GF(p**18, modulus=mod)
R = Zmod(p)
constant_coefficients = [(gg**i).minpoly()(0) for i in range(1000)]
m_options = [
R(constant_coefficients[i + 1]) / R(constant_coefficients[i])
for i in range(len(constant_coefficients) - 1)
]
m = Counter(m_options).most_common()[0][0]
b_options = [
coefficient / (m**i) for i, coefficient in enumerate(constant_coefficients)
]
b = Counter(b_options).most_common()[0][0]
return discrete_log(R(h) / R(b), R(m), ord=p - 1)
residues = [get_position_in_permutation(p, h, mod) for p, h, mod in instances]
moduli = [p - 1 for p, h, mod in instances]
residue = CRT(residues, moduli)
modulus = lcm(moduli)
residue = (residue - mask) % modulus
for guessed_residue in range(1, 65537):
flag = long_to_bytes(CRT(residue, guessed_residue, modulus, 65537) + mask)
if flag.isascii() and flag.decode().isprintable():
print(flag)