Challenge 3 : Algorithme de Grover cassé (2/2)

from machinerie import Circuit, draw404

draw404()

Notre ingénieur s’est trompé lorsqu’il a programmé l’algorithme, il a oublié des \(H\)… Comment faire pour récupérer le drapeau ?

Soit un drapeau “0011011”, le circuit complet s’écrit :

from machinerie import create_grover

flag = [0, 0, 1, 1, 0, 1, 1]
n = len(flag)

grover = create_grover(flag, range(n), range(n))
grover.draw_circuit()

full_circuit = Circuit(n)
full_circuit.h(range(n))
full_circuit.compose(grover, inplace=True)
full_circuit.compose(grover, inplace=True)
full_circuit.compose(grover, inplace=True)
full_circuit.compose(grover, inplace=True)
results = full_circuit.get_measure()
drapeau = sorted(results, key=lambda x: x[1], reverse=True)[0]
print(f"""
Drapeau : {drapeau}
Probabilité : {results[drapeau]}
""")

À une inversion près, on retrouve notre drapeau en 4 coups, … quand le circuit est bien implémenté. Ce n’est malheureusement pas le cas pour le circuit sur nos serveurs, il manque au moins 2 \(H\) par colonne…

Par exemple :

grover = create_grover(flag, range(n - 2), range(n - 2))
grover.draw_circuit()

Pour couronner le tout, il n’y a qu’une passe qui a été implémentée.

Votre mission : récupérer le drapeau.

Vous avez accès à 3 paramètres : - l’entrée - les positions des \(H\) entre \(Z_f\) et \(Z_\text{OR}\) - vous avez le droit d’en poser \(\leq n-2\) - les positions des \(H\) après \(Z_\text{OR}\) - vous avez le droit d’en poser \(\leq n-2\)

à travers la fonction test_flag_grover (j’utilise exactement la même fonction côté API).

Pour éviter le brute force sur le CTFd directement, vous devrez reproduire la procédure deux fois, pour récupérer deux drapeaux de 12 bits chacuns, le drapeau final sera 404CTF{premier_flag+deuxième_flag}, par exemple : 404CTF{0101010101010101010101010}

Pour éviter l’explosion de votre ordinateur lors de l’appel à get_flat_unitary, vous utiliserez des angles pour m’envoyer votre entrée. À partir d’une liste de \(n*3\) flottants, je construis n’importe quel état d’entré avec des portes \(U\). Les angles sont ceux de la sphère de Bloch. Vous avez l’implémentation dans Circuit : Circuit.from_angles().

Par exemple deux Hadamards :

from math import pi

# theta_0, phi_0, lambda_0, theta_1, ...
angles = [pi / 2, 0, pi, pi / 2, 0, pi]
qc = Circuit.from_angles(angles)
qc.draw_qubits()

En appelant l’API, vous obtiendrez une mesure. Pour éviter la surcharge, je mesure à chaque fois sur 1000 essais. Le brute force de l’API est évidemment toujours interdit, vous êtes sensé pouvoir trouver le drapeau avec moins de \(30\) essais (\(5\) si vous n’êtes pas trop malchanceux).

import requests
import json

data = {
    "input_qubits": angles,
    "hadamard_middle": list(range(10)),
    "hadamard_end": list(range(10)),
}

# Première partie du drapeau :
url = "https://causapscal-des-profondeurs.404ctf.fr/grover/1"

# Seconde partie du drapeau :
# url = "https://causapscal-des-profondeurs.404ctf.fr/grover/2"
f
headers = {"Content-Type": "application/json", "Accept": "application/json"}
response = requests.post(url, json=data, headers=headers)

print(json.loads(response.content)["message"])