Experiments to protect against harvest now, decrypt later

Quantum computing needs thousands of qubits to crack the public key encryption we currently rely on and at present the largest (publicly announced) quantum computer only has 433 qubits. The sales pitch for protecting against quantum attacks now is that baddies could be quietly harvesting encrypted data, so that when quantum computers are ready, off they go and decrypt.

There are two main approaches to protect against quantum attacks.

One approach, quantum encryption key distribution (QKD), can be implemented one qubit at a time, e.g., by sending photons along fibre optic cables. Each photon is a realisation of a qubit. HSBC is trialling a QKD approach developed by BT and Toshiba, which builds on BB84 from forty years ago. I’ve attempted to explain BB84 in a previous blog post.

Vodafone has opted for a non-quantum approach to defend against attacks on crypto by trialling new public key encryption algorithms, on classical computers, that are thought to be quantum-safe: post-quantum cryptography (PQC).

The next major revision of Google Chrome will include a hybrid approach combining X25519 , a standard method already used by Chrome and others browsers, with Kyber-768, a PQC method that has so far resisted attack.

Since PQC methods are new, the hybrid approach offers protection while the maths continues to be stress-tested. This is important since there has already beenΒ an embarrassingly quick crack of a supposedly quantum-safe approach.

Privacy implications of hashing data, by John Cook

Cryptographic hash functions are sometimes used to create pseudo IDs from identifiable info like NHS numbers. An advantage of this approach is that two sites that have no way to communicate with each other will generate the same pseudo ID, allowing data to be linked. A disadvantage is that, although in general hashes are impossible to inverse, a rainbow table lookup attack can be used to inverse the hash when the space of inputs is relatively small, as is the case for ID numbers. John Cook explores.

IBM unveils a 433-qubit quantum computer

IBM has today unveiled a 433-qubit quantum processor – progress in the field is accelerating.

One of the example uses of quantum computers is prime factorisation, which they can do much faster than can classical computers. One reason this is of interest is that the security of public key encryption – used everywhere on the net, from LinkedIn to banks – depends on the computational difficulty of prime factorisation.

To break a 2048-bit RSA public key would take trillions of years on a classical computer. A paper published last year argued that a 2048-bit RSA public key could be cracked in 8 hours on a quantum computer. However, that would require 20,000,000 qubits – rather more than the 433 announced today. So, our secrets seem to be safe for a while yet.

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 (e.g., Bob is able to detect polarised photons sent by Alice from a satellite) and a two-way unsecure classical channel (e.g., 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 allows 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 had been 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 the key and retransmit 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 Alice uses to send each bit of the key. The figure below (from Mayers, 2001) shows the bases in state space.

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}\), the Hadamard gate.

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 gate before measuring. The possible outcomes in the absence of eavesdropping 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, with a 50-50 chance of a 1 or 0.

Bob tells Alice via the unsecure channel the sequence of bases he used. 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 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: either they will be missing or Eve will have had to replace them with a random bit.

If Alice and Bob are satisfied that the test qubits made it across okay without being intercepted, 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; while taking account of errors in transmission that will mean qubits don’t arrive intact for innocent reasons other than eavesdropping.

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==" |>
  Β  Β  Β  Β  Β         base64enc::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) |>
  base64enc::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:

But why is the key c6b5ca01? It’s not obviously the letters G, C, H, Q. In decimal, it looks like an IP address, but there’s nothing obvious at 198.181.202.1, and any four 8 bit numbers look like an IP address if you stare long enough.

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.”