These writeups are for challenges I solved after the CTF. Some of these I have captured solutions from others’ writeups for my reference.

Solutions

Crypto/E(Z/C)LCG

We are given an Elliptic Curve cryptography based challenge source, that uses a 80-bit prime, randomized a and b parameters. Using the original generator of this curve, a linear congruential generator is created and the [X,Y] coordinates of two sequential points are given to us. The X coordinate of the third point is used to generate the key for encrypting the flag with AES-CBC. The IV and the encrypted flag are provided to us.

from random import SystemRandom
random = SystemRandom()

def fun_prime(n): # not as smooth as my brain but should be enough
    while True:
        ps = 16
        p = 1
        for i in range(n//ps):
            p *= random_prime(2^ps)
        p += 1
        if is_prime(p):
            return p
def gen(b):
    p = fun_prime(b)
    E = EllipticCurve(GF(p), [random.randint(1, 2^b), random.randint(1,2^b)])
    return E, p, E.order()

C, p, order = gen(80)
# woah thats an lcg
class lcg:
    def __init__(self, C: EllipticCurve):
        self.order = order
        self.a = random.randint(1, self.order)
        self.x = C.gens()[0]
        self.b = self.x * random.randint(1, self.order)
    def next(self):
        self.x = (self.a * self.x + self.b)
        return self.x

prng = lcg(C)
x0 = prng.next()
x1 = prng.next()
x0, y0 = x0.xy()
x1, y1 = x1.xy()
print(f"{x0 = }")
print(f"{y0 = }")
print(f"{x1 = }")
print(f"{y1 = }")
print(f"{p = }")

from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes as l2b
from Crypto.Util.Padding import pad
from os import urandom
v = int(prng.next().xy()[0])
k = pad(l2b(v**2), 16)
iv = urandom(16)
cipher = AES.new(k, AES.MODE_CBC, iv=iv)
print(f"iv = '{iv.hex()}'")
f = open("flag.txt",'rb').read().strip()
enc = cipher.encrypt(pad(f,16))
print(f"enc = '{enc.hex()}'")

The solution approach would be:

  1. Given that (X0, Y0) and (X1, Y1) are points on the curve, determine the original parameters a and b of the Elliptic Curve, assuming that it is a Weierstrass equation of the form \(y^2 = x^3 + ax + b\).
  2. Recreate the curve and recover the generator points using C.gens()
  3. Using three consecutive values of the LCG, recreate the parameters of the LCG
  4. Predict the next point and use it to recreate the AES key
  5. Use the Key and IV to decrypt the encrypted flag.

The coded solution in sagemath is as follows:

# Given x0, y0, x1, y1, p, iv, enc

C_a, C_b = attack(p, x0, y0, x1, y1)        # recover the parameters of the curve
E = EllipticCurve(GF(p), [C_a, C_b])        # recreate the curve using the original parameters

P0 = E.gens()[0]                # get the generator point
# convert the known points to sage format
P1 = E(x0, y0)
P2 = E(x1, y1)

print(f"{P0 =}\n{P1 =}\n{P2 =}")
# Given that P0, P1 and P2 are the consecutive points in a LCG sequence, 
# P1 = P0 * a + b and so on.
lcga = (P1 - P0).discrete_log(P2-P1)
lcgb = P1 - (P0 * lcga)

P3 = P2 * lcga + lcgb

v = int(P3.xy()[0])  # get the X value

import binascii
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes as l2b
from Crypto.Util.Padding import pad, unpad

iv = binascii.unhexlify(iv)
enc = binascii.unhexlify(enc)
k = pad(l2b(v**2), 16)          # Use the x value of the next point as the key
cipher = AES.new(k, AES.MODE_CBC, iv=iv)
print(f"{unpad(cipher.decrypt(enc), 16).decode()} ")

# LITCTF{Youre_telling_me_I_cant_just_throw_elliptic_curves_on_something_and_make_it_100x_secure?_:<}

$$ P_1 = P_0 * a_{lcg} + b_{lcg} \\ P_2 = P_1 * a_{lcg} + b_{lcg} \\ $$

$$ {P_2 - P_1} = a_{lcg} * {P_1 - P_0} \\ \therefore a_{lcg} = {(P_1 - P_0)}\text{.discrete\_log}({P_2 - P_1}) $$

$$ b_{lcg} = P_1 - P_0 * a_{lcg} $$

I used the cryto utility function from https://github.com/jvdsn/crypto-attacks. The underlying logic for why this is the case is:

$$ y_1^2 = x_1^3 + ax_1 + b \mod p\\ y_2^2 = x_2^3 + ax_2 + b \mod p $$

$$ y_1^2 - y_2^2 = x_1^3 - x_2^3 + a (x_1 - x_2) \mod p\\ \therefore a = \frac {(y_1^2 - y_2^2) - (x_1^3 - x_2^3)} {(x_1 - x_2)} \mod p $$

#from https://github.com/jvdsn/crypto-attacks
def attack(p, x1, y1, x2, y2):
    """
    Recovers the a and b parameters from an elliptic curve when two points are known.
    :param p: the prime of the curve base ring
    :param x1: the x coordinate of the first point
    :param y1: the y coordinate of the first point
    :param x2: the x coordinate of the second point
    :param y2: the y coordinate of the second point
    :return: a tuple containing the a and b parameters of the elliptic curve
    """
    a = pow(x1 - x2, -1, p) * (pow(y1, 2, p) - pow(y2, 2, p) - (pow(x1, 3, p) - pow(x2, 3, p))) % p
    b = (pow(y1, 2, p) - pow(x1, 3, p) - a * x1) % p
    return int(a), int(b)

LCG… Squared?

# inferior rngs
from random import SystemRandom
random = SystemRandom()
from Crypto.Util.number import getPrime
p = getPrime(64)
class lcg1:
    def __init__(self, n=64):
        self.a = random.randint(1, 2**n)
        self.b = random.randint(1, 2**n)
        self.x = random.randint(1, 2**n)
        self.m = p
    def next(self):
        ret = self.x
        self.x = (self.a * self.x + self.b) % self.m
        return ret

class lcg2:
    def __init__(self, n=64):
        self.lcg = lcg1(n)
        self.x = random.randint(1, 2**n)
        self.b = random.randint(1, 2**n)
        self.m = p
    def next(self):
        self.x = (self.lcg.next() * self.x + self.b) % self.m
        return self.x

lcg = lcg2()
print(p)            # prints prime
for x in range(5):
    print(lcg.next())   # prints 5 consecutive LCG2 entries.

from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes as l2b
from Crypto.Util.Padding import pad
from os import urandom
r = lcg.next()
k = pad(l2b(r**2), 16)
iv = urandom(16)
cipher = AES.new(k, AES.MODE_CBC, iv=iv)
print(iv.hex())     # prints IV
f = open("flag.txt",'rb').read().strip()
enc = cipher.encrypt(pad(f,16))
print(enc.hex())    # prints ciphertext

$$ LCG_1: \quad \large L = \normalsize \{ {L_0, L_1, L_2, L_3, L_4, … } \} \\ LCG_2: \quad \large M = \normalsize \{ {M_0, M_1, M_2, M_3, M_4, … } \} \\ L_0 = x_1 \\ L_1 = a * L_0 + b \mod {p} \\ L_2 = a * L_1 + b \mod {p} \\ \text{… etc.} \\ \newline M_0 = L_0 * x_2 + b_2 \mod {p} \\ M_1 = L_1 * x_2 + b_2 \mod {p} \\ M_2 = L_2 * x_2 + b_2 \mod {p} \\ \text{… etc.} \\ $$

ILoveRegex

We are given a regular expression, which presumably matches with the flag.

^LITCTF\{(?<=(?=.{42}(?!.)).(?=.{24}greg).(?=.{30}gex).{5})(?=.{4}(.).{19}\1)(?=.{4}(.).{18}\2)(?=.{6}(.).{2}\3)(?=.{3}(.).{11}\4)(?=.{3}(.).{3}\5)(?=.{16}(.).{4}\6)(?=.{27}(.).{4}\7)(?=.{12}(.).{4}\8)(?=.{3}(.).{8}\9)(?=.{18}(.).{2}\10)(?=.{4}(.).{20}\11)(?=.{11}(.).{2}\12)(?=.{32}(.).{0}\13)(?=.{3}(.).{24}\14)(?=.{12}(.).{9}\15)(?=.{7}(.).{2}\16)(?=.{0}(.).{12}\17)(?=.{13}(.).{5}\18)(?=.{1}(.).{0}\19)(?=.{27}(.).{3}\20)(?=.{8}(.).{17}\21)(?=.{16}(.).{6}\22)(?=.{6}(.).{6}\23)(?=.{0}(.).{1}\24)(?=.{8}(.).{11}\25)(?=.{5}(.).{16}\26)(?=.{29}(.).{1}\27)(?=.{4}(.).{9}\28)(?=.{5}(.).{24}\29)(?=.{15}(.).{10}\30).*}$

Formatting the string shows the following sub-expressions …

% sed -e 's/(?/\n(?/g' regex.txt 
^LITCTF\{
(?<=
(?=.{42}
(?!.))
.
(?=.{24}greg)
. 
(?=.{30}gex).{5})
(?=.{4}(.).{19}\1)
(?=.{4}(.).{18}\2)
(?=.{6}(.).{2}\3)
(?=.{3}(.).{11}\4)
... etc ...
(?=.{15}(.).{10}\30).*}$
Exprcurrent position
^LITCTF\{0
(?<=0
(?=.{42}0
(?!.))0
.0
(?=.{24}greg)1
.1
(?=.{30}gex).{5})2
(?=.{4}(.).{19}\1)7
(?=.{4}(.).{18}\2)7
(?=.{6}(.).{2}\3)7
S = Solver()
x = makeIntVector(S, 'X', 42, 33, 127)

for i,c in enumerate('LITCTF{'):
    S.add(x[i] == ord(c))
S.add(x[41] == ord('}'))

L=1     # base for relative positioning
S.add(x[L+24] == ord('g'))
S.add(x[L+25] == ord('r'))
S.add(x[L+26] == ord('e'))
S.add(x[L+27] == ord('g'))

L=2     # base for relative positioning
S.add(x[L+30] == ord('g'))
S.add(x[L+31] == ord('e'))
S.add(x[L+32] == ord('x'))

L=7     # base for relative positioning
S.add(x[L+4] == x[L + 4 + 1 +19])       # created from:  (?=.{4}(.).{19}\1)
S.add(x[L+4] == x[L + 4 + 1 +18])  
S.add(x[L+6] == x[L + 6 + 1 +2])  
S.add(x[L+3] == x[L + 3 + 1 +11]) 
S.add(x[L+3] == x[L + 3 + 1 +3])
S.add(x[L+16] == x[L + 16 + 1 +4])
S.add(x[L+27] == x[L + 27 + 1 +4])
S.add(x[L+12] == x[L + 12 + 1 +4])
S.add(x[L+3] == x[L + 3 + 1 +8])
S.add(x[L+18] == x[L + 18 + 1 +2])
S.add(x[L+4] == x[L + 4 + 1 +20])
S.add(x[L+11] == x[L + 11 + 1 +2])
S.add(x[L+32] == x[L + 32 + 1 +0])
S.add(x[L+3] == x[L + 3 + 1 +24])
S.add(x[L+12] == x[L + 12 + 1 +9])
S.add(x[L+7] == x[L + 7 + 1 +2])
S.add(x[L+0] == x[L + 0 + 1 +12])
S.add(x[L+13] == x[L + 13 + 1 +5])
S.add(x[L+1] == x[L + 1 + 1 +0])
S.add(x[L+27] == x[L + 27 + 1 +3])
S.add(x[L+8] == x[L + 8 + 1 +17])
S.add(x[L+16] == x[L + 16 + 1 +6])
S.add(x[L+6] == x[L + 6 + 1 +6])
S.add(x[L+0] == x[L + 0 + 1 + 1])
S.add(x[L+8] == x[L + 8 + 1 +11])
S.add(x[L+5] == x[L + 5 + 1 +16])
S.add(x[L+29] == x[L + 29 + 1 +1])
S.add(x[L+4] == x[L + 4 + 1 +9])
S.add(x[L+5] == x[L + 5 + 1 +24])
S.add(x[L+15] == x[L + 15 + 1 +10])

if S.check() == sat:
    M = S.model()
    f = ''
    for i in range(42):
        f+= chr(M[x[i]].as_long())
    print(f'Found Solution: {f}')
    # Found Solution: LITCTF{rrregereeregergegegregegggexexexxx}

Writeups and resources

Challenges

ChallengeCategoryDifficultyDescription
crypto/Climbing Snowdoncrypto5
crypto/E(Z/C)LCGcrypto3
crypto/Kirby’s Recipecrypto5
crypto/LCG to the power of n!crypto7
crypto/LCG… Squared?crypto5
crypto/The Door to the Xordcrypto6
crypto/Your Did It!crypto8
crypto/are YOU smarter than Joseph-Louis Lagrange????crypto10
crypto/cursed cipherscrypto4
crypto/icecreamcrypto3
crypto/leaderboard-servicecrypto6
crypto/polypointcrypto6
misc/Blank and Emptymisc2
misc/HelloWorldmisc1
misc/KirbBot has a secret…misc10
misc/So You Think You Can Talkmisc5
misc/Surveymisc1
misc/amogusmisc1
misc/codetiger orzmisc4
misc/discord and moremisc0
misc/geoguessrmisc3
misc/incrediblemisc2
misc/kevinmisc1
misc/obligatory pyjailmisc6
misc/rayzarrayzmisc3
misc/the other obligatory pyjailmisc5
misc/wow it’s another pyjailmisc10
pwn/File Reader?pwn3
pwn/My Pet Canary’s Birthday Piepwn2
pwn/SHA-SHA-Shellpwn4
pwn/catpwn5
pwn/sprintfpwn6
pwn/stiller printfpwn7
pwn/susprintfpwn10
rev/budget-mcrev5
rev/ilovepythonrev8
rev/iloveregexrev4
rev/obfuscationrev3
rev/rickrev1
rev/squishrev5
rev/wharrev7
web/EyangCH Fanfic Makerweb7
web/My boss leftweb3
web/Ping Pong: Under Maintenanceweb5
web/Ping Pongweb2.5
web/The Even More Most LIT Foundationweb10
web/The Most LIT Foundationweb6
web/amogsus-apiweb2.5
web/art-contestweb7
web/fetchweb4
web/license-injectweb3
web/too much kirbyweb20
web/unsecureweb2