Google CTF 2023 - LEAST COMMON GENOMINATOR?

Description

Category: Cryptography

Someone used this program to send me an encrypted message but I can’t read it! It uses something called an LCG, do you know what it is? I dumped the first six consecutive values generated from it but what do I do with it?!

Attachment

1. Overview

For the challenge, we have 4 files:

• dump.txt: contains integers
• flag.txt: encrypted flag
• generate.py: Python script used to encrypt the flag
• public.pem: public key

Let’s find out how the flag has been encrypted by analyzing generate.py.

• It uses a LCG (Linear congruential generator) to generate random numbers;
• The LCG generates random numbers until it generates a certain number (config.it) of prime numbers and meets certain conditions;
• The first 6 numbers generated by the LCG are stored in the dump.txt;
• Once the prime numbers meet the condition, they are used to generate RSA key (multi-prime RSA);
• The flag is encrypted with this multi-prime RSA key and is written in flag.txt with little-endian byte order;
• The public key is stored in public.pem.

To decrypt the flag, we need to break the LCG to recover the private key.

2. Breaking Linear Congruential Generator

A linear congruential generator is defined by the relation (using the same notation as in the script):

\[X_{k+1} = m X_{k} + c \mod n\]

with the initial value \(X_{0}\) (the seed).

We know none of $\textbf{m}$, $\textbf{c}$ and $\textbf{n}$ but we know the first 6 generated numbers and the seed which are enough to recover the LCG.

2.1 Recover $n$

The modulus $\textbf{n}$ can be recovered using the first generated numbers¹. The more generated numbers we have, the higher the probability that we recover the right $\textbf{n}$ will be.

Let’s define:

\[T_{k} = X_{k+1}-X_{k}\] \[U_{k} = |T_{k+2}T_{k}-T_{k+1}^{2}|\]

Then:

\[n = GDC(u_{1}, u_{2}, ...)\]

from functools import reduce

f = open("dump.txt", "r")

X = [int(x.strip()) for x in f.readlines()]
T = [X[n+1] - X[n] for n in range(len(X)-1)]
U = [abs(T[n+2]*T[n] - T[n+1]**2) for n in range(len(T)-2)]

def gcd(a, b):
    if a % b:
        return gcd(b, a % b)
    else:
        return b

n = reduce(gcd, U)

2.2 Recover $m$

\[X_{k+1} = mX_{k}+c \mod n \tag{1}\] \[X_{k+2} = mX_{k+1}+c \mod n \tag{2}\]

By subtracting $(1)$ from $(2)$:

\[X_{k+2}-X_{k+1} = m(X_{k+1}-X_{k}) \mod n\] \[(X_{k+2}-X_{k+1}) (X_{k+1}-X_{k})^{-1} = m \mod n\]

To compute a modular inverse, we can use the Extended Euclidean Algorithm because:

\[\exists u \in \mathbb{Z}, au = 1 \mod n \iff \exists u, v \in \mathbb{Z}, au + nv = 1\]

def extended_euclidean(a, b):
    r, u, v, r_, u_, v_ = a, 1, 0, b, 0, 1

    while r_ != 0:
        q = r // r_
        r, u, v, r_, u_, v_ = r_, u_, v_, r-q*r_, u-q*u_, v-q*v_

    return (r, u, v)

def modinv(a, n):
    r, u, _ = extended_euclidean(a, n)

    if r == 1:
        return u % n
    else:
        raise Exception("No modular inverse")

m = ( (X[2]-X[1]) * modinv(X[1]-X[0], n) ) % n

2.3 Recover $c$

\[X_{k+1} = m X_{k} + c \mod n\] \[c = X_{k+1} - m X_{k} \mod n\]

c = ( X[1] - m*X[0] ) % n

2.4 Recover the LCG

Now, knowing all the parameters and the seed, we can recover the LCG:

class LCG:
    lcg_m = m
    lcg_c = c
    lcg_n = n

    def __init__(self, lcg_s):
        self.state = lcg_s

    def next(self):
        self.state = (self.state * self.lcg_m + self.lcg_c) % self.lcg_n
        return self.state

seed = 211286818345627549183608678726370412218029639873054513839005340650674982169404937862395980568550063504804783328450267566224937880641772833325018028629959635

lcg = LCG(seed)

3. Recover the multi-prime RSA key

We can recover the multi-prime RSA key by generating the prime numbers using the recovered LCG.

from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long, isPrime

# Config values given through assertions
it = 8
bits = 512

primes_arr = []
items = 0
primes_n = 1

while True:
    for i in range(it):
        while True:
            prime_candidate = lcg.next()
            if not isPrime(prime_candidate):
                continue
            elif prime_candidate.bit_length() != bits:
                continue
            else:
                primes_n *= prime_candidate
                primes_arr.append(prime_candidate)
                break

    # Check bit length
    if primes_n.bit_length() > 4096:
        print("bit length", primes_n.bit_length())
        primes_arr.clear()
        primes_n = 1
        continue
    else:
        break

# Create public key 'n'
n = 1
for j in primes_arr:
    n *= j

# Calculate totient 'Phi(n)'
phi = 1
for k in primes_arr:
    phi *= (k - 1)

# Recover e from public key
f = open("public.pem", "rb")
key = RSA.import_key(f.read())

e = key.e

# Calculate private key 'd'
d = pow(e, -1, phi)

4. Decrypt the flag

Now that we have the key, we just need to decrypt it with our key (do not forget the little-endian byte order).

As a reminder:

• Encrypting: \(C = M^{e} \mod n\)
• Decrypting: \(M = C^{d} \mod n\)

flag_file = open("flag.txt", "rb")
flag_enc = int.from_bytes(flag_file.read(), 'little')

flag_long = pow(flag_enc, d, n)

# Decode the flag
decoded_flag = flag_long.to_bytes(n.bit_length(), "little")
flag = decoded_flag.strip(b"\x00")[::-1].decode()
print(flag)

We get the flag: CTF{C0nGr@tz_RiV35t_5h4MiR_nD_Ad13MaN_W0ulD_b_h@pPy}

Additional resources

• TomasGlgg/LCGHack - GitHub
• Breaking Linear Congruential Generator - Sandeep R. Moré
• [Crypto] VolgaCtf2019 - LG - TeamRocketIst

1. Cracking a linear congruential generator - StackExchange ↩