Tokyo Network - zer0pts CTF 2021

tags: zer0pts CTF 2021 misc

Challenge

Googling the challenge description, you can find the challenge is about Quantum Key Distribution. The distributed Python file implements a basic BB84 protocol with quantum error correction.
Be noted that the implemented scheme is not "very-secure" from the perspective of eavesdropping. In real cases, we should correct the error at the end of the protocol using Calderbank-Shor-Steane code, for example.

Error Correction

Every quantum bit is exntended to 9-bit and the state is updated by the following circuit:

CNOT 0,3; CNOT 0,6;
H 0; H 3; H 6;
CNOT 0,1; CNOT 0,2;
CNOT 3,4; CNOT 3,5;
CNOT 6,7; CNOT 6,8;

This circuit is the encoding part of the Shor code. One of the bits may cause error but we can fix it thanks to the Shor code.

noise = QuantumCircuit(9)
idx = random.randrange(0, 9)
noise.add_gate(DephasingNoise(idx, 0.31337))
noise.add_gate(DepolarizingNoise(idx, 0.31337))
noise.add_gate(BitFlipNoise(idx, 0.31337))
noise.update_quantum_state(q)

The Shor code is very strong in the point that it can fix not only bit-flipping error but also phasing error. It can fix not only discrete error but also continuous error. (This is a generic feature of the quantum error correction.)

The decoder requires the Toffoli gate and we need to write it using the given gates. We only use CNOT, H, T, Tdag for this.

Now, we can write the decoder:

CNOT 0,2; CNOT 0,1;
CNOT 3,5; CNOT 3,4;
CNOT 6,8; CNOT 6,7;
H 0; CNOT 1,0; Tdag 0; CNOT 2,0; T 0; CNOT 1,0; Tdag 0; CNOT 2,0; T 0; H 0; T 1; CNOT 2,1; Tdag 1; T 2; CNOT 2,1;
H 3; CNOT 4,3; Tdag 3; CNOT 5,3; T 3; CNOT 4,3; Tdag 3; CNOT 5,3; T 3; H 3; T 4; CNOT 5,4; Tdag 4; T 5; CNOT 5,4;
H 6; CNOT 7,6; Tdag 6; CNOT 8,6; T 6; CNOT 7,6; Tdag 6; CNOT 8,6; T 6; H 6; T 7; CNOT 8,7; Tdag 7; T 8; CNOT 8,7;
H 0; H 3; H 6;
CNOT 0,6; CNOT 0,3;
H 0; CNOT 3,0; Tdag 0; CNOT 6,0; T 0; CNOT 3,0; Tdag 0; CNOT 6,0; T 0; H 0; T 3; CNOT 6,3; Tdag 3; T 6; CNOT 6,3;

Key Distribution

In BB84 protocol, we use the following 4 basis:

$$|0⟩,|1⟩,|+⟩=\frac{1}{\sqrt{2}}(|0⟩+|1⟩),|-⟩=\frac{1}{\sqrt{2}}(|0⟩-|1⟩)$$

$\{|0⟩,|1⟩\}$ and

$\{|+⟩,|-⟩\}$ are called Z-basis and X-basis respectively.
The following steps describe the procotol:

1. Alice chooses a quantum bit
   $a=0,1$ randomly. Alice also chooses X-basis with the probability
   $p$, otherwise Z-basis. If X-basis is chosen, she prepares a qubit
   $|\overline{a}⟩$, otherwise
   $|a⟩$. She sends this quantum bit to Bob.
2. Bob chooses X-basis with the probability
   $p$, otherwise Z-basis. If X-basis is chosen, he observes the state by X-measurement, otherwise by Z-measurement.
3. Alice and Bob disclose the basis they used.
4. Repeat step 1 to 3 for
   $N(1+2\xi +2\sqrt{\xi (1+\xi )}+{\xi }^{\prime })$
5. Count the number of the events
   $N_x$ that Alice and Bob chose X-basis. Also, count the number of the events
   $N_z$ that both of them chose Z-basis. If
   $N_x<N\xi$ or
   $N_z-N<N\xi$, then quit the communication.
6. For the events that both Alice and Bob chose X-basis, Alice tells Bob her original bits. Bob checks how much bits matches and if the error rate is larger than
   ${\delta }_x-ϵ$, they quit the communication.
7. For the events that both Alice and Bob chose Z-basis, Alice picks up
   $N_z-N$ events and tells Bob her original bits. Bob checks the error rate and if it's larger than
   ${\delta }_z-ϵ$, they quit the communication.
8. The remaining
   $N$-bits Alice doesn't disclose so far, becomes the key.

Since Alice sometimes sends X-basis, it's impossible for Eve to distinguish the quantum state. Also, she can't copy the state thanks to the no-cloning theorem. Step 6 and 7 ensures that nobody eavesdropped their communication.

In real cases, the last

$N$-bits may contain some quantum error. They use quantum error correction technique such as CSS code to fix the error without letting Eve know the key.

Solution

Since this is a misc challenge, there's nothing specifial but to implement the protocol.

import random
import base64
from Crypto.Cipher import AES
from ptrlib import *

decoder = """
CNOT 0,2; CNOT 0,1;
CNOT 3,5; CNOT 3,4;
CNOT 6,8; CNOT 6,7;
H 0; CNOT 1,0; Tdag 0; CNOT 2,0; T 0; CNOT 1,0; Tdag 0; CNOT 2,0; T 0; H 0; T 1; CNOT 2,1; Tdag 1; T 2; CNOT 2,1;
H 3; CNOT 4,3; Tdag 3; CNOT 5,3; T 3; CNOT 4,3; Tdag 3; CNOT 5,3; T 3; H 3; T 4; CNOT 5,4; Tdag 4; T 5; CNOT 5,4;
H 6; CNOT 7,6; Tdag 6; CNOT 8,6; T 6; CNOT 7,6; Tdag 6; CNOT 8,6; T 6; H 6; T 7; CNOT 8,7; Tdag 7; T 8; CNOT 8,7;
H 0; H 3; H 6;
CNOT 0,6; CNOT 0,3;
H 0; CNOT 3,0; Tdag 0; CNOT 6,0; T 0; CNOT 3,0; Tdag 0; CNOT 6,0; T 0; H 0; T 3; CNOT 6,3; Tdag 3; T 6; CNOT 6,3;
""".replace("\n", "")

N = 128
xi, xip = 0.98, 0.98
p = (xi * (1 + xi))**0.5 - xi
Np = int(N * (1 + 2*xi + 2*(xi*(1+xi))**0.5 + xip))

#sock = Process(["python", "server.py"], cwd='../challenge')
sock = Socket("localhost", 11099)

bb = 0
for i in range(Np):
    bb <<= 1
    if random.choices([1, 0], [p, 1-p])[0] == 1:
        sock.sendlineafter("Circuit: ", decoder + "H 0;")
        bb |= 1
    else:
        sock.sendlineafter("Circuit: ", decoder)

rb = int(sock.recvlineafter("state: "), 2)
sock.sendlineafter("bb = ", bin(bb))

# We don't use these values now but they are necessary in the real world
# because we need to know how much quantum error happened.
# They are used to ensure nobody sniffed the network.
ba = int(sock.recvlineafter("ba = "), 2)
xa = int(sock.recvlineafter("xa = "), 2)

xb = 0
for i in range(Np):
    if (ba >> i) & 1 == (bb >> i) & 1 == 1:
        xb = (xb << 1) | ((rb >> i) & 1)
print(f"[+] xa = {bin(xa)}")
print(f"[+] xb = {bin(xb)}")

l = []
for i in range(Np):
    if (ba >> i) & 1 == (bb >> i) & 1 == 0:
        l.append(i)
m = int(sock.recvlineafter("m = "), 2)
for i in range(Np):
    if (m >> i) & 1:
        l.remove(i)

k = 0
for i in sorted(l):
    k = (k << 1) | ((rb >> i) & 1)

data = base64.b64decode(sock.recvlineafter(": "))
iv = data[:16]
ct = data[16:]

key = int.to_bytes(k, N // 8, 'big')
cipher = AES.new(key, AES.MODE_CBC, iv)
print(cipher.decrypt(ct))

sock.interactive()

In this challenge, I used Shor code for the quantum error correction. However, it's controversial to use Shor code for some security reasons. I'm not good at this field enough to prove the security but at least the probability that Eve may eavesdrop the bit without causing error gets higher.

Actually I was planning to prepare a challenge to eavesdrop the key but we had enough crypto challenges already.