> For the complete documentation index, see [llms.txt](https://elijahchia.gitbook.io/ctf-blog/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://elijahchia.gitbook.io/ctf-blog/ecsc-2024/offtopic-crypto.md).

# 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:

```python
#!/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:

```python
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()`:

```python
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()`:

```python
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:

```python
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

```python
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:

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

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

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

* `__rmul__`

The implementation is

```python
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__`

```python
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()`:

```python
@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.

```python
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}
```