The challenge is described as follows:

Generate a key using Quantum Key Distribution (QKD) algorithm and decrypt the flag.

We’re given an encrypted flag

U2FsdGVkX19OI2T2J9zJbjMrmI0YSTS+zJ7fnxu1YcGftgkeyVMMwa+NNMG6fGgjROM/hUvvUxUGhctU8fqH4titwti7HbwNMxFxfIR+lR4=

We’re told that the encryption key is being shared
by a simulated Quantum satellite implementing BB84.
We’re given a URL to which we can POST our “qubits and basis of measurement”
(we’re told we need to provide 512 qubits),
and then we can “derive the shared key” from the decoded response.
We’re also given the Python source code of the server.
Finally, we’re given an example of how to decrypt a message
given a shared key.
(See Appendix A for the full text of the challenge).

Analysis

The main difficulty in this challenge
is simply understanding the BB84 protocol
and the mapping between it and the pieces of information we were given.

BB84

Googling for “BB84 quantum” turns up a number of useful sources.
The one that we ultimately found most accessible was
Mart Haitjema’s Survey of the Prominent Quantum Key Distribution Protocols.

Very basically,
the idea is that Alice and Bob have two channels of communication between them:
one classical, and one quantum.
The classical channel is assumed to be public[^1].
The quantum channel is also assumed to be potentially public;
however, the protocol’s guarantee is that given the channel’s quantum nature,
Bob and Alice will be able to detect
if anyone has actually been eavesdropping on a given transmission.
Thus, after having communicated
a random string of bits
over this channel,
they can know whether it has been eavesdropped on.
Given a transmission which has not been seen by any other party,
they now have established a certain amount of shared bits
which are known only to them,
and which can now serve as a one-time pad
for encrypting the actual information they want to share,
allowing it to be shared
over the public, classical channel.

[^1]: To be precise,
we assume the public channel is subject to passive eavesdropping,
but not to active manipulation:
BB84 does not on its own defend against a MITM attacker.
The original paper briefly discusses this issue,
we will not go into it here.

How does transmission over the quantum channel work?
Each bit of information is encoded as a “qubit” (quantum bit)
which takes the form of a photon with a given polarization.
We define two “bases”
(see figure 1, taken from Haitjema’s survey):
the rectilinear basis, in which 0 is encoded by a polarization of 0 degrees and 1 is encoded by polarization 90;
and the diagonal basis, in which 0 is encoded by a polarization of 45 degrees and 1 by polarization of 135.

This is where quantum physics comes in to the story:
(quoting the original BB84 paper (PDF)🙂
“Although polarization is a continuous variable,
the uncertainty principle forbids measurements on any single photon
from revealing more than one bit about its polarization”.
Rather, measurements made using the diagonal basis
will only ever result in an observation of either 45 or 135 degree polarization.
Similarly, measurements made using the rectilinear basis
will only ever result in an observation of either 0 or 90 degree polarization.
The closer the actual polarization is to either of the measurement’s possible outcomes,
the higher the probability that that outcome will be observed.
So, if we measure a photon with polarization 45 using the diagonal basis,
there is a very high probability of actually observing 45 degrees,
thus allowing reliable transmission of the encoded 0 bit.
However, if we measure the same photon using the rectilinear basis,
we have equal chances of observing polarization of 0 or 90,
and thus the value of the decoded bit is essentially random.
Moreover, we will not even have gained any information
that would allow us to know
that we made the measurement using an incorrect basis.

With this knowledge, we can finally understand the details of the BB84 protocol:
In the first phase,
Alice chooses a random string of bits to be transmitted,
and for each bit also randomly chooses which basis to use for encoding it.
The resulting stream of photons makes up her transmission over the quantum channel.
At the receiving end,
Bob randomly chooses a basis for measuring each photon.
As we’ve seen,
wherever he chose the correct basis,
he will, with very high probability, decode the correct value for the bit.
Wherever he chose the incorrect basis,
he will get a random value for the bit.

In the second phase,
Bob and Alice share with each other
— over the insecure, classical channel —
their choices of basis for each bit.
They can now discard any bits at which their choice of basis disagreed.
For the remaining bits, though,
their observed values should agree,
and if so, they have established a secret of shared random bits.

Let’s consider for a moment what would happen
if Eve were eavesdropping on the quantum transmission:
During the transmission of the photons themselves
the correct basis is still known only to Alice
(it is only after Bob has made his measurements
that the choices of bases will be publicly shared).
Thus, Eve cannot know which basis to choose
for measuring any given photon.
This is the same position that Bob is in,
except that Eve is then retransmitting new photons
(encoding the values she has observed)
for Bob to receive, and upon receiving them
Bob goes through the same process again.
So, while in the absence of an eavesdropper,
Alice and Bob expect the values of their bits to match
for all of the bits for which they have chosen the same basis,
in the presence of an eavesdropper this will be much less:
for every bit for which Alice and Bob’s basis choice matched,
but Eve’s differed,
there is only a 50% chance of Alice and Bob’s values agreeing.

Thus, the final phase of the protocol
is for Alice and Bob to compare
a randomly chosen subset
of the “presumed shared” bit values:
if the actual rate of agreement is less than expected,
this indicates the presence of an eavesdropper.
Of course, the bits whose values are compared
(over the classical, public channel)
can no longer be used as key material
(they are no longer secret!),
but that merely requires adjusting the number of transmitted bits
such that enough key material will remain
after the comparison.
Moreover, the number of bits compared can be adjusted
to reach any desired level of confidence
in the secrecy of the transmission.

Mapping the protocol to the challenge

Now that we understand the BB84 protocol,
let’s see how the information we’re given in the challenge
maps to the protocol.

In the challenge,
an exchange is triggered by a POST performed by us.
The POST must include
(as described in How to send qubits)
a list of “qubits”
(each represented by the real and imaginary parts of a complex number)
and a “basis”
(represented by a list of ‘+’ or ‘x’ symbols,
‘+’ signifying the rectilinear basis, and ‘x’ — the diagonal basis).

We, being the initiators of the transmission, are Alice.
The list of qubits we send represents the stream of photons
encoding the random bits we have chosen.
Here, it helps to have prior familiarity
(from Math, Physics or Electrical Engineering studies, for example)
with the fact that complex numbers are often used to represent points on a circle
— in our case, the polarity of a photon —
with the real and imaginary parts representing the X and Y components, respectively.
The ‘basis’ list represents our choices of basis for encoding each of the bits.
(In sending both of these lists together
we have departed somewhat from the true protocol
— as we’ve seen, a vital part of the protocol
is that the sharing of the choice of basis
only be done after the receiving side has performed the measurements!
But hey, this is only a simulation…)

Bob — the server — receives our stream of photons,
and measures each one’s polarization using a randomly chosen basis:

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
.
.
.
sat_basis = [random.choice('+x')...
measured_bits = measure(unmarshal(rx_qubits), sat_basis)

Note that the basis passed into measure() is the satellite’s basis, not ours
(so indeed, our basis does not play a part in the first phase);
that the result of the measurement is always only a single bit 0 or 1,
with the actual polarization only determining the probability for each of those values.
At the end of this process,
Bob has a single bit (measured_bits) — the result of a measurement —
for each of the photons we sent.
This concludes the first phase of the protocol.

In the second phase Alice and Bob compare their bases to derive shared bits.
We’ve already sent our basis choices,
and only now does Bob make use of it,
precisely by keeping (in ret) only those bits for which
his choice of basis and our choice match:

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
.
.
.
  binary_key, err = compare_bases_and_generate_key(rx_basis, sat_basis, measured_bits)

Bob now has the resulting binary_key
(the shared bits, upon whose values we and he should agree).
But we don’t have the shared bits yet!

For that, we need to inspect the server’s response to our POST.
A sample response looks like so:

{"basis": ["+", "+", "x", "x", "+", "x", "+", "x", "x", "+", "x", "x", "x",
"+", "x", "+", "+", "x", "+", "x", "x", "x", "+", "+", "x", "+", "+", "x", "+",
. . .
"x", "+", "x", "+", "x", "+", "+", "+", "+", "+", "+", "x", "+", "+", "x", "+",
"x", "x", "+"], "announcement": "d748fe4acbb99b1c68f9d534371f80b7"}

We see that Bob has sent us his choice of basis.
By comparing it with our basis choices
we, too, can determine which bits of our transmission
to keep as the shared bits.
Now that both sides have the shared bits,
the second phase is complete.

The challenge doesn’t appear to have any analog for the third phase:
the code we’re given simply returns all of the matching bits as the shared key.
Again, this is only a simulation,
in which we don’t seem to be especially concerned
about detecting eavesdropping…

We are not given the code
showing what exactly the server does with the shared key.
However, there is one more piece of information in the response
that we haven’t yet used: the “announcement”.
It took us a while to realize
(more on that in the next section)
that this is actually the encrypted “flag key”,
itself encrypted using the one-time pad resulting from our shared bits.
Thus, simply xor’ing our shared bits with the announcement
results in a key,
which can then be used for decrypting the flag
using the procedure demonstrated in the example.

How we actually solved the challenge

We will not pretend that,
during the CTF itself,
we understood BB84
— or its correspondence to the challenge —
anywhere near as clearly as presented above.

Yes, we started out by reading up on the protocol,
and had a very basic understanding of the concepts involved.
But that’s about it.
For one thing,
we couldn’t even agree as to whether we were Alice or Bob!
Nor were we sure which parts of the communications in the challenge
represented the quantum channel,
and which represented the classical channel.
Indeed, we weren’t even sure
exactly which parts of the protocol
are transmitted over each of the channels!

So, this is where the hacker mindset kicks in:
We’re given a url to which we can POST,
and a description of what to POST,
so let’s just POST, and see what happens!
From there, the process was basically one of
jumping back and forth between the “theory” and the “practice”,
continually trying to narrow the gap (in our understanding) between them,
and figuring out how exactly they fit together.

Our first few attempts at POSTing a request weren’t too successful.
Being lazy, we figured that,
rather than actually start by choosing random qubits and basis,
we’d start with hardcoded values, like so:

import requests

basis = ['+'] * 512
qubits = [{'real':1, 'imag':1} for _ in range(512)]

data = {'basis':basis, 'qubits':qubits}

r = requests.post('https://cryptoqkd.web.ctfcompetition.com/qkd/qubits', json=data)
print(r.status_code)
r = r.content
print(r)

The response we got to this request was:

probabilities do not sum to 1

Hopefully,
after reading the previous sections
the problem is immediately evident.
At the time, however, it took as a while to realize
our mistake:
the point we were giving as the value of the qubit
had 1 as both the real and imaginary parts,
which means that the sum of probabilities is, indeed, greater than 1.
So we tried {'real':1, 'imag':0}, and now we got the response

your random key is not random enough!

Again, in retrospect,
it’s easy to see that
by having chosen the rectilinear basis and a value of 1+0i
( = 0 degrees — the number is entirely in the X component)
we were encoding a value of 0 for every bit,
and the server must be rejecting a key with too many zeros.
At the time, though,
everything still being pretty fuzzy in our minds,
we figured that perhaps the server didn’t like the fact
that the qubit values were “not complex enough”
(i.e., all in the real component)
and so we decided to give a mixed (but still hardcoded) value for all qubits,
only making sure this time that the sum of probabilities remained 1:

{'real':1/math.sqrt(2),'imag':1/math.sqrt(2)}

Aha! This finally gave a non-error response,
similar to the one shown previously,
containing basis and announcement.
For every request,
we get back a different, seemingly random,
basis and announcement.

We were not sure at this point how to interpret our results.
Were we supposed to collect many responses,
extracting some information from each,
until we could build up enough shared key material?
Or were we doing something wrong?

So again, back to the theory, trying to better understand what we had done.
Until we finally realized that
by sending polarization of 45 degrees
together with a rectilinear basis,
we had been sending the server a stream of photons
which it could only measure as random,
resulting in a random response!

Now we understood that with the rectilinear basis,
we need to be sending polarization of either 0 or 90 degrees.
So, if 0 degrees was “not random enough” for the server,
let’s try all 90 degrees!
(Again, laziness, to not have to start dealing with random choices…)
So we sent a request with hardcoded qubits all of 90 degrees,
and finally we started getting consistent results!
The returned basis was still changing randomly (as expected),
but the announcement was now constant:
6b9300936261012ffddcc59593847c4e.

Getting a constant value seemed like a step in the right direction,
however we still were not sure how to interpret it.
We tried using the returned value as the key for decrypting the flag,
but got nowhere.
After analyzing the situation,
we realized that the “shared bits” we were expecting should be all 1’s
(that’s what is encoded by 90 degrees in rectilinear).
We even ran the server code ourselves,
and confirmed that in fact the binary_key it was returning
was indeed all 1’s, given our input.
So where was the constant-but-not-all-1’s response
we were getting from the server
coming from?
Only after some more thinking did we finally realize
that the announcement must be
not the shared bits themselves,
but rather some further processing done by the server,
using those shared bits.
Such as… using the shared bits as a one-time pad
for encrypting the flag key…
So we xor’ed the announcement with our expected shared bits (all 1’s)
and tried using the result for decrypting the flag —
which resulted in

CTF{you_performed_a_quantum_key_exchange_with_a_satellite}.

Indeed…

Appendix A

What follows is a verbatim copy of the text provided at the time of the challenge.
The text was hosted at https://cryptoqkd.web.ctfcompetition.com/qkd/,
this is the base for the relative urls appearing in the text:

Challenge

We are simulating a Quantum satellite that can exchange keys using qubits implementing BB84.
You must POST the qubits and basis of measurement to /qkd/qubits and decode our satellite response,
you can then derive the shared key and decrypt the flag.
Send 512 qubits and basis to generate enough key bits.

This is the server’s code:

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

How to send qubits

POST your qubits in JSON format the following way:

• basis: List of ‘+’ and ‘x’ which represents the axis of measurement. Each basis measures one qubit:
  • +: Normal axis of measurement.
  • x: π/4 rotated axis of measurement.
• qubits: List of qubits represented by a dict containing the following keys:
  • real: The real part of the complex number (int or float).
  • imag: The imaginary part of the complex number (int or float).

The satellite responds:

• basis: List of ‘+’ and ‘x’ used by the satellite.
• announcement: Shared key (in hex), the encryption key is encoded within this key.

Example decryption with hex key 404c368bf890dd10abc3f4209437fcbb:

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

Flag (base64)

U2FsdGVkX19OI2T2J9zJbjMrmI0YSTS+zJ7fnxu1YcGftgkeyVMMwa+NNMG6fGgjROM/hUvvUxUGhctU8fqH4titwti7HbwNMxFxfIR+lR4=