# Cyber Jawara International 2024

This is a short writeup for the CTF event [Cyber Jawara International 2024](https://ctftime.org/event/2552/). I participated with team [SNI](https://ctftime.org/team/279998/), where we did a merger with Mager and TCP1P. This collaboration is quite fruitful as we placed first in the event. Despite the event being one day after my graduation and I was still quite busy, I am glad to be able to solve some challenges anyways.

## Misc/Stone Game
The challenge is just a [classic NIM game](https://codeforces.com/blog/entry/66040), which is quite popular in Competitive Programming. The only twist is that the Grundy sum of the piles are `0`, and we go first so if the computer is perfect, we can never win. However, it seems that the challenge allows us to take 0 stones exactly once, and exploiting this, we can easily win. Assuming the bot is perfect, we can just randomly take stones until two piles of size 1 are left, then take 0 stone, and take the remaining stone and win the game.

## Cry/Tempest
This challenge is quite difficult at first. It mostly revolves around the usage of the [ethsnarks](https://github.com/HarryR/ethsnarks/) Python library, where the challenge uses the Eddsa module of this library.

import time
from random import SystemRandom
from ethsnarks import jubjub, eddsa, field

FLAG = open('flag.txt', 'rb').read()

def serialize(sig: eddsa.Signature):
    return (sig.R.compress() + int(sig.s).to_bytes(32, 'big')).hex()

def deserialize(b):
    b = bytes.fromhex(b)

    R = jubjub.Point.decompress(b[:32])
    s = field.FQ(int.from_bytes(b[32:], 'big'))
    
    return R, s


TICKET_PRICE = {
    "normal": 10,
    "FLAG": 100,
}

TICKET_VALUE = {
    "normal": 10,
}

ISSUED_TICKETS = {}

REFUNDED_TICKETS = []

class Tempus:
    def __init__(self, username: str):
        self.signer = eddsa.MiMCEdDSA()
        self.sk, self.pk = self.signer.random_keypair()
        self.username = int.from_bytes(username.encode(), 'big')
        self.userid = self.signer.hash_public(self.pk, self.username)
        self.balance = 10
        self.refunded = []
        self.issued_tickets = {}
        self.rand = SystemRandom()

        print(f"Successfully registered with User ID: {self.userid}")

    def buy_ticket(self, ticket_type):
        price = TICKET_PRICE.get(ticket_type)
        if self.balance >= price:
            self.balance -= price
            new_ticket_id = self.rand.getrandbits(128)
            ticket_id = int.to_bytes(new_ticket_id, 16, "big")
            signature = self.signer.sign(new_ticket_id, self.sk)
            ISSUED_TICKETS[self.signer.hash_public(signature.A, self.username, new_ticket_id)] = ticket_type
            signature = serialize(signature.sig)

            if ticket_type == "FLAG":
                print(FLAG)
            else:
                print(f"Your ticket: {ticket_id.hex()+signature}")
        else:
            print("[ERROR] Insufficient balance")

    def refund_ticket(self):
        try:
            ticket = input("Input ticket: ")
            ticket_id, signature = bytes.fromhex(ticket[:32]), deserialize(ticket[32:])
            if self.signer.verify(self.pk, signature, int.from_bytes(ticket_id, 'big')):
                ticket_key = int(input("Input ticket key: "))
                if ticket_key in ISSUED_TICKETS and signature not in REFUNDED_TICKETS:
                    ticket_type = ISSUED_TICKETS.get(ticket_key)
                    value = TICKET_VALUE.get(ticket_type, 0)
                    self.balance += value
                    REFUNDED_TICKETS.append(signature)
                    print("Ticket succesfully refunded!")
                else:
                    print("[ERROR] Invalid ticket")
            else:
                print("[ERROR] Invalid ticket")
        except Exception:
            print("[ERROR] Invalid ticket")

    def menu(self):
        print("[1] Buy ticket      ($10)")
        print("[2] Buy FLAG        ($100)")
        print("[3] Refund ticket")
        print("[4] Exit")
        print("")
        print(f"Your balance: ${self.balance}")

def main():

    username = input("Username: ")
    ticketer = Tempus(username)

    while True:
        time.sleep(0.5)
        ticketer.menu()
        option = input("$> ")
        if option == "1":
            ticketer.buy_ticket("normal")
        elif option == "2":
            ticketer.buy_ticket("FLAG")
        elif option == "3":
            ticketer.refund_ticket()
        else:
            break

if __name__ == "__main__":
    main()

There seems to be two main goals of this challenge:
1. Forging either tickets or its signature to refund multiple times.
2. Calculate the `ticket_key` required for actually refunding tickets.

### Forging signatures

After an hour of digging through the library's source code, I found an interesting bug from the verification function from the Eddsa module:

    @classmethod
    def verify(cls, A, sig, msg, B=None):
        if not isinstance(A, Point):
            A = Point(*A)

        if not isinstance(sig, Signature):
            sig = Signature(*sig)

        R, S = sig
        B = B or cls.B()
        lhs = B * S

        M = cls.prehash_message(msg)
        rhs = R + (A * cls.hash_public(R, A, M))
        return lhs == rhs

Notice that the `S` variable from the signature is not validated. This is clearly a vulnerability as `S` should be in the range of `(0, l)` where `l` is the order of the curve. Otherwise, an attacker could forge different `S` values for a known plaintext-signature pair by simply calculating `S'` such that it is equal to `S` modulo `l`.

However, at first glance this bug seems to have been patched in the challenge on the deserialization function:

def deserialize(b):
    b = bytes.fromhex(b)

    R = jubjub.Point.decompress(b[:32])
    s = field.FQ(int.from_bytes(b[32:], 'big'))
    
    return R, s

Here, the `S` variable is placed in a field which automatically does the modulo. Now, notice how the field actually does the modulo:

# Fq is the base field of Jubjub
SNARK_SCALAR_FIELD = 21888242871839275222246405745257275088548364400416034343698204186575808495617
# Fr is the scalar field of Jubjub
FR_ORDER = 21888242871839275222246405745257275088614511777268538073601725287587578984328

From the [field source code](https://github.com/HarryR/ethsnarks/blob/master/ethsnarks/field.py), we notice that the `FQ` field actually does the modulo on the `SNARK_SCALAR_FIELD`, whereas the order of the curve is actually the variable `FR_ORDER`. This should be exploitable, but `FR_ORDER` is larger than `SNARK_SCALAR_FIELD` so we still need some optimization. Fortunately, points seem to be in [curve subgroups](https://eips.ethereum.org/EIPS/eip-2494#order) with order `FR_ORDER/8` most of the time, and this value is indeed smaller than `SNARK_SCALAR_FIELD`.

Thus, we can do an exploit by forging new signatures for the same message (voucher) by adding `FR_ORDER/8` to `S` multiple times as long as it is still smaller than `SNARK_SCALAR_FIELD`.

### Calculating Ticket Key
To redeem our forged `(voucher, signature)`, we also need to calculate the proper `ticket_key`.

ISSUED_TICKETS[self.signer.hash_public(signature.A, self.username, new_ticket_id)] = ticket_type

if ticket_key in ISSUED_TICKETS and signature not in REFUNDED_TICKETS:
        ticket_type = ISSUED_TICKETS.get(ticket_key)
        value = TICKET_VALUE.get(ticket_type, 0)
        self.balance += value
        REFUNDED_TICKETS.append(signature)
        print("Ticket succesfully refunded!")
    else:
        print("[ERROR] Invalid ticket")

Fortunately, this seems to be easy as firstly, the ticket blacklist is only by the ticket signature (which we can forge), and the actual `ticket_id` and `ticket_key` is not blacklisted.

Digging through the library once more, we see that the hash is done with some `mimc` based algorithm:

class MiMCEdDSA(_SignatureScheme):
    @classmethod
    def hash_public(cls, *args, p13n=P13N_EDDSA_VERIFY_RAM):
        return mimc_hash(list(as_scalar(*args)), seed=p13n)

def mimc_hash(x, k=0, seed=DEFAULT_SEED, p=SNARK_SCALAR_FIELD, e=DEFAULT_EXPONENT, R=DEFAULT_ROUNDS):
    """
    The Miyaguchi–Preneel single-block-length one-way compression
    function is an extended variant of Matyas–Meyer–Oseas. It was
    independently proposed by Shoji Miyaguchi and Bart Preneel.

    H_i = E_{H_{i-1}}(m_i) + {H_{i-1}} + m_i

    The previous output is used as the key for
    the next iteration.

    or..

                 m_i
                  |
                  |----,
                  |    |
                  v    |
    H_{i-1}--,-->[E]   |
             |    |    |
             `-->(+)<--'
                  |
                  v
                 H_i

    @param x list of inputs
    @param k initial key
    """
    for x_i in x:
        r = mimc(x_i, k, seed, p, e, R)
        k = (k + x_i + r) % p
    return k

Luckily, it seems that we don't need to know details and just continue the hash from some known state to calculate `ticket_key`. This can be done as the hash is calculated with `hash_public(signature.A, self.username, new_ticket_id)`, whereas we are given `user_id` when connecting to the service which contains the information `hash_public(self.pk, self.username)`. Note that `signature.A` and `self.pk` is the same public key, thus we could just run:

mimc_hash([int.from_bytes(ticket_id, 'big')], k=userid, seed=P13N_EDDSA_VERIFY_RAM)

and obtain the same result.

### Solver

import time
from random import SystemRandom
from pwn import remote, process
from ethsnarks import jubjub, eddsa, field
from ethsnarks.mimc.permutation import mimc_hash

SNARK_SCALAR_FIELD = 21888242871839275222246405745257275088548364400416034343698204186575808495617
JUBJUB_E = 21888242871839275222246405745257275088614511777268538073601725287587578984328
JUBJUB_C = 8		# Cofactor
JUBJUB_L = JUBJUB_E//JUBJUB_C
P13N_EDDSA_VERIFY_RAM = 'EdDSA_Verify.RAM'

#r = process(['python3', 'challenge.py'], level='debug')
r = remote('68.183.177.211', 18272, level='debug')

r.sendlineafter(b'Username:', b'azuketto')
r.recvuntil(b'Successfully registered with User ID: ')
userid = int(r.recvline().strip().decode())

def serialize(sig: eddsa.Signature):
    return (sig.R.compress() + int(sig.s).to_bytes(32, 'big')).hex()

def deserialize(b):
    b = bytes.fromhex(b)

    R = jubjub.Point.decompress(b[:32])
    s = field.FQ(int.from_bytes(b[32:], 'big'))
    
    return R, s

def buy(choice: int = 1):
    r.sendlineafter(b'$> ', str(choice).encode())
    if choice == 1:
        r.recvuntil(b'Your ticket: ')
        return r.recvline().strip().decode()
    else: r.interactive()
    
def redeem(ticket: str, key: str):
    r.sendlineafter(b'$> ', b'3')
    r.sendlineafter(b':', ticket.encode())
    r.sendlineafter(b'key:', key.encode())

ticket = buy()
ticket_id, signature = bytes.fromhex(ticket[:32]), deserialize(ticket[32:])
key = mimc_hash([int.from_bytes(ticket_id, 'big')], k=userid, seed=P13N_EDDSA_VERIFY_RAM)
R, s = signature
for _ in range(15):
    sig = (R.compress()+ int(s).to_bytes(32, 'big')).hex()
    redeem(ticket_id.hex()+sig , str(key))
    if s.n + JUBJUB_L > SNARK_SCALAR_FIELD:
        ticket = buy()
        ticket_id, signature = bytes.fromhex(ticket[:32]), deserialize(ticket[32:])
        key = mimc_hash([int.from_bytes(ticket_id, 'big')], k=userid, seed=P13N_EDDSA_VERIFY_RAM)
        R, s = signature
    else:
        s += JUBJUB_L
    
buy(2)

### Additional Notes
This writeup indeed exposes a 0 day vulnerability of the library. However, after contacting the maintainer of the library, he seems to not have the time to maintain this anymore, and has decided to [deprecate the library](https://github.com/HarryR/ethsnarks/commit/cc5aae9a06267ea9a9afcdb5c48f3f73dfa1467b).

## Cry/Exchange
This is a fairly simple challenge. We are given a near perfect SIDH script, with one tiny flaw:

import random, os
from sage.all import GF, EllipticCurve
from Crypto.Hash import SHA256
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad

from secret import k, secret_message

assert k < 2**80

class SIDHKeyExchange:
    def __init__(self, ea, eb, Px, Py, Qx, Qy):
        self.ea = ea
        self.eb = eb
        self.p = 2**ea * 3**eb - 1
        self.F = GF(self.p**2, modulus=[1, 0, 1], name="i")
        self.E0 = EllipticCurve(self.F, [1,0])
        self.n = self.p + 1
        self.P = self.E0(Px, Py)
        self.Q = self.E0(Qx, Qy)

    def gen_public_key(self, P, Q, P_other, Q_other, k):
        S = P + k * Q
        phi = self.E0.isogeny(S, algorithm="factored")
        phi_P, phi_Q = phi(P_other), phi(Q_other)
        E = phi.codomain()
        return E, phi_P, phi_Q

    def get_secret(self, E, phi_P, phi_Q, k):
        S = phi_P + k * phi_Q
        phi = E.isogeny(S, algorithm="factored")
        return phi.codomain().j_invariant()


class Participant:
    def __init__(self, sidh: SIDHKeyExchange, k=None):
        self.sidh = sidh
        self.k = k if k else random.randint(0, sidh.n - 1)
        self.public_key = None
        self.P = None
        self.Q = None
        self.P_other = None
        self.Q_other = None
        self.shared_secret = None

    def generate_public_key(self):
        self.public_key = self.sidh.gen_public_key(self.P, self.Q, self.P_other, self.Q_other, self.k)

    def compute_shared_secret(self, other_public_key):
        E, phi_P, phi_Q = other_public_key
        self.shared_secret = self.sidh.get_secret(E, phi_P, phi_Q, self.k)

    def encrypt_message(self, message):
        key = SHA256.new(data=str(self.shared_secret).encode()).digest()
        iv = os.urandom(16)
        cipher = AES.new(key, AES.MODE_CBC, iv)
        ct = cipher.encrypt(pad(message, 16))

        return iv.hex(), ct.hex()

class Server(Participant):
    def __init__(self, sidh: SIDHKeyExchange, k=None):
        super().__init__(sidh, k)
        self.P = (sidh.n // 2**sidh.ea) * sidh.P
        self.Q = (sidh.n // 2**sidh.ea) * sidh.Q
        self.P_other = (sidh.n // 3**sidh.eb) * sidh.P
        self.Q_other = (sidh.n // 3**sidh.eb) * sidh.Q


# params
ea, eb = 216, 137
Px, Py = "19629002260899253283957946747466897522475660429050952494632348990720012643804186952501717429174343892395039800185878841093698753933*i + 21000588886550169078507395472843540543638380042132530088238158553508923414317518502680121549885061095065934470295106985227640283273", "13560249428793295825208984866590149450862696800181907880173464654955696194787095135464283707858591438577968786063706580965498135934*i + 21227525746542853125364742330159420698250203945016980815891234503309307307571119288025866772923240030378597416196914652205098993851"
Qx, Qy = "20653307324266777301745266224745462280019066788351952077152874786877832545975431386178311539432979313717724415603792104905464166613*i + 23543412524221765729252528306934564386341553623491347201198996167100895162007001691940922919130176638905146054229833255452149631903", "20303099683704256985792197307242241000101523982229217515269602102967877919445169730337445309155396940855065338113695974349986136276*i + 18114250244485018537853099412437907124848306019791525046747068726333108423955919092536186121751860512435214970727124588973589483061"

sidh = SIDHKeyExchange(ea, eb, Px, Py, Qx, Qy)

server = Server(sidh, k)

server.generate_public_key()

E, phi_P, phi_Q = server.public_key

print("Server public key")
print("E")
print(f"Ea4: {E.a4()}")
print(f"Ea6: {E.a6()}")
print("phi_P")
print(f"x: {phi_P[0]}")
print(f"y: {phi_P[1]}")
print("phi_Q")
print(f"x: {phi_Q[0]}")
print(f"y: {phi_Q[1]}")

print()
print("Input your public key")
print("Input elliptic curve")
Ea4 = input("Ea4: ")
Ea6 = input("Ea6: ")
E = EllipticCurve(sidh.F, [Ea4, Ea6])

print("Input phi_P")
x = input("x: ")
y = input("y: ")
phi_P = E(x, y)
print("Input phi_Q")
x = input("x: ")
y = input("y: ")
phi_Q = E(x, y)

other_public_key = (E, phi_P, phi_Q)
server.compute_shared_secret(other_public_key)

iv, ct = server.encrypt_message(secret_message)

print("Encrypted message")
print(f"iv: {iv}")
print(f"ct: {ct}")

The flaw is located around the initializations of the elliptic curves. Basically, sagemath does not immediately know the order of the curve, and needs to compute it from scratch. This is not necessary as we know that the order of the curve is `(p+1)**2`. Thus, we can just do a patch by adding lines such as `E.set_order(sidh.n ** 2)`, and just run the SIDH protocol.

I will not explain how the protocol works in this writeup as other sources will do a better job, e.g. [Wikipedia](https://en.wikipedia.org/wiki/Supersingular_isogeny_key_exchange)

### Solver

import random, os
from pwn import process, remote
from sage.all import GF, EllipticCurve
from Crypto.Hash import SHA256
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad

from secret import k, secret_message

k = 23
#r = process(['sage', '--python', 'server.py'], level='debug')
r = remote('152.42.183.87', 20003, level='debug')

class SIDHKeyExchange:
    def __init__(self, ea, eb, Px, Py, Qx, Qy):
        self.ea = ea
        self.eb = eb
        self.p = 2**ea * 3**eb - 1
        self.F = GF(self.p**2, modulus=[1, 0, 1], name="i")
        self.E0 = EllipticCurve(self.F, [1,0])
        self.n = self.p + 1
        self.P = self.E0(Px, Py)
        self.Q = self.E0(Qx, Qy)

    def gen_public_key(self, P, Q, P_other, Q_other, k):
        S = P + k * Q
        phi = self.E0.isogeny(S, algorithm="factored")
        phi_P, phi_Q = phi(P_other), phi(Q_other)
        E = phi.codomain()
        return E, phi_P, phi_Q

    def get_secret(self, E, phi_P, phi_Q, k):
        S = phi_P + k * phi_Q
        phi = E.isogeny(S, algorithm="factored")
        return phi.codomain().j_invariant()


class Participant:
    def __init__(self, sidh: SIDHKeyExchange, k=None):
        self.sidh = sidh
        self.k = k if k else random.randint(0, sidh.n - 1)
        self.public_key = None
        self.P = None
        self.Q = None
        self.P_other = None
        self.Q_other = None
        self.shared_secret = None

    def generate_public_key(self):
        self.public_key = self.sidh.gen_public_key(self.P, self.Q, self.P_other, self.Q_other, self.k)

    def compute_shared_secret(self, other_public_key):
        E, phi_P, phi_Q = other_public_key
        self.shared_secret = self.sidh.get_secret(E, phi_P, phi_Q, self.k)

    def encrypt_message(self, message):
        key = SHA256.new(data=str(self.shared_secret).encode()).digest()
        iv = os.urandom(16)
        cipher = AES.new(key, AES.MODE_CBC, iv)
        ct = cipher.encrypt(pad(message, 16))

        return iv.hex(), ct.hex()
    
    def decrypt_message(self, ct, iv):
        key = SHA256.new(data=str(self.shared_secret).encode()).digest()
        cipher = AES.new(key, AES.MODE_CBC, iv)
        pt = cipher.decrypt(ct)
        return pt

class Server(Participant):
    def __init__(self, sidh: SIDHKeyExchange, k=None):
        super().__init__(sidh, k)
        self.P_other = (sidh.n // 2**sidh.ea) * sidh.P
        self.Q_other = (sidh.n // 2**sidh.ea) * sidh.Q
        self.P = (sidh.n // 3**sidh.eb) * sidh.P
        self.Q = (sidh.n // 3**sidh.eb) * sidh.Q


# params
ea, eb = 216, 137
Px, Py = "19629002260899253283957946747466897522475660429050952494632348990720012643804186952501717429174343892395039800185878841093698753933*i + 21000588886550169078507395472843540543638380042132530088238158553508923414317518502680121549885061095065934470295106985227640283273", "13560249428793295825208984866590149450862696800181907880173464654955696194787095135464283707858591438577968786063706580965498135934*i + 21227525746542853125364742330159420698250203945016980815891234503309307307571119288025866772923240030378597416196914652205098993851"
Qx, Qy = "20653307324266777301745266224745462280019066788351952077152874786877832545975431386178311539432979313717724415603792104905464166613*i + 23543412524221765729252528306934564386341553623491347201198996167100895162007001691940922919130176638905146054229833255452149631903", "20303099683704256985792197307242241000101523982229217515269602102967877919445169730337445309155396940855065338113695974349986136276*i + 18114250244485018537853099412437907124848306019791525046747068726333108423955919092536186121751860512435214970727124588973589483061"

sidh = SIDHKeyExchange(ea, eb, Px, Py, Qx, Qy)

server = Server(sidh, k)

server.generate_public_key()


r.recvuntil("Ea4: ")
Ea4 = r.recvline().strip().decode()
r.recvuntil(b'Ea6: ') 
Ea6 = r.recvline().strip().decode()
E = EllipticCurve(sidh.F, [Ea4, Ea6])

print("Input phi_P")
r.recvuntil(b'x: ') 
x = r.recvline().strip().decode()
r.recvuntil(b'y:')
y = r.recvline().strip().decode()
phi_P = E(x, y)
print("Input phi_Q")
r.recvuntil(b'x: ') 
x = r.recvline().strip().decode()
r.recvuntil(b'y:')
y = r.recvline().strip().decode()
phi_Q = E(x, y)

E2, phi_P2, phi_Q2 = server.public_key

print(f"E: {E2.a4()}")
r.sendlineafter(b'Ea4:', str(E2.a4()).encode())
r.sendlineafter(b'Ea6:', str(E2.a6()).encode())    
r.sendlineafter(b'x:', str(phi_P2[0]).encode())
r.sendlineafter(b'y:', str(phi_P2[1]).encode())
r.sendlineafter(b'x:', str(phi_Q2[0]).encode())
r.sendlineafter(b'y:', str(phi_Q2[1]).encode())

E.set_order(sidh.n ** 2)
other_public_key = (E, phi_P, phi_Q)
server.compute_shared_secret(other_public_key)

r.recvuntil(b'iv: ')
iv = r.recvline().strip().decode()
iv = bytes.fromhex(iv)

r.recvuntil(b'ct: ')
ct = r.recvline().strip().decode()
ct = bytes.fromhex(ct)

print(server.decrypt_message(ct, iv))

### Additional notes
The solver only solves part 1 of the challenge, which obtains the following message:

b"here is the first flag CJ{i50g3ny_1z_r3a11y_c00l}, and the second flag is long_to_bytes(k) wrap with '{}'\x07\x07\x07\x07\x07\x07\x07"

The second part can be easily solved by running the [Castryck-Decru attack](https://eprint.iacr.org/2022/975), but I didn't have time for this as the script can take quite a while for the parameter size provided in the challenge.