0xL4ugh CTF v5 2026 - Bitcoin

By Devanandan N B • 4 minutes read •


Table of Contents

Description

The Zwique holds the master key. He’ll offer a quick demonstration using something. Help me to steal his flag.

author: Zwique

difficulty: medium

Points/Solves: 50/60

Challenge source code 
#!/usr/bin/env python3
import re
import time
import sys
from Crypto.Random.random import randint
from ecdsa import SECP256k1


class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def is_infinity(self):
        return self.x is None and self.y is None

    def __eq__(self, other):
        if self.is_infinity() and other.is_infinity():
            return True
        return self.x == other.x and self.y == other.y

    def __repr__(self):
        if self.is_infinity():
            return "Point(infinity)"
        return f"Point({self.x}, {self.y})"

    def __hash__(self):
        if self.is_infinity():
            return hash((None, None))
        return hash((self.x, self.y))

class Squiggle:
    def __init__(self, a, b, p):
        self.a = a
        self.b = b
        self.p = p

    def normalize(self, P):
        if P.is_infinity():
            return P
        return Point(P.x % self.p, P.y % self.p)

    def add(self, P, Q):
        P = self.normalize(P)
        Q = self.normalize(Q)
        if P.is_infinity():
            return Q
        if Q.is_infinity():
            return P
        if P == self.negate(Q):
            return Point(None, None)

        if P == Q:
            # Slope for doubling: (3x^2 + a) / 2y
            num = (3 * P.x * P.x + self.a)
            den = pow(P.y << 1, -1, self.p)
            t = (num * den) % self.p
        else:
            # Slope for adding: (y2 - y1) / (x2 - x1)
            num = (Q.y - P.y)
            den = pow(Q.x - P.x, -1, self.p)
            t = (num * den) % self.p

        x = (t * t - P.x - Q.x) % self.p
        y = ((P.x - x) * t - P.y) % self.p

        return Point(x, y)

    def negate(self, P):
        P = self.normalize(P)
        if P.is_infinity():
            return P
        return Point(P.x, -P.y % self.p)

    def mul(self, k, P):
        P = self.normalize(P)
        result = Point(None, None)
        current = P

        if k < 0:
            return self.mul(-k, self.negate(P))

        while k > 0:
            if k & 1:
                result = self.add(result, current)
            current = self.add(current, current)
            k >>= 1

        return result

def deserialize_point(s):
    s = s.strip()
    if s == "Point(infinity)":
        return Point(None, None)
    else:
        pattern = r"Point\(\s*(\d+)\s*,\s*(\d+)\s*\)"
        match = re.match(pattern, s)
        if not match:
            print("Format error. Use Point(x, y)")
            sys.exit(0)
        arr = s[6:-1].split(",")
        return Point(int(arr[0]), int(arr[1]))

p = SECP256k1.curve.p()
a = 0
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
ord = int(SECP256k1.order)

G = Point(
    SECP256k1.generator.x(),
    SECP256k1.generator.y()
)

squiggle = Squiggle(a, b, p)

def main():
    start_time = time.time()
    
    d = randint(2, ord - 1)
    
    print("--- Curve Oracle Service v2.0 ---")
    print("I possess a secret key: d")
    print("Public Key (hidden): Q = d * G")
    print("---------------------------------")
    
    print("Phase 1:")
    print("Send me ElGamal components (C1, C2).")
    print("I will compute and return: S = C2 - (d * C1)")
    print("Format: Point(x, y)")
    
    for i in range(5):
        try:
            print(f"\nQuery [{i+1}/5]")
            c1_str = input("Input C1 > ")
            c2_str = input("Input C2 > ")
            
            C1 = deserialize_point(c1_str)
            C2 = deserialize_point(c2_str)

            # S = C2 - d*C1
            term = squiggle.mul(-d, C1)
            S = squiggle.add(C2, term)
            
            print(f"Output S > {S}")
        except Exception:
            print("Error parsing input.")
            return

    print("\n---------------------------------")
    print("Phase 2:")
    print("I will provide ciphertext (C1, C2).")
    print("You must decrypt it and provide the Point P.")
    print("System: C1 = k*G, C2 = P + k*Q")
    

    for i in range(5):
        print(f"\nRound [{i+1}/5]")
        

        secret_val = randint(1, ord - 1)
        target_point = squiggle.mul(secret_val, G)
        
        k = randint(1, ord - 1)
        C1_chall = squiggle.mul(k, G)
        
        # C2 = P + k * Q  (where Q = d*G)
        Q = squiggle.mul(d, G)
        shared_secret = squiggle.mul(k, Q)
        C2_chall = squiggle.add(target_point, shared_secret)

        print(f"Given C1: {C1_chall}")
        print(f"Given C2: {C2_chall}")

        try:
            user_input = input("Recovered Point P > ")
            P_input = deserialize_point(user_input)
            
            if P_input == target_point:
                print("Correct.")
            else:
                print("Incorrect.")
                return
        except Exception:
            print("Error.")
            return

    # Check timeout
    if time.time() - start_time >= 10:
        print("Timeout.")
        return

    try:
        with open("flag.txt", "r") as f:
            print(f"\nFlag: {f.read().strip()}")
    except FileNotFoundError:
        print("\nFlag file missing.")

if __name__ == "__main__":
    main()

Analysis

Source code was not given for this challenge. Upon connecting to the remote, we are greeted with these lines:

--- Curve Oracle Service v2.0 ---
I possess a secret key: d
Public Key (hidden): Q = d * G
---------------------------------
Phase 1:
Send me ElGamal components (C1, C2).
I will compute and return: S = C2 - (d * C1)
Format: Point(x, y)

Query [1/5]
Input C1 >

We are presented with an Elgamal scheme with Elliptic Curve points. Initially they give out an oracle; They ask us to give out $C_1$, $C_2$ and they give back out $S$ such that $S = C_2 - (d * C_1)$. We have to do this 5 times. Once we give out these parameters for the 5 queries, we go into phase 2 of the challenge.

---------------------------------
Phase 2:
I will provide ciphertext (C1, C2).
You must decrypt it and provide the Point P.
System: C1 = k*G, C2 = P + k*Q

Round [1/5]
Given C1: Point(85945500062422365948987659750357491139449625902675750904459864271278128760469, 44419415878373631191113536933718701735422256990865178377392909843428186347239)
Given C2: Point(46333289073467086236506365161153170604351884102798361136280050720950285017529, 106583866087329168399591221185060330147733650011094277195297144847061002140703)
Recovered Point P >

Essentially, they are asking us to prove knowledge of the private key. To recover point, $P = C_2 - d*C_1$. Somehow we are to calculate the private key in phase 1, so this is an ECDLP challenge.

Ok, lets first find out the elliptic curve parameters $a, b$, through two points from the second phase.

$$ y_1^2 = x_1^3 + ax_1 + b$$ $$ y_2^2 = x_2^3 + ax_2 + b$$ $$ y_1^2 - y_2^2 = x_1^3 + ax_1 - x_2^3 - ax_2$$ $$ y_1^2 - y_2^2 - x_1^3 + x_2^3 = a(x_1 - x_2)$$ $$ a = (y_1^2 - y_2^2 - x_1^3 + x_2^3) / (x_1 - x_2) $$ $$ b= y_1^2 - x_1^3 - ax_1$$

After doing this, we get the curve parameters as a = 0 and b = 7. That’s the bitcoin curve!. Alright, we are given five queries and somehow, we need to break ECDLP. First thing that comes to mind is Invalid curve, attack. If the server doesn’t actually check whether our points lie on the curve, it can lead to devastating problems.

And sure enough it didn’t. That was expected given that they didn’t reveal to us the source code. So what next? Twist attack comes to mind. We have five queries, so we could try to find twists of the curve with a smooth order and then do ECDLP on each of their smooth subgroups and crt to combine them…

Twists of an elliptic curve over a field K are elliptic curves that are isomorphic to the original curve over the algebraic closure of its base.

Given 5 queries we have 256 bits to recover, that means we need 5 subgroups of roughly 52 bits each. In EC point arithmetic, the parameter b is never used, so what we do is find curves with same a, different b, check its order to see if it has smooth subgroups. And we tried that.

Gs = []
ms = []
Es = []
ps = set()
for b in [1,2,3,4,6]:
    b = K(b)
    E = EllipticCurve(K, (a, b))
    ffs = list(dict(factor(E.order())))
    m = 1
    for q in ffs:
        if q.bit_length() in range(10, 46) and q not in ps:
            m *= q
            ps.add(q)
    ms.append(m)
    G = E.random_point() * (E.order()/m)
    Es.append(E)
    Gs.append(G.xy())

io = remote('challenges4.ctf.sd', 33862  )
Os = []
for i in range(5):
    E = Es[i]
    G = Gs[i]
    C2 = E.random_point().xy()
    io.sendlineafter(b'Input C1 > ', b'Point'+str(G).encode())
    io.sendlineafter(b'Input C2 > ', b'Point'+str(C2).encode())
    io.recvuntil(b'Output S > Point')
    Os.append((E(C2) - E(eval(io.recvline()[:-1]))).log(E(G)))

d = crt(Os, ms[:5])

for _ in range(5):
    G1 = io.recvuntil(b'Given C1: Point')
    G1 = E0(eval(io.recvline()[:-1]))
    G2 = io.recvuntil(b'Given C2: Point')
    G2 = E0(eval(io.recvline()[:-1]))
    P = (G2 - G1*d ).xy()
    io.sendlineafter(b'Recovered Point P > ', b'Point'+str(P).encode())
io.interactive()

Unfortunately, even though we got the correct answer every time, the server kept on timing us out. So what now? Our efforts to make DLP faster was in wain. That’s when it hit. a is 0, if we make b also 0, the curve now becomes a singular curve with a cusp! Which means we get an ismorphism to the additive group mod p where the DLP is trivial!. So we implemented that and we got the flag.

Elliptic curves are defined such that the determinant of their curve equation is never zero. For the short weierstrass form, the determinant is defined as $-16(4a^3 + 27b^2)$. If the determinant is zero, then it’s not an elliptic curve, but rather a singular curve.

When the determinant is zero, there exists an isomorphism $\phi(P) = l$ where $P \in E, l \in \mathbb{Z}_p^+$.

$$\phi(P) = \frac{P_x}{P_y} \pmod{p}$$

and then for discrete, log, we just take the multiplicative inverse of the point with the second point. This approach was what got us the flag. However, after the CTF, the author’s solution baffled me. Instead performing an invalid curve attack, C1 was set to (1,1) and C2 as point at infinity, which means S was approximately (-d, -d). T-T.

Final solve script 
from pwn import remote
from random import randrange, sample
from sage.structure.parent import Parent
from sage.structure.element import Element

class SingularCurve(Parent):
    def __init__(self, K, a4, a6):
        super().__init__(base=K)
        self.K = K
        self.a4 = K(a4)
        self.a6 = K(a6)

    def __call__(self, x, y=None):
        if x == 0 and y == 0:
            return SingularPoint(self, 0, 0, is_singular=True)
        if x is None:
            return SingularPoint(self, None, None, is_inf=True)
        return SingularPoint(self, x, y)

    def random_point(self):
        x = K(self.base().random_element())
        while x**((p-1)/2) != 1:
            x = K(randrange(p)) 
        x3 = x**3
        y = x3.square_root()
        return self.__call__(x, y)

class SingularPoint(Element):
    def __init__(self, parent, x, y, is_inf=False, is_singular=False):
        super().__init__(parent)
        self.x = x
        self.y = y
        self.is_inf = is_inf
        self.is_singular = is_singular

    def __repr__(self):
        if self.is_inf: return "Point at infinity"
        if self.is_singular: return f"Singular Point ({self.x}, {self.y})"
        return f"({self.x}, {self.y})"

    def __add__(self, other):
        if self.is_singular or other.is_singular:
            raise ArithmeticError("Group law undefined at the singular point.")
        if self.is_inf: return other
        if other.is_inf: return self
        
        K = self.parent().K
        p = K.characteristic()
        x1, y1 = self.x, self.y
        x2, y2 = other.x, other.y
        
        if x1 == x2 and y1 == -y2:
            return self.parent()(None)
        
        if self == other:
            m = (3*x1**2 + self.parent().a4) * pow(2*y1, -1, p)
        else:
            m = (y2 - y1) * pow(x2 - x1, -1, p)
            
        x3 = m**2 - x1 - x2
        y3 = m*(x1 - x3) - y1
        return self.parent()(x3, y3)

    def __sub__(self, other):
        if self.is_singular or other.is_singular:
            raise ArithmeticError("Group law undefined at the singular point.")
        if self.is_inf: return other
        if other.is_inf: return self
        
        K = self.parent().K
        p = K.characteristic()
        x1, y1 = self.x, self.y
        x2, y2 = other.x, -other.y
        
        if x1 == x2 and y1 == -y2:
            return self.parent()(None)
        
        if self == other:
            m = (3*x1**2 + self.parent().a4) * pow(2*y1, -1, p)
        else:
            m = (y2 - y1) * pow(x2 - x1, -1, p)
            
        x3 = m**2 - x1 - x2
        y3 = m*(x1 - x3) - y1
        return self.parent()(x3, y3)

    def __mul__(self, n):
        Q = self.parent()(None)
        P = self
        n = int(n)
        while n > 0:
            if n % 2 == 1: Q = Q + P
            P = P + P
            n //= 2
        return Q

    def log(self, P):
        assert self.parent() == P.parent()
        print(P)
        K = self.parent().base()
        s = K(self.y / self.x)
        c = K(P.y / P.x)
        return c / s

p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
K = GF(p)
C = SingularCurve(K, 0, 0)

io = remote('challenges.ctf.sd', 34157)

Os = []
for i in range(5):
    C2 = C.random_point()
    C1 = C.random_point()
    io.sendlineafter(b'Input C1 > ', b'Point'+str(C1).encode())
    io.sendlineafter(b'Input C2 > ', b'Point'+str(C2).encode())
    io.recvuntil(b'Output S > Point')
    P = eval(io.recvline()[:-1])
    x, y = P
    Os.append(((C2) - C(x, y)).log(C1))

assert len(set(Os)) == 1
d = Os[0]

for _ in range(5):
    G1 = io.recvuntil(b'Given C1: Point')
    P = eval(io.recvline()[:-1])
    x, y = P
    G1 = C(x, y)
    G2 = io.recvuntil(b'Given C2: Point')
    P = eval(io.recvline()[:-1])
    x, y = P
    G2 = C(x, y)
    P = ((G2 - G1*d ).x, (G2 - G1*d ).y )
    io.sendlineafter(b'Recovered Point P > ', b'Point'+str(P).encode())
io.interactive()