MaltaCTF: true random

#quantum #crypto

So it seems I need to transfer a flag or something. Fortunately - no cryptographer can break OTP! Unfortunately… my cat may have shuffled my otp codes around. Should be fine though, we have a few quantum circuits conveniently shared between us that we can use as our checksums! Surely the checksum of a random output won’t let you break my OTP!

The challenge generates 13 random quantum circuits, and then gives us 256 pair consisting of:

from qiskit.circuit.random import random_circuit
from qiskit.quantum_info import Operator
from qiskit.quantum_info import Statevector
from numpy import array, save
from math import log2
import random
random = random.SystemRandom()
flag = open("flag.txt", "r").read().strip()
flag_len = len(flag)*8
assert flag_len == 256
depth = 10
qubits = int(log2(flag_len))

flag_bits = [int(bit) for bit in ''.join(format(ord(c), '08b') for c in flag)]



def random_pair(op):
    otp_key = [random.choice([0,1]) for _ in range(flag_len)]
    i = Statevector(otp_key)
    f = i.evolve(op)
    enc = array([flag_bits[i] ^ otp_key[i] for i in range(flag_len)])
    return array([enc, f.data])

ops = []
for _ in range(13):
    qc = random_circuit(qubits, depth, measure=False)
    op = Operator(qc)
    ops.append(op)

sets = 256
data = array([random_pair(random.choice(ops)) for _ in range(sets)])
save("enc.npy", data)

It turns out that, since all quantum gates are unitary transformations (thanks @V3r7ux) we can leak the product between some of the vectors: more precisely we can express these circuits as unitary matrices.

So rephrasing: we have

$$ (v_i \oplus \text{flag}, C_r v_i) $$

where $i$ goes from 0 to 255 and r is chosen randomly between 0 and 12. Let’s consider, for some $i,j$ that share the same $C$

$$ (C v_i)^* (C v_j) = $$

$$ v_i^* C^* C v_j = $$

Since $C$ is unitary, $C^* = C^{-1}$, and since the vectors are real, taking the conjugate does nothing

$$ v_i^\intercal C^{-1} C v_j = v_i^\intercal v_j$$

This of course only holds if the vectors have the same circuit, but we can easily bruteforce it and check for a result with no imaginary part.

So now we have a good amount of quadratic constraints over $2^{16}$ boolean variables, let’s optimize this! If we xor every ciphertext with the first one, we get

$$ v_0 \oplus \text{flag} \oplus v_j \oplus \text{flag} = v_0 \oplus v_j$$

for each vector, this means we can express every element $v_i$ in terms of $v_0$!

This is way better, 256 variables and a few hundred quadratic constraints, but we can still do better~ Let’s suppose we are setting the constraint for $v_i^\intercal v_j = s$: $v_{i,0} * v_{j,0} + v_{i,1} * v_{j,1} + ... = s$ since we know $v_{i,0} \oplus v_{j,0}$, we can use that to simplify the expressions:

If $v_{i,0} \oplus v_{j,0} = 1$, then the product will be always 0, and we can just not include it.

If $v_{i,0} \oplus v_{j,0} = 0$, $v_{i,0} = v_{j,0}$ and since $v_{i,n}$ are booleans we can just use $v_{i,0}$

In other words, from these non linear constraints, we managed to create a fully linear system of equations!

I used google ortools to solve the equation with the boolean constraint, here is the script:

from ortools.sat.python import cp_model
import numpy as np

EPSILON = 0.0000000000001

data = np.load("enc.npy")

vectors = []
magics = []

for i in range(256):
    vectors.append(tuple(map(lambda x: int(x.real), data[i][0].tolist())))
    magics.append(data[i][1])

product_data = []
for i in range(len(magics)):
    for j in range(i):
        h = np.conjugate(magics[j]).T
        res = np.dot(h, magics[i]).item()
        if abs(res.imag) > EPSILON:
            continue
        res_real = round(res.real)
        assert abs(res_real-res.real) < EPSILON
        product_data.append((i, j, res_real))
print("Computed products")

xor = lambda a, b: tuple([aa ^ bb for aa, bb in zip(a, b)])
vectors_xor0 = [xor(vectors[0], v) for v in vectors]
print("Computed xors")

model = cp_model.CpModel()

m_vector = [
    model.new_int_var(0, 1, f"v_{i}")
    for i in range(256)
]
print("Generated model vector")

for i, j, v in product_data:
    vi = vectors_xor0[i]
    vj = vectors_xor0[j]
    tot = 0
    for k in range(256):
        if vi[k] != vj[k]:
            continue
        if vi[k] == 0:
            tot += m_vector[k]
        if vi[k] == 1:
            tot += (1 - m_vector[k])
    model.add_abs_equality(tot, v)

solver = cp_model.CpSolver()
status = solver.solve(model)

if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print("Solvable :3")
    solution = solver.values(m_vector).values
    print(solution)
    flag = xor(vectors[0], solution.tolist())
    flag = [
        int(''.join(map(str,flag[i:i+8])), 2)
        for i in range(0, len(flag), 8)
    ]
    print(bytes(flag))
else:
    print("No solution found.")

PS C:\Users\Fwame\Desktop\malta\true_random> python3 .\solve.py
Computed products
Computed xors
Generated model vector
Solvable :3
[1 1 0 0 0 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 1 0 1 1 0 1 1 1 1 1 0 1 0 1 0
 0 0 1 1 1 1 1 1 0 0 1 0 1 1 1 1 1 0 1 0 1 1 0 0 0 1 1 1 1 0 0 0 0 1 1 0 1
 0 1 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 0 1 0 0 1 1 0 1 0 1 1 1 1 0 1 1 1 1 0 1
 1 1 0 0 0 0 1 1 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 1 0 0 1 1 0 0 1 1 0 0 0 1
 1 1 1 0 1 1 1 0 1 1 0 1 1 0 0 1 0 1 1 0 1 1 0 1 1 1 0 0 0 0 1 1 0 1 1 0 1
 1 1 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 0 1
 1 1 1 0 0 0 0 1 1 0 0 1 1 1 1 1 0 1 1 1 1 1 0 0 1 0 1 0 0 0 1 0 1 0]
b'maltactf{f55dc5132f9529106d6e:3}'