Quantum key distribution using BB84

Suppose Alice has a secret message she wants to send to Bob. They have two information channels: a quantum channel (such as a stream of photons) and an unsecure classical channel (such as unencrypted email). Let’s assume that the message and key are both encoded using binary and the key is a one-time pad. They will eventually XOR message and key to encrypt and decrypt the message.

BB84 (Bennett & Brassard, 1984) is an approach to quantum key distribution that makes it possible for Alice to send an encryption key to Bob and for them to verify with a high level of confidence that the key hasn’t been intercepted. Once convinced that the key was sent securely, Alice can use it to encrypt the secret message and send it over the unsecure classical channel. Bob safely decrypts at the other side.

BB84 takes advantages of three related features of quantum mechanics.

  1. If a qubit is in superposition, e.g., \(\frac{|0\rangle + |1\rangle}{\sqrt{2}}\), then it’s impossible to infer its state from one observation. In particular, suppose an eavesdropper, Eve, measured the qubit and observed \(|1\rangle\). She couldn’t tell whether it was in the state \(\frac{|0\rangle + |1\rangle}{\sqrt{2}}\) or \(|1\rangle\).
  2. Once you measure a qubit in superposition, it collapses to a basis state, so Eve couldn’t intercept it and forward it onto Bob.
  3. You also can’t clone a qubit that is in an unknown state so, e.g., Eve couldn’t intercept a qubit from Alice, clone it, measure one of the pair and pass the other unmeasured qubit onto Bob.

Here’s how BB84 works.

Alice begins by generating a stream of random bits:

110110100110000101110…

Some of these bits will be used for the key.

Next, she generates a random stream of bases, classical basis (\(+\)) or the Hadamard basis (\(\times\)):

\(+\)\(\times\)\(+\)\(+\)\(\times\)\(+\)\(\times\)\(+\)\(\times\)\(\times\)\(+\)\(\times\)\(\times\)\(+\)\(\times\)\(+\)\(\times\)\(\times\)\(+\)\(\times\)\(+\)…

These will determine which basis will be used to send each bit of the key. The figure below shows how Alice will encode the 1s and 0s on these bases (Mayers, 2001).

For a photon, the classical basis corresponds to vertical/horizontal polarisation and the Hadamard basis to the diagonal polarisations. Note in this case the state space corresponds nicely with the physical realisation of the qubit; that won’t always be the case, e.g., consider spin up and down states for electrons.

Here are the qubit states Alice sends:

\(\Psi(0, +) = |0\rangle\)

\(\Psi(1, +) = |1\rangle\)

\(\displaystyle \Psi(0, \times) = H|0\rangle = \frac{|0\rangle + |1\rangle}{\sqrt{2}}\)

\(\displaystyle \Psi(1, \times) = H|1\rangle = \frac{|0\rangle -|1\rangle}{\sqrt{2}}\)

Where \(\displaystyle H = \frac{1}{\sqrt2} \begin{bmatrix}1 & 1\\1 & -1\end{bmatrix}\).

Alice sends the potential key bits using the randomly chosen bases.

Bob measures them, randomly deciding whether to assume a classical or Hadamard basis – for the latter applying the Hadamard operator before measuring. The possible outcomes are as follows:

Alice sends Bob assumes classical Bob assumes Hadamard
\(\Psi(0, +) = |0\rangle\) \(P(|0\rangle) = 1\) \(P(|0\rangle) = \frac{1}{2}\)
\(\Psi(1, +) = |1\rangle\) \(P(|1\rangle) = 1\) \(P(|1\rangle) = \frac{1}{2}\)
\(\Psi(0, \times) = H|0\rangle\) \(P(|0\rangle) = \frac{1}{2}\) \(P(|0\rangle) = 1\)
\(\Psi(1, \times) = H|1\rangle\) \(P(|1\rangle) = \frac{1}{2}\) \(P(|1\rangle) = 1\)

So if Bob randomly chooses the correct basis, he gets the correct bit; if not, he gets a random bit, 50-50 1 or 0.

Bob tells Alice what bases he used on the unsecure channel. At this point, doing so doesn’t help any eavesdroppers since the qubits have already been measured.

Alice tells Bob which bases were correct, again on the unsecure channel, so Bob can discard measurements for the rest. She also sacrifices a random sample of the potential key bits by sharing what the right answer is for those. If Eve the eavesdropper intercepted any, then they won’t all have made it to Bob.

If Alice and Bob are satisfied that the test qubits made it across okay, then they use the remainder for the key, sending the encrypted message through the unsecure channel.

That’s the gist. The devil’s in the detail, e.g., working out how many bits to send to ensure enough remain after checking for intercepts; how many to sacrifice to check that Eve wasn’t eavesdropping; and taking account of errors in transmission.

The security of BB84 depends on the quality of the implementation. The field of quantum hacking explores a variety of ways to exploit imperfections, e.g., classical side channels that leak information about what was sent, which can be intercepted without interfering with the qubit. Researchers devise clever ways to defend against these attacks. See, e.g., Dixon et al. (2017).

References

Bennett, C. H. & Brassard, G. (1984). Quantum cryptography: Public key distribution and coin tossing. Proceedings of IEEE International Conference on Computers, Systems, and Signal Processing (pp. 175-179), India.

Dixon, A. R., Dynes, J. F., Lucamarini, M., Fröhlich, B., Sharpe, A. W., Plews, A., Tam, W., Yuan, Z. L., Tanizawa, Y., Sato, H., Kawamura, S., Fujiwara, M., Sasaki, M., & Shields, A. J. (2017). Quantum key distribution with hacking countermeasures and long term field trial. Scientific Reports, 7, 1978.

Mayers, D. (2001). Unconditional security in quantum cryptography. Journal of the ACM, 48, 351–406.

XOR encryption

GCHQ recently posted the following JavaScript code on its Instagram and Twitter accounts:

The code contains two messages. The first is represented as a simple numerical encoding. The second is a secret message that has been encrypted, alongside code for decrypting it. Here are some clues to make sense of how this second message has been encrypted.

The message uses a symmetric-key encryption approach, the XOR cipher, that involves applying the exclusive or (XOR) operator to each letter of the message and the key, recycling the key until all characters have been decoded. The secret message is wrapped up in a Base64 encoding, which is a way of ensuring that all its characters are printable letters and symbols, so it’s possible to include the message within the JavaScript as “gNSkYr+VqyGl1Lhko8fqYq7UpGajiuo67w==”.

Here’s a shorter version of the code in R:

gchq_message <- "gNSkYr+VqyGl1Lhko8fqYq7UpGajiuo67w==" |>
                   base64decode()
gchq_key <- c(0xc6, 0xb5, 0xca, 0x01) |> as.raw()
xor(gchq_message, gchq_key) |> rawToChar()

(No spoilers here…)

So, the steps to decrypt are:

  1. Translate the Base64 encoded message to raw bytes
  2. XOR those raw bytes with the key
  3. Translate the bytes to ASCII characters so we can read the message

The nice thing about this form of encryption is that the same algorithm does both encrypting and decrypting. So, if you wanted to reply, “No thanks, I’m good” you just do the same in reverse:

  1. Translate your ASCII text message to raw bytes
  2. XOR those bytes with the key
  3. Translate the result to Base64

In R:

"No thanks, I'm good" |>
  charToRaw() |>
  xor(gchq_key) |>
  base64encode()

This gives “iNrqda7UpGq1mepI4djqZqnarg==”.

Fun! Also, I have a tattoo that uses the same approach, except I used Braille ASCII instead of Base64 to ensure that all the characters were tattooable 🙂

If you’re watching The Undeclared War, look out for the shout out to Base64 too:

Solomon Kullback: Oral History Interview

Read about Kullback on Wikipedia.

The oral history is on the NSA website over here.

Loads of cryptanalysis anecdotes therein (if you’re into that kinda thing), e.g., (p. 119):

There used to be coke machines, the Army version of the coke machines, I guess. You put in a nickel and a cup would come and you would get a coke. Well, it wasn’t long before the people discovered that the machine, when you dropped a coin in, would turn on. But if you pull the plug out, the mechanism which turned it off failed to operate. So people would go in there and put in their nickel and get a cup, pull the plug out and everybody in the wing would go get their cup of coke. So after a while, the vendor who filled these machines sort of looked at it and began to complain to General Corderman about the fact that here is a machine at the end of a day, all of the cokes and so on were used up and gone but he only finds a couple of nickels in it. “What gives?” I guess eventually Corderman checked and found out about the fact that people had found out that if you pull the plug once the machine got started then the mechanism which shut it off would fail. So he sent out a very cute notice to everybody in the Arlington Hall Station. It said, “Now that we have solved the machine and have enjoyed some of the fruits of that solution, I think we ought to provide the vendor with a nickel for each cup of coca cola.”