zer0pts CTF 2021 | OT or NOT OT

#zer0ptsCTF2021

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

AESの鍵をNaor-Pinkas OTっぽいOTで保護している。

を満たすように値を作って投げると、が満たされるので解ける

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

非想定解

getStrongPrimeはsafe primeを返すわけではない ので、小さい部分群を使った非想定解法がある。らしいがあまり理解してない