# Arkav 2025
> 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 :
```python
param.py
p = 3711307719289846942219567023821864189758609249064872089779
```
```python
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)
```
```python
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
```
```python
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 :sunglasses:.
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
{% code overflow="wrap" %}
```python
p = 3711307719289846942219567023821864189758609249064872089779
```
{% endcode %}
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 2*G1)*
\
*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 2*G1 = (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
```python
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
