DEF CON Quals CTF 2021: the CHSH Game, Entangled qubits, and Decrypting the Flag

On the first weekend of May, our team from CUJO AI Labs participated in the DEF CON CTF 2021 QUALS. Although we didn’t qualify for DEF CON CTF, we really enjoyed the two days of hacking and are proud to have made it into the top 50 on our first attempt. Below, we share our solution to one of the challenges, which turned out to be a solution for two. Get ready for some quantum computation fun!

The source code and description of the challenges can be found here:

• https://github.com/o-o-overflow/dc2021q-qoo-or-ooo-public
• https://github.com/o-o-overflow/dc2021q-back-to-qoo-public

Both challenges start as the same game, and the only difference between the two is that the second one has more rounds in the game. The qoo-or-ooo challenge could be solved by simple brute-force, but back-to-qoo could not. This means that everyone solving qoo-or-ooo the intended way got a “free flag” on back-to-qoo.

Luckily, our solution for qoo-or-ooo worked for back-to-qoo as well, and we will explain how below.

The Challenges: Playing the Game

The first step of these challenges was a game. In it, we were playing together with Zardus to beat our opponents. We both received a bit from our competitors. The goal was to choose our bits so that the multiplication of the competitors’ bits was equal to the sum of our bits. Multiplication here means a binary AND, while the sum is XOR.

When we set our bet, we could choose not only 0 or 1, as we have a third option, a magic qoin. Looking at the attached python scripts, we found that the magic qoin is a qubit.

The qubit

A qubit (quantum bit) is a unit of quantum information. While a classical bit can be in two states, 0 or 1, a qubit can be in a superposition of both.

Once the qubit is measured, it will be in state |0⟩ with probability | |² and in |1⟩ with probability | |². After the measurement, it will be in the measured state, meaning every further measurement will give the same result. The result of the measurement depends on the basis in which the qubit was measured (the basis is |0⟩ and |1⟩ in the example above).

If we choose the magic qoin, we get a second question whether we want to rotate it or not. Looking at coin.py, we see that after the rotation, the qubit will be measured. Once the qubit is measured, it will take the value 0 or 1.

The CHSH inequality

In the service.py file, we found that our winning rate has to be over 85% to receive additional information from the server.

The game is the so-called CHSH game, based on the CHSH inequality from 1969 – named after John Clauser, Michael Horne, Abner Shimony, and Richard Holt. We can find an implementation of the game here: https://tqsd.github.io/QuNetSim/examples/chsh.html. In this example, we play the role of Bob. This game nicely demonstrates how the quantum strategy can be much more successful than the classical version.

In the classical version, where the players don’t have a quantum coin (qoin), they can achieve a win rate of 75% by always choosing the same bit (either 0 or 1). However, with the quantum strategy, we can increase this rate to 85%.

To achieve 85%, the players must share a set of entangled pairs of qubits among themselves in advance and measure their qubits according to a predefined strategy based on the competitors’ bets.

In quantum physics, entangled particles are connected. Their quantum states cannot be described independently, and measuring one affects its pair even if they are at a great distance from each other. For example, they can be connected in a way that if we measure them in the same basis, they will always give the same result. Superposition is basis-dependent, meaning that the probability of the qubit collapsing to one or the other value after measuring depends on the basis. To increase the win rate, players have to choose their measurement basis in a smart way.

 

 

Using the quantum strategy

If Zardus’ competitor bets on 1 and Zardus’s bets on 0 after measuring his qubit, and if our competitor bets on 0, we can win by choosing 0, while we have to choose 1 if he bets on 1.

Using the rotation options, we can maximize the probability of getting the right bit after measurement. Since we have an entangled pair of qubits with Zardus, his measurements affect our qubit. By choosing the appropriate rotation, we will measure our qubit in a basis where the probability of getting the bit needed to win the game is 85%.

To win the game, we always select the magic qoin, which means choosing a qubit instead of the classical bits. Then, if our competitor bets on 1, we rotate right; if it bets on 0, we rotate left. This strategy always wins the game with at least an 85% success rate.
Mathematical details can be found here for those who are interested: The_CHSH_game_as_a_Bell_test_thought_experiment.pdf.

After the Game: the BB84 Protocol and Decrypting the Flag

Upon winning the game, a chat between Zardus and Adamd occurs. The implementation can be found in the players.py handout file, under each players’ class respectively. Looking at the implementation, we can see that a quantum key distribution, the B884 protocol, is happening between Zardus and Adamd. They create a shared secret key, which Adamd uses to encrypt the flag.

During the BB84 protocol, the participants communicate through a public channel. The security of the key generation relies on the fact that the basis is not known for an eavesdropper and on two properties of qubits. The first one is the result of the no-cloning theorem, which says that it is impossible for an eavesdropper to copy the transferred qubits. The second one is that measuring a qubit by a third party is detectable.

The algorithm, in a nutshell, is the following:

• Alice sends a sequence of qubits
• Bob chooses a measurement basis for each, measures the qubit, and sends 0 or 1 based on which basis he chose
• Alice sends Bob the information if they chose the same basis or not
• They both keep those bits where they used the same basis. This will be their shared key.

Let’s go back to our challenge.

For each round, Adamd and Zardus exchange a sequence of messages:

Zardus sends a qubit to Adamd; in return, Adamd sends his measurement basis (0 or 1), and finally, Zardus sends 0 if he used the same basis to measure the qubit and 1 if he used a different basis. From this communication, we can see Adamd’s messages.

The last two lines leaked by Zardus contain the cryptographic nonce and ciphertext, respectively. All that’s left is to reconstruct the key based on our recorded and the leaked data, and we can decrypt the flag.

From game.py and players.py, we can see that Zardus’ basis bits are the bets of his competitor. The bits of the shared key are built from Zardus’ bets, choosing those where Adamd’s basis is the same as Zardus’ basis. Based on the game’s formula, we can know what Zardus’ bet was for each round, since we know: our bet, our competitor’s bit, and Zardus competitor’s bit. From here, we can learn Zardus’ bet:

(our competitor's bit * Z’s competitor's bit) ^ our bet

if we won that specific round and the opposite if we lost.

Now we have every piece of information required to build the key. For each round, we compare Adamd’s measurement basis with Zardus’ competitor’s bit. If they match, we append Zardus’ bet to the key.

Once we have the key, we can decrypt the flag with a simple AES algorithm.

Our script can be found here: https://github.com/getCUJO/ThreatIntel/blob/master/Scripts/DEFCON-CTF-Q-2021/solve.py

The write-up and script was created by Dorka Palotay and Marton Bak.

Interested in other CTF solutions? See our solutions for the FIRST SecLounge CTF 2020 that got our team the best score among 273 participants.