B4B8
B4B8
BB84
This challenge is based on the BB84 Quantum Key Distribution Protocol for the secure creation of shared secrets.
The standard protocol is as follows:
- Alice creates a set of entangled qubit pairs (bell pairs)
- Alice sends said qubits to Bob.
- Both Alice and Bob randomly pick whether to apply a Hadamard gate for each of their qubits. They write down which they choose for each.
- Alice and Bob measure all their qubits.
- Alice and Bob publicly publish their choice of gates (but not measurements).
- Bob looks at his remaining qubits and randomly picks half of them and publishes which ones he chose and their values.
- If Alice agrees, they use the remaining half to qubits to deterministically construct a shared secret.
The B4B8 protocol differs in that the shared qubits were agreed upon ahead of time, and are always the first half of the remaining qubits, and only the last 128 shared qubits are used for construction of the shared key. (Well, and it doesn’t use real qubits, but I’ll come to that later).
The modification to the protocol makes this directly susceptible to meddling by Eve.
The Code
The QubitPair Class
class QubitPair:
def __init__(self, density_matrix: np.matrix):
global qubit_id
self.density_matrix = density_matrix
self.id = qubit_id
qubit_id += 1
def measure_first(self, POVM: list[np.matrix]):
post_measure = [np.kron(kraus, np.identity(2)) * self.density_matrix * np.kron(kraus.H, np.identity(2)) for
kraus in POVM]
prob = [np.abs(np.trace(m)) for m in post_measure]
result = random.choices([x for x in range(len(POVM))], weights=prob)
self.density_matrix = post_measure[result[0]] / prob[result[0]]
return result[0]
def measure_second(self, POVM: list[np.matrix]):
post_measure = [np.kron(np.identity(2), kraus) * self.density_matrix * np.kron(np.identity(2), kraus.H) for
kraus in POVM]
prob = [np.abs(np.trace(m)) for m in post_measure]
result = random.choices([x for x in range(len(POVM))], weights=prob)
self.density_matrix = post_measure[result[0]] / prob[result[0]]
return result[0]
The QubitPair class is the simplified implementation of a Quantum System. You can only create two qubits,
and gates get directly tied in with measurement. You cannot add qubits to the system, nor entangle separate
qubit pairs. You can measure either qubit of the pair.
Bit Initialization
def bell_state():
return QubitPair(np.matrix([[1 / 2, 0, 0, 1 / 2], [0] * 4, [0] * 4, [1 / 2, 0, 0, 1 / 2]]))
Alice_bits = [(bell_state(), 1) for s in range(n)]
Your_bits = [(x, 2) for x, _ in Alice_bits]
Bob_bits = []
Alice creates a bunch of QubitPairs. Here we see that the scheme to represent a single Qubit
is as a pair of the QubitPair “system” with the qubit id (either 1 or 2). Here, we always get
the second of Alice’s Qubits. Later we’ll see that when we measure, whether measure_first or measure_second
gets called is determiend by whether the index is 1 or 2.
Main Loop
The beginning of the main loop is what happens once Bob recieves 1024 qubits. We’ll ignore that for now, only noting that once that happens, we can still perform actions.
(1) Measure a Qubit
if option == 1:
count = int(input(
"How many Kraus operators does your POVM have? If you just want the standard basis, put 0. If you just want the hadamard basis, put 1."))
if count < 0:
raise ValueError("I don't think you're gonna measure much with that...")
elif count > 4:
raise ValueError("Unfortunately we don't quite have the hardware for that...")
elif count == 0:
POVM = standard_basis()
elif count == 1:
POVM = hadamard_basis()
We can choose to measure the qubit in either the standard basis or the hadamard basis. You can alternatively think of the hadamard basis as simply first applying a hadamard gate and then measuring “in the standard basis”.
There’s also an option to apply up to four POVM transformations to the state. This may have been added as a red herring or because the author was bored. Either way, I’m ignoring it as it isn’t used in any of the attacks.
After that, the measurement is made
index = int(input("Which state would you like to measure?"))
if index < 0 or index >= len(Your_bits):
raise ValueError("That's not a valid state index!")
state, bit_number = Your_bits[index]
print("Making measurement...")
if bit_number == 1:
print(f"The measurement result is: {state.measure_first(POVM)}")
if bit_number == 2:
print(f"The measurement result is: {state.measure_second(POVM)}")
Note, here we see how the service ensures that we only can measure a Qubit that shows up in our
(2) Create a Qubit
if option == 2:
if len(Your_bits) > 2 * n:
raise ValueError("You don't have enough quantum storage for that!")
print("Input the coefficients for the 4x4 density matrix of 2 qubits: ")
m = input_matrix(4)
if check_valid(m):
state = QubitPair(m)
Your_bits.append((state, 1))
Your_bits.append((state, 2))
print(f"Added 2 parts of qubit with id {state.id} into storage")
else:
raise ValueError(
"That doesn't seem to be a physically possible state... but raise a ticket with your input if you think the check is giving a false negative!"
)
The main thing to note here is that we have to specify the initial state of the qubits as a density Matrix. I used Quirk to get the density matrix of a Bell State.
(3) Send Qubit to Bob
if option == 3:
if key_exchanged:
raise ValueError("Bob: Oh look, Eve's trying to send me qubits. That can't be good...")
index = int(input("Which bits would you like to send to Bob?"))
if index < 0 or index >= len(Your_bits):
raise ValueError("That's not a valid state index!")
Bob_bits.append(Your_bits.pop(index))
We can send either (or both!) of the qubits to bob. Once removed from our list of qubits, we won’t be able to measure it later.
(4) Show Qubits
if option == 4:
for i, t in enumerate(Your_bits):
print(f"#{i} | id: #{t[0].id}, part of qubit: {t[1]}")
Nice for debugging and making you feel like you’re interacting with an actual Qubit Service. 10/10
Note that we also get to see the QubitPair system id.
Bob Gets His Qubits
Once bob gets 1024 qubits, alice and bob perform their measurements.
if not key_exchanged and len(Bob_bits) == n:
print("Bob: I've received enough states!")
print("Alice: ok let's start then.")
key_exchanged = True
Alice_basis = int.from_bytes(os.urandom(n // 8), byteorder='big')
Alice_results = measures(Alice_bits, Alice_basis)
print("Alice: i've made my measurements.")
Bob_basis = int.from_bytes(os.urandom(n // 8), byteorder='big')
Bob_results = measures(Bob_bits, Bob_basis)
print("Bob: Same here!")
The challenge author makes our life slightly harder by having Bob check if his qubits look random.
Bob_standard = ""
Bob_hadamard = ""
for i in range(n):
if ((Bob_basis >> i) & 1) == 0:
Bob_standard = Bob_standard + str((Bob_results >> i) & 1)
else:
Bob_hadamard = Bob_hadamard + str((Bob_results >> i) & 1)
if randomness_test(int(Bob_hadamard, 2)) and randomness_test(int(Bob_standard, 2)):
print("Bob: Mine passed the randomness test, looks like everything is good!")
else:
raise ValueError("Bob: Mine doesn't seem that random, maybe Eve's here again...")
Alice and bob exchange basis choices
print(f"Bob: My bases were {('0' * n + bin(Bob_basis)[2:])[-n:]}")
print(f"Alice: cool, my bases were {('0' * n + bin(Alice_basis)[2:])[-n:]}")
(note: the basis choices are presented in the reverse order of the qubits. The measurement basis for the qubit index 0 is in fact the last digit of this string. This was super annoying)
Now they figure out where they match. The associated measurements should match if the qubits were untampered with.
Alice_key = ""
Bob_key = ""
count = 0
chosen = []
for i in range(n):
if ((Alice_basis >> i) & 1) == ((Bob_basis >> i) & 1):
chosen.append(i)
Alice_key = Alice_key + str((Alice_results >> i) & 1)
Bob_key = Bob_key + str((Bob_results >> i) & 1)
count += 1
Then they ensure that about the first half of remaining qubits weren’t tampered with.
print(
f"Bob: Great! Now let's just make sure that our measurements actually match. My first {count // 4} bits are: {Bob_key[:count // 4]}")
if sum([1 if a != b else 0 for a, b in zip(Alice_key[:count // 4], Bob_key[:count // 4])]) > count // 100:
raise ValueError("Alice: that doesn't seem to match mine, eve's dropped by again it seems.")
else:
print("Alice: yeah that looks good.")
Then Alice and Bob construct (what should be) a shared key for AES
Alice_key = int(Alice_key[-128:], 2)
Alice_AES = AES.new(Alice_key.to_bytes(length=16, byteorder='big'), mode=AES.MODE_CBC)
Bob_key = int(Bob_key[-128:], 2)
Bob_AES = AES.new(Bob_key.to_bytes(length=16, byteorder='big'), mode=AES.MODE_CBC)
Alice Encrypts the FLAG
encrypted_once = Alice_AES.encrypt(FLAG)
And then magically sends this encrypted message to Bob (just roll with it) who then encrypts it with his key.
encrypted_twice = Bob_AES.encrypt(encrypted_once)
(Again, please ignore the the logical implications of their setup from this step.)
And we get the resulting magically doubly encrypted message ciphertext and IVs.
print(Alice_AES.iv.hex())
print(Bob_AES.iv.hex())
print(encrypted_twice.hex())
The Attack
It should be noted that we don’t have to measure our Qubits upon recieving them. We can delay that until after Bob has published his measurement basis.
So if we send the first 512 of Alice’s qubits, which won’t be used in the key, Bob and Alice will agree that everything looks good when they measure. So we Send 512 of Alice’s qubits to Bob, and then we create 512 pairs (also in a Bell State) and send those to Bob.
We can measure the remaining Alice qubits ourselves to find out Alice’s Key (we’re basically “Bob” at that point and we now know what basis she measured them in) and then we can measure the remaining Qubits as if we were Alice (again we know the basis that Bob measured in at this point). This get’s us Bob’s key.
And that’s it really.
Attack Code
Full Exploit:
import pwn
import re
from Crypto.Cipher import AES
### Interaction With Service
def send_bell_state(r : pwn.remote):
mat = [[1 / 2, 0, 0, 1 / 2], [0] * 4, [0] * 4, [1 / 2, 0, 0, 1 / 2]]
for row in mat:
for entry in row:
r.sendline(str(entry).encode())
def create_bell_state(r : pwn.remote):
r.sendline(b"2")
send_bell_state(r)
return read_prompt(r)
def read_prompt(r : pwn.remote):
res= r.recvuntil(b"See qubits in storage")
return res
def send_bob_bits(r : pwn.remote, i : int):
r.sendline(b"3")
r.sendline(str(i).encode())
return read_prompt(r)
def measure_qubit(r : pwn.remote, qubit_id : int, basis : int):
r.sendline(b"1")
r.sendline(str(basis).encode())
r.sendline(str(qubit_id).encode())
r.recvuntil(b"The measurement result is: ")
res = r.recvline()[:-1]
return int(res)
# This is just for debugging
def show_qubits(r):
r.sendline(b"4")
print("\n".join(read_prompt(r).decode().split("\n")[:-5]))
def extract_basis(btext):
text = btext.decode()
bob = re.findall("Bob: My bases were ([01]*)", text)[0]
alice = re.findall("Alice: cool, my bases were ([01]*)", text)[0]
return alice, bob
def extract_cipher_data(btext):
text = btext.decode()
text += "\n" # just in case I didn't grab it
res = re.findall("\n([^\n]*)\n([^\n]*)\n([^\n]*)\n\nYou can:\n", text)[0]
return res
# Final Decryption once ciphertext is obtained and keys derived
def decrypt(ciphertext : str, iv1 : str, iv2 : str, key1 : int, key2 : int):
ciphertext = bytes.fromhex(ciphertext)
iv1 = bytes.fromhex(iv1)
iv2 = bytes.fromhex(iv2)
Alice_AES = AES.new(key1.to_bytes(length=16, byteorder='big'), mode=AES.MODE_CBC, iv=iv1)
Bob_AES = AES.new(key2.to_bytes(length=16, byteorder='big'), mode=AES.MODE_CBC,iv=iv2)
return Alice_AES.decrypt(Bob_AES.decrypt(ciphertext))
def compute_shared_basis(alice_basis, bob_basis):
basis = []
assert len(alice_basis) == len(bob_basis)
for i, (a,b) in enumerate(zip(alice_basis[::-1], bob_basis[::-1])):
if a==b:
basis.append((i,a))
return basis
def main():
r = pwn.process(["python3", "b4b8.py"]) # run locally
#r = pwn.remote("b4-the-b8.ctf.umasscybersec.org",1337) # run against server
read_prompt(r)
# send the first 512 qubits from alice to bob
for i in range(512):
send_bob_bits(r, 0)
# Create 512 more pairs, send one from each to bob
# annoying index logic.
for i in range(512):
create_bell_state(r)
chatter = send_bob_bits(r, 512+i)
# print out the alice bob chatter if you want to do the final decryption manually
print(chatter.decode())
# Get the ivs and ciphertext
iv1,iv2, ct = extract_cipher_data(chatter)
# parse alice's and bob's basis from the chatter
alice_basis, bob_basis = extract_basis(chatter)
# Compute the shared basis and then whittle it down to the part that is
# used in key construction
shared_basis = compute_shared_basis(alice_basis, bob_basis)
used_basis = shared_basis[-128:]
# determine alice's bits
alice_key = ""
bob_key = ""
for i,b in used_basis:
alice_qubit = i - 512
bob_qubit = i
alice_measure = measure_qubit(r, alice_qubit, b)
bob_measure = measure_qubit(r, bob_qubit, b)
alice_key += str(alice_measure)
bob_key += str(bob_measure)
# Display our hard earned keys
print("Alice_key", int(alice_key,2))
print("Bob_key", int(bob_key,2))
# decrypt!
print(decrypt(ct, iv1, iv2, int(alice_key,2), int(bob_key,2)))
# have fun with the glorious simulator / debug what went wrong
r.interactive()
Wait not real qubits? What was that?
Oh yeah. There’s another way to deal with this. After the competition @lrnzsir asked
Sure enough our “quantum” bits are using the pseudo random Mersenne Twister
result = random.choices([x for x in range(len(POVM))], weights=prob)
Quick Review of Choices
choices generates a single random floating point number in [0,1). It then
maps each entry, based on the weights, into that interval and uses the random number to select
the correct one. Random floats in python are generated with:
static PyObject *
_random_Random_random_impl(RandomObject *self)
/*[clinic end generated code: output=117ff99ee53d755c input=afb2a59cbbb00349]*/
{
uint32_t a=genrand_uint32(self)>>5, b=genrand_uint32(self)>>6;
return PyFloat_FromDouble((a*67108864.0+b)*(1.0/9007199254740992.0));
}
Which looks intimidating, but is really just constructing 54 non overlapping bits
from two 32 random bit numbers and then mapping dividing by 2**54.
In our specific situation, we want to know when this is greater than or equal to
0.5. If it is, then we get 1. This happens when the high bit of a is 1.
Back to the problem at hand
But hey, we’d need to get 19968 bits of information to reconstruct stuff right? And we can’t have more than 2048 qubits total, right?
Well, we can just alternate the basis and measure the same qubit.
So our alternative gameplan is simply to send all the qubits to Bob, create a new qubit, and just keep measuring it to leak enough bits from the twister. Then we just shove that output into something that can reconstruct the state.
solver = MT19937Solver()
basis = 0
create_bell_state(r)
results = []
for i in range(624*33):
result = measure_qubit(r, 1024, basis)
basis = (basis+1) % 2
solver.submit(32, [result]+[None]*31) # High bit is known and is the result
solver.submit(32, None) # don't know anything about it
initial_state = solver.solve()
rand = random.Random()
rand.setstate(initial_state)
# resync solver
for i in range(624*33):
_ = rand.getrandbits(32)
_ = rand.getrandbits(32)
# send all of alice's bits to bob
for i in range(1024):
chatter = send_bob_bits(r, 0)
iv1,iv2, ct = extract_cipher_data(chatter)
# generated basis is still_random, so we need to get it
alice_basis, bob_basis = extract_basis(chatter)
shared_basis = compute_shared_basis(alice_basis, bob_basis)
used_basis = shared_basis[-128:]
alices_measurements = []
for i in range(len(alice_basis)):
alices_measurements.append(str(rand.choices([0,1], [1,1])))
alice_key = ""
# Here we can throw away the basis info, since we don't
# care anymore. The calls to rand.choices will be the same
for i, _ in used_basis:
alice_key += alice_measurements[i]
bob_key = alice_key
print(decrypt(ct, iv1, iv2, int(alice_key,2), int(bob_key,2)))