➕OffTopic (crypto)

This was the only challenge I solved during the CTF. It had 30 solves in total.

We are given the following challenge related to elliptic curves:

#!/usr/bin/env python3

from Crypto.PublicKey.ECC import EccPoint
from Crypto.Random import random
import hashlib
import json
import os

flag = os.getenv('FLAG', 'ECSC{redacted}')

p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
Gx = 0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296
Gy = 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5
q = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551
G = EccPoint(Gx, Gy)
H = None

class Ciphertext:
    def __init__(self, value):
        self.R = value[0]
        self.S = value[1]

    @classmethod
    def from_pt(cls, m):
        r = random.randint(0, q-1)
        R = r*G
        S = r*H + m*G
        return cls([R, S])

    def __add__(self, other):
        if isinstance(other, int):
            return self + Ciphertext.from_pt(other)
        rand = Ciphertext.from_pt(0)
        return Ciphertext([self.R+other.R+rand.R, self.S+other.S+rand.S])

    def __rmul__(self, other):
        if not isinstance(other, int):
            raise NotImplementedError
        rand = Ciphertext.from_pt(0)
        return Ciphertext([rand.R + other*self.R, rand.S + other*self.S])
    
    def __neg__(self):
        return Ciphertext([-self.R, -self.S])

    def __sub__(self, other):
        return self + (-other)

    def __rsub__(self, other):
        if isinstance(other, int):
            return Ciphertext.from_pt(other) - self
        
def round():
    data = json.loads(input("Send your encrypted choice bit: "))
    C = Ciphertext([EccPoint(data["Rx"], data["Ry"]), EccPoint(data["Sx"], data["Sy"])])
    m0 = random.randint(0, 9)
    m1 = random.randint(0, 9)
    res = m0 * (1-C) + m1 * C
    print(json.dumps({"Rx": int(res.R.x), "Ry": int(res.R.y), "Sx": int(res.S.x), "Sy": int(res.S.y)}))
    data = json.loads(input("Send the recovered messages: "))
    return m0 == data["m0"] and m1 == data["m1"]

def get_pk():
    global H
    data = json.loads(input("Send your public key: "))
    H = EccPoint(data["Hx"], data["Hy"])
    assert H != G

def main():
    print("Welcome to my new guessing game! Are you ready?")
    get_pk()

    for _ in range(128):
        assert round()

    print(flag)

if __name__ == "__main__":
    main()

First we analyse the main function:

def main():
    print("Welcome to my new guessing game! Are you ready?")
    get_pk()

    for _ in range(128):
        assert round()

    print(flag)

The program starts by obtaining a public key from us via get_pk(), then for 128 rounds it checks that round() returns true.

Let's look at get_pk():

def get_pk():
    global H
    data = json.loads(input("Send your public key: "))
    H = EccPoint(data["Hx"], data["Hy"])
    assert H != G

It expects to be sent a json object containing the Hx and Hy fields, representing an elliptic curve point. There is also a check to ensure that our provided point is different from G.

Now let's inspect the crucial verification function round():

def round():
    data = json.loads(input("Send your encrypted choice bit: "))
    C = Ciphertext([EccPoint(data["Rx"], data["Ry"]), EccPoint(data["Sx"], data["Sy"])])
    m0 = random.randint(0, 9)
    m1 = random.randint(0, 9)
    res = m0 * (1-C) + m1 * C
    print(json.dumps({"Rx": int(res.R.x), "Ry": int(res.R.y), "Sx": int(res.S.x), "Sy": int(res.S.y)}))
    data = json.loads(input("Send the recovered messages: "))
    return m0 == data["m0"] and m1 == data["m1"]

The code is surprisingly concise; We are to send a json object containing the Rx, Ry, Sx and Sy fields. Rx and Ry represent an elliptic curve point R, and similarly Sx and Sy represent an elliptic curve point S. The points we provide are used to create a Ciphertext object which is interpreted as a "choice bit".

Then it generates an m0 and m1 which are independent of each other and each between 0 and 9 inclusive. Then, we calculate res using some arithmetic on the Ciphertext object C using the formula res = m0 * (1-C) + m1 * C. res is also a Ciphertext object, and we receive its parameters R.x, R.y, S.x and S.y.

After this, we are required to send another json object, this time with our guesses of m0 and m1. Our guessed values both have to be correct for round() to return true.

Before discussing the solution, we first need to understand the Ciphertext class:

class Ciphertext:
    def __init__(self, value):
        self.R = value[0]
        self.S = value[1]

    @classmethod
    def from_pt(cls, m):
        r = random.randint(0, q-1)
        R = r*G
        S = r*H + m*G
        return cls([R, S])

    def __add__(self, other):
        if isinstance(other, int):
            return self + Ciphertext.from_pt(other)
        rand = Ciphertext.from_pt(0)
        return Ciphertext([self.R+other.R+rand.R, self.S+other.S+rand.S])

    def __rmul__(self, other):
        if not isinstance(other, int):
            raise NotImplementedError
        rand = Ciphertext.from_pt(0)
        return Ciphertext([rand.R + other*self.R, rand.S + other*self.S])
    
    def __neg__(self):
        return Ciphertext([-self.R, -self.S])

    def __sub__(self, other):
        return self + (-other)

    def __rsub__(self, other):
        if isinstance(other, int):
            return Ciphertext.from_pt(other) - self

As previously discussed, creating a Ciphertext object requires two EccPoints R and S. The from_pt function randomly samples an r between 0 and q - 1, and creates a new Ciphertext object where R = r * G and S = r * H + m * G. The resultant Ciphertext created would have an R which is G multiplied by a random integer, and S which is a random integer multiplying our public key H added to the input (m) multiplied by the given point G. In other words, it returns a new Ciphertext object with random points R and S dependent on G, m and H.

The Ciphertext class has several custom arithmetic operations defined: __add__, __rmul__, __neg__, __sub__ and __rsub__. When do we use these arithmetic operations? Only when we do res = m0 * (1-C) + m1 * C in the round() function. Recall that m0 and m1 are integers, and C is a Ciphertext object. Firstly, (1-C) results in __rsub__(1) being called, m0 * (1-C) results in __rmul__(m0) being called, m1 * C results in __rmul__(m1) being called, and m0 * (1-C) + m1 * C) also results in __add__ being called.

__rsub__, __neg__ and __sub__

The implementation is

def __rsub__(self, other):
    if isinstance(other, int):
        return Ciphertext.from_pt(other) - self

This operation creates a (presumably random) point using the integer other, then performs subtraction between that point and self. This operation relies on __sub__. Note that the __rsub__ method has a randomised output as it uses from_pt().

For __sub__ we have:

def __sub__(self, other):
    return self + (-other)

which relies on __add__ and __neg__. For __neg__ we have:

def __neg__(self):
    return Ciphertext([-self.R, -self.S])

__rmul__

The implementation is

def __rmul__(self, other):
    if not isinstance(other, int):
        raise NotImplementedError
    rand = Ciphertext.from_pt(0)
    return Ciphertext([rand.R + other*self.R, rand.S + other*self.S])

Again, there is randomness due to the reliance on from_pt(). After generating the random point, we use the EccPoints contained in rand and perform elliptic curve point addition and multiplication with the EccPoints contained in self.

__add__

def __add__(self, other):
    if isinstance(other, int):
        return self + Ciphertext.from_pt(other)
    rand = Ciphertext.from_pt(0)
    return Ciphertext([self.R+other.R+rand.R, self.S+other.S+rand.S])

The __add__ operation again introduces randomness using from_pt() and does does elliptic curve point addition between the EccPoints in self, other and rand.

In summary, the arithmetic operations done in res = m0 * (1 - C) + m1 * C heavily relies on randomness introduced via from_pt().

Since we know that m0 ranges from 0 to 9 and m1 ranges from 0 to 9, for each round() the intuitive approach is to try all m0 and m1 values and see which one matches the res object produced. The problem with this, however, is that the arithmetic operations are all randomised with the help of from_pt().

Is there any way to make from_pt() non-random (aka deterministic)? It turns out that there is! Let's take a closer look at from_pt():

@classmethod
def from_pt(cls, m):
    r = random.randint(0, q-1)
    R = r*G
    S = r*H + m*G
    return cls([R, S])

However, notice that H is the public key controlled by us! What if H = (0,0)? The resultant Ciphertext object would still have a random R, but S would be deterministic since S = m*G. With this public key, from_pt() would give a deterministic S , making the arithmetic operations in Ciphertext produce deterministic S values.

So the key idea behind the solve is to give a public key of H = (0,0) to make the arithmetic operations produce Ciphertexts with deterministic S values. Then, in each round we provide some arbitrary points S and R, and receive the calculated res value. Then, we bruteforce the 10 possible m0 values and the ten possible m1 values, and see which pair of values gives us the same res.S. Below is the solve script. Since the server had a 30s timeout, I had to modify the bruteforcing to stop the moment a valid m0 and m1 were found for it to survive all 128 rounds.

from Crypto.PublicKey.ECC import EccPoint
from Crypto.Random import random
import hashlib
import json
import os
from pwn import *

p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
Gx = 0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296
Gy = 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5
q = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551
G = EccPoint(Gx, Gy)
H = EccPoint(0, 0)

class Ciphertext:
    def __init__(self, value):
        self.R = value[0]
        self.S = value[1]

    @classmethod
    def from_pt(cls, m):
        r = random.randint(0, q-1)
        R = r*G
        S = r*H + m*G
        return cls([R, S])

    def __add__(self, other):
        if isinstance(other, int):
            return self + Ciphertext.from_pt(other)
        rand = Ciphertext.from_pt(0)
        return Ciphertext([self.R+other.R+rand.R, self.S+other.S+rand.S])

    def __rmul__(self, other):
        if not isinstance(other, int):
            raise NotImplementedError
        rand = Ciphertext.from_pt(0)
        return Ciphertext([rand.R + other*self.R, rand.S + other*self.S])
    
    def __neg__(self):
        return Ciphertext([-self.R, -self.S])

    def __sub__(self, other):
        return self + (-other)

    def __rsub__(self, other):
        if isinstance(other, int):
            return Ciphertext.from_pt(other) - self
context.log_level = 'debug'
# p = process(["python3", "./offtopic.py"])
p = remote("offtopic.challs.jeopardy.ecsc2024.it", 47013)
X, Y = 10 * G, 15 * G 
C = Ciphertext([10 * G, 15 * G])
p.sendlineafter(b": ", b'{"Hx": 0, "Hy": 0}')
for ctr in range(128):
    p.sendlineafter(b": ", b'{"Rx": ' + str(X.x).encode() + b', "Ry": ' + str(X.y).encode() + b', "Sx": ' + str(Y.x).encode() + b', "Sy": ' + str(Y.y).encode() + b'}')
    res = p.recvline()
    res = res.split(b", ")
    Sx, Sy = int(res[2][6:].decode()), int(res[3][6:-2].decode())
    # print(f"Sx: {Sx}")
    # print(f"Sy: {Sy}")
    # print(res)
    a0, a1 = -1, -1 # a0 and a1 store the correct final m0 and m1 values
    for m0 in range(0, 10):
        for m1 in range(0, 10):
            res = m0 * (1-C) + m1 * C
            if (int(res.S.x) == Sx and int(res.S.y) == Sy):
                a0 = m0 
                a1 = m1
                break
        if a0 != -1: # short-circuit the brute-forcing to save time
            break
    # print(f"ctr: {ctr}")
    p.sendlineafter(b"messages: ", b'{"m0": ' + str(a0).encode() + b', "m1": ' + str(a1).encode() + b"}")

p.interactive() # ECSC{ch3w1n5_m0r3_7h4n_y0u_c4n_b1t_6259b94d}

Last updated 9 months ago