M0lecon2025teaser | Yet Another OT

Disclaimer#

I wasn’t able to solve this challenge during the competition, but managed to get to the solution after talking on discord to other competitors who very kindly helped me figure it out.

Introduction#

Yet Another OT was a crypto CTF from m0leCon 2025 hosted by pwnthem0le.

1
import random
2
from hashlib import sha256
3
import json
4
import os
5
from Crypto.Cipher import AES
6
from Crypto.Util.Padding import pad
7

8
random = random.SystemRandom()
9

10

11
def jacobi(a, n):
12
    if n <= 0:
13
        raise ValueError("'n' must be a positive integer.")
14
    if n % 2 == 0:
15
        raise ValueError("'n' must be odd.")
16
    a %= n
17
    result = 1
18
    while a != 0:
19
        while a % 2 == 0:
20
            a //= 2
21
            n_mod_8 = n % 8
22
            if n_mod_8 in (3, 5):
23
                result = -result
24
        a, n = n, a
25
        if a % 4 == 3 and n % 4 == 3:
26
            result = -result
27
        a %= n
28
    if n == 1:
29
        return result
30
    else:
31
        return 0
32

33

34
def sample(start, N):
35
    while jacobi(start, N) != 1:
36
        start += 1
37
    return start
38

39

40
class Challenge:
41
    def __init__(self, N):
42
        assert N > 2**1024
43
        assert N % 2 != 0
44
        self.N = N
45
        self.x = sample(int.from_bytes(sha256(("x"+str(N)).encode()).digest(), "big"), N)
46
        ts = []
47
        tts = []
48
        for _ in range(128):
49
            t = random.randint(1, self.N)
50
            ts.append(t)
51
            tts.append(pow(t, N, N))
52
        print(json.dumps({"vals": tts}))
53
        self.key = sha256((",".join(map(str, ts))).encode()).digest()
54

55
    def one_round(self):
56
        z = sample(random.randint(1, self.N), self.N)
57
        r0 = random.randint(1, self.N)
58
        r1 = random.randint(1, self.N)
59

60
        m0, m1 = random.getrandbits(1), random.getrandbits(1)
61

62
        c0 = (r0**2 * (z)**m0) % self.N
63
        c1 = (r1**2 * (z*self.x)**m1) % self.N
64

65
        print(json.dumps({"c0": c0, "c1": c1}))
66
        data = json.loads(input())
67
        v0, v1 = data["m0"], data["m1"]
68
        return v0 == m0 and v1 == m1
69

70
    def send_flag(self, flag):
71
        cipher = AES.new(self.key, AES.MODE_ECB)
72
        ct = cipher.encrypt(pad(flag.encode(), 16))
73
        print(ct.hex())
74

75

76
FLAG = os.environ.get("FLAG", "ptm{test}")
77

78
def main():
79
    print("Welcome to my guessing game!")
80
    N = int(input("Send me a number: "))
81
    chall = Challenge(N)
82
    for _ in range(128):
83
        if not chall.one_round():
84
            exit(1)
85
    chall.send_flag(FLAG)
86

87

88
if __name__ == "__main__":
89
    main()

We can remotely interact with this service to recover the flag.

Analysis#

Let’s start with the functions: jacobi(a, n) computes the Jacobi symbol of a mod n

sample(start, N) returns the first s >= start such that sample(s, N) == 1

Let’s look at the class Challenge now: __init__(self, N)

N is checked to be odd and greater than $2^{1024}$
self.x is generated from sample(int.from_bytes(sha256(("x"+str(N)).encode()).digest(), "big"), N)
A loop generates 128 random private values ts and their public counterpart tts
self.key is generated from sha256((",".join(map(str, ts))).encode()).digest()

one_round(self)

z is generated from sample(random.randint(1, self.N), self.N)
r0, r1 are random integers in the range $[1, N]$
m0, m1 are randomly chosen from $\{0, 1\}$
$c_0 \equiv r_0^2 \cdot z^{m_0} \pmod N$
$c_1 \equiv r_1^2 \cdot (z \cdot x)^{m_1} \pmod N$
c0, c1 are shared and the user has to correctly guess m0, m1 to continue to the next round

send_flag(self, flag)

encrypts the flag with AES using self.key and sends it to the user

Solution#

The first objective is retrieving the AES key, so from each pow(t, N, N) I had to get t. My idea was to use Fermat’s little theorem, therefore setting N to be prime would make it so tts == ts. This allows easy recovery of self.key but it’s also a grave mistake… The second objective is guessing m0 and m1 128 times in a row to finally get the encrypted flag and decrypt it with our key. The idea is to use theory about quadratic residues, but this is where I got stuck: if N is prime this is actually impossible as sample will always generate a correct quadratic residue and therefore these two cases are indistinguishable

\begin{cases} c_0 \equiv r_0^2 \cdot z \pmod N \\ c_0 \equiv r_0^2 \pmod N \end{cases}

After the end of the CTF I asked on discord for help on figuring out where I went wrong and some competitors who solved it kindly explained it to me. The idea is to use a different value for N. Recovering the private key requires “decrypting” the public values which are encrypted using the usual RSA method, we expect this to be hard without knowing the factorization of N, but as we’re the ones to choose it we can simply generate some primes, take their product and decrypting is easy as we have the factorization of N. Now that N is composite sample won’t always generate quadratic residues mod N (there is still a possibility but it’s low enough to be ignored) so as soon as the Legendre symbol of c0 for any of the prime factors of N isn’t 1 we know we must be in the case where m0 == 1 (same goes for c1and m1). After 128 rounds we are given the encrypted flag which we can just decrypt as we have the key.

1
from Pwn4Sage.pwn import *
2
from Crypto.Cipher import AES
3
from Crypto.Util.Padding import unpad
4
import json, hashlib
5

6
r = remote('yaot.challs.m0lecon.it', 2844)
7

8
primes = [random_prime(2^(32), lbound=2^31) for _ in range(33)]
9
N = prod(primes)
10

11
assert N > 2^1024
12

13
phi = prod([p - 1 for p in primes])
14
d = inverse_mod(N, phi)
15

16
# Pwn4Sage doesn't have sendlineafter
17
r.sendafter(b'number: ', str(N).encode() + b'\n')
18

19
tts = json.loads(r.recvline().rstrip())['vals']
20

21
ts = [pow(tt, d, N) for tt in tts]
22

23
key = hashlib.sha256((",".join(map(str, ts))).encode()).digest()
24

25
for _ in range(128):
26
    data = json.loads(r.recvline().rstrip())
27

28
    c0, c1 = data['c0'], data['c1']
29

30
    m0 = int(any(legendre_symbol(c0, p) != 1 for p in primes))
31
    m1 = int(any(legendre_symbol(c1, p) != 1 for p in primes))
32

33
    payload = json.dumps({'m0': m0, 'm1': m1}).encode()
34

35
    r.sendline(payload)
36

37
enc_flag = bytes.fromhex(r.recvline().rstrip().decode())
38

39
cipher = AES.new(key, AES.MODE_ECB)
40

41
flag = unpad(cipher.decrypt(enc_flag), 16).decode()
42

43
print('flag:', flag)

flag: ptm{t0_b3_0r_n07_t0_b3_4_qu4dr471c_r351du3?}