# OT or not OT

This was a crypto challenge at zer0pts CTF 2021.

We are given the script below, and an endpoint on which its runnning, crypto.ctf.zer0pts.com:10130.

import os
import signal
import random
from base64 import b64encode
from Crypto.Util.number import getStrongPrime, bytes_to_long
from Crypto.Cipher import AES
from flag import flag

p = getStrongPrime(1024)

key = os.urandom(32)
iv = os.urandom(AES.block_size)
aes = AES.new(key=key, mode=AES.MODE_CBC, iv=iv)

key = bytes_to_long(key)
print("Encrypted flag: {}".format(b64encode(iv + c).decode()))
print("p = {}".format(p))
print("key.bit_length() = {}".format(key.bit_length()))

signal.alarm(600)
while key > 0:
r = random.randint(2, p-1)
s = random.randint(2, p-1)
t = random.randint(2, p-1)
print("t = {}".format(t))

a = int(input("a = ")) % p
b = int(input("b = ")) % p
c = int(input("c = ")) % p
d = int(input("d = ")) % p
assert all([a > 1 , b > 1 , c > 1 , d > 1])
assert len(set([a,b,c,d])) == 4

u = pow(a, r, p) * pow(c, s, p) % p
v = pow(b, r, p) * pow(c, s, p) % p
x = u ^ (key & 1)
y = v ^ ((key >> 1) & 1)
z = pow(d, r, p) * pow(t, s, p) % p

key = key >> 2

print("x = {}".format(x))
print("y = {}".format(y))
print("z = {}".format(z))


# Analysis

For each two bits in the AES key, the server will generate $$r,s,t \in [2, p-1]$$ and gives us only $$t$$.

Then we have to provide $$a,b,c,d \in [2,p-1]$$, which must all be different from each other.

The server will compute

\begin{eqnarray} u = a^r \times c^s \mod p \\ v = b^r \times c^s \mod p \\ z = d^r \times t^s \mod p \\ \end{eqnarray}

Finally ,we are given $$x = u \oplus k_0,y = v \oplus k_1$$ and $$z$$, where $$k_0$$ and $$k_1$$ are two key bits.

# Choosing $$a,b,c,d$$

By fixing specific values for $$a,b,c,d$$ its possible to recover the original values of $$u$$ and $$v$$, and compare them to the given ones to recover $$k_0$$ and $$k_1$$

First, lets set $$d = p - 1$$.

By doing this, we have

\begin{cases} d^r = 1 \mod p & r \text{ even} \\d^r = p - 1 \mod p & r \text{ odd} \end{cases}

thus,

\begin{cases} z = t^s \mod p & r \text{ even} \\z = (p-1) \times t^s \mod p & r \text{ odd} \end{cases}

Now, lets set $$c = t$$, and $$b = 2a$$. For simplicity, lets fix $$a = 2$$. This gives us

\begin{eqnarray} u = 2^r \times t^s \mod p \\ v = 4^r \times t^s \mod p \\ \end{eqnarray}

What we can do now is try both possibilites for $$r$$.

• If $$r$$ is even, $$z = t^s \mod p$$, so we can easily get $$t^{-s}$$ by inverting $$z$$.

• Otherwise, if $$r$$ is odd, we have $$t^s = z \times (p-1)^{-1} \mod p$$ and we can also find $$t^{-s}$$

Now that we have $$t^{-s}$$, we can try all $$(k_0', k_1') \in [0,1]^2$$ to find the key bits.

In order to validate our guess, we compute the following :

\begin{eqnarray} v_0 = (x \oplus k_0') \times t^{-s} \mod p = ((2^r \times t^s) \oplus k_0 \oplus k_0') \times t^{-s} \mod p \\ v_1 = (y \oplus k_1') \times t^{-s} \mod p = ((4^r \times t^s) \oplus k_0 \oplus k_0') \times t^{-s} \mod p \\ \end{eqnarray}

Now, if our guess is good, ie $$k_0' = k_0$$ and $$k_1' = k_1$$, everything should simplify to :

\begin{eqnarray} v_0 = 2^r \times t^s \times t^{-s} = 2^r \mod p \\ v_1 = 4^r \times t^s \times t^{-s} = 4^r \mod p \\ \end{eqnarray}

To check if that's the case, we only have to verify if $$v_0^2$$ is equal to $$v_1 \mod p$$,

Here is an implementation of the above solution. It starts by guessing that $$r$$ is even, and if the relation $$v_0^2 = v_1 \mod p$$ doesnt hold for any $$(k_0',k_1')$$, it tries the same withe $$r$$ odd.

from pwn import remote, log
import random
from sage.all import inverse_mod
from Crypto.Util.number import long_to_bytes
from Crypto.Cipher import AES
import base64

io = remote("crypto.ctf.zer0pts.com", 10130)
encflag = base64.b64decode(io.recvline().decode().split(": "))
p = int(io.recvline().decode().split(" = "))
bitlen = int(io.recvline().decode().split(" = "))

key = 0
for i in range(bitlen//2):
t = int(io.recvline().decode().split(" = "))
c = t
d = p-1
a = 2
b = 2*a

io.sendline(str(a).encode())
io.sendline(str(b).encode())
io.sendline(str(c).encode())
io.sendline(str(d).encode())

x = int(io.recvline().decode().split(" = ")[-1])
y = int(io.recvline().decode().split(" = ")[-1])
z = int(io.recvline().decode().split(" = ")[-1])

def find_bits(tsinv):
for k0 in [0,1]:
for k1 in [0,1]:
v0 = (x^k0) * ts_inv % p
v1 = (y^k1) * ts_inv % p

if (v0*v0) % p == v1:
return 2*k1 + k0

# Case r even, d^r = 1, z = t^s
ts_inv = inverse_mod(z, p)
bits = find_bits(ts_inv)

# Case r odd
if bits is None:
ts = z * inverse_mod(p-1, p) % p
ts_inv = inverse_mod(ts, p)
bits = find_bits(ts_inv)
key |= (bits << 2*i)
log.info("bits {} & {} found, key={:b}".format(2*i, 2*i+1, key))

key = long_to_bytes(key, 32)
iv,flag = encflag[:16], encflag[16:]
aes = AES.new(key=key, mode=AES.MODE_CBC, iv=iv)

print(aes.decrypt(flag)) # zer0pts{H41131uj4h_H41131uj4h} 