Flash CTF – Grinch’s Cryptological Defense

December 21, 2024
Challenge Writeups
2 min read

Challenge Objective

#!/usr/local/bin/python

from Crypto.Util.number import * 
from os import urandom
flag = open('/tmp/flag.txt','rb').read()

f = next(f for _ in iter(int, 1) if isPrime(f := bytes_to_long(flag + urandom(128 - len(flag)))) and f.bit_length() == 1023)

print("You'll never get Christmas back without my password! I'm so confident you'll never figure it out, I'll even give you hints!")
while (option := input('Would you like a hint (yes)? ')) == '' or option[0].lower() == 'y':
    print(f'Here you go: {f * getPrime(100) + getPrime(40)}')

The goal of this challenge is to recover the flag integer f using the LLL algorithm. This challenge represents an instance of the approximate GCD problem. Even though the server provides infinite hints, we only need 2-3 to recover the flag.

Proof of Concept (PoC)

The equations for the hints we’re given are:

h_1 = f \cdot p_1 + n_1
h_2 = f \cdot p_2 + n_2
\vdots
h_i = f \cdot p_i + n_i

Where:

  • h represents the hint,
  • p is a prime number,
  • n is a small added noise.

By constructing a lattice, we can use the LLL algorithm to solve for �f. Here’s the reasoning.

Mathematical Breakdown

Consider the first three hint equations:

h_1 = f \cdot p_1 + n_1
h_2 = f \cdot p_2 + n_2
h_3 = f \cdot p_3 + n_3

Isolating f in each equation:

f = \frac{h_1 - n_1}{p_1}
f = \frac{h_2 - n_2}{p_2}
f = \frac{h_3 - n_3}{p_3}

We now set ℎ1h1 as our “constant” and equate the expressions for �f:

\frac{h_1 - n_1}{p_1} = \frac{h_2 - n_2}{p_2}
\frac{h_1 - n_1}{p_1} = \frac{h_3 - n_3}{p_3}

Rearranging to eliminate the denominators, we get:

p_2 (h_1 - n_1) = p_1 (h_2 - n_2)
p_3 (h_1 - n_1) = p_1 (h_3 - n_3)

Since the noise factors �ni are very small and the LLL algorithm is approximate, we can discard �ni and simplify:

p_2 \cdot h_1 \approx p_1 \cdot h_2
p_3 \cdot h_1 \approx p_1 \cdot h_3

 ### Constructing the Lattice

The lattice we construct will be based on the simplified equations:

p_2 \cdot h_1 \approx p_1 \cdot h_2
p_3 \cdot h_1 \approx p_1 \cdot h_3

We will build the lattice in such a way that running the LLL algorithm on it will give us a vector where the small entries correspond to the values of f * p_1, f * p_2, etc. To achieve this, we can construct a matrix with the hint values and carefully chosen coefficients to form a basis that contains these terms.

Let’s define the lattice matrix M as follows:

M = Matrix([
    [1, 0, 0, hs[1], hs[2]],
    [0, 1, 0, -hs[0], 0],
    [0, 0, 1, 0, -hs[0]],
])

This matrix is constructed in such a way that running the LLL algorithm will help us recover the small primes p_1, p_2, and p_3. A vector in this basis will have the form:

(a, b, c, h_1 \cdot a - h_0 \cdot b, h_2 \cdot a - h_0 \cdot c)

After applying LLL to this lattice, we can expect to retrieve the values of the prime multipliers from the shortest vector output by LLL.

Applying LLL

We now apply the LLL algorithm to this matrix to find the small prime multipliers:

M = M.LLL()[0]  # Extract the shortest vector
ps = [M[0], M[1], M[2]]  # The prime multipliers used in the hints

Recovering the Flag

Finally, using the small primes obtained from the LLL output, we can recover the flag f using the hint equations:

def recoverPrime(p, hint):
    p = abs(p)
    add = hint % p  # This extracts the noise
    flag = (hint - add) // p  # Recover the flag
    print(long_to_bytes(int(flag)))

# Recover the flag for each hint using the corresponding prime
for i in range(3):
    recoverPrime(ps[i], hs[i])

This will give us the flag as the output of the script.

Sign In

Get Started