Arkav 2025

very cool final

Chall name : Guess God

Tags : hard, Arkavidia Finals 2025

Okay, i fixed it now, clearly the problem are the elliptic curves! Now, your best odds is probably by guessing

Author: Etynso

TL; DR Predictable RNG via Forced Constant Seed

Key Insight:

• The RNG's next seed is the x-coordinate of (current_seed * G1) in Variety1.

• By setting b1=0 and choosing G1=(1,1) in Variety1, scalar multiplication (e.g., seed * G1) always results in an x-coordinate of 1. This forces the seed to become 1 after the first iteration, making subsequent outputs constant.

Exploit Steps:

1. Set b1=0 in Variety1 to simplify addition/multiplication formulas.

2. Choose G1=(1,1) so all scalar multiples of G1 have x=1 (seed locked to 1).

3. Predict Output: The RNG's output is (G2.x >> 12) (G2's x-coordinate from server, right-shifted by 12 bits).

Constraints Met:

• G1’s coordinates (1,1) are non-zero.

• Large scalar multiples of G1 won’t be the identity (y-coordinate isn’t 0).

Script Flow:

1. Connect to server, read parameters (a1, Gx, etc.).

2. Send {"b1": 0, "x": 1, "y": 1} to define G1.

3. Compute predicted = Gx >> 12.

4. Send {"future": predicted} repeatedly to win the flag.

Result: All RNG outputs become predictable as Gx >> 12, granting the flag after enough correct guesses.

start solving

files given :

param.py
p = 3711307719289846942219567023821864189758609249064872089779

Variety1.py
from param import p

class Variety1:
    class Variety1Element:
        def __init__(self, parent, x, y):
            self.parent = parent
            self.x = x
            self.y = y

        def __add__(self, other):
            a = self.parent.a
            b = self.parent.b

            x0, y0 = self.x, self.y
            x1, y1 = other.x, other.y
            
            A = x0 * x1 % p
            B = x0 * y1 % p
            C = y0 * x1 % p
            D = y0 * y1 % p
            E = (A - b * D) % p
            F = (B + C - a * D) % p

            return self.parent(E, F)

        def __mul__(self, n):
            result = self.parent(1, 0)
            base = self
            while n > 0:
                if n % 2 == 1:
                    result = result + base
                base = base + base
                n //= 2
            return result
        
        def __rmul__(self, n):
            return self.__mul__(n)
        
        def list(self):
            return [self.x, self.y]

    def __init__(self, a, b):
        self.a = a
        self.b = b

    def __call__(self, x, y):
        return Variety1.Variety1Element(self, x, y)

Variety2.py
from param import p
from Crypto.Util.number import inverse
from Crypto.Random.random import randint

def ez_sqrt(x) :
    return pow(x, (p + 1) // 4, p)

def legendre(x) :
    return pow(x, (p - 1) // 2, p)

DD = 119

class Variety2:
    class Variety2Element:
        def __init__(self, parent, x, y):
            self.parent = parent
            self.x = x
            self.y = y

        def __add__(self, other):
            a = self.parent.a
            b = self.parent.b

            x1, y1 = self.x, self.y
            x2, y2 = other.x, other.y

            ab = a * b % p
            ab2 = ab * ab % p
            abrec = inverse(ab, p) % p
            ab2rec = inverse(ab2, p) % p

            A = x1 * x2 % p
            B = x1 * y2 % p
            C = x2 * y1 % p
            D = y1 * y2 % p
            
            E = ab * A % p
            F = D * abrec % p
            G = DD * F * ab2rec % p
            H = ab * (B + C) % p

            X = (E - F + G) % p
            Y = (H + 2*D) % p

            return self.parent(X, Y)

        def __mul__(self, n):
            result = self.parent(inverse(self.parent.a * self.parent.b, p), 0)
            base = self
            while n > 0:
                if n % 2 == 1:
                    result = result + base
                base = base + base
                n //= 2
            return result
        
        def __rmul__(self, n):
            return self.__mul__(n)
        
        def list(self):
            return [self.x, self.y]

    def __init__(self, a, b):
        self.a = a
        self.b = b

    def __call__(self, x, y):
        return Variety2.Variety2Element(self, x, y)
    
    def lift_x(self, x) :
        a, b = self.a, self.b
        invAB = inverse(a * b, p)
        A = - DD * invAB**2 + 1
        B = 2*a*b*x
        C = a**2 * b**2 * x**2 - 1

        disc = B**2 - 4 * A * C
        if legendre(disc) != 1 :
            return None
        
        discq = ez_sqrt(disc)
        y = ((-B + discq) * inverse(2 * A, p)) % p
        return self(x, y)
    
    def random_element(self) :
        G = None
        while G == None :
            x = randint(1, p - 1)
            G = self.lift_x(x)
        return G

chall.py
from Crypto.Random import random
from Variety1 import Variety1
from Variety2 import Variety2
from param import p
import signal
import json

with open('flag.txt', 'r') as f :
    FLAG = f.read()

class RNG:
    def __init__(self, seed, P, Q):
        self.seed = seed
        self.P = P
        self.Q = Q

    def next(self):
        t = self.seed
        s = (t * self.P).x
        self.seed = s
        r = (s * self.Q).x
        return (int(r)) >> 12
        
send = lambda x : print(json.dumps(x))
recv = lambda : json.loads(input())

def main() :
    aura = 5000
    a2 = random.randint(1, p)
    b2 = random.randint(1, p)
    a1 = random.randint(1, p)

    E2 = Variety2(a2, b2)
    G2 = E2.random_element()

    print("Mr. can you see the future?")
    send({"msg" : "Send b1 and a point on E1!", "a1" : a1, "a2" : a2, "b2" : b2, "Gx" : G2.x, "Gy" : G2.y})
    response = recv()

    b1 = response['b1']
    x1, y1 = response['x'] % p, response['y'] % p

    E1 = Variety1(a1, b1)
    G1 = E1(x1, y1)
    
    if (195306067165045895827288868805553560 * G1).list() == [1, 0] or x1 == 0 or y1 == 0:
        print("I don't like that point 🤔")
        exit()

    rand = RNG(random.randint(1, p), G1, G2)

    while 0 < aura < 12000 :
        future = rand.next()
        response = recv()
        
        if response['future'] != future :
            send({"msg" : "Sir, that is not my future, you are a scam artist", "future" : future})
            aura -= 1000
        elif response['future'] == future :
            send({"msg" : "Great, do more", "future" : future})
            aura += 400

    if aura <= 0 :
        print("You fainted")
        exit(1)
    elif aura >= 12000 :
        print("You are a certified dukun!")
        print(f"You earned this {FLAG}")

if __name__ == "__main__" :
    signal.alarm(30)
    try :
        main()
    except Exception as e :
        print(e.__class__)

so this challenge tasked us to predict a custom RNG where every time we predict correctly we will get more aura. Reaching a certain amount of aura rewards us with the flag because we are so sigma 😎.

the challenges uses 2 algebraic structures from Variety1.py and Variety2.py and we were given the initial seed from the challenge, we also have some control over the parameters in Variety1

Understanding the challenge :

so the number p provided that is

p = 3711307719289846942219567023821864189758609249064872089779

is a large prime that will be the mod for all Variety instructions

variety 1

the Variety1 and Variety1Element this class will define a mathematical group like structure where elements are pairs of coordinates.

G1 = E1(x, y)

we will create a point on this variety and choose the x and y for G1

for Variety1 the identity element for addition is (1, 0). This means P + (1,0) = P

Given p0 = (x0, y0) and p1 = (x1, y1) the sum p_new = (x_new, y_new) is:

A = x0 * x1 % p
B = x0 * y1 % p
C = y0 * x1 % p
D = y0 * y1 % p
x_new = (A - b * D) % p = (x0x1 - b1y0y1) % p
y_new = (B + C - a * D) % p = (x0y1 + y0x1 - a1y0*y1) % p

The crucial part here is how b1 that we can control changes x_new.

k * P is equivalent to adding P to itself k times

result = P + P + ..... + P (k times)

the implementation uses the standard double-and-add algorithm starting with the identity element (1,0)

variety2

similar to Variety1 this is another custom algebraic structure

the server defines E2 = Variety2(a2, b2) and a point G2 = E2(Gx, Gy) on it using parameters a2, b2, Gx, Gy that it provides to us

for Variety2, the identity element is (inverse(a*b, p), 0)

the exact formulas for addition and multiplication in Variety2 are more complex but follow similar principles of combining coordinates

the key for us is that G2 is fixed from our perspective

RNG

this is the important part of the challenge

it will initialize the RNG via

rand = RNG(initial_seed, P, Q)

the seed is a random integer chosen by the server.

P: This is our G1 # this is a Variety1Element

Q: This is the servers G2 # this is a Variety2Element

number generation (in RNG)

t = self.seed (current seed, initially initial_seed)
s = (t * self.P).x

this is scalar multiplication of self.P (our G1) by the current seed t

the result is a point on Variety1. s is the x coordinate of this resulting point

self.seed = s (the x coordinate s becomes the new seed for the next iteration)
r = (s * self.Q).x

This is scalar multiplication of self.Q (the servers G2) by the new seed s

The result is a point on Variety2. r is the x coordinate of this resulting point

return (int(r)) >> 12

The final output is the integer part of r, right-shifted by 12 bits (equivalent to floor(r / 2^12))

server constraints

the server provides a1 (Variety1), and a2, b2, Gx, Gy (Variety2, defining G2)

we must send back b1 and the coordinates (x, y) for our point G1 = Variety1(a1, b1)(x, y).

the server imposes constraints on our choice of G1:

(195306067165045895827288868805553560 * G1).list() != [1, 0]: our point G1, when multiplied by a large constant, must not result in the identity element (1,0) of Variety1

x1 != 0 and y1 != 0

the coordinates of our chosen G1 must be non-zero

The Vulnerability

the goal is to make the output of RNG.next() predictable

output = (( ( (old_seed * G1).x ) * G2).x ) >> 12 and the new seed is (old_seed * G1).x

If we can make (t * G1).x (which is s, the new seed) a constant value, then:

1. The RNG.self.seed will become this constant value after the first call to next().

2. In all subsequent calls, t (the seed) will be this constant.

3. s will remain this constant: (constant_seed * G1).x.

4. Then r = (constant_s * G2).x will also be a constant value.

5. Consequently, r >> 12 will be a constant, predictable future.

Exploitation

the strategy is we will try to force a constant seed

How can we make s = (t * G1).x a constant specifically 1?

Recall Variety1Element.add's x-coordinate formula: X_new = (x0x1 - b1y0*y1) % p

the choice of b1 (for Variety1(a1, b1)) If we choose b1 = 0 the formula for the x-coordinate of a sum simplifies dramatically x_new = (x0x1 - 0y0y1) % p = (x0x1) % p

the choice of x for our point G1 = (x_g1, y_g1) If we set b1 = 0 AND choose x_g1 = 1 for our point G1

Let G1 = (1, y_g1) consider G1 + G1 (which is 2G1) x0=1, y0=y_g1 and x1=1, y1=y_g1 x_new = (1 * 1) % p = 1 the y-coordinate will change, but the x-coordinate remains 1 so 2G1 = (1, some_new_y) by induction for any scalar k > 0, the x-coordinate of k * G1 (when b1=0 and x_G1=1) will be 1^k % p = 1

applying this to the RNG's seed generation The RNG calculates s = (t * G1).x. If we choose b1=0 and x_G1=1 then no matter what the current seed t is (t > 0), the x-coordinate of the point t * G1 will be 1

then s = 1

the RNG.self.seed will become 1 after the very first call to next()

In all subsequent calls to next():

1. t = self.seed will be 1.

2. s = (1 * G1).x. Since 1*G1 is just G1, and G1 has an x-coordinate of 1, s will again be 1.

3. the RNG.self.seed will remain fixed at 1.

prediction

once RNG.self.seed is fixed at 1 (which happens when s=1) the calculation of r becomes r = (s * G2).x = (1 * G2).x

scalar multiplication by 1 means 1 * G2 = G2 so r = G2.x G2 is the point Variety2(a2, b2)(Gx, Gy) where Gx and Gy are given by the server thus r will always be Gx (the x-coordinate of the server's G2 point) the final predicted future will be Gx >> 12. This value is constant and calculable by us as soon as the server gives us Gx

solver

solve.py
from pwn import *
import json

# === Primes and Constants ===
p_val = 3711307719289846942219567023821864189758609249064872089779
DD_val = 119

# === Helper: Modular Inverse ===
def inverse(n, prime):
    return pow(n, prime - 2, prime)

# === Variety2 Class (Copied from problem, with minor adjustments for robustness if needed) ===
class Variety2:
    class Variety2Element:
        def __init__(self, parent, x, y):
            self.parent = parent
            self.x = x
            self.y = y

        def __add__(self, other):
            a = self.parent.a
            b = self.parent.b
            global p_val # Use global p_val
            global DD_val # Use global DD_val

            x1, y1 = self.x, self.y
            x2, y2 = other.x, other.y

            ab = a * b % p_val
            if ab == 0:
                # This case should ideally not happen with server's random a,b in (1,p-1)
                log.error("Variety2: a*b is zero, cannot compute inverse for addition.")
                raise ValueError("Variety2: a*b is zero in add")
            
            abrec = inverse(ab, p_val)
            
            ab2 = ab * ab % p_val
            if ab2 == 0:
                log.error("Variety2: (a*b)^2 is zero, cannot compute inverse for addition.")
                raise ValueError("Variety2: (a*b)^2 is zero in add")
            ab2rec = inverse(ab2, p_val)

            A = x1 * x2 % p_val
            B = x1 * y2 % p_val
            C = x2 * y1 % p_val
            D = y1 * y2 % p_val
            
            E = ab * A % p_val
            F = D * abrec % p_val
            G = DD_val * F % p_val * ab2rec % p_val 
            H = ab * (B + C) % p_val

            X = (E - F + G) % p_val
            Y = (H + 2*D) % p_val

            return self.parent(X, Y)

        def __mul__(self, n_orig):
            n = n_orig
            if n < 0: # Though RNG seed is positive, good to be robust
                log.warn("Variety2: Negative scalar multiplication not explicitly defined, proceeding with positive.")
                # For many groups, n*P = (-n)*(-P). Here -P might be (x, -y % p).
                # However, since seed is positive, we likely don't need this.
                n = -n 
                # base_point = self.parent(self.x, -self.y % p_val) # Hypothetical inverse element
                base_point = self # Sticking to positive n as per problem context
            else:
                base_point = self
            
            ab_val = self.parent.a * self.parent.b % p_val
            if ab_val == 0:
                log.error("Variety2: a*b is zero, cannot compute identity for multiplication.")
                raise ValueError("Variety2: a*b is zero in mul")

            # Identity for Variety2
            id_x = inverse(ab_val, p_val)
            id_y = 0
            
            if n == 0:
                return self.parent(id_x, id_y)

            result_point = self.parent(id_x, id_y) # Start with identity

            temp_n = n
            while temp_n > 0:
                if temp_n % 2 == 1:
                    result_point = result_point + base_point
                base_point = base_point + base_point
                temp_n //= 2
            return result_point
        
        def __rmul__(self, n):
            return self.__mul__(n)
        
        def list(self):
            return [self.x, self.y]

    def __init__(self, a, b):
        self.a = a
        self.b = b

    def __call__(self, x, y):
        return Variety2.Variety2Element(self, x, y)

# === Variety1 Class (Copied from problem) ===
class Variety1:
    class Variety1Element:
        def __init__(self, parent, x, y):
            self.parent = parent
            self.x = x
            self.y = y

        def __add__(self, other):
            a = self.parent.a # This is a1
            b = self.parent.b # This is b1
            global p_val

            x0, y0 = self.x, self.y
            x1, y1 = other.x, other.y
            
            A = x0 * x1 % p_val
            B = x0 * y1 % p_val
            C = y0 * x1 % p_val
            D = y0 * y1 % p_val
            E = (A - b * D) % p_val 
            F = (B + C - a * D) % p_val

            return self.parent(E, F)

        def __mul__(self, n_orig):
            n = n_orig
            global p_val
            # Identity for Variety1 is (1,0)
            result_point = self.parent(1, 0) 
            
            if n < 0:
                log.warn("Variety1: Negative scalar multiplication not explicitly defined.")
                # base_point = self.parent(self.x, -self.y % p_val) # Hypothetical
                n = -n
                base_point = self # Sticking to positive n
            else:
                base_point = self

            if n == 0:
                return result_point
            
            temp_n = n
            while temp_n > 0:
                if temp_n % 2 == 1:
                    result_point = result_point + base_point
                base_point = base_point + base_point
                temp_n //= 2
            return result_point
        
        def __rmul__(self, n):
            return self.__mul__(n)
        
        def list(self):
            return [self.x, self.y]

    def __init__(self, a, b): # a is a1, b is b1
        self.a = a
        self.b = b

    def __call__(self, x, y):
        return Variety1.Variety1Element(self, x, y)

# --- Main Exploit Logic ---
HOST = "moklet-sec.site"
PORT = 59948

r = remote(HOST, PORT)

try:
    initial_greeting = r.recvline().decode().strip()
    log.info(f"S: {initial_greeting}")

    server_params_json = r.recvline().decode().strip()
    log.info(f"S: {server_params_json}")
    server_params = json.loads(server_params_json)

    # We don't need a1, a2, b2 for our chosen G1 or for prediction
    # a1_server = server_params['a1']
    # a2_server = server_params['a2'] # Used to define E2, G2 is on this
    # b2_server = server_params['b2'] # Used to define E2, G2 is on this
    G2_x_server = server_params['Gx'] # Crucial for our prediction
    # G2_y_server = server_params['Gy']

    # Our chosen parameters for G1 to make (seed * G1).x predictable
    b1_chosen = 0
    x1_chosen = 1
    y1_chosen = 1 # Any non-zero value to avoid G1 being identity and pass checks

    payload_for_G1 = {
        "b1": b1_chosen,
        "x": x1_chosen,
        "y": y1_chosen
    }
    log.info(f"C: {json.dumps(payload_for_G1)}")
    r.sendline(json.dumps(payload_for_G1).encode())

    # Calculate the constant future prediction
    # (Initial random_seed * G1).x will be 1 because x1_chosen=1 and b1_chosen=0.
    # So, RNG's internal seed becomes 1.
    # Then, r_rng = (1 * G2).x = G2.x (since 1*G2 = G2).
    # Our prediction is G2.x >> 12.
    predicted_future = G2_x_server >> 12
    log.success(f"Constant predicted future: {predicted_future}")

    aura = 5000 # Initial aura given in problem
    max_aura_needed = 12000

    while 0 < aura < max_aura_needed:
        log.info(f"Current (estimated) aura: {aura}")
        
        # Send our prediction
        prediction_payload = {"future": predicted_future}
        log.info(f"C: {json.dumps(prediction_payload)}")
        r.sendline(json.dumps(prediction_payload).encode())

        # Receive server's feedback
        feedback_json = r.recvline().decode().strip()
        log.info(f"S: {feedback_json}")
        feedback = json.loads(feedback_json)

        if "msg" in feedback:
            message = feedback["msg"]
            if "not my future" in message:
                log.warning("Prediction was wrong. Strategy might be flawed or an edge case hit.")
                aura -= 1000 # As per problem
            elif "Great, do more" in message:
                log.success("Prediction was correct!")
                aura += 400 # As per problem
            elif "certified dukun" in message or "earned this" in message:
                log.success("FLAG OBTAINED (in message part)!")
                print("\nFLAG FOUND IN MESSAGE:")
                print(message)
                if "KONEKO" in feedback_json: # Check if flag is directly in json string
                     print(feedback_json)
                # The problem statement's example print(f"You earned this {FLAG}")
                # suggests the flag might be appended to the message.
                # Check the full JSON for flag too.
                if "KONEKO" in str(feedback): # Crude check in whole dict as string
                    log.info(f"Full feedback containing flag: {feedback}")
                break # Exit loop on success
            elif "fainted" in message:
                log.error("Aura depleted. You fainted.")
                break
        else:
            log.error(f"Unexpected feedback format: {feedback_json}")
            break # Unknown state

        if aura >= max_aura_needed:
            log.success("Aura goal reached! Waiting for final flag message if any.")
            # Server might send one final message with the flag after this loop condition is met
            # based on the problem description's `elif aura >= 12000 : print(FLAG)`
            # The loop structure implies feedback is received *after* we send prediction.
            # If the "Great, do more" that pushed aura >= 12000 *also* contains the flag,
            # the above `if "certified dukun"` block should catch it.
            # If not, we might need one more recv.
            # However, the problem code's main loop structure suggests the flag is printed
            # immediately after the aura condition is met *within the server's loop* for that round.
            # So, the message that confirms the last correct prediction *should* contain the flag.
            pass # The check for "certified dukun" should handle this.

        if aura <= 0:
            log.error("Aura ran out based on local tracking.")
            break
            
except EOFError:
    log.error("Connection closed by server (EOF).")
except Exception as e:
    log.error(f"An error occurred: {type(e).__name__} - {e}")
    import traceback
    traceback.print_exc()
finally:
    r.close()
    log.info("Connection closed.")

what i learned :

1. The challenge highlighted how custom algebraic operations (in Variety1/Variety2) can introduce vulnerabilities

2. The RNG's reliance on the x-coordinate of scalar-multiplied points as the next seed was a critical weakness by forcing the seed to a constant value (1) through parameter manipulation (b1=0, G1=(1,1)) I made all future outputs predictable