# OT or NOT OT - zer0pts CTF 2021
###### tags: `zer0pts CTF 2021` `crypto`

## overview

The server encrypts flag with AES-CBC. Then provide us the chance to get the AES key. We repeatedly input some parameters $a, b, c, d$, then the server manipulates 2 bits of the key with them and gives us $x, y, z$.

$x, y, z$ are calculated as shown the following.

$u = a^rc^s \mod p$
$v = b^rc^s \mod p$
$x = u \oplus k_i$
$y = v \oplus k_{i+1}$
$z = d^rt^s \mod p$

import os
import signal
import random
from base64 import b64encode
from Crypto.Util.number import getStrongPrime, bytes_to_long
from Crypto.Util.Padding import pad
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)
c = aes.encrypt(pad(flag, AES.block_size))

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))

## solution

This seems like some of **oblivious transfer** protocols. We can easily get either $k_i$ xor $k_{i+1}$. Then how do we get both of them?

As we can input four values, we must think out of how to choose them. For example, if $u = v$ or $u = -v$ stands, the challenge seems to become pretty easy.

Thus, we need to make $a^rc^s \equiv b^rc^s \mod n$ or $a^rc^s \equiv -b^rc^s \mod n$. In order to do it, choosing $a = -b$ is the easiest way.

$c, d$ should satisfy $c \equiv t^{-1}, d \equiv a^{-1} \pmod p$.

Then $u \equiv a^rt^{-s}, v \equiv (-a)^rt^{-s}, z \equiv a^{-r}t^s \pmod n$ stands. So $u \equiv z^{-1} \mod p$ and $v \equiv \pm u$.

## exploit

from ptrlib import Socket
from Crypto.Cipher import AES
import base64
import os

HOST = os.getenv("HOST", "localhost")
PORT = os.getenv("PORT", "9999")

sock = Socket(HOST, int(PORT))

b = base64.b64decode(sock.recvlineafter("flag: "))
iv, cipher = b[:AES.block_size], b[AES.block_size:]

p = int(sock.recvlineafter("p = "))
keylen = int(sock.recvlineafter("() = "))

binflag = ""
for i in range((keylen + 1) // 2):
    print(i)
    t = int(sock.recvlineafter("t = "))

    a = 2
    b = p - a
    c = pow(t, -1, p)
    d = pow(a, -1, p)

    sock.sendlineafter("a = ", str(a))
    sock.sendlineafter("b = ", str(b))
    sock.sendlineafter("c = ", str(c))
    sock.sendlineafter("d = ", str(d))

    x = int(sock.recvlineafter("x = "))
    y = int(sock.recvlineafter("y = "))
    z = int(sock.recvlineafter("z = "))

    u = pow(z, -1, p)
    v = -u % p

    m0 = x ^ u

    if x == y or x == -y % p:
        # (m0 == m1 and r is even) or (m0 == m1 and r is odd)
        m1 = m0
    elif abs(x - y) == 1 or abs(x - (-y%p)) == 1:
        # (m0 != m1 and r is even) or (m0 != m1 and r is odd)
        m1 = m0 ^ 1
    else:
        raise ValueError("WOW")

    binflag += str(m0)
    binflag += str(m1)


key = int.to_bytes(int(binflag[::-1], 2), 32, 'big')
aes = AES.new(key=key, mode=AES.MODE_CBC, iv=iv)
flag = aes.decrypt(cipher)
print(flag)

sock.close()