Try   HackMD

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=arcsmodp
v=brcsmodp

x=u⊕ki

y=v⊕ki+1

z=drtsmodp

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

ki xor
ki+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

arcs≡brcsmodn or
arcs≡−brcsmodn
. In order to do it, choosing
a=−b
is the easiest way.

c,d should satisfy
c≡t−1,d≡a−1(modp)
.

Then

u≡art−s,v≡(−a)rt−s,z≡a−rts(modn) stands. So
u≡z−1modp
and
v≡±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()