Google CTF 2019 (Quals) – Quantum Key Distribution

This years online qualification for the Google Capture The Flag finals (ctftime.org) ran from 22/06/2019, 00:01 UTC to 23/06/2019 23:59 UTC.

As last year, there were plenty of diversified challenges, which were worked out very well.

I tried to take at least a look at as much challenges as possible and solved the challenge Quantum Key Distribution, which was relatively easy based on the amounts of solves. Within this article I want to share my writeup on this challenge.

The writeup is divided into the following sections:

• Challenge description
• BB84 protocol
• Source code
• Outlined process
• Solution

Challenge description

The challenge description contains a very detailed explanation of what we are supposed to do as well as parts of the source code running on the server.

import random
import numpy

from math import sqrt
from flask import current_app

def rotate_45(qubit):
  return qubit * complex(0.707, -0.707)

def measure(rx_qubits, basis):
  measured_bits = ""
  for q, b in zip(rx_qubits, basis):
    if b == 'x':
      q = rotate_45(q)
    probability_zero = round(pow(q.real, 2), 1)
    probability_one = round(pow(q.imag, 2), 1)
    measured_bits += str(numpy.random.choice(numpy.arange(0, 2), p=[probability_zero, probability_one]))
  return measured_bits

def compare_bases_and_generate_key(tx_bases, rx_bases, measure):
  """Compares TX and RX bases and return the selected bits."""
  if not (len(tx_bases) == len(rx_bases) == len(measure)):
    return None, "tx_bases(%d), rx_bases(%d) and measure(%d) must have the same length." % (len(tx_bases), len(rx_bases), len(measure))
  ret = ''
  for bit, tx_base, rx_base in zip(measure, tx_bases, rx_bases):
    if tx_base == rx_base:
      ret += bit
  return ret, None

def unmarshal(qubits):
  return [complex(q['real'], q['imag']) for q in qubits]

# Receive user's qubits and basis, return the derived key and our basis.
def perform(rx_qubits, rx_basis):
  random.seed()
  # Multiply the amount of bits in the encryption key by 4 to obtain the amount of basis.
  sat_basis = [random.choice('+x') for _ in range(len(current_app.config['ENCRYPTION_KEY'])*16)]
  measured_bits = measure(unmarshal(rx_qubits), sat_basis)
  binary_key, err = compare_bases_and_generate_key(rx_basis, sat_basis, measured_bits)
  if err:
    return None, None, err
  # ENCRYPTION_KEY is in hex, so multiply by 4 to get the bit length.
  binary_key = binary_key[:len(current_app.config['ENCRYPTION_KEY'])*4]
  if len(binary_key) < (len(current_app.config['ENCRYPTION_KEY'])*4):
    return None, sat_basis, "not enough bits to create shared key: %d want: %d" % (len(binary_key), len(current_app.config['ENCRYPTION_KEY']))
  return binary_key, sat_basis, None

echo "404c368bf890dd10abc3f4209437fcbb" > /tmp/plain.key; xxd -r -p /tmp/plain.key > /tmp/enc.key

echo "U2FsdGVkX182ynnLNxv9RdNdB44BtwkjHJpTcsWU+NFj2RfQIOpHKYk1RX5i+jKO" | openssl enc -d -aes-256-cbc -pbkdf2 -md sha1 -base64 --pass file:/tmp/enc.key

U2FsdGVkX19OI2T2J9zJbjMrmI0YSTS+zJ7fnxu1YcGftgkeyVMMwa+NNMG6fGgjROM/hUvvUxUGhctU8fqH4titwti7HbwNMxFxfIR+lR4=

The most crucial aspects are:

• The challenge simulates a quantum key exchange using the BB84 protocol.
• The flag is encrypted and provided as a base64 encoded string.
• In order to decrypt the flag, an encryption key is required.
• This encryption key is encoded within the key shared through the quantum key exchange.

Since I didn’t know about the BB84 protocol, I started to read up on it before diving into the actual code.

BB84 protocol

There are quite a few good resources on the BB84 protocol. As usual, a good starting point is wikipedia. There is also a good video on YouTube, which is worth watching at least for the inventive visualization.

Despite of the plenty resources, let me shortly describe the protocol in the context of this challenge:

The BB84 protocol is used to exchange a secret key over a potentially insecure channel. The notable peculiarity is the way, how eavesdropping is prevented or rather detected. For comparison let’s consider the non quantum Diffie-Hellman (DH) key exchange. DH is based on the fact, that both parties posses a secret information, which is not directly transmitted. An attacker may eavesdrop on all transferred information, but is unable to derive the key without the secret information in a reasonable time. When using the BB84 quantum key exchange there is no secret information, which is not send over the insecure channel. Every information is transmitted. However an eavesdropper can actively be detected. This is rendered possible by the fact, that a part of the information is transferred using qubits and the state of a qubit is changed by reading or rather measuring it (the state of a qubit cannot be copied).

There are several ways to implement qubits physically, but for this challenge simulated photons are used, which are represented as imaginary numbers. The photon’s attribute used to encode the value of a qubit is its polarization. Basically a photon can be polarized vertically (0° degree) or horizontally (90° degree). In the implementation of this challenge a vertically polarized photon represents the bit value 1 and a horizontally polarized photon 0.

When a diagonal basis has been applied (we will get to basis shortly), the polarization will be rotated by 45° degrees before being measured. This means that a polarization of 315° degrees ends up as 0° degree (vertically polarized = bit value 1) and a polarization of 45° degrees is equal to 90° degrees after the rotation (horizontally polarized = bit value 0). In total this results in four possible states of polarization, which are represented by the corresponding imaginary number:

In order to share a secret key with Bob, Alice needs to create a qubit stream first. For each qubit of this stream she can choose between two basis: rectilinear (+) or diagonal (x). Let’s assume she chooses a rectilinear basis (+) for a qubit. This means that no rotation is made and if she wants to transmit the bit value 1, she will send a photon with a polarization of 0° degrees (0.0 + 1.0i). If she wants to transmit the bit value 0, she will send a photon with a polarization of 90° degrees (1.0 + 0.0i). On the other hand, if she chooses a diagonal basis (x), she would send a photon with a polarization of 315° degrees (-0.707 + 0.707i) to transmit the bit value 1 and a photon with a polarization of 45° degrees (0.707 + 0.707i) in order to transmit the bit value 0. The following tables shows these four possibilities:

In a real world application of the protocol, Bob could not know if the photon he receives was rotated or not. In other words, he does not know which basis Alice used. Thus he could only guess, if he needs to apply a rotation before measuring the photon or not. When Bob assumes the wrong basis, the outcome of the measured bit being zero or one is 50/50. This means that 50% of the measurements are wrong, if Bob assumed the wrong basis. As we will see later when analyzing the challenge’s source code, this characteristic of a real world photon is also true for the implementation using imaginary numbers.

In order to identify which measured bits are potentially wrong, Alice also sends the sequence of basis she used to Bob. By comparing this own basis with the ones Alice sent, Bob can discard the potentially wrong bits:

After Bob has sent the basis he used to Alice too, she can also determine, which bits have been correctly measured by Bob. These bits can now be used as a secret key (e.g. for a symmetric encryption algorithm).

Although it is not relevant for this challenge, let’s have a brief look at the concept of detecting a potential eavesdropper called Eve. For this it is important to know, that in a real application of the BB84 protocol Alice sends the qubit stream before sending the basis, she used. When intercepting the qubit stream Alice is sending, Eve needs to choose a basis for each qubit in order to measure it, before knowing which basis Alice used. If Eve chooses a wrong basis on a qubit, there is a 50% probability that the measured bit is false.

Based on her measured bit stream, Eve creates a qubit stream, which she sends to Bob. Because she probably did not use the exact same basis as Alice did, the measured bits of Eve contain wrong bits and thus the resulting qubit streams also differs from the one Alice sent. When Bob receives this qubit stream, he assumes a basis on his own and determines the measured bit for each qubit. Yet again, a few basis in Bob’s assumption differ from the ones Alice and Eve used.

In order to detect that Eve was eavesdropping on the qubit stream sent by Alice, Bob sends part of his measured bits as well as the corresponding basis he used to Alice. By verifying the values of the measured bits from Bob, on which he used the correct basis, Alice can determine if Eve eavesdropped on the transmission. These bits should match the original bit stream. If this is not the case, Eve is unveiled.

The following pictures illustrates the whole process:

After this illustration of the BB84 protocol in context of the challenge, let’s have a look at the provided implementation.

Source code

In the scenario explained in the description we (Alice) are supposed to send 512 qubits and basis to a satellite (Bob). As we already know, a qubit is represented by an imaginary number and a basis can either be + or x. The satellite responds with the 512 basis used by itself as well as an announcement, which is the shared key (the encryption key required to decrypt the flag is encoded in this key).

Based on the logical order, the first function being called is perform. The qubits and basis, which are sent to the server, are passed as arguments to this function:

# Receive user's qubits and basis, return the derived key and our basis.
def perform(rx_qubits, rx_basis):
  ...

At the beginning of the function the 512 basis of the satellite are generated randomly (+ or x):

  random.seed()
  # Multiply the amount of bits in the encryption key by 4 to obtain the amount of basis.
  sat_basis = [random.choice('+x') for _ in range(len(current_app.config['ENCRYPTION_KEY'])*16)]
  ...

After this the function measure is called passing the received qubits (rx_qubits) and the satellite’s basis (sat_basis):

  measured_bits = measure(unmarshal(rx_qubits), sat_basis)

This function iterates over the qubits and basis. If a basis is equal to x, the corresponding qubit is rotated by 45° degrees:

def measure(rx_qubits, basis):
  measured_bits = ""
  for q, b in zip(rx_qubits, basis):
    if b == 'x':
      q = rotate_45(q)
	...

A rotation is simply a multiplication with the imaginary number 0.707 - 0.707i:

def rotate_45(qubit):
  return qubit * complex(0.707, -0.707)

After the possible rotation the probabilities for the qubit being zero or one are calculated:

    probability_zero = round(pow(q.real, 2), 1)
    probability_one = round(pow(q.imag, 2), 1)

The two lines above are quite significant. The probability for a qubit being zero is calculated by raising the real part of the imaginary number to the power of two. Respectively the probability for a qubit being one is calculated by raising the imaginary part to the power of two. Let’s have a look at a few examples:

As we can see, the outcome of a measurement is well-defined for a rectangular imaginary number, since either the probability for the qubit being 1 is 100%, or the probability for it being 0 is 100%. On the other hand the probability for both cases is 50%, if the orientation of the imaginary number is diagonal. This only happens, if a wrong basis was assumed and thus matches the real world characteristic of a photon.

The next line of code simulates the actual measuring by generating a 0 or 1 randomly (based on the probabilities) and adding it to the bit stream stored in measured_bits:

    measured_bits += str(numpy.random.choice(numpy.arange(0, 2), p=[probability_zero, probability_one]))
  return measured_bits

Back in the perform function the function compare_bases_and_generate_key is called passing both basis as well as the measured bit stream:

  binary_key, err = compare_bases_and_generate_key(rx_basis, sat_basis, measured_bits)

This function simply compares both basis and discards all bits, whose basis are not equal:

def compare_bases_and_generate_key(tx_bases, rx_bases, measure):
  """Compares TX and RX bases and return the selected bits."""
  if not (len(tx_bases) == len(rx_bases) == len(measure)):
    return None, "tx_bases(%d), rx_bases(%d) and measure(%d) must have the same length." % (len(tx_bases), len(rx_bases), len(measure))
  ret = ''
  for bit, tx_base, rx_base in zip(measure, tx_bases, rx_bases):
    if tx_base == rx_base:
      ret += bit
  return ret, None

The last part within the function perform takes the amount of bits equal to the length of the shared key from the resulting bit stream stored in binary_key. These bits are actually the shared key:

  # ENCRYPTION_KEY is in hex, so multiply by 4 to get the bit length.
  binary_key = binary_key[:len(current_app.config['ENCRYPTION_KEY'])*4]
  if len(binary_key) < (len(current_app.config['ENCRYPTION_KEY'])*4):
    return None, sat_basis, "not enough bits to create shared key: %d want: %d" % (len(binary_key), len(current_app.config['ENCRYPTION_KEY']))
  return binary_key, sat_basis, None

Let’s shortly outline the whole process before we construct a solution.

Outlined process

Based on the source code the simulated quantum key exchange can be outlined as following:

1. We send a qubit stream (as well as the corresponding basis) to the satellite.
2. The satellite measures the qubits using his own basis.
3. The satellite discards all measured bits, on which it used a different basis than we did.
4. The resulting bit stream is cut to the length of the shared key and combined with the actual encryption key (this is not part of the source code but stated in the description).
5. This final bit stream is replied to us within the announcement field as well as the basis used by the satellite.

The following picture illustrates this process:

In order to encode the encryption key within the correctly measured bit stream, the assumption that XOR is used seemed likely. Since the satellite is sending us the shared key (announcement), we only need to know the correctly measured bits, in order to recover the encryption key:

encryption key = announcement ^ correctly measured bit stream

Keeping this in mind, let’s create the final solution.

Solution

According to our previous insights we would like to be sure about the result of the correctly measured bit stream, the satellite calculated.

In order to determine this bit stream, we can simply wait for the satellite to send us its used basis and then carry out the same calculations the satellite did. By comparing our own basis with the satellite’s basis we can discard the bits from the bit stream, on which the basis do not match. The result is the correctly measured bit stream.

An even easier approach would be to use a constant bit stream like 000000000000.... Although the satellite will choose a wrong basis for a few bits, the correctly measured bit stream can only contain bits with the value 0, since the original bit stream does not contain 1. XORing a constant bit stream of 0 with the encrypting key would result in.. the encryption key, because XORing a bit with 0 does not change it. Thus the announcement would exactly contain the encryption key.

So let’s try this by simply sending 512 qubits being 1.0 + 0.0i as well as 512 basis being +. This equals a bit stream of 000000000000...:

#!/usr/bin/env python

import requests

url = 'https://cryptoqkd.web.ctfcompetition.com/qkd/qubits'
j = {}
j['basis']  = 512 * ['+']
j['qubits'] = 512 * [{'real':1.0,'imag':0.0}]

r = requests.post(url, json=j)
print(r.text)

Running the script outputs the following error message:

root@kali:~/gctf19/qkd# ./firstApproach.py
{"error": "your random key is not random enough!"}

There seems to be yet another part of server side code, which is not provided. Obviously a filter is preventing us from directly echoing the encryption key.

So let’s try to send a constant bit stream of 1. This can be achieved by sending 512 qubits being 0.0 + 1.0i as well as 512 basis being +. This equals a bit stream of 111111111111...:

#!/usr/bin/env python

import requests

url = 'https://cryptoqkd.web.ctfcompetition.com/qkd/qubits'
j = {}
j['basis']  = 512 * ['+']
j['qubits'] = 512 * [{'real':0.0,'imag':1.0}]

r = requests.post(url, json=j)
print(r.text)

Now we actually get a valid response:

root@kali:~/gctf19/qkd# ./secondApproach.py
{"basis": ["x", "x", "x", "x", "+", "+", "+", ...], "announcement": "6b9300936261012ffddcc59593847c4e"}

As we already assumed, we have to XOR the shared key (announcement) with the measured bit stream to recover the encryption key. We also know that each bit of the measured bit stream is one. Thus we have to XOR the announcement with 111111111111... = 0xffffff...:

>>> shared_key = 0x6b9300936261012ffddcc59593847c4e
>>> mes_bitstr = 0xffffffffffffffffffffffffffffffff
>>> hex(shared_key ^ mes_bitstr)
'0x946cff6c9d9efed002233a6a6c7b83b1L'

Accordingly the encryption key is 946cff6c9d9efed002233a6a6c7b83b1. We can verify this by trying to decrypt the flag:

root@kali:~/gctf19/qkd# echo "946cff6c9d9efed002233a6a6c7b83b1" > /tmp/plain.key; xxd -r -p /tmp/plain.key > /tmp/enc.key
root@kali:~/gctf19/qkd# echo "U2FsdGVkX19OI2T2J9zJbjMrmI0YSTS+z..." | openssl enc -d -aes-256-cbc -pbkdf2 -md sha1 -base64 --pass file:/tmp/enc.key
CTF{you_performed_a_quantum_key_exchange_with_a_satellite}

Great, it worked! The flag is CTF{you_performed_a_quantum_key_exchange_with_a_satellite}.

For the sake of completeness let’s also implement the intended process by generating a random bit stream and calculating the correctly measured bits:

#!/usr/bin/env python

import requests
import json
import random

url = 'https://cryptoqkd.web.ctfcompetition.com/qkd/qubits'

j = {}
j['basis'] = []
j['qubits'] = []

# generate random bit stream
bit_stream = [random.choice('01') for i in range(512)]

# map bit stream to qubit stream
for bit in bit_stream:

  # generate random basis
  basis = random.choice('+x')
  j['basis'].append(basis)

  # determine qubit
  qubit = None
  if (bit == '1' and basis == '+'): qubit = {'real':0.0, 'imag':1.0}
  if (bit == '1' and basis == 'x'): qubit = {'real':-0.707, 'imag':0.707}
  if (bit == '0' and basis == '+'): qubit = {'real':1.0, 'imag':0.0}
  if (bit == '0' and basis == 'x'): qubit = {'real':0.707, 'imag':0.707}
  j['qubits'].append(qubit)

# send qubit stream and basis to satellite
resp = json.loads(requests.post(url, json=j).text)

# compare basis and determine correctly measured bits
bit_stream_correct = ''
for i in range(512):
  sat_base = resp['basis'][i]
  own_base = j['basis'][i]
  if (sat_base == own_base):
    bit_stream_correct += bit_stream[i]

# recover encryption key
shared_key = int(resp['announcement'], 16)
bit_stream_correct_cut = int(bit_stream_correct[:128], 2)
encrypt_key = shared_key ^ bit_stream_correct_cut

print(hex(encrypt_key))

Running this script also prints the encryption key:

root@kali:~/gctf19/qkd# ./qkd.py
0x946cff6c9d9efed002233a6a6c7b83b1L

That’s it. Really great challenge 🙂