Fake Medallion – PlaidCTF 2021

by goulov and ice and mandlebro

Points: 420 (4 solves)

Given: Medallions are tokens for games at our carnival, selling at $1000 each. Our system makes sure that you cannot forge your own. Can you win some money at the carnival?

fake.medallion.pwni.ng 15215, 15214, 15213, 15212, 15211, 15210

fake-medallion.535079809a4644a52ec5721be7e49868cd8e386c844851a58da53b5a345ebc13.tgz

tldr

  1. The protocol resembles the Quantum Money scheme, where we are given 30 random qubits (a medallion) from \(\{\left\vert 0\right>, \left\vert 1\right>, \left\vert +\right>, \left\vert -\right>\}\), and are asked to clone them and sell 15 medallions.

  2. The bases and values of the qubits are generated with the Python Mersenne Twister PRNG with the outputs truncated, which is insecure. But recovering the internal state still requires us to clone the 30 qubits once, to get enough bits.

  3. Construct a circuit to clone a qubit with high enough fidelity \((5/6)\), such that we can successfully duplicate the money once, allowing us to break the PRNG and predict with certainty how the next medallions will be prepared, giving us infinite money and winning the game.

breaking the truncated Mersenne Twister

Assume we have enough money to exchange medallions 624 times using the med_for_med option, which costs $1. Everytime we exchange a medallion for another medallion, the server leaks the full quantum state of the previous medallion:

...
return {'msg': f"New medallion {new_id} created. " +
                "Your old one was " +
                old_medallion +                      #HERE
                ". That one is now invalid."}

The state will look something like 011-1100++-000++--0+0-0++--11-, which we can decode by inverting the get_medallion function:

def get_res(qubits):
    '''
        Inverse of get_medallion function
    '''
    bits = ''
    bases = ''
    for i in qubits:
        if i == '0':
            bits += '0'
            bases += '0'
        elif i == '1':
            bits += '1'
            bases += '0'
        elif i == '+':
            bits += '0'
            bases += '1'
        elif i == '-':
            bits += '1'
            bases += '1'
    return bits[::-1], bases[::-1]

This will give us the random numbers bits and bases that were generated for that medallion. It’s now well known in the CTF world that if you have 624 consecutive outputs from the Python builtin random generator, you can learn its internal state and predict all “random numbers” that may come next. What may not be so well known is that even if those outputs are partially truncated, you can still find the internal state, given enough additional numbers. To our knowledge, there aren’t many tools online that let you crack Python’s random with truncated output.

So we went ahead and modeled the Mersenne Twister algorithm (MT19937) as a Z3 program:

def symbolic_twist(self, MT, n=624, \
  upper_mask=0x80000000, lower_mask=0x7FFFFFFF, a=0x9908B0DF, m=397):
    for i in range(n):
        x = (MT[i] & upper_mask) + (MT[(i+1) % n] & lower_mask)
        xA = LShR(x, 1)
        xB = If(x & 1 == 0, xA, xA ^ a)
        MT[i] = MT[(i + m) % n] ^ xB
    return MT

And implemented a program that given partial outputs from getrandbits, recovers a valid internal state using Z3 SMT solver. You can find it here.

ut = Untwister()

for i in range(624):
    out = interact(p, {'option': 'med_for_med', 'med_id': med_id})
    med_id = out['msg'].split(' ')[2]
    old_med = out['msg'].split(' ')[-6][:-1]
    bits, bases = get_res(old_med)

    ut.submit(bases + '??') #2 unknown bits because getrandbits(30) truncated 2 lsbs
    ut.submit(bits + '??')

#Obtain cloned random
r = ut.get_random()

bases = r.getrandbits(NUM_QUBITS) #predict bases
bits = r.getrandbits(NUM_QUBITS)  #predict bits

So, we have to exchange a medallion for another medallion 624 times, but we only have $23 after buying the first medallion. If only we could sell a medallion twice…

(almost) cloning a qubit

From here on we’ll assume you have a little knowledge of Quantum Physics/Computation.

The protocol in this challenge looks heavily based on the Quantum Money protocol, which holds on the fact that arbitrary quantum states cannot be perfectly copied (known as the No-cloning theorem) to devise a test which will fail if one tries to duplicate the money (i.e. clone the qubits). Intuitively what’s happening is: some entity, let’s call it the bank, creates the money (i.e. prepares the qubits) and keeps a record of its properties (i.e. its state). Then, if you try to clone the money (read qubits) you’re going to need to somehow “mess with it”, and by doing so, you’ll change its properties and you’ll be caught when the bank tests the qubits.

So what is this test?

Basically, the test checks if the properties of the money are still the same as when it was created. These properties are the basis and eigenvalue of each qubit. Here, the bases are the computational basis (or Z-basis) and the X-basis, and the eigenvalues are \(\{-1,1\}\), which result in four possibilities for the qubits, \(\{\left|0\right>\), \(\left|1\right>\), \(\left|+\right>\), \(\left|-\right>\}\). Now, to check if the properties are unaltered, the bank measures each qubit in the basis it was prepared, and compares the eigenvalue with the original one, passing if it matches and aborting if it doesn’t. For this it uses the fact that these two bases are mutually unbiased bases, which implies that:

  • if a qubit is measured in the same basis that it was prepared, then its outcome will be the same eigenvalue as when it was prepared;
  • if a qubit is measured in another basis then all outcomes will have an equal probability of occurring.

Notice that this algorithm is probabilistic, and even if a wrong basis is used, the measured eigenvalue will still be correct half the times, meaning that there is actually a (3/4) probability of yielding the correct eigenvalue if the measurement is preformed in a random basis. Meaning that for \(n\) qubits, the probability to randomly pass the test exponentially drops to \((3/4)^n\).

Coming back to the challenge…

The challenge uses IBM Qiskit framework to simulate the quantum computations. The server, which is playing the bank, uses Python’s random modules to sample twice 30 bits, first 30 bases (bitstring bases, bit 0 for the computational basis and bit 1 for the X-basis) and then 30 eigenvalues (bitstring bits, bit 0 for eigenvalue 1 and bit 1 for eigenvalue -1), and prepares the 30 qubits accordingly. These 30 qubits make a medallion, which is the unit of currency of this challenge, and is associated with an ID, that is the AES encryption of the eigenvalues and bases of all 30 qubits.

In order to sell a medallion with some ID, the test must pass for the bases and eigenvalues the bank recovers by decrypting the ID (only the bank knows the key). For each money-qubit (q_0) we have access to two auxiliary qubits (ancillas) (q_1, q_2) which the server does not touch. The system is initialized in the separable state \(\left|000\right>\), and it is prepared by applying to q_0 the NOT gate (X-gate) if the eigenvalue-bit a was 1, and applying the Hadamard gate if the basis-bit b was 1. Again, the q_0 state will be: \(\left|0\right>\) if a=0, b=0, \(\left|1\right>\) if a=1, b=0, \(\left|+\right>\) if a=0, b=1, \(\left|-\right>\) if a=1, b=1, and it will be separable from the ancilla qubits of which we have total control. We’ll be presenting the circuits (for 1 qubit) one step at a time; this is what the server does before handing the medallion to us:

      ┌──────────────────────────────┐┌───┐┌───┐ »
q_0:  ┤0                             ├┤ Xᵃ├┤ Hᵇ├─»
      │                              │└───┘└───┘ »
q_1:  ┤1 initialize(1,0,0,0,0,0,0,0) ├───────────»
      │                              │           »
q_2:  ┤2                             ├───────────»
      └──────────────────────────────┘           »
c0: 1/═══════════════════════════════════════════»
                                                 »

After, the server allows us to perform any arbitrary unitary operation on the entire system, i.e. q_0 and the two ancillary qubits q_1, q_2, or a measurement. Indeed, we know that we won’t be able to clone q_0 to an ancilla because of the No-cloning theorem. However, this doesn’t mean that we cannot make a good enough copy that allows us to win the challenge with high-enough probability. An interesting page on wikipedia about quantum cloning tells us that an arbitrary qubit can be cloned into two identical copies with a fidelity of \(5/6\) and the circuit (also below) is found in the references (for instance here). So, we get two copies (one in q_0 and another in q_1) which resemble the original state on q_0, and which will pass the test with probability \(5/6\) each.

«                                                                 ┌───┐┌───┐ »
«q_0:  ───────────────────────────────────────────────────■────■──┤ X ├┤ X ├─»
«       ┌──────────┐                  ┌───┐┌───────────┐┌─┴─┐  │  └─┬─┘└─┬─┘ »
«q_1:  ─┤RY(1.1071)├──■───────────────┤ X ├┤RY(0.46365)├┤ X ├──┼────■────┼───»
«       └──────────┘┌─┴─┐┌───────────┐└─┬─┘└───────────┘└───┘┌─┴─┐       │   »
«q_2:  ─────────────┤ X ├┤RY(0.72973)├──■────────────────────┤ X ├───────■───»
«                   └───┘└───────────┘                       └───┘           »
«c0: 1/══════════════════════════════════════════════════════════════════════»
«                                                                            »

When we sell our only medallion, the bank measures the 30 qubits in the basis they were prepared in (according to the decryption of ID), and aborts if any measurement gives the wrong eigenvalue. To test our circuit, we use the Aer.get_backend('qasm_simulator') Qiskit backend and run it 1000 times getting back the measurements {'0': 835, '1': 165} for a \(\left|+\right>\) prepared state which matches the expected \(5/6 = 0.8(3)\) probability (remember 0 means eigenvalue 1), double-checking the other possible states yields identical results. Be warned that we will fail some times, i.e. only with probability \((5/6)^{30} ≈ 0.0042\) we will be able to sell this slightly modified medallion.

«        ┌───┐┌─┐┌─────────────────┐  »
«q_0:  ──┤ Hᵇ├┤M├┤ initialize(1,0) ├──»
«        └───┘└╥┘└─────────────────┘  »
«q_1:  ────────╫──────────────────────»
«              ║                      »
«q_2:  ────────╫──────────────────────»
«              ║                      »
«c0: 1/════════╩══════════════════════»
«              0                      »

Now we have no medallion left… No problem, we ask to sell the same medallion ID (which correspond to a medallion with 30 qubits with the same bases and eigenvalues as before) and we just swap our ancilla q_1, holding the almost clone of the first medallion, to the q_0 register using the SWAP gate, and sell this copy instead!

«             »
«q_0:  ───X───»
«         │   »
«q_1:  ───X───»
«             »
«q_2:  ───────»
«             »
«c0: 1/═══════»
«             »

Once more, we’ll fail a few times. We can simulate the circuit again and check that ({'0': 832, '1': 168}) we are getting away cheating with probability \(5/6\) per qubit again.

«        ┌───┐┌─┐
«q_0:  ──┤ Hᵇ├┤M├
«        └───┘└╥┘
«q_1:  ────────╫─
«              ║
«q_2:  ────────╫─
«              ║
«c0: 1/════════╩═
«              0

Assembling everything (and compiling the circuit into only one unitary to save time communicating with the server using Aer.get_backend('unitary_simulator')), we can now cheat the bank by selling two clones of the same medallion with probability \({(5/6)^{30}}^2 ≈ 1.775\cdot 10^{-5}\). This means that in 1 in around 60k tries we should be able to cheat the bank twice, for q_0 and q_1. This challenge requires solving a proof-of-work before being able to try, but nothing that spawning a few hundred connections simultaneously doesn’t do in a few hours.

reconstructing the state

We sold our cloned medallion twice, and now have $1998 to add to our previous $23, so we have enough money to buy a medallion and exchange it 624 times to have enough consecutive outputs from the Python random generator and recover the Mersenne Twister state. However, we still need $15213 to get the flag. Since we know the internal state of the PRNG, we know exactly what are the bases and eigenvalues of the qubits the upcoming medallion, which we buy. Therefore, we simply sell this same medallion 15 times by constructing its quantum state using the available unitary operations (NOT and Hadamard gates), so all the qubits will be in a correctly verifiable state with probability 1.

def state_reconstruct(c, bases, bits):
    ''' Copied from challenge '''
    for qubit in range(NUM_QUBITS):
        measure(c, 0, qubit=qubit)
        if bases % 2:
            if bits % 2:
                # This gives |->
                xgate(c, 0, qubit=qubit)
                hadamard(c, 0, qubit=qubit)
            else:
                # This gives |+>
                hadamard(c, 0, qubit=qubit)
        else:
            if bits % 2:
                # This gives |1>
                xgate(c, 0, qubit=qubit)
            else:
                # This gives |0>, cuz why not
                xgate(c, 0, qubit=qubit)
                xgate(c, 0, qubit=qubit)

        bases //= 2
        bits //= 2

for _ in range(15):
    assert sell_medallion(p, med_id) #Always selling the same medallion
    state_reconstruct(p, bases, bits) #We can reset the state because we know the bases and bits

conclusion

Finally, and after way more attempts than expected (more than 100k instead of 60k), we receive the flag and become one of the only four teams to solve this very interesting challenge, which combined knowledge on multiple fields of modern cryptography.

{'msg': 'Here you go. ', 'flag': "We shan't begin to fathom how you cheated at our raffle game. To attempt to appease you, here is a flag: PCTF{1_D1d_nO7_L13_7O_YoU_R422l3_R34lLy_15_4_5c4M}", 'curr_money': 16382}

The solution code can be found in sol.py.